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?
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.
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:
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.
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.
By that definition C89 has generics too (arrays and pointers). The whole point of generics is that they are user definable. Everything else is hairsplitting.
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.
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?
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.
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.
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.
Rob Pike wrote a bit about it in "less is exponentially more". He points out that generics are used by languages that focus on types and that Go focuses on composition and uses interfaces ( and language buildins ) instead of types to solve problems.
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?)
Time and priorities. They didn't have the time until now as their priorities were elsewhere (as they should have been, they were building tools for their own use cases).
You can argue until the heat death of the universe about wether those priorities were chosen wisely, but it's irrelevant now. They built the tools for themselves focusing on what they found to be most important at the time. It's clearly worked out well enough for them and many of us like how Go turned out despite its short comings.
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.
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).
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.
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.
(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.
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.
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:
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.
There is a lot to learn from K, but there are two problems:
1) It is not open source, but a commercial product. Although some source code can be found online, there is no license, so I would not dare using any of it in a free software project.
2) Whitney's code is worth studying. I have spent a lot of time "deciphering" the b interpreter in kparc and it has been a great exercise, but it is not for everybody. Most people will find it unnecessarily obfuscated. It certainly is not obvious for a casual observer.
I wish (1) changed, then we could see annotated versions of the code that made it more palatable to solve (2) too. But according to what I have seen, this is not going to happen.
One wish of mine (because I'm working in a relational/array lang) is find a minimal implementation of K anotated and explained. Like "Let's build a array interpreter" like with http://www.craftinginterpreters.com/.
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).
[+] [-] kjeetgill|7 years ago|reply
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|7 years ago|reply
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.
[+] [-] blixt|7 years ago|reply
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:
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: While this is a good intro to hash tables in general, the Go specific part feels a little bit lacking.[+] [-] benmmurphy|7 years ago|reply
like
[+] [-] Animats|7 years ago|reply
[+] [-] mseepgood|7 years ago|reply
[+] [-] masklinn|7 years ago|reply
> 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.
[+] [-] boomlinde|7 years ago|reply
[+] [-] royjacobs|7 years ago|reply
[+] [-] usrusr|7 years ago|reply
[+] [-] Sinidir|7 years ago|reply
Seems really strange.
[+] [-] sgtcodfish|7 years ago|reply
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.
[+] [-] josefx|7 years ago|reply
[+] [-] chombier|7 years ago|reply
Also, choosing which compilation strategy to use has a big impact on the compiler architecture (monomorphization? boxing? a mix of both?)
[+] [-] bmurphy1976|7 years ago|reply
You can argue until the heat death of the universe about wether those priorities were chosen wisely, but it's irrelevant now. They built the tools for themselves focusing on what they found to be most important at the time. It's clearly worked out well enough for them and many of us like how Go turned out despite its short comings.
[+] [-] emmelaich|7 years ago|reply
[+] [-] di4na|7 years ago|reply
[+] [-] lifthrasiir|7 years ago|reply
[+] [-] Matthias247|7 years ago|reply
> 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.
[+] [-] comesee|7 years ago|reply
[+] [-] skybrian|7 years ago|reply
[+] [-] sacado2|7 years ago|reply
[+] [-] alpb|7 years ago|reply
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|7 years ago|reply
https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
http://hackage.haskell.org/package/hashmap-1.3.3/docs/Data-H...
https://stdlib.ponylang.org/collections-HashMap/
https://api.dartlang.org/stable/1.24.3/dart-collection/HashM...
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.
[+] [-] unknown|7 years ago|reply
[deleted]
[+] [-] beagle3|7 years ago|reply
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:
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.
[+] [-] yiyus|7 years ago|reply
1) It is not open source, but a commercial product. Although some source code can be found online, there is no license, so I would not dare using any of it in a free software project.
2) Whitney's code is worth studying. I have spent a lot of time "deciphering" the b interpreter in kparc and it has been a great exercise, but it is not for everybody. Most people will find it unnecessarily obfuscated. It certainly is not obvious for a casual observer.
I wish (1) changed, then we could see annotated versions of the code that made it more palatable to solve (2) too. But according to what I have seen, this is not going to happen.
[+] [-] mamcx|7 years ago|reply
[+] [-] aidenn0|7 years ago|reply
[+] [-] saagarjha|7 years ago|reply
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|7 years ago|reply
[+] [-] Someone|7 years ago|reply
[+] [-] teraflop|7 years ago|reply
[+] [-] yani|7 years ago|reply