Re: A look at some alternative PACK file encodings

From: Linus Torvalds <torvalds@osdl.org>
Date: Sep 7, 2006, 00:45 UTC
Message-ID: <Pine.LNX.4.64.0609061737040.27779@g5.osdl.org>
In-Reply-To: <44FF6586.8080206@gmail.com>

On Wed, 6 Sep 2006, A Large Angry SCM wrote:

Show 7 quoted lines

> 
> > Btw, that "keeping the ordering it had" part I'm not convinced we actually 
> > enforce. That would depend on the sort algorithm used by "qsort()", I 
> > think. So there might be room for improvement there in order to keep 
> > things in recency order.
> 
> qsort() is not stable.

Well, quicksort isn't, but a lot of systems don't actually use quicksort to implement qsort() - despite the name.

I think, for example, that glibc uses a merge-sort when there are lots of entries (to avoid any potential bad behaviour with quicksort), and that should be stable. But I didn't actually check..

In fact, I didn't even think of this issue originally, but it might actually be worthwhile doing our own sort, exactly because we'll otherwise have different systems generating different pack-files due to issues like this.

So even if we don't actually _care_ whether the sorting is stable or not, we might well care that we always get the same results, regardless of what C library we have.

> > Is there any way to get zlib to just generate a suggested dictionary from 
> > a given set of input?
> 
> The docs suggest "no".

Oh, well.

			Linus