[plt-scheme] help on how to write a frequency-counting function in a more functional way

At Tue, 28 Apr 2009 23:02:37 -0400, Doug Orleans wrote:
> On Sun, Apr 19, 2009 at 11:56 AM, Matthew Flatt <mflatt at cs.utah.edu> wrote:
> > The performance is close to the binary-tree performance, probably
> > because that's how functional hash tables are implemented internally
> > (but as red-black trees, so they're always balanced).
> 
> I had been naively assuming that immutable hash tables were as
> efficient as mutable ones.  It would be good to say more about their
> relative performance in the reference manual than just "immutable
> tables support constant-time functional update."

Ok, I extended the note there.

> I had also been assuming that immutable structures were better than
> mutable ones because of garbage collector write-barrier issues.   Are
> there situations where immutable hash tables are more efficient in
> practice than mutable ones due to this effect, even if they are
> algorithmically less efficient?

I think you'd need a lot of hash tables that keep referencing newly
allocated values, so that there are lots of minor GCs that have to
traverse lots of old data. Meanwhile, in our current implementation
(write barriers based on page protection), I don't think the write
barrier is not a significant cost in mutating an object.

With our implementation, immutable hash tables are probably only better
when they give you a better algorithm --- one that can needs O(1)
operations on a mapping and where the operations are aren't
"single-threaded" in the cumulative sense (i.e., you start with some
mapping and you want to extend it in different, independent ways).