Got Mirror

Blame

Date:: Mon Feb 26 16:25:15 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 f6027426 2022-02-12 naddy 	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 fcece718 2024-02-26 op 
29 fcece718 2024-02-26 op 	/*
30 fcece718 2024-02-26 op 	 * Index for blocks.  offs[n] is zero when the slot is free,
31 fcece718 2024-02-26 op 	 * otherwise it points to blocks[offs[n] - 1].
32 fcece718 2024-02-26 op 	 */
33 fcece718 2024-02-26 op 	uint32_t		*offs;
34 fcece718 2024-02-26 op 	int			 len;
35 fcece718 2024-02-26 op 	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 1ac8bad9 2022-02-11 stsp 	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 d6a28ffe 2022-05-20 op     off_t fileoffset, off_t filesize, uint32_t seed);
52 64a8571e 2022-01-07 stsp const struct got_error *got_deltify_init_mem(struct got_delta_table **dt,
53 d6a28ffe 2022-05-20 op     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 d6a28ffe 2022-05-20 op     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 64a8571e 2022-01-07 stsp const struct got_error *got_deltify_file_mem(
59 64a8571e 2022-01-07 stsp     struct got_delta_instruction **deltas, int *ndeltas,
60 d6a28ffe 2022-05-20 op     FILE *f, off_t fileoffset, off_t filesize, uint32_t seed,
61 d6a28ffe 2022-05-20 op     struct got_delta_table *dt, uint8_t *basedata, off_t basefile_offset0,
62 d6a28ffe 2022-05-20 op     off_t basefile_size);
63 64a8571e 2022-01-07 stsp const struct got_error *got_deltify_mem_file(
64 64a8571e 2022-01-07 stsp     struct got_delta_instruction **deltas, int *ndeltas,
65 d6a28ffe 2022-05-20 op     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
66 d6a28ffe 2022-05-20 op     struct got_delta_table *dt, FILE *basefile, off_t basefile_offset0,
67 d6a28ffe 2022-05-20 op     off_t basefile_size);
68 64a8571e 2022-01-07 stsp const struct got_error *got_deltify_mem_mem(
69 64a8571e 2022-01-07 stsp     struct got_delta_instruction **deltas, int *ndeltas,
70 d6a28ffe 2022-05-20 op     uint8_t *data, off_t fileoffset, off_t filesize, uint32_t seed,
71 d6a28ffe 2022-05-20 op     struct got_delta_table *dt, uint8_t *basedata, off_t basefile_offset0,
72 d6a28ffe 2022-05-20 op     off_t basefile_size);
73 69aa0e90 2021-03-10 stsp void got_deltify_free(struct got_delta_table *dt);