4 ms·

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

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.

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.