Is this the right way to do copy-on-write / use isKnownUniquelyReferenced?

In that case yes, your code above looks ok.

I suggest you benchmark the difference between that implementation and simply using [Integer: [Integer]] though. If you judiciously use reserveCapacity on your backing sets, I suspect you'll find the moderate increase in number of allocations could well be entirely outweighed by the improvement in cache locality.

(The digression: a linked list is an incredibly cache-unfriendly data structure, as the program jumps are essentially random and the odds of two nodes sharing a cache line are basically zero. This causes a lot of cache misses and CPU stalls. Moving to a linear data structure like Array, even though you will need to allocate slightly more, may well return its gains in locality. You could also try Set<Integer> to avoid needing to construct one, though Set is a bit less space-efficient and a lot less access efficient.)

1 Like