Golang append memory allocation VS. STL push_back memory allocation

Question

I compared the Go append function and the STL vector.push_back and found that different memory allocation strategy which confused me. The code is as follow:

// CPP STL code
void getAlloc() {
    vector<double> arr;
    int s = 9999999; 
    int precap = arr.capacity();
    for (int i=0; i<s; i++) {
        if (precap < i) {
            arr.push_back(rand() % 12580 * 1.0);
            precap = arr.capacity();
            printf("%d  %p\n", precap, &arr[0]);
        } else {
            arr.push_back(rand() % 12580 * 1.0);
        }
    }
    printf("\n");
    return;
}


// Golang code    
func getAlloc() {
    arr := []float64{}
    size := 9999999
    pre := cap(arr)
    for i:=0; i<size; i++ {
        if pre < i {
            arr = append(arr, rand.NormFloat64())
            pre = cap(arr)
            log.Printf("%d %p\n", pre, &arr)
        } else {
            arr = append(arr, rand.NormFloat64())
        }
    }
    return;
}

But the memory address is invarient to the increment of size expanding, this really confused me. By the way, the memory allocation strategy is different in this two implemetation (STL VS. Go), I mean the expanding size. Is there any advantage or disadvantage? Here is the simplified output of code above[size and first element address]:

Golang                            CPP STL
2 0xc0800386c0                    2  004B19C0
4 0xc0800386c0                    4  004AE9B8
8 0xc0800386c0                    6  004B29E0
16 0xc0800386c0                   9  004B2A18
32 0xc0800386c0                   13  004B2A68
64 0xc0800386c0                   19  004B2AD8
128 0xc0800386c0                  28  004B29E0
256 0xc0800386c0                  42  004B2AC8
512 0xc0800386c0                  63  004B2C20
1024 0xc0800386c0                 94  004B2E20
1280 0xc0800386c0                 141  004B3118
1600 0xc0800386c0                 211  004B29E0
2000 0xc0800386c0                 316  004B3080
2500 0xc0800386c0                 474  004B3A68
3125 0xc0800386c0                 711  004B5FD0
3906 0xc0800386c0                 1066  004B7610
4882 0xc0800386c0                 1599  004B9768
6102 0xc0800386c0                 2398  004BC968
7627 0xc0800386c0                 3597  004C1460
9533 0xc0800386c0                 5395  004B5FD0
11916 0xc0800386c0                8092  004C0870
14895 0xc0800386c0                12138  004D0558
18618 0xc0800386c0                18207  004E80B0
23272 0xc0800386c0                27310  0050B9B0
29090 0xc0800386c0                40965  004B5FD0
36362 0xc0800386c0                61447  00590048
45452 0xc0800386c0                92170  003B0020
56815 0xc0800386c0                138255  00690020
71018 0xc0800386c0                207382  007A0020
....

UPDATE:

See comments for Golang memory allocation strategy.

For STL, the strategy depends on the implementation. See this post for further information.

score 2 · Answer 1 · answered Mar 11 '14 at 03:54

2

Your Go and C++ code fragments are not equivalent. In the C++ function, you are printing the address of the first element in the vector, while in the Go example you are printing the address of the slice itself.

Like a C++ std::vector, a Go slice is a small data type that holds a pointer to an underlying array that holds the data. That data structure has the same address throughout the function. If you want the address of the first element in the slice, you can use the same syntax as in C++: &arr[0].

answered Mar 11 '14 at 03:54

James Henstridge

42,244
6
132
114

Thanks for your comment. By the way, could you explain the difference of magic incremental allocation? – Jiaxiang Mar 11 '14 at 04:50
1

The Go strategy seems to be to double the backing array size up to 1024 elements, and then increase in 25% increments. I'm not sure what strategy that STL implementation is using. – James Henstridge Mar 11 '14 at 07:14

score 0 · Answer 2 · answered Mar 11 '14 at 03:53

You're getting the pointer to the slice header, not the actual backing array. You can think of the slice header as a struct like

type SliceHeader struct {
    len,cap int
    backingArray unsafe.Pointer
}

When you append and the backing array is reallocated, the pointer backingArray will likely be changed (not necessarily, but probably). However, the location of the struct holding the length, cap, and pointer to the backing array doesn't change -- it's still on the stack right where you declared it. Try printing &arr[0] instead of &arr and you should see behavior closer to what you expect.

This is pretty much the same behavior as std::vector, incidentally. Think of a slice as closer to a vector than a magic dynamic array.

Golang append memory allocation VS. STL push_back memory allocation

2 Answers2