Jeff King [off-list ref] writes:
On Tue, May 19, 2015 at 01:24:09AM +0200, René Scharfe wrote:
quoted
Use an automatic variable for recent_bitmaps, an array of pointers.
This way we don't allocate too much and don't have to free the memory
at the end. The old code over-allocated because it reserved enough
memory to store all of the structs it is only pointing to and never
freed it. 160 64-bit pointers take up 1280 bytes, which is not too
much to be placed on the stack.
MAX_XOR_OFFSET is turned into a preprocessor constant to make it
constant enough for use in an non-variable array declaration.
Noticed-by: Stefan Beller [off-list ref]
Suggested-by: Jeff King <redacted>
Signed-off-by: Rene Scharfe <redacted>
---
This seems to have fallen through the cracks, or did I just miss it?
Thanks, this looks good.
I looked over the function one more time to make sure it is the function
that is wrong, and not my suggestion. :) The current code seems pretty
obviously wrong.
I actually cannot guess what the current code is trying to do. Was
it an attempt to cache that many entries, but instead allocated and
discarded the space it tried to use as a cache every time?
On Tue, May 19, 2015 at 12:45:46PM -0700, Junio C Hamano wrote:
quoted
I looked over the function one more time to make sure it is the function
that is wrong, and not my suggestion. :) The current code seems pretty
obviously wrong.
I actually cannot guess what the current code is trying to do. Was
it an attempt to cache that many entries, but instead allocated and
discarded the space it tried to use as a cache every time?
Sort of. There are two caches at work.
The bitmaps on disk may be stored as XORs against nearby bitmaps up to
MAX_XOR_OFFSET slots away. So our goal is to reconstruct the actual
bitmaps and put them in our cache for later use. That's actually done by
store_bitmap(), which puts them into a hash table indexed by sha1.
But because we get the XOR base as an offset, we also need to be able to
quickly say "what was the bitmap that was N slots ago?", and the hash
cannot answer that quickly. So we keep a sliding window of the last
MAX_XOR_OFFSET bitmaps (pointing to the cached bitmaps stored in the
hash), and then we can index that directly by offset. And we can reuse
the array as a circular buffer (notice we always index it modulo the max
offset).
So you can think of the recent_bitmaps as an auxiliary index into the
bitmaps already cached by store_bitmap(). We don't need it after the xor
reconstruction (actually I think we don't do the xor reconstruction
here, but instead retain a pointer to the xor base and lazily do it, but
the point is that we've created that pointer).
-Peff