RFC: Deque: should it have an opaque index?

<Light bulb moment after reading RFC: Deque: should it be self-slicing>

AIUI, Johannes is arguing that there is another, equally valid, way to represent locations in a flat storage buffer -- essentially by having indices store direct pointers to the underlying memory. And he is right! (I forgot that CircularBuffer worked that way. :see_no_evil: I think the three points I raised above are still valid, it's just that there is nothing "theoretical" about this approach.)

In Deque's case, having indices store an offset from the beginning of the storage buffer (rather than from the logical beginning of the collection) would at first glance eliminate a (fairly predictable) branch in the subscript implementation -- however, the same branch would just come back in the precondition that protects against out-of-bounds indices, so performance-wise, this would be a wash. (Or maybe even a slight overall pessimization, if we consider that the extra branches would also seep into things like index(after:) (which is literally just index + 1 in the current Deque).

Pointers-as-indices enable self-slicing, which seems largely undesirable to me in general -- because it leads to people unknowingly holding on to tiny slices of a huge collection, preventing it from getting released. Forcing people to make a copy is a good thing sometimes.

However, there is one particular, very high-profile case where self-slicing and non-integer indices would've made perfect sense for a RandomAccessCollection: it's UnsafeBufferPointer. Using UnsafePointers as indices would have been a terrific choice for it! It would have allowed it to be self-slicing, eliminating the clumsy rebasing: initializers. The memory leak above isn't relevant to UBP, because it isn't owning its memory, so there is no danger whatsoever of people accidentally retaining large buffers.

I think my adjusted position is that range-replaceable random-access collections ought to always use integer offsets as indices.

3 Likes