From 5da12fc106daf5d858b503a77f47a9fc22170cfa Mon Sep 17 00:00:00 2001 From: dotdotisdead Date: Sun, 14 Jan 2007 21:35:47 +0000 Subject: Cleanup the calculation of -B and -W, get the minimum source buffer size (-B) to work, enforce a maximum input window size (-W). Add some debugging output. Correct a bug in setting the large hashtable size. I've noticed some odd behavior with the -W setting, more tests to do. --- xdelta3/xdelta3-main.h | 69 +++++++++++++++++++++++++++++----------- xdelta3/xdelta3-regtest.py | 65 +++++++++++++++++--------------------- xdelta3/xdelta3-test.h | 2 +- xdelta3/xdelta3.c | 79 ++++++++-------------------------------------- xdelta3/xdelta3.h | 28 +++++++--------- 5 files changed, 105 insertions(+), 138 deletions(-) diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h index d33ccd3..0a2592e 100755 --- a/xdelta3/xdelta3-main.h +++ b/xdelta3/xdelta3-main.h @@ -234,6 +234,9 @@ struct _main_blklru main_blklru_list link; }; +#define LRU_SIZE 32U +#define XD3_MINSRCWINSZ XD3_ALLOCSIZE + /* ... represented as a list (no cache index). */ XD3_MAKELIST(main_blklru_list,main_blklru,link); @@ -402,7 +405,7 @@ main_malloc1 (usize_t size) { void* r = malloc (size); if (r == NULL) { XPR(NT "malloc: %s\n", xd3_mainerror (ENOMEM)); } - else if (option_verbose > 2) { XPR(NT "malloc: %u: %p\n", size, r); } + else if (option_verbose > 3) { XPR(NT "malloc: %u: %p\n", size, r); } return r; } @@ -425,7 +428,7 @@ main_alloc (void *opaque, static void main_free1 (void *opaque, void *ptr) { - if (option_verbose > 2) { XPR(NT "free: %p\n", ptr); } + if (option_verbose > 3) { XPR(NT "free: %p\n", ptr); } free (ptr); } @@ -589,16 +592,25 @@ main_strtoxoff (const char* s, xoff_t *xo, char which) } static int -main_atou (const char* arg, usize_t *xo, usize_t low, char which) +main_atou (const char* arg, usize_t *xo, usize_t low, usize_t high, char which) { xoff_t x; int ret; if ((ret = main_strtoxoff (arg, & x, which))) { return ret; } - if (x > USIZE_T_MAX || x < low) + if (x < low) + { + XPR(NT "-%c: minimum value: %u\n", which, low); + return EXIT_FAILURE; + } + if (high == 0) + { + high = USIZE_T_MAX; + } + if (x > high) { - XPR(NT "-%c: minimum value: %u", which, low); + XPR(NT "-%c: maximum value: %u\n", which, high); return EXIT_FAILURE; } (*xo) = (usize_t)x; @@ -863,7 +875,7 @@ main_file_read (main_file *ifile, } else { - if (option_verbose > 2) { XPR(NT "main read: %s: %u\n", ifile->filename, (*nread)); } + if (option_verbose > 3) { XPR(NT "main read: %s: %u\n", ifile->filename, (*nread)); } ifile->nread += (*nread); } @@ -903,7 +915,7 @@ main_file_write (main_file *ofile, uint8_t *buf, usize_t size, const char *msg) } else { - if (option_verbose > 2) { XPR(NT "main write: %s: %u\n", ofile->filename, size); } + if (option_verbose > 3) { XPR(NT "main write: %s: %u\n", ofile->filename, size); } ofile->nwrite += size; } @@ -2035,16 +2047,16 @@ main_set_source (xd3_stream *stream, int cmd, main_file *sfile, xd3_source *sour else { /* Minimum size check */ - option_srcwinsz = max(option_srcwinsz, XD3_ALLOCSIZE); + option_srcwinsz = max(option_srcwinsz, XD3_MINSRCWINSZ); if (!option_srcwinsz_set) { /* If the flag was not set, scale srcwinsz up to 64MB. */ - option_srcwinsz = min(1ULL<<26, source->size); + option_srcwinsz = min((xoff_t) XD3_DEFAULT_SRCWINSZ, source->size); } - source->blksize = (option_srcwinsz / 32) & ~(XD3_ALLOCSIZE - 1);; - lru_size = 32; + source->blksize = (option_srcwinsz / LRU_SIZE); + lru_size = LRU_SIZE; } main_blklru_list_init (& lru_list); @@ -2398,11 +2410,6 @@ main_input (xd3_cmd cmd, return EXIT_FAILURE; } - if (option_verbose > 1) - { - XPR(NT "scanner configuration: %s\n", stream.smatcher.name); - } - /* This times each window. */ get_millisecs_since (); @@ -2637,6 +2644,24 @@ done: return EXIT_FAILURE; } + if (option_verbose > 1) + { + XPR(NT "scanner configuration: %s\n", stream.smatcher.name); + XPR(NT "target hash table size: %u\n", stream.small_hash.size); + if (sfile->filename != NULL) + { + XPR(NT "source hash table size: %u\n", stream.large_hash.size); + } + } + + if (option_verbose > 2) + { + XPR(NT "source copies: %"Q"u (%"Q"u bytes)\n", stream.n_scpy, stream.l_scpy); + XPR(NT "target copies: %"Q"u (%"Q"u bytes)\n", stream.n_tcpy, stream.l_tcpy); + XPR(NT "adds: %"Q"u (%"Q"u bytes)\n", stream.n_add, stream.l_add); + XPR(NT "runs: %"Q"u (%"Q"u bytes)\n", stream.n_run, stream.l_run); + } + xd3_free_stream (& stream); if (option_verbose) @@ -2870,7 +2895,10 @@ main (int argc, char **argv) /* only set profile count once, since... */ if (option_profile_cnt == 0) { - if ((ret = main_atou(my_optarg, (usize_t*) & option_profile_cnt, 0, 'P'))) { goto exit; } + if ((ret = main_atou(my_optarg, (usize_t*) & option_profile_cnt, 0, 0, 'P'))) + { + goto exit; + } if (option_profile_cnt <= 0) { @@ -2891,12 +2919,15 @@ main (int argc, char **argv) else { option_appheader = (uint8_t*) my_optarg; } break; case 'B': option_srcwinsz_set = 1; - if ((ret = main_atou (my_optarg, & option_srcwinsz, XD3_ALLOCSIZE, 'B'))) + if ((ret = main_atou (my_optarg, & option_srcwinsz, XD3_MINSRCWINSZ, + 0, 'B'))) { goto exit; } break; - case 'W': if ((ret = main_atou (my_optarg, & option_winsize, XD3_ALLOCSIZE, 'W'))) + case 'W': + if ((ret = main_atou (my_optarg, & option_winsize, XD3_ALLOCSIZE, + XD3_HARDMAXWINSIZE, 'W'))) { goto exit; } diff --git a/xdelta3/xdelta3-regtest.py b/xdelta3/xdelta3-regtest.py index fdebffe..520ec81 100755 --- a/xdelta3/xdelta3-regtest.py +++ b/xdelta3/xdelta3-regtest.py @@ -559,34 +559,27 @@ def ReportSpeed(L,tr,desc): print '%s 0-run length %u: dsize %u: time %.3f ms: encode %.0f B/sec: in %ux%u trials' % \ (desc, L, tr.r1.dsize, tr.time.mean * 1000.0, ((L+tr.r1.dsize) / tr.time.mean), tr.trials, tr.reps) -def BigFileRuns(rcsf): - while 1: - - rand = random.Random() - f1 = open(TMPDIR + "/big.1", "w") - f2 = open(TMPDIR + "/big.2", "w") - f1sz = 0 - f2sz = 0 - for file in rcsf.rcsfiles: - if file.versions < 2: - continue - r1 = 0 - r2 = 0 - while r1 == r2: - r1 = rand.randint(0, len(file.versions) - 1) - r2 = rand.randint(0, len(file.versions) - 1) - f1sz += file.AppendVersion(f1, r1) - f2sz += file.AppendVersion(f2, r2) - - f1.close() - f2.close() - - print "Test input sizes: %d %d" % (f1sz, f2sz) - - BigFileRun(TMPDIR + "/big.1", - TMPDIR + "/big.2") - #continue - #end +def MakeBigFiles(rcsf): + rand = random.Random() + f1 = open(TMPDIR + "/big.1", "w") + f2 = open(TMPDIR + "/big.2", "w") + f1sz = 0 + f2sz = 0 + for file in rcsf.rcsfiles: + if file.versions < 2: + continue + r1 = 0 + r2 = 0 + while r1 == r2: + r1 = rand.randint(0, len(file.versions) - 1) + r2 = rand.randint(0, len(file.versions) - 1) + f1sz += file.AppendVersion(f1, r1) + f2sz += file.AppendVersion(f2, r2) + + f1.close() + f2.close() + return (TMPDIR + "/big.1", + TMPDIR + "/big.2") def BigFileRun(f1, f2): @@ -616,12 +609,12 @@ def BigFileRun(f1, f2): def RandomBigRun(f1, f2): input_ranges = [ - (7, 13, 'large_look'), - (1, 50, 'large_step'), - (4, 6, 'small_look'), - (1, 10, 'small_chain'), - (1, 5, 'small_lchain'), - (0, 0, 'ssmatch'), + (7, 9, 'large_look'), + (1, 10, 'large_step'), + (4, 5, 'small_look'), + (1, 20, 'small_chain'), + (1, 10, 'small_lchain'), + (0, 1, 'ssmatch'), (0, 1, 'trylazy'), (1, 32, 'max_lazy'), (1, 64, 'long_enough'), @@ -656,6 +649,8 @@ def RandomBigRun(f1, f2): result.time.mean, result.trials) + return (config, result.r1.dsize, result.time.mean) + def RunSpeed(): for L in Decimals(MAX_RUN): SetFileSize(RUNFILE, L) @@ -670,8 +665,6 @@ if __name__ == "__main__": #rcsf = Test() #rcsf.PairsByDate(Xdelta3Pair()) #RunSpeed() - #BigFileRuns(rcsf) - #BigFileRun("/tmp/big.1", "/tmp/big.2") while 1: try: RandomBigRun("/tmp/big.1", "/tmp/big.2") diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h index 1694a6d..dc67848 100755 --- a/xdelta3/xdelta3-test.h +++ b/xdelta3/xdelta3-test.h @@ -1908,7 +1908,7 @@ test_identical_behavior (xd3_stream *stream, int ignore) if (memcmp (rec, buf, IDB_TGTSZ) != 0) { stream->msg = "wrong data reconstruction"; goto fail; } /* Check that there was one copy per window. */ - IF_DEBUG (if (stream->n_cpy != IDB_WINCNT || + IF_DEBUG (if (stream->n_scpy != IDB_WINCNT || stream->n_add != 0 || stream->n_run != 0) { stream->msg = "wrong copy count"; goto fail; }); diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index 9d6c3b6..14a3c08 100755 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c @@ -1969,46 +1969,6 @@ xd3_sizeof_uint64_t (uint64_t num) #endif -/****************************************************************************************** - Debug instruction statistics - ******************************************************************************************/ - -#if XD3_DEBUG -static void -xd3_count_inst (xd3_stream *stream, uint code) -{ - IF_DEBUG1 ({ - if (stream->i_freqs == NULL && - (stream->i_freqs = xd3_alloc0 (stream, sizeof (stream->i_freqs[0]), 256)) == NULL) { abort (); } - - stream->i_freqs[code] += 1; - }); - stream->n_ibytes += 1; -} - -static void -xd3_count_mode (xd3_stream *stream, uint mode) -{ - IF_DEBUG1 ({ - if (stream->i_modes == NULL && - (stream->i_modes = xd3_alloc0 (stream, sizeof (stream->i_modes[0]), TOTAL_MODES (stream))) == NULL) { abort (); } - stream->i_modes[mode] += 1; - }); -} - -static void -xd3_count_size (xd3_stream *stream, usize_t size) -{ - IF_DEBUG1({ - if (stream->i_sizes == NULL && - (stream->i_sizes = xd3_alloc0 (stream, sizeof (stream->i_sizes[0]), 64)) == NULL) { abort (); } - - if (size < 64) { stream->i_sizes[size] += 1; } - }); - stream->n_sbytes += xd3_sizeof_size (size); -} -#endif - /****************************************************************************************** Address cache stuff ******************************************************************************************/ @@ -2114,8 +2074,6 @@ xd3_encode_address (xd3_stream *stream, usize_t addr, usize_t here, uint8_t* mod xd3_update_cache (acache, addr); - IF_DEBUG (xd3_count_mode (stream, bestm)); - (*mode) += bestm; return 0; @@ -2368,10 +2326,6 @@ xd3_free_stream (xd3_stream *stream) } #endif - IF_DEBUG (xd3_free (stream, stream->i_freqs)); - IF_DEBUG (xd3_free (stream, stream->i_modes)); - IF_DEBUG (xd3_free (stream, stream->i_sizes)); - XD3_ASSERT (stream->alloc_cnt == stream->free_cnt); memset (stream, 0, sizeof (xd3_stream)); @@ -2768,16 +2722,22 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) XD3_ASSERT (inst->addr >= src->srcbase); XD3_ASSERT (inst->addr + inst->size <= src->srcbase + src->srclen); addr = (inst->addr - src->srcbase); + stream->n_scpy += 1; + stream->l_scpy += inst->size; } else { /* with source window: target copy address is offset by taroff. */ addr = stream->taroff + (usize_t) inst->addr; + stream->n_tcpy += 1; + stream->l_tcpy += inst->size; } } else { addr = (usize_t) inst->addr; + stream->n_tcpy += 1; + stream->l_tcpy += inst->size; } XD3_ASSERT (inst->size >= MIN_MATCH); @@ -2788,9 +2748,6 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) return ret; } - IF_DEBUG (stream->n_cpy += 1); - IF_DEBUG (stream->l_cpy += inst->size); - IF_DEBUG1 ({ static int cnt; P(RINT "[iopt copy:%d] pos %"Q"u-%"Q"u addr %"Q"u-%"Q"u size %u\n", @@ -2807,9 +2764,8 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) if ((ret = xd3_emit_byte (stream, & DATA_TAIL (stream), inst->xtra))) { return ret; } - IF_DEBUG (stream->n_run += 1); - IF_DEBUG (stream->l_run += inst->size); - IF_DEBUG (stream->n_dbytes += 1); + stream->n_run += 1; + stream->l_run += inst->size; IF_DEBUG1 ({ static int cnt; @@ -2822,9 +2778,8 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst) if ((ret = xd3_emit_bytes (stream, & DATA_TAIL (stream), stream->next_in + inst->pos, inst->size))) { return ret; } - IF_DEBUG (stream->n_add += 1); - IF_DEBUG (stream->l_add += inst->size); - IF_DEBUG (stream->n_dbytes += inst->size); + stream->n_add += 1; + stream->l_add += inst->size; IF_DEBUG1 ({ static int cnt; @@ -3196,12 +3151,8 @@ xd3_emit_single (xd3_stream *stream, xd3_rinst *single, uint code) if (has_size) { if ((ret = xd3_emit_size (stream, & INST_TAIL (stream), single->size))) { return ret; } - - IF_DEBUG (xd3_count_size (stream, single->size)); } - IF_DEBUG (xd3_count_inst (stream, code)); - return 0; } @@ -3225,8 +3176,6 @@ xd3_emit_double (xd3_stream *stream, xd3_rinst *first, xd3_rinst *second, uint c second->size, code)); - IF_DEBUG (xd3_count_inst (stream, code)); - return 0; } @@ -3496,23 +3445,22 @@ xd3_encode_init (xd3_stream *stream) // TODO: experiments have to be done!!! if (large_comp) { - usize_t hash_values = (stream->srcwin_maxsz / stream->smatcher.large_look); + usize_t hash_values = (stream->srcwin_maxsz / stream->smatcher.large_step); xd3_size_hashtable (stream, hash_values, & stream->large_hash); - IF_DEBUG1 (P(RINT "[encode_init] large hash %u slots\n", hash_values)); } if (small_comp) { /* Hard-coded, keeps table small because small matches become inefficient. */ - usize_t hash_values = min(stream->winsize / stream->smatcher.small_look, 65536U); + // TODO: verify this + usize_t hash_values = min(stream->winsize, 65536U); xd3_size_hashtable (stream, hash_values, & stream->small_hash); - IF_DEBUG1 (P(RINT "[encode_init] small hash %u slots\n", hash_values)); } for (i = 0; i < ENC_SECTS; i += 1) @@ -4040,6 +3988,7 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) diff = logical_input_cksum_pos - stream->srcwin_cksum_pos; onblk = min(blkoff + diff, onblk); + // TODO: is this inefficient for large_step < large_look? while (blkoff <= onblk) { uint32_t cksum = xd3_lcksum (stream->src->curblk + blkoff, stream->smatcher.large_look); diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h index 2ae1273..0c5bd43 100755 --- a/xdelta3/xdelta3.h +++ b/xdelta3/xdelta3.h @@ -45,7 +45,7 @@ /* Default total size of the source window used in xdelta3-main.h */ #ifndef XD3_DEFAULT_SRCWINSZ -#define XD3_DEFAULT_SRCWINSZ (1U << 23) +#define XD3_DEFAULT_SRCWINSZ (1U << 26) #endif /* When Xdelta requests a memory allocation for certain buffers, it rounds up to units of @@ -61,7 +61,7 @@ * without a copy window will require 3 bytes to encode (7 bits per byte, HERE and SAME * modes making every address within half the window away. */ #ifndef XD3_HARDMAXWINSIZE -#define XD3_HARDMAXWINSIZE (1U<<23) +#define XD3_HARDMAXWINSIZE (1U<<24) #endif /* The XD3_NODECOMPRESSSIZE parameter tells the xdelta main routine not to try to @@ -774,27 +774,21 @@ struct _xd3_stream xd3_sec_stream *sec_stream_i; xd3_sec_stream *sec_stream_a; -#if XD3_DEBUG /* statistics */ - usize_t n_cpy; - usize_t n_add; - usize_t n_run; - - usize_t n_ibytes; - usize_t n_sbytes; - usize_t n_dbytes; + xoff_t n_scpy; + xoff_t n_tcpy; + xoff_t n_add; + xoff_t n_run; - usize_t l_cpy; - usize_t l_add; - usize_t l_run; + xoff_t l_scpy; + xoff_t l_tcpy; + xoff_t l_add; + xoff_t l_run; +#if XD3_DEBUG usize_t sh_searches; usize_t sh_compares; - usize_t *i_freqs; - usize_t *i_modes; - usize_t *i_sizes; - usize_t large_ckcnt; /* memory usage */ -- cgit v1.2.3