RFC: Hash dumps in sorted order

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
Received on Mon May 31 00:12:39 2004