ContiguousArray and Data Locality

Question

Hello, I am looking to understand ContiguousArray Better.

I am working on a game and I need to store thousands of entities of the same Type ( Reference type ) contiguous and ordered in memory in order to traverse and update the entities in this collection in a cache friendly manner.

The problem is that these entities can die randomly and so I need to remove them randomly from the Contiguous Array, and this is where I have difficulty understanding if Contiguous Array keeps its elements contiguous and in order in memory after certain operations.

Lets say I have a Contiguous Array named entities.

var entities: ContiguousArray<Type1> = []

Where Type1 is a class ( Reference type )

As the game goes, I append 1000 entities in the array using the method append( Element ) Are they contiguous in memory after these operations ? Also are they ordered in memory according to their position in the array ?

Then lets say entities from index 10 to 100 die and also entities from index 300 to 500 die and I remove them form the array using the method remove( at: Int ), are the remaining entities still contiguous in memory after these operations ? Also are they ordered in memory according to their new positions in the array ?

Lets say these entities die but I dont remove them from the array and instead I directly shift all the entities inside the array, shifting live entities to a position where an entity died using the subscript entities[ deadEntityIndex ] = entities[ liveEntityIndex ] repeatedly,is the array still contiguous after all these operations ? Also are they ordered in memory according to their new positions in the array ?

Basically I am looking to understand if the contigupus array keeps being contiguous in memory and also ordered in memory according to their position in the array after these operations:

Appending Entities
Removing entities at random places
Shifting entities inside the array from one place to another
Changing entities position inside the array

If there is a precise description of the locality of entities in ContunuousArray after these operations please refer me to it.

Finally just out of curiosity lets say we have two contiguous arrays arr1 and arr2 of elements of the same type ( Reference Type ) and they both share a common element.

arr1[ 10 ] = element1

arr2[ 100 ] = element1

Obviously both cant be contiguous because the shared element cant be duplicated in memory, so wich of these arrays is contiguous, the last one in wich an operation was performed ?

Thanks a lot for reading my question and helping.

Swift

1.1k

Posted by

AlexRainforestDev

Reply

Add a Comment

Answer 1

My understanding:

The

ContiguousArray

type is a specialized array that always stores its elements in a contiguous region of memory.

So depending on what elements are :

either you store a value in the array : then you will have a (new) copy in each array

or you store by reference, which is what I described in my previous post. But the objects themselves should not be contiguous.

Posted by

Claude31

Add a Comment

Answer 2

Just for cusriosity: why do you care ?

On your last question though:

Finally just out of curiosity lets say we have two contiguous arrays arr1 and arr2 of elements of the same type ( Reference Type ) and they both share a common element.

arr1[ 10 ] = element1

arr2[ 100 ] = element1

Obviously both cant be contiguous because the shared element cant be duplicated in memory, so wich of these arrays is contiguous, the last one in wich an operation was performed ?

Both could be contiguous. arr1[ 10 ] and arr2[ 100 ] point to the same element1, but that has nothing to do with contiguosity.

Try to illustrate:

arr1 : item0, item 1…………… item 10 …………… item 50

points to v

element1 <-------------------- points to

|

arr2 : item0, item 1…………… item 10 …………… ....................item 100

Posted by

Claude31

Add a Comment

Answer 3

So that means that only the pointers are contiguous in memory ? I tought the actual objects became contiguous. Like if I insert 100 reference type objects in arr1 do the objects get arranged contiguously in memory or just the pointers ?

Well about my last question I was wondering at what points do ContiguousArray used on reference types arranges the location in memory of the objects it stores, if it even does.

For instance lets say there are 20 reference type objects not contiguous in memory then you insert them all in a contiguous array, are these objects relocated to be contiguous after the insertion ? or are just the pointers that are contiguous

Posted by

AlexRainforestDev

Add a Comment

Answer 4

My understanding:

The

ContiguousArray

type is a specialized array that always stores its elements in a contiguous region of memory.

So depending on what elements are :

either you store a value in the array : then you will have a (new) copy in each array

or you store by reference, which is what I described in my previous post. But the objects themselves should not be contiguous.

Posted by

Claude31

Add a Comment

Answer 5

I have confirmed that this is indeed the case. So I am looking into using an underlying array of value types. Is it allways the case that a contiguous array of structs or value types will directly store its elements contiguous in memory as a buffer ?

Thanks

Posted by

AlexRainforestDev

Add a Comment

Answer 6

In Swift, Array is a value type, but it can have elements of value type (scalar, struct, enum, etc) or reference type (class instances). If the elements are of value type, the array stores copies of the values, so equal ("the same") values in different arrays are separate items. For such arrays, the storage is documented to be contiguous:

https://developer.apple.com/documentation/swift/array

(under the heading "Growing the Size of an Array").

For arrays of reference types, different arrays store copies of the object references (8 bytes each), but the objects themselves are not duplicated (unless you explicitly make copies yourself). In this case, the array may be stored in Swift-native form, which is a contiguous array of references, or Obj-C native form, which uses a NSArray object as the underlying storage.

You originally asked about arrays of reference type elements, so what you get will depend on how you create the array. If you do it with pure-native Swift code, you'll presumably get a Swift-native array.

OTOH, the performance characteristics of NSArray is pretty well known. You can expect identical performance to a strictly contigous array up to a couple of hundred thousand elements. After that, NSArray will perform better than a true contiguous array. (Counterintuitive, but true.)

So, while it's good that you're thinking about performance, agonizing over the exact representation is probably a case of premature optimization. For arrays of thousands or even tens of thousands of entries, the default behavior is probably the best choice.

Ultimately, if you run into a performance problem, the solution will likely be to use something other than array.

Posted by

QuinceyMorris

Add a Comment

ContiguousArray and Data Locality

Accepted Reply

Replies