4 ms·

Can someone explain this bit (re: Go implementation) > To reduce the allocations, we’ll use a map[string]*int instead of map[string]int so we only have to allo

Can someone explain this bit (re: Go implementation) > To reduce the allocations, we’ll use a map[string]*int instead of map[string]int so we only have to allocate once per unique word Does the `map[string]int` approach allocate a new integer each time it is incremented?

deleted 6y ago
[deleted]
coder543 6y ago
Yeah. I want to check that locally... I don't feel like that's doing anything useful here. For starters, ints aren't normally "allocated" (in the heap sense). Go is value oriented, not reference oriented. I feel like the bigger change in the code was avoiding the allocation of the string for each word in the source text, and instead passing the byte slice directly to the point where it was used as the map key. Since strings are immutable, when you convert a byte slice to a string, it must be copied into a new immutable backing slice so that no one else can touch it. The exception is that the compiler optimizes map accesses where the key is a string type, but the code is converting a byte slice into a string at the point of using it as a map key. The compiler elides that conversion, making it a no-op, and instead just passes the byte slice in, since the hash map can make a copy of the string if it needs to, but it will otherwise avoid the unnecessary allocation and copying that converting this would otherwise require. I feel like that's where the big difference is. Heap allocating the integers and storing references in the map doesn't feel like it's actually doing anything here, although storing pointer values in maps can be useful in certain scenarios.
cp9 6y ago
https://github.com/golang/go/issues/45021 https://github.com/golang/go/issues/45021
benhoyt 6y ago
No, map[string]int doesn't allocate ints. Why the map[string]*int version is faster is because it avoids a "write" to the map when you're not adding new words -- it can just look up the pointer and increment what it points to. The Go compiler is not smart enough (yet) to optimize the former to avoid a map write. (That's my understanding, anyway.)

deleted 6y ago

[deleted]

coder543 6y ago

Yeah. I want to check that locally... I don't feel like that's doing anything useful here. For starters, ints aren't normally "allocated" (in the heap sense). Go is value oriented, not reference oriented. I feel like the bigger change in the code was avoiding the allocation of the string for each word in the source text, and instead passing the byte slice directly to the point where it was used as the map key. Since strings are immutable, when you convert a byte slice to a string, it must be copied into a new immutable backing slice so that no one else can touch it. The exception is that the compiler optimizes map accesses where the key is a string type, but the code is converting a byte slice into a string at the point of using it as a map key. The compiler elides that conversion, making it a no-op, and instead just passes the byte slice in, since the hash map can make a copy of the string if it needs to, but it will otherwise avoid the unnecessary allocation and copying that converting this would otherwise require. I feel like that's where the big difference is. Heap allocating the integers and storing references in the map doesn't feel like it's actually doing anything here, although storing pointer values in maps can be useful in certain scenarios.

cp9 6y ago

https://github.com/golang/go/issues/45021 https://github.com/golang/go/issues/45021

benhoyt 6y ago

No, map[string]int doesn't allocate ints. Why the map[string]*int version is faster is because it avoids a "write" to the map when you're not adding new words -- it can just look up the pointer and increment what it points to. The Go compiler is not smart enough (yet) to optimize the former to avoid a map write. (That's my understanding, anyway.)