Re: fix git-pack-redundant crashing sometimes

From: Linus Torvalds <torvalds@osdl.org>
Date: Nov 15, 2005, 17:28 UTC
Message-ID: <Pine.LNX.4.64.0511150921420.3945@g5.osdl.org>
In-Reply-To: <81b0412b0511150811w2a7a2c4ft9a2920ac4f030ee4@mail.gmail.com>

On Tue, 15 Nov 2005, Alex Riesen wrote:

Show 7 quoted lines

> On 11/15/05, Timo Hirvonen <tihirvon@gmail.com> wrote:
> > > The code could profit from double-linked lists greatly, IMHO.
> >
> > I use list.h from Linux when I need double-linked lists.  It is very
> > easy to use, efficient and fast.
> 
> Yes, I had it in mind, too.

There's a "ptrlist" implementation in sparse, which does a very space-efficient implementation of arbitrary lists of pointers. It's also very CPU-efficient (in fact, thanks to being very cache-friendly, more so than the kernel list.h implementation) for most well-behaved operations (ie it's not hugely friendly to removal, but it's great for "add to end" and "traverse the list").

The ptrlist implementation is optimized for cases where the lists are usually shortish, but not trivial. So they are worthwhile if you expect the list length to be on the order of 5-10 entries rather than just 1-2 (if you have just a couple of entries, the kernel lists are better). But perhaps more importantly, they are very space-efficient when the lists grow bigger (ie they average to just about 5% over the memory cost of a single pointer per list element for long lists).

Sparse in general is under the OSL license, but I'll happily dual-license the ptrlist thing, it's trivial and all my code (and I already checked with the person who did the list sorting code that we can dual-license that too).

			Linus