Clarify 'long term storage' of ArraySlice?

Using Swift
,
1

Hello! I’m developing a data structure where I’m creating a structured representation of an unordered, idempotent representation. I’d ideally like to avoid copying data from structure A to structure B, and my thought was to use ArraySlice.

For example, in a structure like this where tree nodes reference some underlying storage array to avoid copying from the serialized representation:

Tree:      [Node A, ArraySlice[0][0..<1]]
 [Node B, ArraySlice[0][2..<3]]     [Node C, ArraySlice[1][0..<3]
Data: [0, 1, 2], [3, 4, 5]

My question is related to the lifetime of ArraySlice. The documentation says that “Long-term storage of ArraySlice instances is discouraged.”. Would this be a misuse of ArraySlice? I’m thinking not for a few reasons but want to make sure:

  • The slices lifetimes are the same as the original arrays, the ‘data’ list in the example will outlive any tree nodes.
  • I’m not passing the slices outside of the structure. When interrogated, the structure will copy into a new array.
1 Like
2

The part of that warning after what you quoted helps to explain things:

Long-term storage of ArraySlice instances is discouraged. A slice holds a reference to the entire storage of a larger array, not just to the portion it presents, even after the original array’s lifetime ends. Long-term storage of a slice may therefore prolong the lifetime of elements that are no longer otherwise accessible, which can appear to be memory and object leakage.

So "long-term" is really trying to say "may outlive the original array/slice", since the entire buffer will remain in memory even if some of those elements have become inaccessible by virtue of being excluded from the live slices.

Based on what you've said, if the slices won't outlive the array, then you're probably fine. (And depending on your minimum deployment constraints, Span and explicit lifetimes may be a better option in the future to help express this more cleanly.)

2 Likes
3

Thanks, that’s insightful! The Span idea is something I had considered, would Span be better in this case? I’m maybe misunderstanding what benefits Span would have over a slice.

4

Span should fail to compile rather than keeping the original Array alive. Whether that’s better depends on what you want.

5

Hmm… what was the biggest factor for you in choosing to give every node an ArraySlice instead of a Range or ClosedRange? Why does every node need to save its own source of truth instead of just saving the correct "key-index" to look up the source of truth from another place?

Assuming this data structure is not constant I assume you would need some algorithm to update slices if the underlying Array is mutated… I think that work would be equal in complexity to updating all the ranges.

6

Instead of saving ArraySlices, which is unsafe, you can save the array itself. The array itself uses copy on write, so there is no real copying made unless you mutate the array. So instead of keeping an ArraySlice each node can store the Array itself (which is effectively a pointer to heap allocated buffer) and indices.
To know which elements from the source Array belong to the node, each node can store either:

  • Range of indices (e.g. 2..<5)
  • IndexSet
  • RangeSet
7

ArraySlice is totally safe. It is essentially an Array + Range.[1]
swift-asn1 and swift-certificates uses ArraySlice throughout it’s entire implementation to avoid copying data. A certificate is parsed from an Array<UInt8> and the parser slices that into smaller ArraySlice<UInt8>’s. In our public API we only expose Array<UInt8> so that users don’t need to think about that.

Your use case sounds very similar to this. As long as you make sure large Arrays aren’t accidentally keeping alive a lot of unused memory it is totally fine.

  1. The memory layout isn’t ideal. If your structure is truly temporary Span might be memory wise better as it is only using 2 word instead of ArraySlices 4. But ~Escapable is currently still very limiting and representing a Tree is likely very difficult or impossible with ~Escapable types. ↩︎

10 Likes