[r6rs-discuss] [Formal] Formal semantics should not contain complicating optimizations

From: Thomas Lord <lord>
Date: Thu Mar 15 22:59:07 2007

John Cowan wrote:
> BTW, it occurred to me that a representation-switching implementation
> of strings can switch representations atomically provided the
> pointer to the code units (8-bit, 16-bit, or 32-bit) contains
> some tag bits indicating which one it is. When a string mutator
> detects that it needs to convert the representation, it builds up
> a new representation in freshly allocated memory, constructs the
> specially tagged pointer to it, and atomically swaps in the new
> pointer for the old. No locks.
>
>

Meanwhile, another thread has picked up the old pointer, added an index
and is about to mutate now-stale memory just after you've swapped pointers.

The difficulty in implementing that kind of string isn't limited to threaded
systems, either. You can easily wind up with stale pointers to the previous
string rep lots of ways.

It's not *that* hard, I think, to do it well, though. String rep
changes shouldn't
happen all that often (and you can take simple steps to make sure that's
the case).
So, for example, you can reasonably trade off locking granularity
(latency on
rep changes) for overall speed.

There's other tricks that can help, too, but we've prbly handed out enough
rope (cough, cough) for people string themselves up, already. (hint, hint)

In some sense, coming to grips with the extra code all this takes is, if
done well, also a way to come to grips with how memory hierarchies
really work.


-t
Received on Thu Mar 15 2007 - 23:08:23 UTC