9 ms·
Go map vs C++ maps, they pretty much the same for Go 1.9. In Go, once you instantiate a map with a length, you can avoid GC and memory allocs as it grows. http
by innagadadavida 8y ago
Go map vs C++ maps, they pretty much the same for Go 1.9. In Go, once you instantiate a map with a length, you can avoid GC and memory allocs as it grows.
https://medium.com/@griffinish/c-and-golang-neck-and-neck-on-maps-e7867adfadc6 https://medium.com/@griffinish/c-and-golang-neck-and-neck-on...
- tcbawo 8y agoIf you're going to compare performance of C++ maps, you may want to consider std::unordered_map, which is a hash map implementation vs std::map's red-black tree.
- shaklee3 8y agoNot only consider, but comparing a Go map to C++ absolutely has to do that since go is unordered. A c++ unordered can be significantly faster than ordered in many contexts.
- adev_ 8y agoNot even considering that unordered_map is not the fastest hash map implementation for C++. There is plenty of the flat hash map implementation (swiss tables) around that beats unordered_map by an other factor.... https://abseil.io/blog/20180927-swisstables https://abseil.io/blog/20180927-swisstables
- aaaaaaaaaaab 8y agoDid you read the article? >Then of course I remembered that std::map is a red-black tree, i.e. ordered, whereas the Go map is not. Change out std::map for std::unordered_map and C++ pulled ahead, 20% faster than the Go code.
- yoklov 8y agoEven that's surprising, since std::unordered_map is notoriously slow (and impossible to optimize given weirdly exposed implementation details in it's API)
- innagadadavida 8y agoDid you read the update on Go 1.9? It is on par, I tried the benchmark on my machine why not try it yourself instead of downvoting?
- shaklee3 8y agoYou aren't reading it correctly. The OP was saying it's not fair unless you compare against an unordered map. The update is referring to an ordered map which is much slower than an unordered. The GO math implementation, which is an unordered map, is still significantly slower than the C++ unordered map.
- detaro 8y agoNo, it's fairly clear that the update refers to the unordered maps case.
- innagadadavida 8y agoSo I created a Gist: https://gist.github.com/AshKash/ebf1f70949e76439d6ffed9ccde337be https://gist.github.com/AshKash/ebf1f70949e76439d6ffed9ccde3... upped it to 10M ops and used .reserve to avoid unwanted allocs. Go 1.12 is 2X faster than C++. This was totally unexpected as I feel the basic algorithms are simple and there is not much you can do to make it faster. If you have know what is going on, please share.
- apta 8y agoAnd Java is 2x faster than golang in this benchmark when I ran it. Many benchmarks are to be taken with a grain of salt. golang: 7.76 real 8.67 user 0.08 sys Java: 3.74 real 3.58 user 0.46 sys public class Test { public static void main(String[] args) { final int numOfStrings = 100_000; final int numIters = 1_000; var numStrings = new String[numOfStrings]; for (int i = 0; i < numStrings.length; i++) { numStrings[i] = Integer.toString(i); } for (int i = 0; i < numIters; i++) { var strToInt = new java.util.HashMap<String, Integer>(numOfStrings); for (final var s : numStrings) { strToInt.put(s, s.length()); } } } }
- yoklov 8y agoWhat's happening is that the std::unordered_map was a mistake. Many parts of it's API prevent implementing it efficiently (For example, every insertion requires allocation, even if you reserve). It's widely regarded, within and outside the standards committee, as a very unfortunate mistake. swisstable (absl::flat_hash_map) is a popular choice right now for the hash table to use for C++ code that cares about performance. There are other choices as well (dense_hash_map, F14FastMap, etc), But honestly most choices these days are worse than std::unordered_map (well, boost::unordered_map is probably just as bad, since std's implementation was taken wholesale from boost without any thought!)
- deleted 8y ago[deleted]
- Toury2d 8y agoI can't believe the author still published that article even after he realised he was comparing different map data structures.