3 ms·

I am curious how much of a difference there would be if the author would use result := make([]unit64, 0, len(elements)) in the old func. I think that the wa

I am curious how much of a difference there would be if the author would use result := make([]unit64, 0, len(elements)) in the old func. I think that the way it is written, it will continually have to be expanded as the backing array exceeds its capacity (in the course of append() calls). And as others have pointed out, maybe use an empty struct (as opposed to a bool or empty interface) as the map value type. Also TIL about make(map[T]S, len) - didn’t know you could set len, or at least hadn’t seen it in practice, but it was suggested here and I think it would likely help as well. Edited: I forgot to set len to 0.

cyber_kinetist 3y ago
In C++'s STL you can reserve() a specific capacity for the std::vector to use, and at the end of your operation you can trim off the remaining memory using shrink_to_fit(): std::vector<int> elems; elems.reserve(max_bound_num_of_elems); // do some push_back()'s elems.shrink_to_fit(); Is there anything similar in Go?
- avg_dev 3y ago
  Interesting idea. I am not sure that such is available in Go. In Go, with slices, once the backing array has been allocated, I don’t think you can deallocate some at the end of it. But I might be wrong. There is a difference in Go’s slices between length and capacity. Length is the number of elements in the slice, and capacity is the number of elements that can fit in the backing array (so len <= cap).
- tomohawk 3y ago
  Yes. You can make a slice with zero length but the required capacity and append to it as you go. You can also make a slice of the estimated length and then reslice to the actual length. arr := make([]uint64, estimatedLength) ... arr = arr[:actualLength]
  - shakow 3y ago
    This would reallocate, wouldn't it?
    - orbz 3y ago
      If you were using append, then yes. Minor nit: when allocating with length (make(type, len)), you’ll get a slice with zero values for n elements. If you use make(type, len, capacity), then it would only reallocate if your estimated size was under the actual size. Also I believe that re-slicing would still use the same underlying array, so it would set the length but still keep the capacity. You’d have to create a new slice of actual capacity and copy to it.
    - tomohawk 3y ago
      Neither approach will reallocate. In the append case, since the underlying slice has capacity, then each append will just extend the length. If estimated length was too small, then reallocation would occur. In the reslice case, the new slice is a value type that points to the original underlying memory, with a length that is shorter. So no reallocation.
- foldr 3y ago
  That can do almost anything (including reallocating), so you can’t really rely on it: “Requests the container to reduce its capacity to fit its size. “The request is non-binding, and the container implementation is free to optimize otherwise and leave the vector with a capacity greater than its size. “This may cause a reallocation, but has no effect on the vector size and cannot alter its elements.”
LordHeini 3y ago
The same would be true for the initial map: Replacing encountered := map[uint64]bool{} with encountered := make(map[uint64]bool, len(elements)) Should be faster. Golang Hashmaps initially have one bucket with a size of 8. If more elements are added new buckets are created. So giving a hint to initialize a correct number of things should always be faster.

cyber_kinetist 3y ago

In C++'s STL you can reserve() a specific capacity for the std::vector to use, and at the end of your operation you can trim off the remaining memory using shrink_to_fit(): std::vector<int> elems; elems.reserve(max_bound_num_of_elems); // do some push_back()'s elems.shrink_to_fit(); Is there anything similar in Go?

avg_dev 3y ago
Interesting idea. I am not sure that such is available in Go. In Go, with slices, once the backing array has been allocated, I don’t think you can deallocate some at the end of it. But I might be wrong. There is a difference in Go’s slices between length and capacity. Length is the number of elements in the slice, and capacity is the number of elements that can fit in the backing array (so len <= cap).
tomohawk 3y ago
Yes. You can make a slice with zero length but the required capacity and append to it as you go. You can also make a slice of the estimated length and then reslice to the actual length. arr := make([]uint64, estimatedLength) ... arr = arr[:actualLength]
- shakow 3y ago
  This would reallocate, wouldn't it?
  - orbz 3y ago
    If you were using append, then yes. Minor nit: when allocating with length (make(type, len)), you’ll get a slice with zero values for n elements. If you use make(type, len, capacity), then it would only reallocate if your estimated size was under the actual size. Also I believe that re-slicing would still use the same underlying array, so it would set the length but still keep the capacity. You’d have to create a new slice of actual capacity and copy to it.
  - tomohawk 3y ago
    Neither approach will reallocate. In the append case, since the underlying slice has capacity, then each append will just extend the length. If estimated length was too small, then reallocation would occur. In the reslice case, the new slice is a value type that points to the original underlying memory, with a length that is shorter. So no reallocation.
foldr 3y ago
That can do almost anything (including reallocating), so you can’t really rely on it: “Requests the container to reduce its capacity to fit its size. “The request is non-binding, and the container implementation is free to optimize otherwise and leave the vector with a capacity greater than its size. “This may cause a reallocation, but has no effect on the vector size and cannot alter its elements.”

LordHeini 3y ago

The same would be true for the initial map: Replacing encountered := map[uint64]bool{} with encountered := make(map[uint64]bool, len(elements)) Should be faster. Golang Hashmaps initially have one bucket with a size of 8. If more elements are added new buckets are created. So giving a hint to initialize a correct number of things should always be faster.