Hacker News Reader

Comment by avg_dev | Hacker News Reader

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.

View on HN

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?

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).

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]

This would reallocate, wouldn't it?

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.

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.

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.”

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.

Reply on news.ycombinator.com