[plt-scheme] likely 3.99.0.22 -> 3.99.0.23 incompatibility: hashtables

At Tue, 08 Apr 2008 20:40:07 +0200, "Majorinc, Kazimir" wrote:
> Matthew Flatt wrote:
> > Immutable hash-table update will be constant time. (Well, O(lg n), but
> > the constant will be so small that it's effectively O(n).) Mutable
> > hash-table update would be O(n).
> >
> > That's different from lists, where operating on the two kinds have the
> > same complexity, and I think it's a sever enough difference to
> > discourage the operation on mutable hash tables.
> >   
> Why O(n) if you already have O(log n) immutable hash table? Isn't it 
> very easy to define at least equally efficient hash table then? Is it 
> political or technical decision?

While `hash-set!' could be implemeted with `hash-set' and a mutable
cell, the constant facter on the current `hash-set!' is lower than the
constant on `hash-set'.

In my tests, the difference is a factor of 2 to 5, depending on the
complexity of the key and including GC time.

Matthew