Re: [PATCH] Keep last used delta base in the delta window

From: Junio C Hamano <gitster@pobox.com>
Date: Aug 29, 2007, 19:26 UTC
Message-ID: <7vsl62p2gg.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.LFD.0.999.0708291339580.16727@xanadu.home>

Nicolas Pitre <nico@cam.org> writes:

Show 10 quoted lines

>> > Instead of treating the "the last used one happened to be on the
>> > horizon -- try not to drop it" special case, I wonder if it
>> > makes sense to float the last used delta base object early in
>> > the window _after_ it is used.  Wouldn't we keep more than one
>> > very recently used delta base objects in the window that way?
>> 
>> The attached is my quick-and-dirty one.  
>
> I like this.  A LRU sorting of base objects is obviously a good thing to 
> do.  Some comments below.

Well, I said it is Q&D, because _I_ didn't like what I did ;-).

The original implementation of window as a plain array of "struct unpacked" made perfect sense because its use was strict FIFO. Adding new element and expiring oldest element was just an increment of the "idx" integer, and there was no memmove overhead.

If we are to make this into LRU (which I _do_ like), however, the data structure's circular FIFO origin makes the code unnecessary complex and inefficient, I think.

 - We can always say 0 is the bottom and (window-1) is the top.
   Then ((idx+1)%window) becomes unnecessary.  As a bonus, we do
   not have to disagree if it should be (window <= idx) or (idx
   >= window).

 - Shifting elements down to make room can become a single
   memmove() if we remove the circular FIFO origin from the
   window implementation.  The Q&D one has tons of structure
   assignments in each iteration.  It might even make sense to
   change the window itself an array of "struct unpacked *" and
   make LRU management into just memmove() of bunch of pointers.