Re: [TCLCORE] Upgrade of Tcl's String Hash Algorithm

[Larry M. <lm...@bi...>]

On Mon, Feb 15, 2010 at 03:14:07PM +0000, Donal K. Fellows wrote:
> The main issue with the old hash algorithm was that it was too easy to
> attack it and turn hash table accesses from O(1) to O(n**2). 

So there must be bug reports or feature requests from users complaining
about this.  Could we see those?

> On non-malicious datasets, Tcl's original algorithm works pretty well.
> It's the case when someone's deliberately trying to provoke bad
> behaviour that concerned me. FNV seems to do better (and has reasonable
> distribution behaviour on the non-malicious datasets I've tried it with,
> such as the contents of /usr/share/dict/words and the first million
> cardinal numbers).

What's wrong with letting people who are trying to break the system
suffer poor performance?

You've got working code, well thought out, field tested for a couple
of decades, no complaints that I have seen, and you want to change it.
That's fine but there should be a compelling case for doing so.  In the
absence of one any sane group of engineers would not change something that
works just because they think the new one might be better.  Experience has
shown all of us that every change has some unexpected costs.
-- 
---
Larry McVoy                lm at bitmover.com           http://www.bitkeeper.com