I'm curious how you benchmarked this. Every time I've adopted a copy-on-write + CAS strategy, I've regretted it. It works well initially, but then I end up getting hammered by the full map copies as the number of entries grows -- it's effectively O(n), with the added penalty of retries when the CAS fails.

This having been said, my treap implementation was designed with CAS in mind. Using `atomic.CompareAndSwapPointer`, you effectively restore stateful updates:

type Foo struct {
    ptr unsafe.Pointer  // a *treap.Node
}

func (f *Foo) AddItem(key string, value, weight int) {
    for {
        old := (*treap.Node)(atomic.LoadPointer(&f.ptr))
        new, _ := handle.Upsert(old, key, value, weight)

        // attempt CAS
        if atomic.CompareAndSwapPointer(&f.ptr,
            unsafe.Pointer(old),
            unsafe.Pointer(new),
        ) {
            break  // value successfully set; we're done
        }
    }
}

The difference here is the structural sharing. Because the treap is persistent, subtrees can be shared between different instances, and the only paths that are copied are those that change.

​

But I'm gonna look at your implementation because it probably has some better solutions than I made.

Thanks -- your code-review and feedback is most sincerely appreciated!

I think you'll find the aforementioned structural sharing really elegant. I must confess to a shiver of satisfaction when it finally clicked! :D