Re: A look at some alternative PACK file encodings

From: Linus Torvalds <torvalds@osdl.org>
Date: 2006-09-07 10:45:01
On Wed, 6 Sep 2006, A Large Angry SCM wrote:
> 
> > 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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Received on Thu Sep 07 10:45:13 2006

This archive was generated by hypermail 2.1.8 : 2006-09-07 10:47:22 EST