Comment by duneroadrunner | Hacker News Reader

Comment by duneroadrunner | Hacker News Reader

Parent Full thread

> Most of the following blog post is written from a game developer’s perspective, but should also apply to other areas ...

Video games are a special case where allocations and deallocations are often well scheduled and predictable. For the more general case, using a data type like ivector[1] for the object arrays would provide the desired memory safety. It gives you the flexibility of safely accessing an object via index, iterator or (zero-overhead smart) pointer. Even though it's a vector (like std::vector) its iterators behave like list iterators. That is, after an insertion or removal operation, unlike indexes, they continue to point to the same item (not necessarily the same position) and they only become invalid when the item they point to is removed. In particular, they don't become invalid after a resize/reallocation operation.

So using ivector's iterators instead of index handles would allow you to safely perform insertion/removal operations if necessary.

Also, for performance reasons you may sometimes want to temporarily obtain a direct pointer to the item. ivector allows you to obtain a zero-overhead smart pointer to the item that is guaranteed not to become invalid. [2] It does this by disabling "resize" operations on the vector while it exists.

[1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus#vectors

[2] https://github.com/duneroadrunner/SaferCPlusPlus#make_xscope...

The next step is to use the old structure called gap buffer, piece table or the more general zipper... And drop the pretense you are inventing something new. :)

Pretense not intended, thanks for clarifying. :) Rather than algorithmic novelty, the point is more that ivector has an API and implementation that is memory safe (memory safety seemed to be an emphasis of the blog post).

As for those next steps, I'm under the vague impression that they aren't as popular these days because larger cpu caches have greatly reduced the cost of moving contiguous data in most real-world scenarios. So that more often than not the cache coherency benefits of simple contiguous data outweigh the avoidance of shifting some of that (contiguous) data.[1]

[1] simple microbenchmark of contiguous vs non-contiguous containers near the end of the article: https://www.codeproject.com/articles/1087021/stable-iterator...

Exactly why a gap buffer, piece table and zipper are a thing. These structures are optimized exactly for local modification, especially chunked or contiguous. These are semi-contiguous structures.

At some point with bigger data you will hit the brick wall where the memory move is too expensive. This is typically at a bunch of megabytes in size for localized block inserts. The idea of these only slightly more advanced structures is to amortize the cost or defer it.

For instance, a gap buffer is essentially 3 vectors/arrays. Piece table is a few more, merged as needed, usually few. A zipper can mix contiguous (potentially heap) access with tree structuring for rarely modified or accessed parts.

As for iterator stability. Either the structure knows about a active iterators (expensive) and fixes them up or you should probably use plain old pointers as such. Bet you didn't know you can and should use a pointer as an iterator to a contiguous memory... And if you really for some reason do need to hold stable iterators to anything, std::array is good enough. Remember you cannot safely resize due to potential for memory copies on reallocation. (yes there are tricks, no they're very not cheap nor threadsafe nor concurrent) The consistency model of ivector iterators is not quite explicit.

Reply on news.ycombinator.com