Okay, two interned strings will be represented by the same pointer. That doesn't complicate the comparison logic that much; the common case of interned-interned

Okay, two interned strings will be represented by the same pointer. That doesn't complicate the comparison logic that much; the common case of interned-interned comparisons can be checked for first, and the branch predictor will get rid of most of the overhead of having an extra check in there. This is similar to a trick for representing bignums on a 32-bit system. You can use the lowest bit of a 32-bit value as a tag: if it's zero, then the number is a 31-bit integer; if it's 1, then the number (with the low bit cleared) is a pointer to a heap-allocated bignum. The common case is that you're doing operations with numbers that fit in 31 bits, so the code for handling bignums is avoided by the branch predictor. (This works even better on a 64-bit system, where the common case is even more common.) As for cache effects, I think the main issues there, for ropes, are tree depth and chunk size. You want the tree to be shallow (so as to minimize the number of potential cache misses before you reach the chunk you're looking for) and you want the chunks to be large enough that they get good cache locality, but small enough that you get fast insertion/deletion/concatenation/etc.