/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/diff-delta.c

  • Committer: John Arbash Meinel
  • Date: 2009-03-18 22:32:01 UTC
  • mto: (3735.2.157 brisbane-core)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090318223201-rpttk4ur07xar0z5
Increasing EXTRA_NULLS to 2 from 1 ups the hit rate
9.1k => 10k without expanding, and 1407=>433 expansions.
Drops the overall time 3m45s=>3m40s.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/diff-delta.c
25
25
#define RABIN_SHIFT 23
26
26
#define RABIN_WINDOW 16
27
27
 
28
 
#define EXTRA_NULLS 1
 
28
/* The hash map is sized to put 4 entries per bucket, this gives us 2 blank
 
29
 * spaces.
 
30
 */
 
31
#define EXTRA_NULLS 2
29
32
 
30
33
static const unsigned int T[256] = {
31
34
    0x00000000, 0xab59b4d1, 0x56b369a2, 0xfdeadd73, 0x063f6795, 0xad66d344,
576
579
        /* Copy any of the old entries across */
577
580
        /* Would we rather use memcpy? */
578
581
        if (hmask == old_index->hash_mask) {
579
 
            found_null = 0;
580
582
            for (entry = old_index->hash[i];
581
 
                 entry < old_index->hash[i+1];
 
583
                 entry < old_index->hash[i+1] && entry->ptr != NULL;
582
584
                 ++entry) {
583
 
                if (entry->ptr == NULL) {
584
 
                    found_null = 1;
585
 
                    continue;
586
 
                } else if (found_null) {
587
 
                    fprintf(stderr, "Found a non-null entry after a"
588
 
                                    " NULL entry!\n"
589
 
                                    " new offset %x"
590
 
                                    " w/ value %x\n",
591
 
                                    i, entry->val);
592
 
                }
593
585
                assert((entry->val & hmask) == i);
594
586
                *packed_entry++ = *entry;
595
587
            }
599
591
             * spread across the new locations.
600
592
             */
601
593
            j = i & old_index->hash_mask;
602
 
            found_null = 0;
603
594
            for (entry = old_index->hash[j];
604
 
                 entry < old_index->hash[j+1];
 
595
                 entry < old_index->hash[j+1] && entry->ptr != NULL;
605
596
                 ++entry) {
606
 
                if (entry->ptr == NULL) {
607
 
                    found_null = 1;
608
 
                    continue;
609
 
                } else if (found_null) {
610
 
                    fprintf(stderr, "Found a non-null entry after a"
611
 
                                    " NULL entry!\n"
612
 
                                    " offset %x for new offset %x"
613
 
                                    " w/ value %x\n",
614
 
                                    j, i, entry->val);
615
 
                }
616
597
                assert((entry->val & old_index->hash_mask) == j);
617
 
                if (!(j == i || j + old_index->hash_mask + 1 == i)) {
618
 
                    fprintf(stderr, "Old hash entry %x"
619
 
                                    " doesn't fit with new %x\n"
620
 
                                    "old_mask: %x new_mask: %x\n",
621
 
                                    j, i, old_index->hash_mask, hmask);
622
 
                }
 
598
                // if (!(j == i || j + old_index->hash_mask + 1 == i)) {
 
599
                //     fprintf(stderr, "Old hash entry %x"
 
600
                //                     " doesn't fit with new %x\n"
 
601
                //                     "old_mask: %x new_mask: %x\n",
 
602
                //                     j, i, old_index->hash_mask, hmask);
 
603
                // }
623
604
                assert(j == i || j + old_index->hash_mask + 1 == i);
624
605
                if ((entry->val & hmask) == i) {
625
606
                    /* Any entries not picked up here will be picked up on the
855
836
        old_entry++;
856
837
        if (old_entry->ptr != NULL
857
838
            || old_entry >= old_index->hash[hash_offset + 1]) {
858
 
            char buff[128];
859
 
            get_text(buff, entry->ptr);
860
 
            fprintf(stderr, "Failed to find an opening @%x for %8x:\n '%s'\n",
861
 
                    hash_offset, entry->val, buff);
862
 
            for (old_entry = old_index->hash[hash_offset];
863
 
                 old_entry < old_index->hash[hash_offset+1];
864
 
                 ++old_entry) {
865
 
                get_text(buff, old_entry->ptr);
866
 
                fprintf(stderr, "  [%2d] %8x %8x: '%s'\n",
867
 
                        (int)(old_entry - old_index->hash[hash_offset]),
868
 
                        old_entry->val, old_entry->ptr, buff);
869
 
            }
 
839
            /* There is no room for this entry, we have to resize */
 
840
            // char buff[128];
 
841
            // get_text(buff, entry->ptr);
 
842
            // fprintf(stderr, "Failed to find an opening @%x for %8x:\n '%s'\n",
 
843
            //         hash_offset, entry->val, buff);
 
844
            // for (old_entry = old_index->hash[hash_offset];
 
845
            //      old_entry < old_index->hash[hash_offset+1];
 
846
            //      ++old_entry) {
 
847
            //     get_text(buff, old_entry->ptr);
 
848
            //     fprintf(stderr, "  [%2d] %8x %8x: '%s'\n",
 
849
            //             (int)(old_entry - old_index->hash[hash_offset]),
 
850
            //             old_entry->val, old_entry->ptr, buff);
 
851
            // }
870
852
            break;
871
853
        }
872
854
        num_inserted++;
880
862
        /* We couldn't fit the new entries into the old index, so allocate a
881
863
         * new one, and fill it with stuff.
882
864
         */
883
 
        fprintf(stderr, "inserted %d before resize\n", num_inserted);
 
865
        // fprintf(stderr, "inserted %d before resize\n", num_inserted);
884
866
        new_index = create_index_from_old_and_new_entries(old_index,
885
867
            entry, num_entries);
886
868
    } else {