Pali Rohár <[email protected]> writes: > Rémi Cardona remi at gentoo.org wrote: >> >> See this thread for some reasoning >> http://lists.x.org/archives/xorg/2007-August/026730.html > > I still do not understand what cryptographic safe hash function solving in > hash map of glyphs. Why there is need to use sha1 hash function for hash > map? I have never seen use of sha1 hash function for implementing hash map. > For me this is really overkill. > > CCing Carl, please can you explain your decision for sha1? Maybe I did not > catch something important.
Short answer: Yes. I intentionally chose a cryptographic hash function for the glyph cache here. Long answer: I tried to explain things in the mailing-list post cited above. Apparently that wasn't sufficiently clear. Hopefully, if I try again now, it can become more clear. You said you've never seen the use of a sha1 hash function for implementing a hash map. It is common to use a much cheaper hash function, (but with much greater probability of collisions). In such a map, the code will generally be setup to deal with hash collisions, (such as by direct comparison of the hash keys). In the work I did to move the cached glyph images to pixmaps (in video memory), the cached images effectively become unavailable to the software implementing the cache. (It might be technically possible to read the images back, but it would be so prohibitively expensive that it would invalidate the gains of the cache.) So with this cache, without any way to deal with collisions, I chose a hash function that would be extremely unlikely to result in any collisions. I'll be the first to admit that it feels a little strange to have a glyph cache that will only *probably* give you the right image, (even if the implementation has no bugs). If someone can design and implement something that will give the right result 100% of the time and perform as well, I certainly won't stand in the way. But in the meantime, yes, the current design does depend on the properties of a cryptographic hash function. (That said, I don't have any strong opinions on *which* cryptographic hash function should be used, nor which implementation.) I hope that helps, -Carl
pgpKQnUwjM7EV.pgp
Description: PGP signature
_______________________________________________ [email protected]: X.Org development Archives: http://lists.x.org/archives/xorg-devel Info: http://lists.x.org/mailman/listinfo/xorg-devel
