Gotweb

Blame

Date:: Sat Mar 2 00:19:56 2024 UTC
Message:: attempt to speed up the deltification for big files The current hash table perform poorly on big files due to a small resize step that pushes the table to its limits continuously. Instead, to have both a better performing hash table and keep the memory consumption low, save the blocks in an array and use the hash table as index. Then, use a more generous resizing scheme that guarantees the good properties of the hash table. To avoid having to rebuild the table when the array is resized, save the indexes in the table, and to further reduce the memory consumption use 32 bit indices. On amd64 this means that each slot is 4 bytes instead of 8 for a pointer or 24 for a struct got_deltify_block. ok stsp@
Actions:: History | Blob | Raw File

 1 69aa0e90 2021-03-10 stsp /*
 2 69aa0e90 2021-03-10 stsp  * Copyright (c) 2020 Ori Bernstein
 3 69aa0e90 2021-03-10 stsp  * Copyright (c) 2021 Stefan Sperling <stsp@openbsd.org>
 4 69aa0e90 2021-03-10 stsp  *
 5 69aa0e90 2021-03-10 stsp  * Permission to use, copy, modify, and distribute this software for any
 6 69aa0e90 2021-03-10 stsp  * purpose with or without fee is hereby granted, provided that the above
 7 69aa0e90 2021-03-10 stsp  * copyright notice and this permission notice appear in all copies.
 8 69aa0e90 2021-03-10 stsp  *
 9 69aa0e90 2021-03-10 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 69aa0e90 2021-03-10 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 69aa0e90 2021-03-10 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 69aa0e90 2021-03-10 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 69aa0e90 2021-03-10 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 69aa0e90 2021-03-10 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 69aa0e90 2021-03-10 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 69aa0e90 2021-03-10 stsp  */
17 69aa0e90 2021-03-10 stsp 
18 69aa0e90 2021-03-10 stsp struct got_delta_block {
19 69aa0e90 2021-03-10 stsp 	off_t		len;
20 69aa0e90 2021-03-10 stsp 	off_t		offset;
21 90dfa2bf 2022-02-13 thomas 	uint32_t	hash;
22 69aa0e90 2021-03-10 stsp };
23 69aa0e90 2021-03-10 stsp 
24 69aa0e90 2021-03-10 stsp struct got_delta_table {
25 69aa0e90 2021-03-10 stsp 	struct got_delta_block	*blocks;
26 69aa0e90 2021-03-10 stsp 	int			nblocks;
27 69aa0e90 2021-03-10 stsp 	int			nalloc;
28 2633cf30 2024-03-02 thomas 
29 2633cf30 2024-03-02 thomas 	/*
30 2633cf30 2024-03-02 thomas 	 * Index for blocks.  offs[n] is zero when the slot is free,
31 2633cf30 2024-03-02 thomas 	 * otherwise it points to blocks[offs[n] - 1].
32 2633cf30 2024-03-02 thomas 	 */
33 2633cf30 2024-03-02 thomas 	uint32_t		*offs;
34 2633cf30 2024-03-02 thomas 	int			 len;
35 2633cf30 2024-03-02 thomas 	int			 size;
36 69aa0e90 2021-03-10 stsp };
37 69aa0e90 2021-03-10 stsp 
38 69aa0e90 2021-03-10 stsp struct got_delta_instruction {
39 69aa0e90 2021-03-10 stsp 	int	copy;
40 69aa0e90 2021-03-10 stsp 	off_t	offset;
41 69aa0e90 2021-03-10 stsp 	off_t	len;
42 69aa0e90 2021-03-10 stsp };
43 69aa0e90 2021-03-10 stsp 
44 69aa0e90 2021-03-10 stsp enum {
45 9f656b20 2022-02-12 thomas 	GOT_DELTIFY_MINCHUNK	= 32,
46 69aa0e90 2021-03-10 stsp 	GOT_DELTIFY_MAXCHUNK	= 8192,
47 69aa0e90 2021-03-10 stsp 	GOT_DELTIFY_SPLITMASK	= (1 << 8) - 1,
48 69aa0e90 2021-03-10 stsp };
49 69aa0e90 2021-03-10 stsp 
50 69aa0e90 2021-03-10 stsp const struct got_error *got_deltify_init(struct got_delta_table **dt, FILE *f,
51 cc524d36 2022-05-31 thomas     off_t fileoffset, off_t filesize, uint32_t seed);
52 2b0ae357 2022-01-10 thomas const struct got_error *got_deltify_init_mem(struct got_delta_table **dt,
53 cc524d36 2022-05-31 thomas     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed);
54 69aa0e90 2021-03-10 stsp const struct got_error *got_deltify(struct got_delta_instruction **deltas,
55 cc524d36 2022-05-31 thomas     int *ndeltas, FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
56 f34b169e 2021-06-18 stsp     struct got_delta_table *dt, FILE *basefile, off_t basefile_offset0,
57 f34b169e 2021-06-18 stsp     off_t basefile_size);
58 2b0ae357 2022-01-10 thomas const struct got_error *got_deltify_file_mem(
59 2b0ae357 2022-01-10 thomas     struct got_delta_instruction **deltas, int *ndeltas,
60 cc524d36 2022-05-31 thomas     FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
61 cc524d36 2022-05-31 thomas     struct got_delta_table *dt, uint8_t *basedata, off_t basefile_offset0,
62 cc524d36 2022-05-31 thomas     off_t basefile_size);
63 2b0ae357 2022-01-10 thomas const struct got_error *got_deltify_mem_file(
64 2b0ae357 2022-01-10 thomas     struct got_delta_instruction **deltas, int *ndeltas,
65 cc524d36 2022-05-31 thomas     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
66 cc524d36 2022-05-31 thomas     struct got_delta_table *dt, FILE *basefile, off_t basefile_offset0,
67 cc524d36 2022-05-31 thomas     off_t basefile_size);
68 2b0ae357 2022-01-10 thomas const struct got_error *got_deltify_mem_mem(
69 2b0ae357 2022-01-10 thomas     struct got_delta_instruction **deltas, int *ndeltas,
70 cc524d36 2022-05-31 thomas     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
71 cc524d36 2022-05-31 thomas     struct got_delta_table *dt, uint8_t *basedata, off_t basefile_offset0,
72 cc524d36 2022-05-31 thomas     off_t basefile_size);
73 69aa0e90 2021-03-10 stsp void got_deltify_free(struct got_delta_table *dt);