From: Junio C Hamano <gitster@pobox.com>
To: Nicolas Pitre <nico@cam.org>
Cc: Martin Koegler <mkoegler@auto.tuwien.ac.at>, git@vger.kernel.org
Subject: Re: [PATCH] Keep last used delta base in the delta window
Date: Wed, 29 Aug 2007 12:26:07 -0700 [thread overview]
Message-ID: <7vsl62p2gg.fsf@gitster.siamese.dyndns.org> (raw)
In-Reply-To: <alpine.LFD.0.999.0708291339580.16727@xanadu.home> (Nicolas Pitre's message of "Wed, 29 Aug 2007 14:21:33 -0400 (EDT)")
Nicolas Pitre <nico@cam.org> writes:
>> > 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.
next prev parent reply other threads:[~2007-08-29 19:26 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-08-26 20:56 [PATCH] Keep last used delta base in the delta window Martin Koegler
2007-08-27 8:48 ` Junio C Hamano
2007-08-27 10:07 ` David Kastrup
2007-08-27 20:43 ` Martin Koegler
2007-08-27 21:04 ` David Kastrup
2007-08-27 12:12 ` Junio C Hamano
2007-08-29 18:21 ` Nicolas Pitre
2007-08-29 19:26 ` Junio C Hamano [this message]
2007-08-29 21:02 ` Nicolas Pitre
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=7vsl62p2gg.fsf@gitster.siamese.dyndns.org \
--to=gitster@pobox.com \
--cc=git@vger.kernel.org \
--cc=mkoegler@auto.tuwien.ac.at \
--cc=nico@cam.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).