附加到长度未知的大数组的最佳执行方式

Question

There are several ways how to append to an array. Wondering is there known best performing way for appending to a huge array (100Mb) with unknown length? I want to avoid copying as it is increases chances to run out of memory and it will degrade performance. Should I consider using two dimensional arrays?

Answer 1

In Golang we have array and slice.

---

Arrays have fixed size, when you need more space you need to create bigger array copy all values from the old array and replace the old reference with the new array.

You should not hold the reference to the old array, so this memory will be garbage collected.

---

Alternatively, you can use slices (which is a wrapper on top of an array). Resize and copy will be done for you automatically.

---

You can also control resize manually, this could reduce GC. But it should be profiled and compared with slices.

I've added an example with storing in a multi-dimension array, I strongly recommend avoiding this approach. It will make traversal more complex and slower, high probability of memory leaks and many more. GC in Golang is extreamly fast.

BenchmarkStore/array-6            100000         20090 ns/op           0 B/op          0 allocs/op
BenchmarkStore/slice-6              5000        259940 ns/op     4654337 B/op         30 allocs/op
BenchmarkStore/Custom-6            10000        194152 ns/op     1747860 B/op          8 allocs/op
BenchmarkStore/Dimensions-6         3000        418654 ns/op     4458593 B/op         20 allocs/op

package main

import (
    "testing"
)

const size = 100000

// Wrapper around slice
type MyStore struct {
    growthFactor int
    watermark    int
    Data         []int
}

func NewMyStore(growthFactor, initialSize int) *MyStore {
    return &MyStore{growthFactor: growthFactor, watermark: -1, Data: make([]int, initialSize)}
}

func (s *MyStore) Append(v int) {
    nextPosition := s.watermark + 1
    currentSize := len(s.Data)
    full := currentSize == nextPosition
    if full {
        dataResize := make([]int, currentSize*s.growthFactor)
        copy(dataResize, s.Data)
        s.Data = dataResize
    }

    s.Data[nextPosition] = v
    s.watermark = nextPosition
}

// Dimensions
const chunkSize = 10
type MyStoreMultiDimensions struct {
    size      int
    watermark int
    data      [][chunkSize]int
}

func NewStoreMultiDimensions(chunks int) *MyStoreMultiDimensions {
    return &MyStoreMultiDimensions{watermark: -1, data: make([][chunkSize]int, chunks)}
}

func (s *MyStoreMultiDimensions) Append(v int) {
    nextPosition := s.watermark + 1
    chunk := nextPosition / chunkSize
    if len(s.data) <= chunk {
        s.data = append(s.data, [chunkSize]int{})
    }

    s.data[chunk][nextPosition%chunkSize] = v
    s.watermark = nextPosition
}

func BenchmarkStore(b *testing.B) {
    b.Run("array", func(b2 *testing.B) {
        for i := 0; i < b2.N; i++ {
            var store [size]int
            for item := 0; item < size; item++ {
                store[item] = item
            }
        }
    })
    b.Run("slice", func(b2 *testing.B) {
        for i := 0; i < b2.N; i++ {
            var store []int
            for item := 0; item < size; item++ {
                store = append(store, item)
            }
        }
    })
    b.Run("Custom", func(b2 *testing.B) {
        for i := 0; i < b2.N; i++ {
            var store = NewMyStore(4, 10)
            for item := 0; item < size; item++ {
                store.Append(item)
            }
        }
    })
    b.Run("Dimensions", func(b2 *testing.B) {
        for i := 0; i < b2.N; i++ {
            var store = NewStoreMultiDimensions(2)
            for item := 0; item < size; item++ {
                store.Append(item)
            }
        }
    })
}