10 ms·

How the Go runtime implements maps efficiently without generics

197 points by kjeetgill 8y ago

saagarjha 8y ago
> Each different map are different types. For N map types in your source, you will have N copies of the map code in your binary. Is this necessarily true? IIRC the compiler will roll identical functions into one if it detects that they have the same body (instructions wise).
- initium 8y ago
  Won't the read/written values to the data structure depend on different constant values (data size) in the different functions, making it unfoldable?
  - saagarjha 8y ago
    Ok, here's a weaker question: do instantiating an std::unordered_map<int, int * > and std::unordered_map<int, long * > cause two copies of the template to appear? Yes, I know that the functions must both appear so that they can be called–but do the function bodies get duplicated (as opposed to one "function" just falling through into the shared implementation).
    - iainmerrick 8y ago
      I haven’t checked but I wouldn’t be surprised if they are duplicated. (Edit to add: if this done, it’ll be part of the link-time optimization step, which I think is relatively new in all the major C++ compilers.) If you include debugging symbols, there will probably be multiple copies of the duplicated code just because it has different names. You certainly should be able to merge duplicated functions after stripping symbols but I don’t know if that’s a standard thing. I’ve definitely been disappointed in the past by the performance of “dead code stripping” optimization. It’s not quite as trivial a problem as it sounds because when you have groups of functions that call each other, you need to unify two graphs rather than just look for individual identical blobs. The obvious implementation (multiple passes looking for identical leaf functions) is slow and will miss some cases.
      - jcelerier 8y ago
        > which I think is relatively new in all the major C++ compilers. LTO has been available in gcc since 2009 and even longer in clang AFAIK. MSVC had LTO for... I don't know but googling a bit shows that visual studio 2005 supports /GL.
        iainmerrick 8y ago
        Yeah, sorry, I should have clarified “relatively recent” as meaning the last 10 years or so. That’s recent for C++! :) This stuff is being actively worked on so I don’t know if merging identical template instantiations is a thing yet. Any idea?
        jcelerier 8y ago
        MSVC has /OPT:ICF which does this. GCC has -fipa-icf, and the GNU Gold linker has --icf={safe,all} options (since it's operating on ASM it needn't be at the compiler level). In both cases it does not only work with templates, but with any kind of function. However if you use --icf=all, some subtle bugs can appear since function pointers that would compare different in a default build would now compare equal. I have never been bitten by those.
        iainmerrick 8y ago
        Cool! I’ll give those a try.
      - ebikelaw 8y ago
        Debug symbols don’t inhibit identical code folding. What you get is one copy of the function and one arbitrary file/line entry which makes it look like your program makes impossible function calls, if you happen to walk the stack. This can easily be seen in a C++ program with lots of Protocol Buffers because protobuf generated code has lots of identical small functions.
    - jmgao 8y ago
      There's an optimization that targets specifically this case: identical code folding. It's not safe in general, because the standard requires that the different versions must have different addresses, but if the compiler can prove that at least one of the functions doesn't have its address taken (or if the user passes in a flag saying "no, I don't care about that bit of the standard"), they can be merged.
      - leni536 8y ago
        Isn't it trivial to satisfy the standard by making one of the functions to use a trivial indirection? Or just prepend the function body with a nop and one of the functions point there. I am curious which part of the standard specifically disallows aliasing function pointers though. I guess it's only a problem for static member functions that have the same signature for both instantiations, since only these can have the same type. Edit: Actually is it the opposite? Aliasing is allowed for pointers of the same type, the problem would be the aliasing of function pointers of different type. Then again, I think the nop solution should work.
  - fnord123 8y ago
    Generally you would have a different implementation for each struct you use as a key. And this is a template argument so this would certainly get in the way of folding.
- teraflop 8y ago
  Which do you mean by "the compiler"? I'm pretty sure the Go compiler doesn't have a feature like that.
  - saagarjha 8y ago
    This was referencing templated maps, so your favorite optimizing C++ compiler.
    - mhh__ 8y ago
      Or most optimizing compilers written after the mid 80s? (Looking to be corrected, not sure)
  - mhh__ 8y ago
    It's worth discussing: Just because "the" Go compiler doesn't implement it now doesn't mean a Go compiler won't in future
- Someone 8y ago
  Not necessarily, but it takes extra work to make that happen (and it’s the linker that does it, not the compiler. See for example https://ai.google/research/pubs/pub36912 https://ai.google/research/pubs/pub36912).
alpb 8y ago
(This is a bit off-topic, but I couldn't help it.) I noticed the article refers to "hashmap" as a data structure. Such as this statement: > Go maps are hashmaps I think instead of hashmap, this article could use "hash table", which is the actual data structure. The term hashmap sounds almost Java-specific to me (but I understand it helps distinguish when you have both TreeMap and HashMap in a language, like Java). This is a cool article regardless, giving a sneak peek into the internals of Go map type.
- kaoD 8y ago
  Didn't sound that Java-specific to me: https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm... http://hackage.haskell.org/package/hashmap-1.3.3/docs/Data-HashMap.html http://hackage.haskell.org/package/hashmap-1.3.3/docs/Data-H... https://stdlib.ponylang.org/collections-HashMap/ https://stdlib.ponylang.org/collections-HashMap/ https://api.dartlang.org/stable/1.24.3/dart-collection/HashMap-class.html https://api.dartlang.org/stable/1.24.3/dart-collection/HashM... https://pocoproject.org/docs/Poco.HashMap.html https://pocoproject.org/docs/Poco.HashMap.html For me, HashMap is an abstract data type that adheres to the Map interface and is implemented with (i.e. has the performance characteristics of) a hash table. It's a subset of Map, hence the "go's maps are hashmaps" remark. HashSet is often implemented with hash tables too. I guess the difference is ADT vs data structure (and I see your point there), not Java-specificity.
- deleted 8y ago
  [deleted]
skybrian 8y ago
The claim is that Go maps are "very fast" but that's relative to what you're trying to do. If you're writing an interpreter loop, you want to avoid maps as much as you can and use arrays instead.
- sacado2 8y ago
  Indeed. Go maps are slow as hell. Everytime I need them in a tight loop, I have to make an ad-hoc equivalent with slices, if at all possible.
  - _old_dude_ 8y ago
    I believe it's because map access are not inlinined in Go. Swift uses a similar strategy as Go to implement dictionary (a runtime data structure that describe data access is sent as a supplementary parameter) but the backend of Swift is able to inline most of the calls. So at some point in the future, Go maps may be faster.
Animats 8y ago
Go hashmaps are generics, or at least parameterized types. You can't create new parameterized types in Go, but you get maps and channels built in.
- boomlinde 8y ago
  Don't forget slices and arrays
- masklinn 8y ago
  and arrays and slices and pointers. > You can't create new parameterized types in Go Or create functions on parameterized types (without providing concrete type parameters), which is possibly a bigger annoyance than the other one: slices are a thing, but you can't operate on arbitrary slices without reflection. As well as generic types being restricted to builtins, generic functions (e.g. close, copy, len) also are.
  - frou_dh 8y ago
    We're provided with some nice fake type signatures for such builtin functions in the godoc: https://golang.org/pkg/builtin/#copy https://golang.org/pkg/builtin/#copy https://golang.org/pkg/builtin/#Type https://golang.org/pkg/builtin/#Type
    - vorg 8y ago
      If Go 2 is bringing us generics, then couldn't that `builtin` package provide real type signatures for the builtin functions instead of fake ones? Instead of func delete(m map[Type]Type1, key Type) it could have func Delete(type Type, Type1 somecontract) (m map[Type]Type1, key Type) in there, and a program compiled with Go 2 would have an implied instance of func delete = builtin.Delete(T, U) in its global namespace for every map with a `delete` used somewhere in the code.
  - mikekchar 8y ago
    Yeah, for me this is the big problem. For example, I once built a generic flow based library in Go for work (Go was not my choice, and while I like Go it was not really the best choice for this library). The idea is to have a pipeline of go routines where data flows from one stage in the pipeline to the next. Channels and go routines are awesome for this, but setting up all the types for the channels based on the types in the functions being run by the go routines was quite difficult. I had to do it all by reflection and the code was really complicated. With generics, it would have been trivial. The proposal in the 2.0 spec looks promising and I'm looking forward to hopefully being able to play with an implementation sometime.
di4na 8y ago
So basically they invented a runtime type system. Again.
- lifthrasiir 8y ago
  Yeah, a callback approach like this is actually one of common strategies for data structures implemented in C. Others include a requirement that both the key and value should be byte sequences or equivalent (you can always `memcpy` primitives from/to byte sequences).
Sinidir 8y ago
I really don't understand why go doesn't have generics. Shouldn't it be even easier because go has no inheritance? So the problem of covariance and contravariance goes away. Seems really strange.
- sgtcodfish 8y ago
  There are proposals to add generics soon: https://go.googlesource.com/proposal/+/master/design/go2draft-generics-overview.md https://go.googlesource.com/proposal/+/master/design/go2draf... It's not a question of whether or not it's easy or hard; it's definitely technically doable. It's a question whether or not it's desirable. I think the consensus is shifting decisively to saying that it _is_ desirable. The question then becomes how you can assert concepts on a type at compile time. E.g. for a function add(a T, b T) and a type T, how do we assert that a + b is a valid statement? The draft design shows one approach to this.
  - josteink 8y ago
    > It's not a question of whether or not it's easy or hard; it's definitely technically doable. It's a question whether or not it's desirable. And everyone not trying to make excuses for the Go-team knows what the one and only answer to that question is.
- chombier 8y ago
  The current generics proposal includes some form of ad-hoc polymorphism (overloading) on top of standard parametric polymorphism, which complicates things quite a lot. Also, choosing which compilation strategy to use has a big impact on the compiler architecture (monomorphization? boxing? a mix of both?)
- emmelaich 8y ago
  I think the article answers that. There's a whole bunch of design and implementation decisions that would be very different and more complex with generics.
  - 8y ago
royjacobs 8y ago
How can the author claim that "Just like C++ and just like Java, Go’s hashmap written in Go" (sic) when there is clearly a whole bunch of compiler magic going on that goes beyond plain Go?
- usrusr 8y ago
  The implementation is in Go, compiled from the source of the runtime library when that was built, but the syntactic desugaring of your map-accessing code is happening in the compiler.
  - royjacobs 8y ago
    That's still a bunch of magic that C++ and Java don't really get to use though, isn't it? Or would you consider this to be on the same level of adding opcodes to the JVM?
    - usrusr 8y ago
      Sure, the desugaring is special treatment, compiler "magic" that is not available at all to other libraries that might like to similarly hook into the map syntax. I was just trying to explain how this does not have to conflict with the claim that the map implementation (the runtime library functions that are called by the desugared version) is plain, regular Go. You could rewrite the map implementation, you just would not get the nice syntax. Compared to Java, it's somewhere in the middle between the regular, entirely "un-magic" implementation of maps and the deeply built in nature of the array primitive, which is not only special at compile time (like Go maps) but also at runtime.
    - jerf 8y ago
      I'd consider it fairly similar to the distinction between Java and the JVM, yes, in that the JVM technically has more power than the Java language exposes. There's multiple levels, with different powers. You're not going to be able to draw a sharp line here where Go is somehow on one side of it and most other languages aren't. In a sense the entire point of a "language" in the first place is to provide various bits of "magic" to make your life easier. For instance, you can't implement your own exceptions system, because the compiler hooks in at a deeper level than you can get to. (In both cases you can probably do it via what are technically platform-specific hacks, but I wouldn't say that you've implemented it in the language.) The only language with "no magic" is pure assembler, with either no macros or at least no predefined macros.
beagle3 8y ago
The dict/hash implementation in K (since 1993 or so ..) is much simpler, cleaner, takes much less memory and often faster - though speed depends on the actual use case more than anything. The idea is that instead of the hash map being a list of <key,value> items indexed by key, there's a vector of keys, a vector of values (with matching indices), and a search index (usually a hash, but could be a tree) that maps a key to the index; note that the search index does not need a copy of the key even if it is inexact because one can always refer to the keys vector. The cons: * You can't pass a single <key,value> object without building one * You may incur twice or thrice cache loads (one for index, one for key, and if correct, one for value) whereas on a conventional <key, value> list, they are likely to be on the same cache line. * (edit: added based on aidenn0 comment, see discussion below): Removal is generally O(n) unless you are willing to give up one of the pros; but even if you give some up, it's still usually more featureful than commonly used implementations. The pros: * Insertion order is preserved - OrderedDict for free! * Getting the list of keys, or the list of values, e.g. python's keys() and values() methods, are O(1) and allocation free * Applying a function to each item needs to allocate a new value vector, but can reuse the key vector -- and if the function doesn't need the key, you don't actually have to fetch it - e.g., to normalize a map so values sum to 1, you can do: whole = sum(mymap.values()) normalized = apply_values(mymap, lambda x: x/whole) And get a normalized map with the same keys and literally the minimal number of allocations and operations possible for a concrete datatype * Specialization is by the key type, regardless of the value type - which means that a few efficient implementations (for ints, longs, floats, strings, symbols) manage to often provide C++ speeds for an interpreted language. * Memory packing is about as tight as it can be. Your key is a double, and your value is one byte? You pay exactly 9 bytes per record + index size (which, e.g. for a 30,000 record map, takes two bytes per hash slot, or ~128KB for a 64K slot table). This is true whether you are running on an 16-bit, 32-bit, 64-bit or 128-bit processor. * It is straightforward and natural to implement with almost no pointers involved, meaning that it is trivial to share memory among processes (at least for read only accesses) and to use with memory-mapped storage -- to the point that you can have an 8GB dictionary which is instantly mmap()/MapViewOfFile()d into existence, and is no different in any way than any other one - you pay disk access for the records you use, but enjoy OS cache/page management, with cache shared between processes and between subsequent runs -- no need to special case this dictionary just because it's big. The Python 3.6 implementation switched from a hash-indexed <hash,key,value> vector to a <hash -> order> and ordered <key,value> vector, and saw speed improvements and memory use reductions. Due to Python's legacy and structure, they could not have gone farther on the K way, except for CPU cache effects. Having used APL and K for over 15 years now, I find it weird seeing the same Smalltalk-inspired hash table structure come up in every single new runtime and language implementation.
comesee 8y ago
The nice thing about C++ and templates is that you can implement a scheme exactly like this without special help from the compiler :)
kjeetgill 8y ago
If you're familiar with how go does interfaces it's kind-of reminiscent of how they do maps. A variable that is of an interface type has 2 parts: And pointer to the Itable mapping functions in the interface to their implementations in hard type, and a pointer to data of that instance of the hard type. The creation and assignment of that Itable is invisible at user level and baked in at compile time (with reasonable but irritating consequences like type nils). Similar to an Itable, they're injecting a type descriptor table (maptype) in the function parameter that can get things like the size of a key or value, alignment, kind, etc. I had two questions: A) why can't hmap struct keep a pointer to the maptype? it shouldn't vary per callsite right? B) does this count as generics? It's strange. Like a half erased, half reified generics. It seems erased in that the hmap itself doesn't carry the type information but it's reified at each callsite?
- ainar-g 8y ago
  >B) does this count as generics? I think "generic programming" is more about generic algorithms than it is about data structures. Because without generic functions, generic data structures are less useful. Can you create a new map type in Go? Yes. Can you create a function that works on any map? Only with reflection, which you should consider your last measure.
  - jimmy1 8y ago
    > Can you create a function that works on any map? Only with reflection Most experienced go developers at this point would template the function and generate it for any type they might need it for, before they reach for reflection.
    - ainar-g 8y ago
      Depends on the environment, I guess. I've been programming Go professionally for over 3 years, and I've never used such "templates" for generic types. As I've said in another thread, I've had a need for sum types much more often than a need for generics.
    - 8y ago
yani 8y ago
Everytime I see an article from Dave Cheney I am wonder why is it so popular?
blixt 8y ago
The article explains how you can get arbitrarily typed values out of the map using unsafe pointers, but it never really explains how they're put in. The insert example in the article uses a function that doesn't actually exist in the runtime package, and it implies you can just give it a plain value as input: m["key"] = 9001 → runtime.mapinsert(m, ”key", 9001) I would assume that is only possible if the 9001 value can make its way through as an actual value on the stack, not as a pointer. Here's what I would expect to actually happen: ptr := runtime.mapallocate(m, "key") // unsafe.Pointer *(*int)(ptr) = 9001 // Is there a non-typed way to do this? While this is a good intro to hash tables in general, the Go specific part feels a little bit lacking.
- benmmurphy 8y ago
  my guess is it allocates the value onto the stack and then inside mapinsert it knows to memcpy the value into the bucket because it knows the size of the value. like tmp = 9001 runtime.mapinsert(m, "key", &tmp)
  - blixt 8y ago
    Yup, that looks simpler than what I put in my comment. Do you know where the actual implementation is so we can confirm?
    - benmmurphy 8y ago
      Nah. I just decompiled m["foo"] = 5 and it is closer to what is in your comment than mine. so for this it does: push addr of string push $3 call runtime.mapassign_faststr mov $5, 0($ax) test.go:4 0x104b4cb 488d05f9c20100 LEAQ go.string.*+91(SB), AX test.go:4 0x104b4d2 4889442410 MOVQ AX, 0x10(SP) test.go:4 0x104b4d7 48c744241803000000 MOVQ $0x3, 0x18(SP) test.go:4 0x104b4e0 e8cbc6fbff CALL runtime.mapassign_faststr(SB) test.go:4 0x104b4e5 488b442420 MOVQ 0x20(SP), AX test.go:4 0x104b4ea 48c70005000000 MOVQ $0x5, 0(AX) so its kind of like: ptr = runtime.mapassign_faststr("foo") *ptr = 5 EDIT: oops confused 0x3 with the value the first time around
Matthias247 8y ago
I think there's some contradiction between those statements: > Rather than having, as C++ has, a complete map implementation for each unique map declaration, the Go compiler creates a maptype during compilation and uses that value when calling into the runtime’s map functions. > Does the compiler use code generation? > No, there is only one copy of the map implementation in a Go binary The compiler certainly does code generation, as outlined in the article. It just minimizes the amount of generated code, and uses explicit non-generic functions on some higher layers. One can do the same in a generic C++ map implementation too, by delegating some of the logic into non-generic functions. It's a thing that is commonly done in manually size-optimized code. One could also hope that the compiler automatically detects some of the duplicated code between template instances, and deduplicates it.

197 points by kjeetgill 8y ago

> Each different map are different types. For N map types in your source, you will have N copies of the map code in your binary. Is this necessarily true? IIRC the compiler will roll identical functions into one if it detects that they have the same body (instructions wise).

initium 8y ago
Won't the read/written values to the data structure depend on different constant values (data size) in the different functions, making it unfoldable?
- saagarjha 8y ago
  Ok, here's a weaker question: do instantiating an std::unordered_map<int, int * > and std::unordered_map<int, long * > cause two copies of the template to appear? Yes, I know that the functions must both appear so that they can be called–but do the function bodies get duplicated (as opposed to one "function" just falling through into the shared implementation).
  - iainmerrick 8y ago
    I haven’t checked but I wouldn’t be surprised if they are duplicated. (Edit to add: if this done, it’ll be part of the link-time optimization step, which I think is relatively new in all the major C++ compilers.) If you include debugging symbols, there will probably be multiple copies of the duplicated code just because it has different names. You certainly should be able to merge duplicated functions after stripping symbols but I don’t know if that’s a standard thing. I’ve definitely been disappointed in the past by the performance of “dead code stripping” optimization. It’s not quite as trivial a problem as it sounds because when you have groups of functions that call each other, you need to unify two graphs rather than just look for individual identical blobs. The obvious implementation (multiple passes looking for identical leaf functions) is slow and will miss some cases.
    - jcelerier 8y ago
      > which I think is relatively new in all the major C++ compilers. LTO has been available in gcc since 2009 and even longer in clang AFAIK. MSVC had LTO for... I don't know but googling a bit shows that visual studio 2005 supports /GL.
      - iainmerrick 8y ago
        Yeah, sorry, I should have clarified “relatively recent” as meaning the last 10 years or so. That’s recent for C++! :) This stuff is being actively worked on so I don’t know if merging identical template instantiations is a thing yet. Any idea?
        jcelerier 8y ago
        MSVC has /OPT:ICF which does this. GCC has -fipa-icf, and the GNU Gold linker has --icf={safe,all} options (since it's operating on ASM it needn't be at the compiler level). In both cases it does not only work with templates, but with any kind of function. However if you use --icf=all, some subtle bugs can appear since function pointers that would compare different in a default build would now compare equal. I have never been bitten by those.
        iainmerrick 8y ago
        Cool! I’ll give those a try.
    - ebikelaw 8y ago
      Debug symbols don’t inhibit identical code folding. What you get is one copy of the function and one arbitrary file/line entry which makes it look like your program makes impossible function calls, if you happen to walk the stack. This can easily be seen in a C++ program with lots of Protocol Buffers because protobuf generated code has lots of identical small functions.
  - jmgao 8y ago
    There's an optimization that targets specifically this case: identical code folding. It's not safe in general, because the standard requires that the different versions must have different addresses, but if the compiler can prove that at least one of the functions doesn't have its address taken (or if the user passes in a flag saying "no, I don't care about that bit of the standard"), they can be merged.
    - leni536 8y ago
      Isn't it trivial to satisfy the standard by making one of the functions to use a trivial indirection? Or just prepend the function body with a nop and one of the functions point there. I am curious which part of the standard specifically disallows aliasing function pointers though. I guess it's only a problem for static member functions that have the same signature for both instantiations, since only these can have the same type. Edit: Actually is it the opposite? Aliasing is allowed for pointers of the same type, the problem would be the aliasing of function pointers of different type. Then again, I think the nop solution should work.
- fnord123 8y ago
  Generally you would have a different implementation for each struct you use as a key. And this is a template argument so this would certainly get in the way of folding.
teraflop 8y ago
Which do you mean by "the compiler"? I'm pretty sure the Go compiler doesn't have a feature like that.
- saagarjha 8y ago
  This was referencing templated maps, so your favorite optimizing C++ compiler.
  - mhh__ 8y ago
    Or most optimizing compilers written after the mid 80s? (Looking to be corrected, not sure)
- mhh__ 8y ago
  It's worth discussing: Just because "the" Go compiler doesn't implement it now doesn't mean a Go compiler won't in future
Someone 8y ago
Not necessarily, but it takes extra work to make that happen (and it’s the linker that does it, not the compiler. See for example https://ai.google/research/pubs/pub36912 https://ai.google/research/pubs/pub36912).

alpb 8y ago

(This is a bit off-topic, but I couldn't help it.) I noticed the article refers to "hashmap" as a data structure. Such as this statement: > Go maps are hashmaps I think instead of hashmap, this article could use "hash table", which is the actual data structure. The term hashmap sounds almost Java-specific to me (but I understand it helps distinguish when you have both TreeMap and HashMap in a language, like Java). This is a cool article regardless, giving a sneak peek into the internals of Go map type.

kaoD 8y ago
Didn't sound that Java-specific to me: https://doc.rust-lang.org/std/collections/struct.HashMap.html https://doc.rust-lang.org/std/collections/struct.HashMap.htm... http://hackage.haskell.org/package/hashmap-1.3.3/docs/Data-HashMap.html http://hackage.haskell.org/package/hashmap-1.3.3/docs/Data-H... https://stdlib.ponylang.org/collections-HashMap/ https://stdlib.ponylang.org/collections-HashMap/ https://api.dartlang.org/stable/1.24.3/dart-collection/HashMap-class.html https://api.dartlang.org/stable/1.24.3/dart-collection/HashM... https://pocoproject.org/docs/Poco.HashMap.html https://pocoproject.org/docs/Poco.HashMap.html For me, HashMap is an abstract data type that adheres to the Map interface and is implemented with (i.e. has the performance characteristics of) a hash table. It's a subset of Map, hence the "go's maps are hashmaps" remark. HashSet is often implemented with hash tables too. I guess the difference is ADT vs data structure (and I see your point there), not Java-specificity.
deleted 8y ago
[deleted]

skybrian 8y ago

The claim is that Go maps are "very fast" but that's relative to what you're trying to do. If you're writing an interpreter loop, you want to avoid maps as much as you can and use arrays instead.

sacado2 8y ago
Indeed. Go maps are slow as hell. Everytime I need them in a tight loop, I have to make an ad-hoc equivalent with slices, if at all possible.
- _old_dude_ 8y ago
  I believe it's because map access are not inlinined in Go. Swift uses a similar strategy as Go to implement dictionary (a runtime data structure that describe data access is sent as a supplementary parameter) but the backend of Swift is able to inline most of the calls. So at some point in the future, Go maps may be faster.

Animats 8y ago

Go hashmaps are generics, or at least parameterized types. You can't create new parameterized types in Go, but you get maps and channels built in.

boomlinde 8y ago
Don't forget slices and arrays
masklinn 8y ago
and arrays and slices and pointers. > You can't create new parameterized types in Go Or create functions on parameterized types (without providing concrete type parameters), which is possibly a bigger annoyance than the other one: slices are a thing, but you can't operate on arbitrary slices without reflection. As well as generic types being restricted to builtins, generic functions (e.g. close, copy, len) also are.
- frou_dh 8y ago
  We're provided with some nice fake type signatures for such builtin functions in the godoc: https://golang.org/pkg/builtin/#copy https://golang.org/pkg/builtin/#copy https://golang.org/pkg/builtin/#Type https://golang.org/pkg/builtin/#Type
  - vorg 8y ago
    If Go 2 is bringing us generics, then couldn't that `builtin` package provide real type signatures for the builtin functions instead of fake ones? Instead of func delete(m map[Type]Type1, key Type) it could have func Delete(type Type, Type1 somecontract) (m map[Type]Type1, key Type) in there, and a program compiled with Go 2 would have an implied instance of func delete = builtin.Delete(T, U) in its global namespace for every map with a `delete` used somewhere in the code.
- mikekchar 8y ago
  Yeah, for me this is the big problem. For example, I once built a generic flow based library in Go for work (Go was not my choice, and while I like Go it was not really the best choice for this library). The idea is to have a pipeline of go routines where data flows from one stage in the pipeline to the next. Channels and go routines are awesome for this, but setting up all the types for the channels based on the types in the functions being run by the go routines was quite difficult. I had to do it all by reflection and the code was really complicated. With generics, it would have been trivial. The proposal in the 2.0 spec looks promising and I'm looking forward to hopefully being able to play with an implementation sometime.

di4na 8y ago

So basically they invented a runtime type system. Again.

lifthrasiir 8y ago
Yeah, a callback approach like this is actually one of common strategies for data structures implemented in C. Others include a requirement that both the key and value should be byte sequences or equivalent (you can always `memcpy` primitives from/to byte sequences).

Sinidir 8y ago

I really don't understand why go doesn't have generics. Shouldn't it be even easier because go has no inheritance? So the problem of covariance and contravariance goes away. Seems really strange.

sgtcodfish 8y ago
There are proposals to add generics soon: https://go.googlesource.com/proposal/+/master/design/go2draft-generics-overview.md https://go.googlesource.com/proposal/+/master/design/go2draf... It's not a question of whether or not it's easy or hard; it's definitely technically doable. It's a question whether or not it's desirable. I think the consensus is shifting decisively to saying that it _is_ desirable. The question then becomes how you can assert concepts on a type at compile time. E.g. for a function add(a T, b T) and a type T, how do we assert that a + b is a valid statement? The draft design shows one approach to this.
- josteink 8y ago
  > It's not a question of whether or not it's easy or hard; it's definitely technically doable. It's a question whether or not it's desirable. And everyone not trying to make excuses for the Go-team knows what the one and only answer to that question is.
chombier 8y ago
The current generics proposal includes some form of ad-hoc polymorphism (overloading) on top of standard parametric polymorphism, which complicates things quite a lot. Also, choosing which compilation strategy to use has a big impact on the compiler architecture (monomorphization? boxing? a mix of both?)
emmelaich 8y ago
I think the article answers that. There's a whole bunch of design and implementation decisions that would be very different and more complex with generics.
- 8y ago

royjacobs 8y ago

How can the author claim that "Just like C++ and just like Java, Go’s hashmap written in Go" (sic) when there is clearly a whole bunch of compiler magic going on that goes beyond plain Go?

usrusr 8y ago
The implementation is in Go, compiled from the source of the runtime library when that was built, but the syntactic desugaring of your map-accessing code is happening in the compiler.
- royjacobs 8y ago
  That's still a bunch of magic that C++ and Java don't really get to use though, isn't it? Or would you consider this to be on the same level of adding opcodes to the JVM?
  - usrusr 8y ago
    Sure, the desugaring is special treatment, compiler "magic" that is not available at all to other libraries that might like to similarly hook into the map syntax. I was just trying to explain how this does not have to conflict with the claim that the map implementation (the runtime library functions that are called by the desugared version) is plain, regular Go. You could rewrite the map implementation, you just would not get the nice syntax. Compared to Java, it's somewhere in the middle between the regular, entirely "un-magic" implementation of maps and the deeply built in nature of the array primitive, which is not only special at compile time (like Go maps) but also at runtime.
  - jerf 8y ago
    I'd consider it fairly similar to the distinction between Java and the JVM, yes, in that the JVM technically has more power than the Java language exposes. There's multiple levels, with different powers. You're not going to be able to draw a sharp line here where Go is somehow on one side of it and most other languages aren't. In a sense the entire point of a "language" in the first place is to provide various bits of "magic" to make your life easier. For instance, you can't implement your own exceptions system, because the compiler hooks in at a deeper level than you can get to. (In both cases you can probably do it via what are technically platform-specific hacks, but I wouldn't say that you've implemented it in the language.) The only language with "no magic" is pure assembler, with either no macros or at least no predefined macros.

beagle3 8y ago

The dict/hash implementation in K (since 1993 or so ..) is much simpler, cleaner, takes much less memory and often faster - though speed depends on the actual use case more than anything. The idea is that instead of the hash map being a list of <key,value> items indexed by key, there's a vector of keys, a vector of values (with matching indices), and a search index (usually a hash, but could be a tree) that maps a key to the index; note that the search index does not need a copy of the key even if it is inexact because one can always refer to the keys vector. The cons: * You can't pass a single <key,value> object without building one * You may incur twice or thrice cache loads (one for index, one for key, and if correct, one for value) whereas on a conventional <key, value> list, they are likely to be on the same cache line. * (edit: added based on aidenn0 comment, see discussion below): Removal is generally O(n) unless you are willing to give up one of the pros; but even if you give some up, it's still usually more featureful than commonly used implementations. The pros: * Insertion order is preserved - OrderedDict for free! * Getting the list of keys, or the list of values, e.g. python's keys() and values() methods, are O(1) and allocation free * Applying a function to each item needs to allocate a new value vector, but can reuse the key vector -- and if the function doesn't need the key, you don't actually have to fetch it - e.g., to normalize a map so values sum to 1, you can do: whole = sum(mymap.values()) normalized = apply_values(mymap, lambda x: x/whole) And get a normalized map with the same keys and literally the minimal number of allocations and operations possible for a concrete datatype * Specialization is by the key type, regardless of the value type - which means that a few efficient implementations (for ints, longs, floats, strings, symbols) manage to often provide C++ speeds for an interpreted language. * Memory packing is about as tight as it can be. Your key is a double, and your value is one byte? You pay exactly 9 bytes per record + index size (which, e.g. for a 30,000 record map, takes two bytes per hash slot, or ~128KB for a 64K slot table). This is true whether you are running on an 16-bit, 32-bit, 64-bit or 128-bit processor. * It is straightforward and natural to implement with almost no pointers involved, meaning that it is trivial to share memory among processes (at least for read only accesses) and to use with memory-mapped storage -- to the point that you can have an 8GB dictionary which is instantly mmap()/MapViewOfFile()d into existence, and is no different in any way than any other one - you pay disk access for the records you use, but enjoy OS cache/page management, with cache shared between processes and between subsequent runs -- no need to special case this dictionary just because it's big. The Python 3.6 implementation switched from a hash-indexed <hash,key,value> vector to a <hash -> order> and ordered <key,value> vector, and saw speed improvements and memory use reductions. Due to Python's legacy and structure, they could not have gone farther on the K way, except for CPU cache effects. Having used APL and K for over 15 years now, I find it weird seeing the same Smalltalk-inspired hash table structure come up in every single new runtime and language implementation.

comesee 8y ago

The nice thing about C++ and templates is that you can implement a scheme exactly like this without special help from the compiler :)

kjeetgill 8y ago

If you're familiar with how go does interfaces it's kind-of reminiscent of how they do maps. A variable that is of an interface type has 2 parts: And pointer to the Itable mapping functions in the interface to their implementations in hard type, and a pointer to data of that instance of the hard type. The creation and assignment of that Itable is invisible at user level and baked in at compile time (with reasonable but irritating consequences like type nils). Similar to an Itable, they're injecting a type descriptor table (maptype) in the function parameter that can get things like the size of a key or value, alignment, kind, etc. I had two questions: A) why can't hmap struct keep a pointer to the maptype? it shouldn't vary per callsite right? B) does this count as generics? It's strange. Like a half erased, half reified generics. It seems erased in that the hmap itself doesn't carry the type information but it's reified at each callsite?

ainar-g 8y ago
>B) does this count as generics? I think "generic programming" is more about generic algorithms than it is about data structures. Because without generic functions, generic data structures are less useful. Can you create a new map type in Go? Yes. Can you create a function that works on any map? Only with reflection, which you should consider your last measure.
- jimmy1 8y ago
  > Can you create a function that works on any map? Only with reflection Most experienced go developers at this point would template the function and generate it for any type they might need it for, before they reach for reflection.
  - ainar-g 8y ago
    Depends on the environment, I guess. I've been programming Go professionally for over 3 years, and I've never used such "templates" for generic types. As I've said in another thread, I've had a need for sum types much more often than a need for generics.
  - 8y ago

yani 8y ago

Everytime I see an article from Dave Cheney I am wonder why is it so popular?

blixt 8y ago

The article explains how you can get arbitrarily typed values out of the map using unsafe pointers, but it never really explains how they're put in. The insert example in the article uses a function that doesn't actually exist in the runtime package, and it implies you can just give it a plain value as input: m["key"] = 9001 → runtime.mapinsert(m, ”key", 9001) I would assume that is only possible if the 9001 value can make its way through as an actual value on the stack, not as a pointer. Here's what I would expect to actually happen: ptr := runtime.mapallocate(m, "key") // unsafe.Pointer *(*int)(ptr) = 9001 // Is there a non-typed way to do this? While this is a good intro to hash tables in general, the Go specific part feels a little bit lacking.

benmmurphy 8y ago
my guess is it allocates the value onto the stack and then inside mapinsert it knows to memcpy the value into the bucket because it knows the size of the value. like tmp = 9001 runtime.mapinsert(m, "key", &tmp)
- blixt 8y ago
  Yup, that looks simpler than what I put in my comment. Do you know where the actual implementation is so we can confirm?
  - benmmurphy 8y ago
    Nah. I just decompiled m["foo"] = 5 and it is closer to what is in your comment than mine. so for this it does: push addr of string push $3 call runtime.mapassign_faststr mov $5, 0($ax) test.go:4 0x104b4cb 488d05f9c20100 LEAQ go.string.*+91(SB), AX test.go:4 0x104b4d2 4889442410 MOVQ AX, 0x10(SP) test.go:4 0x104b4d7 48c744241803000000 MOVQ $0x3, 0x18(SP) test.go:4 0x104b4e0 e8cbc6fbff CALL runtime.mapassign_faststr(SB) test.go:4 0x104b4e5 488b442420 MOVQ 0x20(SP), AX test.go:4 0x104b4ea 48c70005000000 MOVQ $0x5, 0(AX) so its kind of like: ptr = runtime.mapassign_faststr("foo") *ptr = 5 EDIT: oops confused 0x3 with the value the first time around

Matthias247 8y ago

I think there's some contradiction between those statements: > Rather than having, as C++ has, a complete map implementation for each unique map declaration, the Go compiler creates a maptype during compilation and uses that value when calling into the runtime’s map functions. > Does the compiler use code generation? > No, there is only one copy of the map implementation in a Go binary The compiler certainly does code generation, as outlined in the article. It just minimizes the amount of generated code, and uses explicit non-generic functions on some higher layers. One can do the same in a generic C++ map implementation too, by delegating some of the logic into non-generic functions. It's a thing that is commonly done in manually size-optimized code. One could also hope that the compiler automatically detects some of the duplicated code between template instances, and deduplicates it.