4 ms·

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

• 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
  • badsectoracula 4y ago
    I see, i was vaguely aware of them but not to the extent described here. Sadly it seems you need to configure the OS for them - might work for something like a server under your control, but it isn't something you can rely on in general use. I tried to use posix_memalign + madvice MADV_HUGEPAGE to allocate the memory for use in the test program (if i understood the documentation correctly, the "transparent huge page support" that madvice relies on doesn't need any system setup) but didn't see any difference from just using malloc (perhaps the advice was ignored). Either way, both were much slower than just statically allocating the data like in the test program.
• eterm 4y ago
  How would pre-allocating affect the lookup time? Am I naive in thinking it would only be insert time that would be affected by pre-allocating? Also I would recommend swapping the order in which you are testing them, just in case there are any issues there. While I would expected the std implementation to be slower, that certainly feels like an order of magnitude too slow for the standard library.
  • badsectoracula 4y ago
    You specify the number of buckets but it can still affect how they're built and thus how they are used. This is a guess TBH since i don't know exactly what G++'s unordered_set does. You are right about execution order, not sure what is going on since both are isolated (i literally just swapped the code around) but doing that almost doubled the std version performance :-/ - the custom one didn't change at all though. Perhaps the optimizer somehow interferes with both tests since the code is next to each and they use the same source data - a way to work around that might be to implement the lookup tests in separate shared objects with the "fill set" and "lookup set" to be in separate functions. I might do that at some point later.
    • eterm 4y ago
      Oh I see, how many did you choose for the bucket numbers? ( I assumed pre-allocate was a capacity allocation rather than bucket parameter ) I'd recommend 82139 which is the closest prime above 82137 which is Sqrt(Pi/2 * 2^32) which is the expected number of items before a collision. I'd also be interested to hear the performance under the hash function: hash(x) = x This is the CLR and JRE's prefered int32 hash. It's a poor hash for cryptographic purposes or wanting random bits but it has stellar performance for the most part.
      • badsectoracula 4y ago
        I linked the source above. The bucket count is a bit highter than 82139... just 101473717 :-P. Changing it with 82139 does make it twice as slow though. I used 101473717 because that was the number i got from bucket_count() after running it with the default buckets. About hash(x)=x, that is interesting, i never thought to just use x itself as the hash :-P. The performance is actually a tiny bit better (~17%) for checking if a number is in the set.