6 ms·

> If we use standard libraries, we can benefit from extreme optimization I did a quick test[0] about that since it is a common thing people claim ("use the sta

> If we use standard libraries, we can benefit from extreme optimization I did a quick test[0] about that since it is a common thing people claim ("use the standard library, it has been battle tested and optimized to heavens", etc). Since the article is mainly just about the hash part of the hash table, i only tried with hash sets instead of full hash maps, though the difference is trivial. I generated a 256MB file with 67108864 32bit unique random integers and tried to use both C++'s unordered_set as well as a custom set built using the method described in the site (i also used the 32bit integer hash from a link in the article). I used C++ because it is the closest to C that has a standard library that provides a hash set. The results on my machine (Ryzen 3700X, Linux, GCC 12.1.1) are: std version: 19504ms custom version: 3979ms The "std version" is almost five times slower than the custom purpose-built version. Note that this is the "best case" scenario where i specify a number of buckets to minimize resizing - without that the std version needs 41382ms instead (i.e. a naive use of unordered_set would be almost twice as slow as with providing the bucket count and about 10 times slower than the custom version). So yeah, i don't think the days of writing your own data structures are left behind, at least as far as purpose built structures for improving performance are concerned. Of course sometimes you just want to replace a very simple/naive algorithm with an at least theoretically faster one (i.e. replacing a linear search in a big unordered array with some map) so having the language provide some reusable data structures is convenient. But if that doesn't solve the performance problem you may have and the problem is in the data structure you can most likely do better than the generic structures the language has - after all you know your data and your code at a better and higher level than the compiler ever will. [0] http://xtra.runtimeterror.com/snippets/dir?ci=tip&name=hash/customvsstd http://xtra.runtimeterror.com/snippets/dir?ci=tip&name=hash/...

adgjlsfhk1 4y ago
note that the c++ built-in hash table is known to be really bad.
- badsectoracula 4y ago
  Yeah i guessed (i haven't really used them much myself), but the argument was about using the functionality in the standard library. Of course another practical alternative to both C++ and C (since the linked article is about C) is to use some 3rd party library.
  - adgjlsfhk1 4y ago
    The poor quality and inability to fix the the C and C++ std libraries are a large part of why (IMO) C and C++ aren't the future.
- chrsig 4y ago
  s/be really bad/have an interface that precludes many optimizations. By saying things like "really bad", it discourages use at all, and for most uses std::unordered_map is fine.
  - tialaramex 4y ago
    It would be worth somebody gathering real world numbers from systems, to find out where people use std::unordered_map, how much are they leaving on the table, versus where people use say Folly F14, how small is the gain they're getting with their real workload. I would guess there are a lot of maps out there which in practice have a dozen things in them and so it doesn't matter how it works, a naive linear search would be fine too. But I genuinely have no idea, maybe it's 99% maybe it's 1%.
bbqbbqbbq 4y ago
C++'s `std::unordered_[map|set]` has a requirement that the addresses of objects in the map don't change on a reallocation -- this forces it to use buckets with linked lists under the hood. Try absl::flat_hash_set (https://github.com/abseil/abseil-cpp/blob/master/absl/container/flat_hash_set.h https://github.com/abseil/abseil-cpp/blob/master/absl/contai...) and see how it goes.
anonymoushn 4y ago
30ns per lookup is ok. I think you could do around 6ns per lookup (maybe less?) without changing the hash algorithm, using huge pages, reordering the lookups, or dropping the requirement that it be a hash table.
- badsectoracula 4y ago
  Note that the time is for both insertion and lookup, i didn't actually check lookup alone, just how general "use" compares between the two. Pure lookup is std version: 8563ms custom version: 1660ms (i.e. std version is ~5.1 times slower, again with the preallocated buckets - without preallocating the buckets it is 15298ms) That puts lookup to ~24.8ns. > I think you could do around 6ns per lookup (maybe less?) without changing the hash algorithm, using huge pages, reordering the lookups, or dropping the requirement that it be a hash table. Yeah, considering this is just a "set of 32bit numbers" i could just as easily use a bitmap - a simple implementation with a bitmap array had it at ~6.3ns per lookup - but the discussion was on hash maps/sets and i wanted to keep it as close to the article. I'm not sure what you refer to with "huge pages" though. Can you elaborate or provide some info? Also about reordering the lookups you mean changing the order of the values i check? I wanted to have a random lookup since this was a test for how well arbitrary lookups would perform, this is why i generated a file with unique random numbers ahead of time.
  - anonymoushn 4y ago
    I was informally referring to the insert and the much later lookup as "2 lookups." > I'm not sure what you refer to with "huge pages" though. Can you elaborate or provide some info? CPUs for servers and desktops made within my lifetime (?) use what's called a translation lookaside buffer (TLB) to cache some of the most recently used mappings from virtual pages to physical pages. Page sizes on commonly used CPUs are 4KB except for Apple Silicon which uses 16KB pages. Since at least 1996[0], consumer CPUs have shipped with the ability to use 2MB (or larger) pages in addition the default page size. This capability is awkwardly exposed on Linux. Linux users can either use transparent huge pages, which will slowly replace 2MB-aligned 2MB regions allocated by long-running programs with huge pages, or they can use hugetlbfs to directly request huge pages when calling mmap. Windows nominally supports this feature and calls it "large pages," but in practice users can either run their program as administrator right after booting the machine and then never close it or give up. macOS supports this feature since 2016 and calls it "superpages." I haven't used that so I can't comment on how usable it is in practice. A lot of the runtime of a program like this is TLB misses. So you can just have way, way fewer TLB misses, like >99% fewer, if you use 2MB pages instead of 4KB pages. The mmap man page[1] says how to ask for huge pages when you call mmap. Here are some other[2] pages[3] about setting up hugetlbfs, which you must do before calling mmap in this way will work. > Also about reordering the lookups you mean changing the order of the values i check? I wanted to have a random lookup since this was a test for how well arbitrary lookups would perform, this is why i generated a file with unique random numbers ahead of time. I just wanted to be specific, like maybe a program could compute the set and then check that the set was computed correctly more quickly by partially sorting the input. No sorting allowed! 0: http://www.rcollins.org/ddj/Jul96/ http://www.rcollins.org/ddj/Jul96/ 1: https://man7.org/linux/man-pages/man2/mmap.2.html https://man7.org/linux/man-pages/man2/mmap.2.html 2: https://www.kernel.org/doc/html/latest/admin-guide/mm/hugetlbpage.html https://www.kernel.org/doc/html/latest/admin-guide/mm/hugetl... 3: https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt

adgjlsfhk1 4y ago

note that the c++ built-in hash table is known to be really bad.

badsectoracula 4y ago
Yeah i guessed (i haven't really used them much myself), but the argument was about using the functionality in the standard library. Of course another practical alternative to both C++ and C (since the linked article is about C) is to use some 3rd party library.
- adgjlsfhk1 4y ago
  The poor quality and inability to fix the the C and C++ std libraries are a large part of why (IMO) C and C++ aren't the future.
chrsig 4y ago
s/be really bad/have an interface that precludes many optimizations. By saying things like "really bad", it discourages use at all, and for most uses std::unordered_map is fine.
- tialaramex 4y ago
  It would be worth somebody gathering real world numbers from systems, to find out where people use std::unordered_map, how much are they leaving on the table, versus where people use say Folly F14, how small is the gain they're getting with their real workload. I would guess there are a lot of maps out there which in practice have a dozen things in them and so it doesn't matter how it works, a naive linear search would be fine too. But I genuinely have no idea, maybe it's 99% maybe it's 1%.

bbqbbqbbq 4y ago

C++'s `std::unordered_[map|set]` has a requirement that the addresses of objects in the map don't change on a reallocation -- this forces it to use buckets with linked lists under the hood. Try absl::flat_hash_set (https://github.com/abseil/abseil-cpp/blob/master/absl/container/flat_hash_set.h https://github.com/abseil/abseil-cpp/blob/master/absl/contai...) and see how it goes.

anonymoushn 4y ago

30ns per lookup is ok. I think you could do around 6ns per lookup (maybe less?) without changing the hash algorithm, using huge pages, reordering the lookups, or dropping the requirement that it be a hash table.

badsectoracula 4y ago
Note that the time is for both insertion and lookup, i didn't actually check lookup alone, just how general "use" compares between the two. Pure lookup is std version: 8563ms custom version: 1660ms (i.e. std version is ~5.1 times slower, again with the preallocated buckets - without preallocating the buckets it is 15298ms) That puts lookup to ~24.8ns. > I think you could do around 6ns per lookup (maybe less?) without changing the hash algorithm, using huge pages, reordering the lookups, or dropping the requirement that it be a hash table. Yeah, considering this is just a "set of 32bit numbers" i could just as easily use a bitmap - a simple implementation with a bitmap array had it at ~6.3ns per lookup - but the discussion was on hash maps/sets and i wanted to keep it as close to the article. I'm not sure what you refer to with "huge pages" though. Can you elaborate or provide some info? Also about reordering the lookups you mean changing the order of the values i check? I wanted to have a random lookup since this was a test for how well arbitrary lookups would perform, this is why i generated a file with unique random numbers ahead of time.
- anonymoushn 4y ago
  I was informally referring to the insert and the much later lookup as "2 lookups." > I'm not sure what you refer to with "huge pages" though. Can you elaborate or provide some info? CPUs for servers and desktops made within my lifetime (?) use what's called a translation lookaside buffer (TLB) to cache some of the most recently used mappings from virtual pages to physical pages. Page sizes on commonly used CPUs are 4KB except for Apple Silicon which uses 16KB pages. Since at least 1996[0], consumer CPUs have shipped with the ability to use 2MB (or larger) pages in addition the default page size. This capability is awkwardly exposed on Linux. Linux users can either use transparent huge pages, which will slowly replace 2MB-aligned 2MB regions allocated by long-running programs with huge pages, or they can use hugetlbfs to directly request huge pages when calling mmap. Windows nominally supports this feature and calls it "large pages," but in practice users can either run their program as administrator right after booting the machine and then never close it or give up. macOS supports this feature since 2016 and calls it "superpages." I haven't used that so I can't comment on how usable it is in practice. A lot of the runtime of a program like this is TLB misses. So you can just have way, way fewer TLB misses, like >99% fewer, if you use 2MB pages instead of 4KB pages. The mmap man page[1] says how to ask for huge pages when you call mmap. Here are some other[2] pages[3] about setting up hugetlbfs, which you must do before calling mmap in this way will work. > Also about reordering the lookups you mean changing the order of the values i check? I wanted to have a random lookup since this was a test for how well arbitrary lookups would perform, this is why i generated a file with unique random numbers ahead of time. I just wanted to be specific, like maybe a program could compute the set and then check that the set was computed correctly more quickly by partially sorting the input. No sorting allowed! 0: http://www.rcollins.org/ddj/Jul96/ http://www.rcollins.org/ddj/Jul96/ 1: https://man7.org/linux/man-pages/man2/mmap.2.html https://man7.org/linux/man-pages/man2/mmap.2.html 2: https://www.kernel.org/doc/html/latest/admin-guide/mm/hugetlbpage.html https://www.kernel.org/doc/html/latest/admin-guide/mm/hugetl... 3: https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt