+1 on this, and please note how diligently I resist commenting on any
of the spinoff threads this proposal produced :-).
-Karl
Greg Hudson <ghudson@MIT.EDU> writes:
> I'd like to modify subversion/libsvn_subr/hash.c:hash_write() to dump
> hashes in sorted key order. There are two advantages here:
>
> * It makes the dumped representation of a hash deterministic. Not
> exceptionally important for anything we care about right now, but
> it allows the dumped representation of a hash to be signed, for
> instance, or tested for validity.
>
> * It opens the door to, some day, writing code to search a seekable
> hash representation in O(lg(n)) time. Obviously, we'd have to be
> very careful about what contexts we do that in, since we have a
> bunch of 1.0.x code running around writing unsorted hashes right
> now.
>
> (A possible application would be directory lookups in FSFS,
> although I have no plans to implement such a thing any time soon.)
>
> The down side is that sorting takes O(n lg(n)) time, as opposed to the
> O(n) time it takes to naively write out a hash. I doubt there would
> be any kind of visible performance difference, though; lg(n) is
> effectively a constant, and a much lesser one than the I/O overhead of
> writing out hashes.
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Received on Wed Jun 2 18:57:22 2004