Golang的append内存分配 VS. STL的push_back内存分配

huangapple
go评论110阅读模式
英文:

Golang append memory allocation VS. STL push_back memory allocation

问题

我比较了Go语言的append函数和STL的vector.push_back函数，并发现它们使用了不同的内存分配策略，这让我感到困惑。以下是代码示例：

  1. // CPP STL 代码
  2. void getAlloc() {
  3.     vector<double> arr;
  4.     int s = 9999999; 
  5.     int precap = arr.capacity();
  6.     for (int i=0; i<s; i++) {
  7.         if (precap < i) {
  8.             arr.push_back(rand() % 12580 * 1.0);
  9.             precap = arr.capacity();
  10.             printf("%d  %p\n", precap, &arr[0]);
  11.         } else {
  12.             arr.push_back(rand() % 12580 * 1.0);
  13.         }
  14.     }
  15.     printf("\n");
  16.     return;
  17. }
  20. // Golang 代码    
  21. func getAlloc() {
  22.     arr := []float64{}
  23.     size := 9999999
  24.     pre := cap(arr)
  25.     for i:=0; i<size; i++ {
  26.         if pre < i {
  27.             arr = append(arr, rand.NormFloat64())
  28.             pre = cap(arr)
  29.             log.Printf("%d %p\n", pre, &arr)
  30.         } else {
  31.             arr = append(arr, rand.NormFloat64())
  32.         }
  33.     }
  34.     return;
  35. }

但是，无论扩展大小如何增加，内存地址都保持不变，这让我非常困惑。顺便说一下，这两种实现（STL和Go）的内存分配策略是不同的，我指的是扩展大小。这是上述代码的简化输出[大小和第一个元素的地址]：

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

更新：

有关Golang的内存分配策略，请参阅评论。

对于STL，策略取决于具体的实现。请参阅此帖子以获取更多信息。

英文:

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:

  1. // CPP STL code
  2. void getAlloc() {
  3.     vector&lt;double&gt; arr;
  4.     int s = 9999999; 
  5.     int precap = arr.capacity();
  6.     for (int i=0; i&lt;s; i++) {
  7.         if (precap &lt; i) {
  8.             arr.push_back(rand() % 12580 * 1.0);
  9.             precap = arr.capacity();
  10.             printf(&quot;%d  %p\n&quot;, precap, &amp;arr[0]);
  11.         } else {
  12.             arr.push_back(rand() % 12580 * 1.0);
  13.         }
  14.     }
  15.     printf(&quot;\n&quot;);
  16.     return;
  17. }
  20. // Golang code    
  21. func getAlloc() {
  22.     arr := []float64{}
  23.     size := 9999999
  24.     pre := cap(arr)
  25.     for i:=0; i&lt;size; i++ {
  26.         if pre &lt; i {
  27.             arr = append(arr, rand.NormFloat64())
  28.             pre = cap(arr)
  29.             log.Printf(&quot;%d %p\n&quot;, pre, &amp;arr)
  30.         } else {
  31.             arr = append(arr, rand.NormFloat64())
  32.         }
  33.     }
  34.     return;
  35. }

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]:

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

UPDATE:

See comments for Golang memory allocation strategy.

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

答案1

得分: 2

你的Go和C++代码片段并不等价。在C++函数中，你打印的是向量中第一个元素的地址，而在Go示例中，你打印的是切片本身的地址。

就像C++的std::vector一样，Go的切片是一个小的数据类型，它持有一个指向底层数组的指针来保存数据。这个数据结构在整个函数中具有相同的地址。如果你想要获取切片中第一个元素的地址，你可以使用与C++相同的语法：&arr[0]。

英文:

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++: &amp;arr[0].

答案2

得分: 0

你得到的是切片头的指针，而不是实际的底层数组。你可以将切片头想象成一个类似结构体的东西，如下所示：

  1. type SliceHeader struct {
  2.     len,cap int
  3.     backingArray unsafe.Pointer
  4. }

当你执行追加操作并且底层数组被重新分配时，指针 backingArray 可能会被改变（不一定，但很可能）。然而，持有长度、容量和指向底层数组的指针的结构体的位置并不会改变，它仍然在你声明它的地方的栈上。尝试打印 &arr[0] 而不是 &arr，你应该会看到更接近你期望的行为。

顺便说一下，这与 std::vector 的行为几乎相同。将切片视为更接近于 vector 而不是一个神奇的动态数组。

英文:

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

  1. type SliceHeader struct {
  2.     len,cap int
  3.     backingArray unsafe.Pointer
  4. }

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 &amp;arr[0] instead of &amp;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.

huangapple
  • 本文由 发表于 2014年3月11日 11:46:59
  • 转载请务必保留本文链接：https://go.coder-hub.com/22316057.html
  • go
  • memory
  • stl
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定