CODEWITHSUNDEEP
arraysswift
PGDev
PGDev

Reputation: 24341

How ArraySlice in Swift work internally?

I have already read multiple posts and articles about how ArraySlice works with Array in `Swift.

But, what I couldn't find is how it works internally? What does ArraySlice are Views onto Arrays exactly mean?

var arr = [1, 2, 3, 4, 5]
let slice = arr[2...4]

arr.remove(at: 2)
print(slice.startIndex) //2
print(slice.endIndex)   //5
slice[slice.startIndex] //3

In the code above, I've removed element at index-2 (i.e 3) from arr. Index-2 is the startIndex of slice as well. When I print slice[slice.startIndex] it still prints 3.

Since no extra storage is created for ArraySlice, then how come any changes in Array doesn't reflect in ArraySlice?

The articles/ posts can be found here:

https://dzone.com/articles/arrayslice-in-swift

https://marcosantadev.com/arrayslice-in-swift/

Upvotes: 5

Views: 1874

Answers (2)

Martin R
Martin R

Reputation: 539705

Both Array and ArraySlice are value types, which means that after

var array = [0, 1, 2, 3, 4, 5]
var slice = array[0..<2]

array and slice are independent values, and mutating one does not affect the other:

print(slice) // [0, 1]
array.remove(at: 0)
print(slice) // [0, 1]

How that is achieved is an implementation detail of the Swift standard library, but one can inspect the source code to get some ideas: At Array.swift#L1241 we find the implementation of Array.remove(at:):

  public mutating func remove(at index: Int) -> Element {
    _precondition(index < endIndex, "Index out of range")
    _precondition(index >= startIndex, "Index out of range")
    _makeUniqueAndReserveCapacityIfNotUnique()

   // ...
  }

which uses

  @inlinable
  @_semantics("array.make_mutable")
  internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
    if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
      _copyToNewBuffer(oldCount: _buffer.count)
    }
  }

Following that trail, we find at ArrayBuffer.swift#L107

  /// Returns `true` iff this buffer's storage is uniquely-referenced.
  @inlinable
  internal mutating func isUniquelyReferenced() -> Bool {

    // ...
  }

This isn't the full implementation yet, but (hopefully) already demonstrates that the (mutating) remove(at:) method copies the element storage to a new buffer if is was shared (with another array or an array slice).

We can also verify that by printing the element storage base address:

var array = [0, 1, 2, 3, 4, 5]
var slice = array[0..<2]

array.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101927190
slice.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101927190

array.remove(at: 0)

array.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101b05350
slice.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101927190

The same “copy-on-write” technique is used if arrays, dictionaries, or strings are copied, or if String and Substring share storage.

So an array slice shares the element storage with its originating array as long as neither of them is mutated.

That is still a useful feature. Here is a simple example:

let array = [1, 4, 2]
let diffs = zip(array, array[1...]).map(-)
print(diffs) // [-3, 2]

array[1...] is a view/slice of the given array, without actually copying the elements.

A recursive binary search function where slices (of the left or right half) are passed down would be another application.

Upvotes: 9

user1046037
user1046037

Reputation: 17685

Explanation:

Array slice is a view to the underlying array and retains the array.

Probably (not 100% sure), when you remove an element from the array, it is still retained and is just marked as removed.

That is why when you print the array you don't see 3 but the slice still shows it.

Example:

class Car : CustomStringConvertible {
    var description: String {

        let objectIdentifier = ObjectIdentifier(self) //To get the memory address

        return "car instance - \(objectIdentifier) "
    }

    deinit {
        print("car deallocated")
    }
}

var carSlice : ArraySlice<Car>?

var cars : [Car]? = [Car(), Car(), Car()]

carSlice = cars?[0...1]


print("Going to make cars nil")

cars = nil

print("cars     = \(cars?.description ?? "nil")")
print("carSlice = \(carSlice?.description ?? "nil")")

print("----------------")

print("Going to make carSlice nil")

carSlice = nil

print("carSlice = \(carSlice?.description ?? "nil")")

Output:

Going to make cars nil
cars     = nil
carSlice = [car instance - ObjectIdentifier(0x000060c00001e7b0) , car instance - ObjectIdentifier(0x000060c00001e7c0) ]
----------------
Going to make carSlice nil
carSlice = nil
car deallocated
car deallocated
car deallocated

Apple Documentation:

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.

Refer:

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

Upvotes: 2

Related Questions