Rev 5541: Revert to previous code. in http://bazaar.launchpad.net/~jameinel/bzr/2.3-gcb-peak-mem
John Arbash Meinel
john at arbash-meinel.com
Thu Dec 2 20:12:45 GMT 2010
At http://bazaar.launchpad.net/~jameinel/bzr/2.3-gcb-peak-mem
------------------------------------------------------------
revno: 5541
revision-id: john at arbash-meinel.com-20101202201238-31yot935saovm9z5
parent: john at arbash-meinel.com-20101202193104-hk2y015fy71azhm2
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.3-gcb-peak-mem
timestamp: Thu 2010-12-02 14:12:38 -0600
message:
Revert to previous code.
-------------- next part --------------
=== modified file 'bzrlib/_delta_index_pyx.pyx'
--- a/bzrlib/_delta_index_pyx.pyx 2010-12-02 19:31:04 +0000
+++ b/bzrlib/_delta_index_pyx.pyx 2010-12-02 20:12:38 +0000
@@ -170,7 +170,7 @@
# will overlap for any table size less than 0x10000, at *all* steps) I
# don't know how common collisions are, but it may be more-than-normal
# because RABIN isn't a super-strong hash.
- self._next_hash = (rabin_val ^ (rabin_val >> 24))
+ self._next_hash = rabin_val
@cython.profile(False)
cdef rabin_entry* next_with_dummy(self): # noexcept
@@ -189,7 +189,7 @@
while self._step < self._table_mask:
slot = self._table + (self._next_hash & self._table_mask)
self._step += 1
- self._next_hash += self._step
+ self._next_hash = self._next_hash + self._step
if slot.ptr == NULL:
# We found a blank entry, so this chain is done
if self.free_slot == NULL:
@@ -222,72 +222,7 @@
self._next_hash))
@cython.profile(False)
-cdef inline RabinEntrySearch_start(RabinEntrySearch self, unsigned int rabin_val):
- self.rabin_val = rabin_val
- self.entry = NULL
- self.match_count = 0
-
- self.free_slot = NULL
- self._step = 0
- # Consider, self._next_hash & self._table_mask never see the 'upper'
- # bits of the rabin_val. Is there a decent way to 'mix that in', to
- # help keep chains from overlapping too much? (ATM 0x10001 and 0x20001
- # will overlap for any table size less than 0x10000, at *all* steps) I
- # don't know how common collisions are, but it may be more-than-normal
- # because RABIN isn't a super-strong hash.
- self._next_hash = (rabin_val ^ (rabin_val >> 24))
-
- at cython.profile(False)
-cdef inline rabin_entry* RabinEntrySearch_next_with_dummy(RabinEntrySearch self): # noexcept
- cdef rabin_entry *slot
- # This uses Quadratic Probing:
- # http://en.wikipedia.org/wiki/Quadratic_probing
- # with c1 = c2 = 1/2
- # This leads to probe locations at:
- # h0 = hash(k1)
- # h1 = h0 + 1 = h0 + 1
- # h2 = h0 + 3 = h1 + 2
- # h3 = h0 + 6 = h2 + 3
- # h4 = h0 + 10 = h2 + 4
- # Note that all of these are '& mask', but that is computed *after* the
- # offset.
- while self._step < self._table_mask:
- slot = self._table + (self._next_hash & self._table_mask)
- self._step += 1
- self._next_hash += self._step
- if slot.ptr == NULL:
- # We found a blank entry, so this chain is done
- if self.free_slot == NULL:
- self.free_slot = slot
- return NULL
- elif slot.ptr == dummy_ptr:
- if self.free_slot == NULL:
- self.free_slot = slot
- return slot
- if slot.rabin_val != self.rabin_val:
- continue
- # We found an entry that matches exactly, return it
- self.match_count += 1
- return slot
- return NULL
-
- at cython.profile(False)
-cdef inline RabinEntrySearch_next(RabinEntrySearch self):
- cdef rabin_entry *slot
- # Don't search forever, even if we have bogus entries in the table
- while self._step < self._table_mask:
- slot = self.next_with_dummy()
- if (slot != NULL and slot.ptr == dummy_ptr):
- continue
- self.entry = slot
- return
- raise RuntimeError("We seem to have stepped too far while searching"
- " for rabin_val = %d, we took %d steps, hash %d"
- % (self.rabin_val, self._step,
- self._next_hash))
-
- at cython.profile(False)
-cdef int _peek(RabinEntrySearch self, unsigned int rabin_val): # noexcept
+cdef inline int _peek(RabinEntrySearch self, unsigned int rabin_val): # noexcept
"""Check and see if there might be anything at a given rabin_val.
The idea is that most lookups fail to find anything, and we want it to
@@ -296,7 +231,7 @@
then there might be something, might not. Concretely, we return 0 if
there is null in the first slot, 1 otherwise.
"""
- return self._table[(rabin_val ^ (rabin_val >> 24)) & self._table_mask].ptr != NULL
+ return self._table[rabin_val & self._table_mask].ptr != NULL
cdef public unsigned int MIN_TABLE_SIZE
@@ -461,12 +396,12 @@
# TODO: We may want to shrink at this point if we find that we
# over-allocated. (Say we got 1MB of all 0's, then we end up with
# a single entry in the map, but reserved lots of space)
- if (self.table_mask != 0 and total_entries * 2 < table_size * 1):
+ if (self.table_mask != 0 and total_entries * 3 < table_size * 2):
# We have enough room already
return
# We need to resize, find out the new table size required
table_size = MIN_TABLE_SIZE
- while table_size < total_entries * 3 and table_size < 2**31:
+ while table_size < total_entries * 2 and table_size < 2**31:
table_size = table_size * 2
trace.mutter('resizing table %08x from %d to %d'
' for %d new_entries, %d total'
@@ -953,11 +888,11 @@
cdef _DeltaCreator creator
if not self.sources:
return None
- t = _timer()
+ # t = _timer()
creator = _DeltaCreator(self, content, max_delta_size, noisy)
val = creator.create()
- global make_delta_total_time
- make_delta_total_time += _timer() - t
+ # global make_delta_total_time
+ # make_delta_total_time += _timer() - t
return val
@@ -1018,6 +953,61 @@
self.out[self.out_pos] = <unsigned char>(i)
self.out_pos += 1
+ @cython.profile(False)
+ cdef int _find_better_match(self, const_data data, const_data data_end,
+ unsigned int cur_rabin_val,
+ RabinEntrySearch search) except -1:
+ cdef rabin_entry *cur_entry
+ cdef const_data cur
+ cdef const_data ref
+ cdef const_data ref_start
+ cdef const_data ref_end
+ cdef Py_ssize_t cur_match_size
+ cdef Py_ssize_t remaining_data_len
+ cdef SourceInfo ref_source
+ cdef int comparisons
+
+ # This is the function that gets triggered the most. Something like
+ # 420 calls while repacking bzr. (only one higher is search.next()
+ # having 500M calls.) Out of those 420M calls, 392M of those failed to
+ # match anything significant (try_again_count).
+
+ search.start(cur_rabin_val)
+ search.next()
+ if search.entry == NULL:
+ global nil_match
+ nil_match += 1
+ remaining_data_len = data_end - data
+ comparisons = 0
+ while search.entry != NULL:
+ cur_entry = search.entry
+ search.next()
+ ref = cur_entry.ptr
+ cur_match_size = remaining_data_len
+ if cur_entry.match_tail < remaining_data_len:
+ cur_match_size = cur_entry.match_tail
+ ref_end = ref + cur_entry.match_tail
+ if cur_match_size <= self.match_size:
+ # Our current best match is better than this one could possibly
+ # be
+ continue
+ # Now actually compare the bytes, and see how many match
+ cur = data
+ comparisons += 1
+ while cur_match_size > 0 and cur[0] == ref[0]:
+ cur += 1
+ ref += 1
+ cur_match_size -= 1
+ cur_match_size = (cur - data)
+ if cur_match_size > self.match_size:
+ # This match is better
+ self.match_size = cur_match_size
+ self.match_entry = cur_entry
+ if cur_match_size >= 4096:
+ # Stop searching for better matches
+ return comparisons
+ return comparisons
+
cdef _finalize_pending_insert(self):
cdef unsigned char insert_byte
cdef Py_ssize_t out_pos
@@ -1177,7 +1167,7 @@
# Pull in the next data character
RABIN_UPDATE(cur_rabin_val, data[-RABIN_WINDOW], data[0])
if _peek(search, cur_rabin_val):
- count = _find_better_match(self, data, data_end, cur_rabin_val,
+ count = self._find_better_match(data, data_end, cur_rabin_val,
search)
global matches_checked
matches_checked += count
@@ -1213,58 +1203,3 @@
_PyString_Resize(&self.output_buff, self.out_pos)
ret = <object>self.output_buff
return ret
-
-
- at cython.profile(False)
-cdef inline int _find_better_match(_DeltaCreator self, const_data data, const_data data_end,
- unsigned int cur_rabin_val,
- RabinEntrySearch search) except -1:
- cdef rabin_entry *cur_entry
- cdef const_data cur
- cdef const_data ref
- cdef const_data ref_end
- cdef Py_ssize_t cur_match_size
- cdef Py_ssize_t remaining_data_len
- cdef int comparisons
-
- # This is the function that gets triggered the most. Something like
- # 420 calls while repacking bzr. (only one higher is search.next()
- # having 500M calls.) Out of those 420M calls, 392M of those failed to
- # match anything significant (try_again_count).
-
- RabinEntrySearch_start(search, cur_rabin_val)
- RabinEntrySearch_next(search)
- if search.entry == NULL:
- global nil_match
- nil_match += 1
- remaining_data_len = data_end - data
- comparisons = 0
- while search.entry != NULL:
- cur_entry = search.entry
- RabinEntrySearch_next(search)
- ref = cur_entry.ptr
- cur_match_size = remaining_data_len
- if cur_entry.match_tail < remaining_data_len:
- cur_match_size = cur_entry.match_tail
- ref_end = ref + cur_entry.match_tail
- if cur_match_size <= self.match_size:
- # Our current best match is better than this one could possibly
- # be
- continue
- # Now actually compare the bytes, and see how many match
- cur = data
- comparisons += 1
- while cur_match_size > 0 and cur[0] == ref[0]:
- cur += 1
- ref += 1
- cur_match_size -= 1
- cur_match_size = (cur - data)
- if cur_match_size > self.match_size:
- # This match is better
- self.match_size = cur_match_size
- self.match_entry = cur_entry
- if cur_match_size >= 4096:
- # Stop searching for better matches
- return comparisons
- return comparisons
-
More information about the bazaar-commits
mailing list