[darcs-users] Re: [zander at kde.org: Re: Re: Frustrations diffing against the last change to a file]

Jamie Webb j at jmawebb.cjb.net
Sun Apr 3 19:59:14 UTC 2005


On Sat, Apr 02, 2005 at 03:26:34PM -0800, Michael G Schwern wrote:
> We don't need to be cryptographically secure, but we do need to reasonably
> avoid collisions within a project.  I don't know how to run the numbers to 
> find out the odds of a collision.  Anyone?

Patches in repo | Collision probability
----------------+----------------------
2048            | 0.00003
4096            | 0.00012
8192            | 0.00048
16384           | 0.00195
32768           | 0.00778
65536           | 0.03076
131072          | 0.11750
262144          | 0.39346
524288          | 0.86466
1048576         | 0.99966

So, much less than 1 per thousand real projects could be expected to
see collisions with a 36-bit hash.  Provided that such conflicts were
merely a nuisance (i.e. darcs complains if you try to refer to a patch
by digest when there's a conflict involving that particular patch),
that is IMO quite acceptable.

I don't much like the idea of having to deal with base64 values
though. I'd prefer a 7-character (35-bit) 'base32' value that's case
insensitive. But a non-unique sequential number is probably still
nicer.

-- Jamie Webb




More information about the darcs-users mailing list