One Terabyte Array Idea

Evolution Pitches
4

Edit: Thanks to @ibex10 for alerting me about bugs and suggestions how to improve the implementation. Now the results are much more sane and not off the charts. For debug mode I'm reducing the element count 100x fold to not wait too long. If you try the app better use release mode.

I gave this idea a test:

sample app 
import Foundation

let kb = 1024
let mb = 1024*kb
let gb = 1024*mb
let tb = 1024*gb

// TODO: COW, etc
struct QuickArray<Element> {
    var items: UnsafeMutablePointer<Element>
    var startOffset: Int
    
    init() {
        let count = tb / MemoryLayout<Element>.stride
        items = UnsafeMutableRawPointer
            .allocate(byteCount: tb, alignment: MemoryLayout<Element>.alignment)
            .bindMemory(to: Element.self, capacity: count)
        startOffset = count / 2
    }
    
    func deinitialize() {
        items.deallocate()
    }
    
    subscript(_ index: Int) -> Element {
        get {
            precondition(index >= 0 && index < count)
            return items[startOffset + index]
        }
        set {
            precondition(index >= 0 && index < count)
            items[startOffset + index] = newValue
        }
    }
    
    private (set) var count: Int = 0
    
    mutating func append(_ element: Element) {
        count += 1
        self[count - 1] = element
    }
    
    mutating func prepend(_ element: Element) {
        count += 1
        startOffset -= 1
        self[0] = element
    }
}

extension Array {
    mutating func prepend(_ element: Element) {
        insert(element, at: 0)
    }
}

@inline (never)
func test_arrayOperation(size: Int, execute: (Int) -> Void) {
    for i in 0 ..< size {
        execute(i)
    }
}

@inline (never)
func test_appendQuickArray(size: Int) {
    var items = QuickArray<UInt8>()
    test_arrayOperation(size: size) { i in
        items.append(UInt8(i & 0xFF))
    }
    items.deinitialize()
}

@inline (never)
func test_prependQuickArray(size: Int) {
    var items = QuickArray<UInt8>()
    test_arrayOperation(size: size) { i in
        items.prepend(UInt8(i & 0xFF))
    }
    items.deinitialize()
}

@inline (never)
func test_appendNormalArray(size: Int) {
    var items: [UInt8] = []
    items.reserveCapacity(size)
    test_arrayOperation(size: size) { i in
        items.append(UInt8(i & 0xFF))
    }
    items.removeAll()
    items.reserveCapacity(0)
}

@inline (never)
func test_prependNormalArray(size: Int) {
    var items: [UInt8] = []
    items.reserveCapacity(size)
    test_arrayOperation(size: size) { i in
        items.prepend(UInt8(i & 0xFF))
    }
    items.removeAll()
    items.reserveCapacity(0)
}

func runTests() {
    #if DEBUG
    print("tests started DEBUG mode")
    let bigArraySize = 10*mb
    let smallArraySize = 1*mb
    #else
    print("tests started RELEASE mode")
    let bigArraySize = 1000*mb
    let smallArraySize = 1*mb
    #endif

    print("append quick array test")
    var start = Date()
    test_appendQuickArray(size: bigArraySize)
    print("append quick array \(bigArraySize/mb) million elements: \(Date().timeIntervalSince(start)) sec")
    sleep(5)

    print("prepend quick array test")
    start = Date()
    test_prependQuickArray(size: bigArraySize)
    print("prepend quick array \(bigArraySize/mb) million elements: \(Date().timeIntervalSince(start)) sec")
    sleep(5)

    print("append normal array test")
    start = Date()
    test_appendNormalArray(size: bigArraySize)
    print("append normal array \(bigArraySize/mb) million elements: \(Date().timeIntervalSince(start)) sec")
    sleep(5)

    print("prepend normal array test")
    // too slow, using smaller size
    start = Date()
    test_prependNormalArray(size: smallArraySize)
    print("prepend normal array \(smallArraySize/mb) million elements!!!: \(Date().timeIntervalSince(start)) sec")
    sleep(5)

    print("tests done")
}

runTests()

Got these results:

RELEASE mode!
append quick array 1000 million elements: 0.95 sec
prepend quick array 1000 million elements: 0.77 sec
append normal array 1000 million elements: 2.35 sec
prepend normal array 1 million elements: 10.53 sec // 1000x fewer elements

All ops above but prepend on normal array are O(1), and as prepend on normal array is O(N) I can't run it with the same large number of elements to directly compare the speed difference. Note that this simple QuickArray implementation supports only POD types at the moment.

This was on 64 bits CPU that has an enormous address space. How to do a similar thing on 32 bits that doesn't have huge address space? We could do something similar with smaller upfront allocation: e.g. for an array that grows to 100K elements we allocate 200K elements with the start offset positioned to 50K from the arena start so the array elements are "centred". Once array is outgrown the allocated arena - double arena size and place array elements "centred" again in the arena area. Similarly for shrinking.

This might seem irrelevant at the first glance but poses a question: if it is possible to do a quick array implementation that allows quick appending / removing from both ends, why bother having a special "dequeue" type to begin with (let alone discussing its proper name :crazy_face:)