<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>README.md - collab/1brc @ back-to-mmap</title>
<meta name="description" content="README.md in collab/1brc at back-to-mmap.">
<meta property="og:title" content="README.md - collab/1brc @ back-to-mmap">
<meta property="og:description" content="README.md in collab/1brc at back-to-mmap.">
<meta property="og:type" content="website">
<meta property="og:site_name" content="git.julia.blue">
<link rel="stylesheet" href="/css/style.css?v=62">
<script type="module" src="/js/main.js?v=62"></script>
</head>
<body>
<main data-ref="back-to-mmap" data-tip="9e4db4fe886aa6b13e0903a44d042a2fedfff587">
<noscript>
  <div class="callout">
    <p>
      hey! this is a static git repo viewer. commit diffs, file history,
      older commits and other revisions won't load without javascript.
    </p>
    <p>
      you are still able to view source files on branch/tag tips,
      but the experience is degraded.
    </p>
  </div>
</noscript>
<header class="repo"><div>
<h1>collab/1brc</h1>
<p class="desc">the one billion row challenge</p>
</div>
<pre class="clone">git clone https://git.julia.blue/collab/1brc</pre>
</header>
<p class="snapshot-commit"><span class="commit-author">Rahul Butani</span><span class="commit-message" data-commit="9e4db4fe886aa6b13e0903a44d042a2fedfff587">exp/file-io: `io_uring` mem b/w experiment</span><span class="snapshot-sha sha" data-commit="9e4db4fe886aa6b13e0903a44d042a2fedfff587">9e4db4f</span><time datetime="2026-01-05T17:19:12-08:00" title="2026-01-05 17:19:12 -0800">2026-01-05</time></p>
<header class="topbar"><details class="switcher"><summary>back-to-mmap</summary><div class="menu"><strong>branches</strong><a class="current" href="/collab/1brc/ref/back-to-mmap/">back-to-mmap</a><a href="/collab/1brc/ref/julia-baseline/">julia-baseline</a><a href="/collab/1brc/ref/main/">main</a><a class="all" href="/collab/1brc/refs">all refs →</a></div></details><nav class="crumbs"><a href="/collab/1brc/">1brc</a> / <span class="cur">README.md</span></nav>
<span class="view-stats"><span>17.6 KiB</span><span>439 lines</span></span><span class="actions"><a class="raw" href="/collab/1brc/raw/04e58a1150b034f30b17930ac3e1a198d2b77745/README.md">raw</a></span></header>
<div class="markdown-view"><input type="radio" name="markdown-view" id="markdown-rendered" checked><label for="markdown-rendered">rendered</label><input type="radio" name="markdown-view" id="markdown-code"><label for="markdown-code">code</label><section class="readme rendered"><h1>One Billion Row Challenge</h1>
<p>See <a href="https://github.com/gunnarmorling/1brc">here</a>.</p>
<hr />
<h2>results</h2>
<blockquote>
<p>On an <a href="https://www.intel.com/content/www/us/en/products/sku/212262/intel-xeon-e2378g-processor-16m-cache-2-80-ghz/specifications.html">E-2378G</a> w/o SMT w/turbo.</p>
</blockquote>
<table><thead><tr><th style="text-align: center">name</th><th style="text-align: center">details</th><th style="text-align: center">result (ms)</th><th style="text-align: center">result: 10k stations (ms)</th></tr></thead><tbody>
<tr><td style="text-align: center"><a href="https://github.com/gunnarmorling/1brc/blob/db064194be375edc02d6dbcd21268ad40f7e2869/src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java">upstream baseline</a></td><td style="text-align: center"><code>nix run .#bench.baseline.1br</code></td><td style="text-align: center">135835 ± 1866</td><td style="text-align: center">169128 ± 1378</td></tr>
<tr><td style="text-align: center"><a href="https://github.com/gunnarmorling/1brc/blob/db064194be375edc02d6dbcd21268ad40f7e2869/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java">upstream #1</a></td><td style="text-align: center"><code>nix run .#bench.1stAvx10.1br</code></td><td style="text-align: center">1583 ± 18</td><td style="text-align: center">5773 ± 143</td></tr>
<tr><td style="text-align: center"><a href="#baseline">baseline</a></td><td style="text-align: center"><a href="https://github.com/rrbutani/1brc/tree/checkpoint/01-baseline"><code>checkpoint/01-baseline</code></a></td><td style="text-align: center">58583 ± 975</td><td style="text-align: center">79712 ± 318</td></tr>
</tbody></table>
<h2>how to run?</h2>
<p>runnables:</p>
<ul>
<li><code>nix run .#bench.&lt;impl name&gt;.&lt;input name&gt;</code>
<ul>
<li>benchmarks a particular implemetnation on a particular input</li>
<li>i.e. <code>nix run .#bench.baseline.small</code></li>
</ul>
</li>
<li><code>nix run .#testRunners.&lt;input name&gt; -- &lt;args to run an implementation&gt;</code>
<ul>
<li>tests that the implementation's outputs match reference outputs, for a particular input</li>
</ul>
</li>
<li><code>nix run .#testRunners.all -- &lt;args to run an implementation&gt;</code>
<ul>
<li>test an implementation on <em>all</em> inputs</li>
<li>also accessible as <code>nix run .#testRunners</code></li>
</ul>
</li>
<li><code>nix run .#benchRunners.&lt;input name&gt; -- &lt;args to run an implementation&gt;</code>
<ul>
<li>benchmarks (<code>hyperfine</code>) the implementation when run on a particular input</li>
</ul>
</li>
<li><code>nix run .#impls.&lt;impl name&gt;</code>
<ul>
<li>run a particular implementation</li>
<li>you probably do not want to do this directly (impls expect <code>measurements.txt</code> in cwd)
<ul>
<li>using <code>.#testRunner</code>/<code>.#benchRunner</code> or <code>.#bench.&lt;impl name&gt;.&lt;input name&gt;</code> will handle this for you</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>notable impls:</p>
<ul>
<li><code>baseline</code>: baseline Java implementation from upstream</li>
<li><code>1stNative</code>: 1st place Java implementation, compiled (graalvm) for the current CPU (build time)</li>
<li><code>1stAvx2</code>: ^ but compiled for <code>x86_64-v3</code></li>
<li><code>1stAvx10</code>: ^ but compiled for <code>x86_64-v4</code> (AVX512)</li>
<li><code>1stASIMD</code>: ^ but compiled for <code>armv8.1-a</code> (ASIMD, no SVE/SVE2)</li>
<li><code>this-avx10</code>:</li>
<li><code>this-avx2</code>:</li>
</ul>
<p>notable inputs:</p>
<ul>
<li><code>1br</code>: default billion row input</li>
<li><code>1br-many-stations</code>: billion row input with 10K stations</li>
<li><code>small</code>: 100K row input</li>
</ul>
<h2>details</h2>
<h3>baseline</h3>
<h3>mem bandwidth testing</h3>
<p>timings:
0. no-op: <code>460.9 µs ±  37.6 µs</code></p>
<ol>
<li>mmap:
- 1 thread: <code>597.8 µs ±  52.9 µs</code>
- 8 threads: <code>762.0 µs ± 121.9 µs</code></li>
<li>read:</li>
<li>read avx512:</li>
</ol>
<p>mmap stuff, linux:</p>
<ul>
<li>
<p>FilePmdMapped</p>
</li>
<li>
<p>page cache huge pages?</p>
</li>
<li>
<p>look at <code>/proc/&lt;pid&gt;/smaps</code></p>
</li>
<li>
<p>https://news.ycombinator.com/item?id=35457499</p>
<ul>
<li><code>CONFIG_READ_ONLY_THP_FOR_FS</code></li>
</ul>
</li>
<li>
<p>https://lwn.net/Articles/718102/</p>
<ul>
<li>huge pages for filesystems</li>
</ul>
</li>
<li>
<p>alternatively: hugetlbfs</p>
<ul>
<li>https://lwn.net/Articles/374424/</li>
<li>https://stackoverflow.com/questions/10343124/how-to-use-linux-hugetlbfs-for-shared-memory-maps-of-files</li>
<li>https://stackoverflow.com/a/64914391</li>
<li>https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt
<ul>
<li><code>default_hugepagesz=1G hugepages=32</code></li>
</ul>
</li>
</ul>
</li>
<li>
<p><code>i7-10610U</code> (kernel <code>6.12.59</code> w/<code>CONFIG_READ_ONLY_THP_FOR_FS</code>) measurements:</p>
<ul>
<li>1 thread:
<ul>
<li>no hugetlbfs (4K pages) mmap: 1326ms (210583 page faults)</li>
<li>2MB hugetlbfs mmap: 760ms (6656 page faults)</li>
<li>1GB hugetlbfs mmap: 760ms (89 page faults)</li>
</ul>
</li>
<li>8 threads:
<ul>
<li>no hugetlbfs (4K pages) mmap: 786ms</li>
<li>2MB hugetlbfs mmap: 663.5ms</li>
<li>file I/O (256K buf size): 641ms</li>
</ul>
</li>
</ul>
</li>
<li>
<p><code>2x E5-2699 v4</code> (kernel <code>6.5.0</code>) measurements:</p>
<ul>
<li>mem b/w:
<ul>
<li>theoretical: 2 socket, 4 channel (per socket) DDR4, 2133 MT/s -&gt; 136 GB/s</li>
<li>measured: 120 GB/s</li>
</ul>
</li>
<li>20 threads:
<ul>
<li>commands:<pre class="language-bash"><a-pr>file</a-pr>=/tmp/_1br/1br/measurements.txt <a-c># `/dev/shm/measurements.txt` performs worse (??)</a-c>
<a-pr>NUM_THREADS</a-pr>=20 <a-f>hyperfine</a-f> \
    <a-s>&quot;</a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s> \
    <a-s>&quot;ONEMMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s> \
    <a-s>&quot;TLB_2MB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/hugepages/measurements.txt&quot;</a-s> \
    <a-s>&quot;TLB_1GB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/huge-1gb/measurements.txt&quot;</a-s> \
    <a-s>&quot;DONTMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s>

<a-f>vmtouch</a-f> <a-co>-e</a-co> <a-s>&quot;</a-s><a-o>$</a-o><a-pr>file</a-pr><a-s>&quot;</a-s>
<a-c># &lt;warmup&gt;</a-c>
<a-pr>NUM_THREADS</a-pr>=20 <a-pr>NUMA</a-pr>=1 <a-f>hyperfine</a-f> \
    <a-s>&quot;</a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s> \
    <a-s>&quot;ONEMMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s> \
    <a-s>&quot;TLB_2MB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/hugepages/measurements3.txt&quot;</a-s> \
    <a-s>&quot;TLB_1GB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/huge-1gb/measurements3.txt&quot;</a-s> \
    <a-s>&quot;DONTMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s></pre>
</li>
<li>no hugetlbfs (4K pages) mmap: 708ms</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 719ms</li>
<li>2MB hugetlbfs mmap: 333ms</li>
<li>1GB hugetlbfs mmap: 332ms</li>
<li>file I/O (256K buf size): 358ms</li>
<li>NUMA aware:
<ul>
<li>no hugetlbfs (4K pages) mmap: 760ms (??)</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 743ms (??)</li>
<li>2MB hugetlbfs mmap: 208ms (!)</li>
<li>1GB hugetlbfs mmap: 214ms (!)</li>
<li>file I/O (256K buf size): 267ms (!)</li>
</ul>
</li>
</ul>
</li>
<li>88 threads:
<ul>
<li>(same as above but with all threads on machine)</li>
<li>no hugetlbfs (4K pages) mmap: 673ms</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 684ms</li>
<li>2MB hugetlbfs mmap: 360ms</li>
<li>1GB hugetlbfs mmap: 350ms</li>
<li>file I/O (256K buf size): 363ms</li>
<li>NUMA aware:
<ul>
<li>no hugetlbfs (4K pages) mmap: 559ms (!)</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 563ms (!)</li>
<li>2MB hugetlbfs mmap: 202ms (!)</li>
<li>1GB hugetlbfs mmap: 205ms (!)</li>
<li>file I/O (256K buf size): 214ms (!)</li>
</ul>
</li>
</ul>
</li>
<li>20 threads, 10x repeat:
<ul>
<li>(same as <code>20 threads</code> above but with <code>REPEAT=10</code> and no <code>--min-runs</code>)</li>
<li>no hugetlbfs (4K pages) mmap: 2900ms
<ul>
<li><code>(2900 - 708)/9</code> -&gt; 244ms per read (after first)</li>
</ul>
</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 2900ms
<ul>
<li><code>(2900 - 719)/9</code> -&gt; 242ms per read (after first)</li>
</ul>
</li>
<li>2MB hugetlbfs mmap: 2591ms
<ul>
<li><code>(2591 - 333)/9</code> -&gt; 251ms per read (after first)</li>
</ul>
</li>
<li>1GB hugetlbfs mmap: 2599ms
<ul>
<li><code>(2599 - 332)/9</code> -&gt; 252ms per read (after first)</li>
</ul>
</li>
<li>file I/O (256K buf size): 2908ms
<ul>
<li><code>(2908 - 358)/9</code> -&gt; 283ms per read (after first)</li>
</ul>
</li>
</ul>
</li>
<li>20 threads, 100x repeat:
<ul>
<li>(same as <code>20 threads</code> above but with <code>REPEAT=100</code> and no <code>--min-runs</code> or <code>--warmup</code>)</li>
<li>no hugetlbfs (4K pages) mmap: 22871ms
<ul>
<li><code>(22871 - 708)/99</code> -&gt; 224ms per read (after first)</li>
</ul>
</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 22834ms
<ul>
<li><code>(22834 - 719)/99</code> -&gt; 223ms per read (after first)</li>
</ul>
</li>
<li>2MB hugetlbfs mmap: 24256ms
<ul>
<li><code>(24256 - 333)/99</code> -&gt; 242ms per read (after first)</li>
</ul>
</li>
<li>1GB hugetlbfs mmap: 24643ms
<ul>
<li><code>(24643 - 332)/99</code> -&gt; 246ms per read (after first)</li>
</ul>
</li>
<li>file I/O (256K buf size): 27503ms
<ul>
<li><code>(27503 - 358)/99</code> -&gt; 274ms per read (after first)</li>
</ul>
</li>
<li>NUMA aware:
<ul>
<li>no hugetlbfs (4K pages) mmap: 12316ms
<ul>
<li><code>(12316 - 760)/99</code> -&gt; 117ms per read (after first)</li>
</ul>
</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 12125ms
<ul>
<li><code>(12125 - 743)/99</code> -&gt; 115ms per read (after first)</li>
</ul>
</li>
<li>2MB hugetlbfs mmap: 17033ms
<ul>
<li><code>(17033 - 208)/99</code> -&gt; 170ms per read (after first)</li>
</ul>
</li>
<li>1GB hugetlbfs mmap: 17623ms
<ul>
<li><code>(17623 - 214)/99</code> -&gt; 176ms per read (after first)</li>
</ul>
</li>
<li>file I/O (256K buf size): 20820ms
<ul>
<li><code>(20820 - 267)/99</code> -&gt; 208ms per read (after first)</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>re: the memory b/w we're seeing
<ul>
<li>input file is about 14GB, at ~225ms per read (when not accounting for NUMA) that's ~62 GB/s</li>
<li>with NUMA-awareness (pinning threads, taking care to populate page cache and hugetlbfs this way) we see ~115ms for reads meaning ~118GB/s – a match for the measured memory b/w (<code>mlc</code>)!</li>
<li>there is some weirdness in the NUMA results though:
<ul>
<li>in the 100x repeat, hugetlbfs doesn't see the same speedup from NUMA awareness... I'm not totally clear on how hugepages are allocated; it may be the case that despite the NUMA "awareness" in <code>f2htlbfs</code>, pages (allocated when bumping <code>/sys/kernel/mm/hugepages/hugepages-*/nr_hugepages</code>?) are allocated such that there's cross-domain memory traffic</li>
<li>not entirely sure what's going on w/file I/O w/NUMA-awareness and why it's not saturating memory b/w..</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
<li>
<p><code>5950X</code> (kernel: <code>6.12.61</code>)</p>
<ul>
<li>mem b/w:
<ul>
<li>theoretical: 2 channel DDR4, 3200 MT/s -&gt; 51.2 GB/s</li>
<li>measured: 40.2 GB/s</li>
</ul>
</li>
<li>32 threads:
<ul>
<li><code>hyperfine "$bin /dev/shm/measurements.txt" "ONEMMAP=1 $bin /dev/shm/measurements.txt" "TLB_2MB=1 $bin /dev/hugepages/measurements.txt" "DONTMAP=1 BUF_SIZE=65536 $bin /dev/shm/measurements.txt" "DONTMAP=1 BUF_SIZE=262144 $bin /dev/shm/measurements.txt" --warmup 3</code></li>
<li>no hugetlbfs (4K pages) mmap: 611ms</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 632ms</li>
<li>2MB hugetlbfs mmap: 344ms</li>
<li>file I/O (4K buf size): 387ms</li>
<li>file I/O (8K buf size): 384ms</li>
<li>file I/O (16K buf size): 388ms</li>
<li>file I/O (32K buf size): 392ms</li>
<li>file I/O (65K buf size): 396ms</li>
<li>file I/O (256K buf size): 413ms</li>
</ul>
</li>
<li>32 threads, 100x repeat:
<ul>
<li>(same as above but with <code>REPEAT=100</code> and <code>--min-runs 3</code> and no <code>--warmup</code>)</li>
<li>no hugetlbfs (4K pages) mmap: 34818ms
<ul>
<li><code>(34818 - 611)/99</code> -&gt; 346ms per read (after first)</li>
</ul>
</li>
<li>no hugetlbfs (4K pages) mmap (shared across threads): 34696ms
<ul>
<li><code>(34696 - 632)/99</code> -&gt; 344ms per read (after first)</li>
</ul>
</li>
<li>2MB hugetlbfs mmap: 34255ms
<ul>
<li><code>(34255 - 344)/99</code> -&gt; 343ms per read (after first)</li>
</ul>
</li>
<li>file I/O (4K buf size): 36144ms
<ul>
<li><code>(36144 - 387)/99</code> -&gt; 361ms per read (after first)</li>
</ul>
</li>
<li>file I/O (8K buf size): 36342ms
<ul>
<li><code>(36342 - 384)/99</code> -&gt; 363ms per read (after first)</li>
</ul>
</li>
</ul>
</li>
<li>note: <code>(1000ms / 345ms) * 13795366173 bytes</code> comes out to 39.871 GB/s, matching the measured memory bandwidth for the system</li>
</ul>
</li>
<li>
<p><em>verdict</em>:</p>
<ul>
<li>after all the page faults have happened, regular page-sized <code>mmap</code>'d memory is the fastest</li>
<li>hugeTLB <code>mmap</code>'d pages are sometimes a bit slower? not sure why though...
<ul>
<li>caution: may be specific to <code>E5-2699 v4</code>, may be a NUMA side-effect, etc</li>
</ul>
</li>
<li>file I/O is slower (extra syscall) but not by much...
<ul>
<li>as seen above for one shot file reads, its overhead is less than page fault/PTE setup (when using regular sized pages)</li>
<li>even when using huge TLB pages its pretty close..</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>todo, comparison knobs:</p>
<ul>
<li>madv Sequential hint or not</li>
<li>no preread or manual preread or madv LinuxPopulateRead</li>
<li>thp or not</li>
</ul>
<p>darwin mmap:</p>
<ul>
<li>
<p>note: <a href="https://gist.github.com/pankkor/8e6b87f914f5a6697469af85fbbbf1bf#macos-super-pages">no darwin "superpage" support on apple silicon</a></p>
</li>
<li>
<p>see <a href="https://developer.apple.com/library/archive/documentation/FileManagement/Conceptual/FileSystemAdvancedPT/MappingFilesIntoMemory/MappingFilesIntoMemory.html#//apple_ref/doc/uid/TP40010765-CH2-SW1">guidance on <code>mmap</code></a></p>
<ul>
<li>should try just reading the file in chunks instead of <code>mmap</code>-ing</li>
</ul>
</li>
<li>
<p>findings:</p>
<ul>
<li>using one <code>mmap</code> (shared across threads) is faster than using one per thread
<ul>
<li>on Linux its about equivalent, separate mmap per thread is a bit faster</li>
</ul>
</li>
<li>just reading the file (no mmap) is significantly faster!
<ul>
<li>this is true on Linux as well, actually (though its less dramatic)</li>
<li>page fault overhead is brutal I guess? reading the file data multiple times tips things in <code>mmap</code>s favor again (but on my M1 this is only true once you get up to &gt;=8 reads of the file!)
<ul>
<li>(todo: get m1 numbers for each iteration to compare first and steady state numbers for mmap read vs file read)</li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
<p>notes:</p>
<ul>
<li>perf events to assess cross-NUMA domain accesses:<pre>mem_load_uops_l3_miss_retired.local_dram
mem_load_uops_l3_miss_retired.remote_dram
mem_load_uops_l3_miss_retired.remote_fwd
mem_load_uops_l3_miss_retired.remote_hitm
</pre>
</li>
</ul>
<h5>linux page fault exploration</h5>
<p>three profiles:</p>
<ol>
<li><code>250mb.2r.no-preload.ftf.gz</code>
+ <code>NUM_THREADS=1 REPEAT=2</code></li>
<li><code>250mb.2r.manual-preread.ftf.gz</code>
+ <code>NUM_THREADS=1 REPEAT=2 PREREAD=1</code>
+ (has a background thread go and access each page)</li>
<li><code>250mb.2r.madv-pop.ftf.gz</code>
+ <code>NUM_THREADS=1 REPEAT=2 PREPOP=1</code>
+ (uses madvise populate_read to eagerly load in all the pages)</li>
</ol>
<p>observations:</p>
<ul>
<li>the number of separate <code>asm_exc_page_fault</code> calls in the profile matches the number of minor faults we see in <code>perf stat</code>!
<ul>
<li>for <code>madv-pop</code> we don't see separate <code>asm_exc_page_fault</code> but we do see the <code>handle_mm_fault</code> calls that correspond (under <code>do_madvise</code>)</li>
</ul>
</li>
<li>comparing where the <code>handle_mm_fault</code> calls are across the profiles is (imo) instructive:
<ol>
<li>spread exclusively throughout the 1st execution of <code>process</code></li>
<li>a few in the start of the 1st execution of <code>process</code>, the vast majority grouped together in the background thread</li>
<li>all under the <code>madvise</code> syscall, before <code>process</code> runs</li>
</ol>
</li>
</ul>
&lt;!-- TODO: distribution of `handle_mm_fault` timings; aggregate timings --&gt;
<ul>
<li>comparing how long it takes the first <code>process</code> invocation vs the 2nd follows one's expectations:
<ol>
<li>158.844ms vs. 90.881ms</li>
<li>117.508ms vs. 108.613ms</li>
<li>105.613ms vs. 112.253ms</li>
</ol>
</li>
</ul>
&lt;!-- todo: graphs, graph script --&gt;
<ul>
<li>comparing page fault "overhead":
<ol>
<li>comparing 1st run vs 2nd run timings above (158ms - 90ms) yields ~68ms</li>
<li>manual pre-read (naive, manually reading pages) took 75.396ms</li>
<li><code>madvise</code> (foreground) took 65.954ms</li>
</ol>
</li>
</ul>
&lt;!-- todo: switch to issuing the madvise in the background instead of manually hitting pages --&gt;
<p>compare pre-read/pre-populate/no pre:</p>
<pre class="language-bash"><a-pr>bin</a-pr>=/home/rahul/.target/release/onebrc <a-pr>inp</a-pr>=/dev/shm/measurements.txt
<a-f>hyperfine</a-f> <a-co>-P</a-co> N 1 <a-eb>$(</a-eb><a-f>nproc</a-f><a-eb>)</a-eb> <a-co>--export-json</a-co> page_fault.bench.json \
  <a-s>&quot;NUM_THREADS={N} </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>inp</a-pr><a-s>&quot;</a-s> \
  <a-s>&quot;NUM_THREADS={N} PREREAD=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>inp</a-pr><a-s>&quot;</a-s> \
  <a-s>&quot;NUM_THREADS={N} PREPOP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>inp</a-pr><a-s>&quot;</a-s> \
  <a-s>&quot;NUM_THREADS={N} BACKPOP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>inp</a-pr><a-s>&quot;</a-s></pre>
<p>compare runtimes for multiple repetitions:</p>
<pre class="language-bash"><a-pr>bin</a-pr>=/home/rahul/.target/release/onebrc <a-pr>inp</a-pr>=/dev/shm/measurements.txt
<a-f>hyperfine</a-f> <a-co>-P</a-co> R 1 5 <a-co>--export-json</a-co> repeat.bench.json \
  <a-s>&quot;NUM_THREADS=1 REPEAT={R} </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>inp</a-pr><a-s>&quot;</a-s></pre>
<h4><code>io_uring</code></h4>
<p>links:</p>
<ul>
<li>Jens Axboe's original <a href="https://www.youtube.com/watch?v=-5T4Cjw46ys"><code>io_uring</code> talk</a></li>
<li>https://unixism.net/loti/</li>
<li>https://blog.cloudflare.com/missing-manuals-io_uring-worker-pool/</li>
<li>https://kernel.dk/io_uring.pdf</li>
</ul>
&lt;!-- tons of wrong information in this thread: https://news.ycombinator.com/item?id=45132710 --&gt;
<h3>hash table</h3>
<p>can "cheat" (use a priori knowledge of the actual station names in the input to go faster) so long as we don't sacrifice correctness (for inputs that have other stations names we should still give the right answer, even if it comes at extreme performance cost)</p>
<p>413 unique stations names in the actual input (~9 bits worth)</p>
<blockquote>
<p>[!NOTE]
(Julia)
Using the <a href="https://docs.rs/phf">phf</a> crate (attempted in 65c05cd) performs worse than
our custom hash function, even with the naive implementation. It ran around 15% slower
on both HAL and GLaDOS.</p>
</blockquote>
<p>links:</p>
<ul>
<li>http://www.0x80.pl/notesen/2023-04-30-lookup-in-strings.html</li>
</ul>
<h3>SIMD entry processing</h3>
<p>similar idea as above; imo we're allowed to tailor to patterns in the actual input so long as we're still correct (but slow) for other inputs</p>
<p>with newlines, distribution of entry lengths in the actual input:</p>
<pre>8 296680
9 13368845
10 56549519
11 126363662
12 200403848
13 157218545
14 130256624
15 100182128
16 61784198
17 58822394
18 37971047
19 19794500
20 11156550
21 4870157
22 11128531
23 3317775
24 1639407
25 35715
29 888692
30 1246628
31 559663
32 2142634
33 2258
</pre>
<p><a href="/collab/1brc/ref/back-to-mmap/blob/misc/entry-size-analysis.py">analysis</a> of how many entries can fit into a given vector width:</p>
<pre>&lt;vector width in bytes&gt;
   &lt;num entries that can fit in width&gt;: &lt;count&gt;
     - &lt;avg number of bytes&gt;

16
   0: 180641947
    - 16.30481090308443
   1: 843762726
    - 12.85910339917054
   2: 78
    - 16.0

32
   0: 2258
    - 33.0
   1: 75066439
    - 18.90311886247861
   2: 455687003
    - 26.846872602157582
   3: 4519099
    - 31.539677267526116

64
   1: 1
    - 32.0
   2: 426053
    - 46.05559636946577
   3: 18677350
    - 51.90815774186381
   4: 167686146
    - 56.34797425662106
   5: 54414955
    - 61.64345858597145
   6: 49414
    - 63.474379730440766
</pre>
<p>I'm going to assume AVX2+ (sorry arm NEON processors); 32 bytes per vector means we can handle all but <code>2258</code> entries using the "fast" path (vectorized)</p>
<ul>
<li>i'm comfortable selling this case out; we can have 2258 branch mispredicts and be okay I think</li>
</ul>
<p>for AVX512 (64 byte vectors) we never need to fall back</p>
<p>links:</p>
<ul>
<li>https://mcyoung.xyz/2023/11/27/simd-base64/</li>
<li>https://branchfree.org/2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/</li>
<li>https://www.officedaytime.com/simd512e/
<ul>
<li>https://www.officedaytime.com/tips/simd.html</li>
</ul>
</li>
<li>http://users.atw.hu/instlatx64/</li>
<li>https://github.com/WojciechMula/man-intrinsics (todo: package)</li>
</ul>
<p>experiments:</p>
<ul>
<li>find character index w/<code>std::simd</code> (x86 &amp; arm): <a href="https://rust.godbolt.org/z/3TdefvWaP">godbolt</a></li>
</ul>
<hr />
<p>file I/O execution strategies:</p>
<ul>
<li>mmap:
<ul>
<li>one vs. per thread</li>
<li>manual preread vs madvise prepop vs none</li>
<li>(linux only) hugepages: thp vs hugetlbfs 2MB vs hugetlbfs 1GB vs none</li>
</ul>
</li>
<li>regular file I/O:
<ul>
<li>buffer size: 4K, 16K, 65K, 256K (sweet spot?), 1M, 4M</li>
</ul>
</li>
<li>io_uring (linux only)</li>
</ul>
<hr />
<p>impls:</p>
<ul>
<li>
<p>baseline</p>
</li>
<li>
<p>u16 instead of f32</p>
</li>
<li>
<p>"branchless" parse instead of regular</p>
</li>
<li>
<p>hash function change?</p>
</li>
<li>
<p>mmap</p>
</li>
<li>
<p>threading</p>
</li>
<li>
<p>(experiment) avx512 read max roofline test</p>
</li>
<li>
<p>...</p>
</li>
</ul>
<p>opts to try/things to look into:</p>
<ul>
<li>file read opts:
<ul>
<li>huge pages (probably not helpful?)</li>
<li>NUMA-aware page cache set up?
<ul>
<li>duplicating pages across NUMA domains? (see: <a href="https://lwn.net/Articles/223056/">replicated cache</a> in older kernels?)</li>
</ul>
</li>
<li>io_uring?</li>
<li>unmap memory maps in background while reducing?</li>
</ul>
</li>
<li>tree reduce (very minor)</li>
</ul>
<p>todo: linux vm on m1 mac</p>
</section><div class="code-panel"><pre class="code src language-markdown"><span class="code-line"><a class="ln" id="L1" href="#L1">1</a><span class="code-text"><a-p>#</a-p> <a-tt>One Billion Row Challenge</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L2" href="#L2">2</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L3" href="#L3">3</a><span class="code-text">See [here](https://github.com/gunnarmorling/1brc).</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L4" href="#L4">4</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L5" href="#L5">5</a><span class="code-text"><a-p>---</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L6" href="#L6">6</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L7" href="#L7">7</a><span class="code-text"><a-p>##</a-p> <a-tt>results</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L8" href="#L8">8</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L9" href="#L9">9</a><span class="code-text"><a-p>&gt; </a-p>On an [E-2378G](https://www.intel.com/content/www/us/en/products/sku/212262/intel-xeon-e2378g-processor-16m-cache-2-80-ghz/specifications.html) w/o SMT w/turbo.</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L10" href="#L10">10</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L11" href="#L11">11</a><span class="code-text">| name | details | result (ms) |  result: 10k stations (ms) |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L12" href="#L12">12</a><span class="code-text">|:----:|:-------:|:-----------:|:--------------------------:|</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L13" href="#L13">13</a><span class="code-text">| [upstream baseline](https://github.com/gunnarmorling/1brc/blob/db064194be375edc02d6dbcd21268ad40f7e2869/src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java) | `nix run .#bench.baseline.1br` | 135835 ± 1866 | 169128 ± 1378 |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L14" href="#L14">14</a><span class="code-text">| [upstream #1](https://github.com/gunnarmorling/1brc/blob/db064194be375edc02d6dbcd21268ad40f7e2869/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java) | `nix run .#bench.1stAvx10.1br` | 1583 ± 18 | 5773 ± 143 |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L15" href="#L15">15</a><span class="code-text">| [baseline](#baseline) | [`checkpoint/01-baseline`](https://github.com/rrbutani/1brc/tree/checkpoint/01-baseline) | 58583 ± 975 | 79712 ± 318 |</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L16" href="#L16">16</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L17" href="#L17">17</a><span class="code-text"><a-p>##</a-p> <a-tt>how to run?</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L18" href="#L18">18</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L19" href="#L19">19</a><span class="code-text">runnables:</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L20" href="#L20">20</a><span class="code-text"><a-p>  - </a-p>`nix run .#bench.&lt;impl name&gt;.&lt;input name&gt;`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L21" href="#L21">21</a><span class="code-text"><a-p>    + </a-p>benchmarks a particular implemetnation on a particular input</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L22" href="#L22">22</a><span class="code-text"><a-p>    + </a-p>i.e. `nix run .#bench.baseline.small`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L23" href="#L23">23</a><span class="code-text">  <a-p>- </a-p>`nix run .#testRunners.&lt;input name&gt; -- &lt;args to run an implementation&gt;`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L24" href="#L24">24</a><span class="code-text"><a-p>    + </a-p>tests that the implementation&#39;s outputs match reference outputs, for a particular input</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L25" href="#L25">25</a><span class="code-text">  <a-p>- </a-p>`nix run .#testRunners.all -- &lt;args to run an implementation&gt;`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L26" href="#L26">26</a><span class="code-text"><a-p>    + </a-p>test an implementation on _all_ inputs</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L27" href="#L27">27</a><span class="code-text"><a-p>    + </a-p>also accessible as `nix run .#testRunners`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L28" href="#L28">28</a><span class="code-text">  <a-p>- </a-p>`nix run .#benchRunners.&lt;input name&gt; -- &lt;args to run an implementation&gt;`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L29" href="#L29">29</a><span class="code-text"><a-p>    + </a-p>benchmarks (`hyperfine`) the implementation when run on a particular input</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L30" href="#L30">30</a><span class="code-text">  <a-p>- </a-p>`nix run .#impls.&lt;impl name&gt;`</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L31" href="#L31">31</a><span class="code-text"><a-p>    + </a-p>run a particular implementation</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L32" href="#L32">32</a><span class="code-text"><a-p>    + </a-p>you probably do not want to do this directly (impls expect `measurements.txt` in cwd)</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L33" href="#L33">33</a><span class="code-text"><a-p>      * </a-p>using `.#testRunner`/`.#benchRunner` or `.#bench.&lt;impl name&gt;.&lt;input name&gt;` will handle this for you</span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L34" href="#L34">34</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L35" href="#L35">35</a><span class="code-text"><a-p>notable impls:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L36" href="#L36">36</a><span class="code-text"><a-p>  - `baseline`: baseline Java implementation from upstream</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L37" href="#L37">37</a><span class="code-text"><a-p>  - `1stNative`: 1st place Java implementation, compiled (graalvm) for the current CPU (build time)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L38" href="#L38">38</a><span class="code-text"><a-p>  - `1stAvx2`: ^ but compiled for `x86_64-v3`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L39" href="#L39">39</a><span class="code-text"><a-p>  - `1stAvx10`: ^ but compiled for `x86_64-v4` (AVX512)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L40" href="#L40">40</a><span class="code-text"><a-p>  - `1stASIMD`: ^ but compiled for `armv8.1-a` (ASIMD, no SVE/SVE2)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L41" href="#L41">41</a><span class="code-text"><a-p>  - `this-avx10`:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L42" href="#L42">42</a><span class="code-text"><a-p>  - `this-avx2`:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L43" href="#L43">43</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L44" href="#L44">44</a><span class="code-text"><a-p>notable inputs:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L45" href="#L45">45</a><span class="code-text"><a-p>  - `1br`: default billion row input</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L46" href="#L46">46</a><span class="code-text"><a-p>  - `1br-many-stations`: billion row input with 10K stations</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L47" href="#L47">47</a><span class="code-text"><a-p>  - `small`: 100K row input</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L48" href="#L48">48</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L49" href="#L49">49</a><span class="code-text"><a-p>## </a-p><a-tt>details</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L50" href="#L50">50</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L51" href="#L51">51</a><span class="code-text"><a-p>### </a-p><a-tt>baseline</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L52" href="#L52">52</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L53" href="#L53">53</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L54" href="#L54">54</a><span class="code-text"><a-p>### </a-p><a-tt>mem bandwidth testing</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L55" href="#L55">55</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L56" href="#L56">56</a><span class="code-text"><a-p>timings:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L57" href="#L57">57</a><span class="code-text"><a-p>  0. no-op: `460.9 µs ±  37.6 µs`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L58" href="#L58">58</a><span class="code-text"><a-p>  1. mmap:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L59" href="#L59">59</a><span class="code-text"><a-p>    - 1 thread: `597.8 µs ±  52.9 µs`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L60" href="#L60">60</a><span class="code-text"><a-p>    - 8 threads: `762.0 µs ± 121.9 µs`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L61" href="#L61">61</a><span class="code-text"><a-p>  2. read:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L62" href="#L62">62</a><span class="code-text"><a-p>  3. read avx512:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L63" href="#L63">63</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L64" href="#L64">64</a><span class="code-text"><a-p>mmap stuff, linux:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L65" href="#L65">65</a><span class="code-text"><a-p>  - FilePmdMapped</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L66" href="#L66">66</a><span class="code-text"><a-p>  - page cache huge pages?</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L67" href="#L67">67</a><span class="code-text"><a-p>  - look at `/proc/&lt;pid&gt;/smaps`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L68" href="#L68">68</a><span class="code-text"><a-p>  - https://news.ycombinator.com/item?id=35457499</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L69" href="#L69">69</a><span class="code-text"><a-p>    + `CONFIG_READ_ONLY_THP_FOR_FS`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L70" href="#L70">70</a><span class="code-text"><a-p>  - https://lwn.net/Articles/718102/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L71" href="#L71">71</a><span class="code-text"><a-p>    + huge pages for filesystems</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L72" href="#L72">72</a><span class="code-text"><a-p>  - alternatively: hugetlbfs</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L73" href="#L73">73</a><span class="code-text"><a-p>    + https://lwn.net/Articles/374424/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L74" href="#L74">74</a><span class="code-text"><a-p>    + https://stackoverflow.com/questions/10343124/how-to-use-linux-hugetlbfs-for-shared-memory-maps-of-files</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L75" href="#L75">75</a><span class="code-text"><a-p>    + https://stackoverflow.com/a/64914391</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L76" href="#L76">76</a><span class="code-text"><a-p>    + https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L77" href="#L77">77</a><span class="code-text"><a-p>      * `default_hugepagesz=1G hugepages=32`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L78" href="#L78">78</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L79" href="#L79">79</a><span class="code-text"><a-p>  - `i7-10610U` (kernel `6.12.59` w/`CONFIG_READ_ONLY_THP_FOR_FS`) measurements:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L80" href="#L80">80</a><span class="code-text"><a-p>    + 1 thread:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L81" href="#L81">81</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 1326ms (210583 page faults)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L82" href="#L82">82</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 760ms (6656 page faults)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L83" href="#L83">83</a><span class="code-text"><a-p>      * 1GB hugetlbfs mmap: 760ms (89 page faults)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L84" href="#L84">84</a><span class="code-text"><a-p>    + 8 threads:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L85" href="#L85">85</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 786ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L86" href="#L86">86</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 663.5ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L87" href="#L87">87</a><span class="code-text"><a-p>      * file I/O (256K buf size): 641ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L88" href="#L88">88</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L89" href="#L89">89</a><span class="code-text"><a-p>  - `2x E5-2699 v4` (kernel `6.5.0`) measurements:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L90" href="#L90">90</a><span class="code-text"><a-p>    + mem b/w:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L91" href="#L91">91</a><span class="code-text"><a-p>      * theoretical: 2 socket, 4 channel (per socket) DDR4, 2133 MT/s -&gt; 136 GB/s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L92" href="#L92">92</a><span class="code-text"><a-p>      * measured: 120 GB/s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L93" href="#L93">93</a><span class="code-text"><a-p>    + 20 threads:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L94" href="#L94">94</a><span class="code-text"><a-p>      * commands:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L95" href="#L95">95</a><span class="code-text"><a-p>        </a-p><a-tl>```bash</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L96" href="#L96">96</a><span class="code-text"><a-p>        </a-p><a-pr>file</a-pr><a-tl>=/tmp/_1br/1br/measurements.txt </a-tl><a-c># `/dev/shm/measurements.txt` performs worse (??)</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L97" href="#L97">97</a><span class="code-text"><a-p>        </a-p><a-pr>NUM_THREADS</a-pr><a-tl>=20 </a-tl><a-f>hyperfine</a-f><a-tl> \</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L98" href="#L98">98</a><span class="code-text"><a-p>        </a-p><a-tl>    </a-tl><a-s>&quot;</a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s><a-tl> \</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L99" href="#L99">99</a><span class="code-text"><a-p>        </a-p><a-tl>    </a-tl><a-s>&quot;ONEMMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s><a-tl> \</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L100" href="#L100">100</a><span class="code-text"><a-p>        </a-p><a-tl>    </a-tl><a-s>&quot;TLB_2MB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/hugepages/measurements.txt&quot;</a-s><a-tl> \</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L101" href="#L101">101</a><span class="code-text"><a-p>        </a-p><a-tl>    </a-tl><a-s>&quot;TLB_1GB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/huge-1gb/measurements.txt&quot;</a-s><a-tl> \</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L102" href="#L102">102</a><span class="code-text"><a-p>        </a-p><a-tl>    </a-tl><a-s>&quot;DONTMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L103" href="#L103">103</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L104" href="#L104">104</a><span class="code-text"><a-p>        </a-p><a-f>vmtouch</a-f><a-p> </a-p><a-co>-e</a-co><a-p> </a-p><a-s>&quot;</a-s><a-o>$</a-o><a-pr>file</a-pr><a-s>&quot;</a-s></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L105" href="#L105">105</a><span class="code-text"><a-p>        </a-p><a-c># &lt;warmup&gt;</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L106" href="#L106">106</a><span class="code-text"><a-p>        </a-p><a-pr>NUM_THREADS</a-pr><a-p>=20 </a-p><a-pr>NUMA</a-pr><a-p>=1 </a-p><a-f>hyperfine</a-f><a-p> \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L107" href="#L107">107</a><span class="code-text"><a-p>            </a-p><a-s>&quot;</a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s><a-p> \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L108" href="#L108">108</a><span class="code-text"><a-p>            </a-p><a-s>&quot;ONEMMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s><a-p> \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L109" href="#L109">109</a><span class="code-text"><a-p>            </a-p><a-s>&quot;TLB_2MB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/hugepages/measurements3.txt&quot;</a-s><a-p> \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L110" href="#L110">110</a><span class="code-text"><a-p>            </a-p><a-s>&quot;TLB_1GB=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-s> /dev/huge-1gb/measurements3.txt&quot;</a-s><a-p> \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L111" href="#L111">111</a><span class="code-text"><a-p>            </a-p><a-s>&quot;DONTMAP=1 </a-s><a-o>$</a-o><a-pr>bin</a-pr><a-o> $</a-o><a-pr>file</a-pr><a-s>&quot;</a-s></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L112" href="#L112">112</a><span class="code-text"><a-p>        ```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L113" href="#L113">113</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 708ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L114" href="#L114">114</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap (shared across threads): 719ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L115" href="#L115">115</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 333ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L116" href="#L116">116</a><span class="code-text"><a-p>      * 1GB hugetlbfs mmap: 332ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L117" href="#L117">117</a><span class="code-text"><a-p>      * file I/O (256K buf size): 358ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L118" href="#L118">118</a><span class="code-text"><a-p>      * NUMA aware:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L119" href="#L119">119</a><span class="code-text"><a-p>        - no hugetlbfs (4K pages) mmap: 760ms (??)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L120" href="#L120">120</a><span class="code-text"><a-p>        - no hugetlbfs (4K pages) mmap (shared across threads): 743ms (??)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L121" href="#L121">121</a><span class="code-text"><a-p>        - 2MB hugetlbfs mmap: 208ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L122" href="#L122">122</a><span class="code-text"><a-p>        - 1GB hugetlbfs mmap: 214ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L123" href="#L123">123</a><span class="code-text"><a-p>        - file I/O (256K buf size): 267ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L124" href="#L124">124</a><span class="code-text"><a-p>    + 88 threads:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L125" href="#L125">125</a><span class="code-text"><a-p>      * (same as above but with all threads on machine)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L126" href="#L126">126</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 673ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L127" href="#L127">127</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap (shared across threads): 684ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L128" href="#L128">128</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 360ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L129" href="#L129">129</a><span class="code-text"><a-p>      * 1GB hugetlbfs mmap: 350ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L130" href="#L130">130</a><span class="code-text"><a-p>      * file I/O (256K buf size): 363ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L131" href="#L131">131</a><span class="code-text"><a-p>      * NUMA aware:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L132" href="#L132">132</a><span class="code-text"><a-p>        - no hugetlbfs (4K pages) mmap: 559ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L133" href="#L133">133</a><span class="code-text"><a-p>        - no hugetlbfs (4K pages) mmap (shared across threads): 563ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L134" href="#L134">134</a><span class="code-text"><a-p>        - 2MB hugetlbfs mmap: 202ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L135" href="#L135">135</a><span class="code-text"><a-p>        - 1GB hugetlbfs mmap: 205ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L136" href="#L136">136</a><span class="code-text"><a-p>        - file I/O (256K buf size): 214ms (!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L137" href="#L137">137</a><span class="code-text"><a-p>    + 20 threads, 10x repeat:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L138" href="#L138">138</a><span class="code-text"><a-p>      * (same as `20 threads` above but with `REPEAT=10` and no `--min-runs`)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L139" href="#L139">139</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 2900ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L140" href="#L140">140</a><span class="code-text"><a-p>        - `(2900 - 708)/9` -&gt; 244ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L141" href="#L141">141</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap (shared across threads): 2900ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L142" href="#L142">142</a><span class="code-text"><a-p>        - `(2900 - 719)/9` -&gt; 242ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L143" href="#L143">143</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 2591ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L144" href="#L144">144</a><span class="code-text"><a-p>        - `(2591 - 333)/9` -&gt; 251ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L145" href="#L145">145</a><span class="code-text"><a-p>      * 1GB hugetlbfs mmap: 2599ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L146" href="#L146">146</a><span class="code-text"><a-p>        - `(2599 - 332)/9` -&gt; 252ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L147" href="#L147">147</a><span class="code-text"><a-p>      * file I/O (256K buf size): 2908ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L148" href="#L148">148</a><span class="code-text"><a-p>        - `(2908 - 358)/9` -&gt; 283ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L149" href="#L149">149</a><span class="code-text"><a-p>    + 20 threads, 100x repeat:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L150" href="#L150">150</a><span class="code-text"><a-p>      * (same as `20 threads` above but with `REPEAT=100` and no `--min-runs` or `--warmup`)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L151" href="#L151">151</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 22871ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L152" href="#L152">152</a><span class="code-text"><a-p>        - `(22871 - 708)/99` -&gt; 224ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L153" href="#L153">153</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap (shared across threads): 22834ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L154" href="#L154">154</a><span class="code-text"><a-p>        - `(22834 - 719)/99` -&gt; 223ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L155" href="#L155">155</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 24256ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L156" href="#L156">156</a><span class="code-text"><a-p>        - `(24256 - 333)/99` -&gt; 242ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L157" href="#L157">157</a><span class="code-text"><a-p>      * 1GB hugetlbfs mmap: 24643ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L158" href="#L158">158</a><span class="code-text"><a-p>        - `(24643 - 332)/99` -&gt; 246ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L159" href="#L159">159</a><span class="code-text"><a-p>      * file I/O (256K buf size): 27503ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L160" href="#L160">160</a><span class="code-text"><a-p>        - `(27503 - 358)/99` -&gt; 274ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L161" href="#L161">161</a><span class="code-text"><a-p>      * NUMA aware:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L162" href="#L162">162</a><span class="code-text"><a-p>        * no hugetlbfs (4K pages) mmap: 12316ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L163" href="#L163">163</a><span class="code-text"><a-p>          - `(12316 - 760)/99` -&gt; 117ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L164" href="#L164">164</a><span class="code-text"><a-p>        * no hugetlbfs (4K pages) mmap (shared across threads): 12125ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L165" href="#L165">165</a><span class="code-text"><a-p>          - `(12125 - 743)/99` -&gt; 115ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L166" href="#L166">166</a><span class="code-text"><a-p>        * 2MB hugetlbfs mmap: 17033ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L167" href="#L167">167</a><span class="code-text"><a-p>          - `(17033 - 208)/99` -&gt; 170ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L168" href="#L168">168</a><span class="code-text"><a-p>        * 1GB hugetlbfs mmap: 17623ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L169" href="#L169">169</a><span class="code-text"><a-p>          - `(17623 - 214)/99` -&gt; 176ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L170" href="#L170">170</a><span class="code-text"><a-p>        * file I/O (256K buf size): 20820ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L171" href="#L171">171</a><span class="code-text"><a-p>          - `(20820 - 267)/99` -&gt; 208ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L172" href="#L172">172</a><span class="code-text"><a-p>    + re: the memory b/w we&#39;re seeing</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L173" href="#L173">173</a><span class="code-text"><a-p>      * input file is about 14GB, at ~225ms per read (when not accounting for NUMA) that&#39;s ~62 GB/s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L174" href="#L174">174</a><span class="code-text"><a-p>      * with NUMA-awareness (pinning threads, taking care to populate page cache and hugetlbfs this way) we see ~115ms for reads meaning ~118GB/s – a match for the measured memory b/w (`mlc`)!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L175" href="#L175">175</a><span class="code-text"><a-p>      * there is some weirdness in the NUMA results though:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L176" href="#L176">176</a><span class="code-text"><a-p>        - in the 100x repeat, hugetlbfs doesn&#39;t see the same speedup from NUMA awareness... I&#39;m not totally clear on how hugepages are allocated; it may be the case that despite the NUMA &quot;awareness&quot; in `f2htlbfs`, pages (allocated when bumping `/sys/kernel/mm/hugepages/hugepages-*/nr_hugepages`?) are allocated such that there&#39;s cross-domain memory traffic</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L177" href="#L177">177</a><span class="code-text"><a-p>        - not entirely sure what&#39;s going on w/file I/O w/NUMA-awareness and why it&#39;s not saturating memory b/w..</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L178" href="#L178">178</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L179" href="#L179">179</a><span class="code-text"><a-p>  - `5950X` (kernel: `6.12.61`)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L180" href="#L180">180</a><span class="code-text"><a-p>    + mem b/w:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L181" href="#L181">181</a><span class="code-text"><a-p>      * theoretical: 2 channel DDR4, 3200 MT/s -&gt; 51.2 GB/s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L182" href="#L182">182</a><span class="code-text"><a-p>      * measured: 40.2 GB/s</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L183" href="#L183">183</a><span class="code-text"><a-p>    + 32 threads:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L184" href="#L184">184</a><span class="code-text"><a-p>      * `hyperfine &quot;$bin /dev/shm/measurements.txt&quot; &quot;ONEMMAP=1 $bin /dev/shm/measurements.txt&quot; &quot;TLB_2MB=1 $bin /dev/hugepages/measurements.txt&quot; &quot;DONTMAP=1 BUF_SIZE=65536 $bin /dev/shm/measurements.txt&quot; &quot;DONTMAP=1 BUF_SIZE=262144 $bin /dev/shm/measurements.txt&quot; --warmup 3`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L185" href="#L185">185</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 611ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L186" href="#L186">186</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap (shared across threads): 632ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L187" href="#L187">187</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 344ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L188" href="#L188">188</a><span class="code-text"><a-p>      * file I/O (4K buf size): 387ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L189" href="#L189">189</a><span class="code-text"><a-p>      * file I/O (8K buf size): 384ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L190" href="#L190">190</a><span class="code-text"><a-p>      * file I/O (16K buf size): 388ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L191" href="#L191">191</a><span class="code-text"><a-p>      * file I/O (32K buf size): 392ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L192" href="#L192">192</a><span class="code-text"><a-p>      * file I/O (65K buf size): 396ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L193" href="#L193">193</a><span class="code-text"><a-p>      * file I/O (256K buf size): 413ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L194" href="#L194">194</a><span class="code-text"><a-p>    + 32 threads, 100x repeat:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L195" href="#L195">195</a><span class="code-text"><a-p>      * (same as above but with `REPEAT=100` and `--min-runs 3` and no `--warmup`)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L196" href="#L196">196</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap: 34818ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L197" href="#L197">197</a><span class="code-text"><a-p>        - `(34818 - 611)/99` -&gt; 346ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L198" href="#L198">198</a><span class="code-text"><a-p>      * no hugetlbfs (4K pages) mmap (shared across threads): 34696ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L199" href="#L199">199</a><span class="code-text"><a-p>        - `(34696 - 632)/99` -&gt; 344ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L200" href="#L200">200</a><span class="code-text"><a-p>      * 2MB hugetlbfs mmap: 34255ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L201" href="#L201">201</a><span class="code-text"><a-p>        - `(34255 - 344)/99` -&gt; 343ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L202" href="#L202">202</a><span class="code-text"><a-p>      * file I/O (4K buf size): 36144ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L203" href="#L203">203</a><span class="code-text"><a-p>        - `(36144 - 387)/99` -&gt; 361ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L204" href="#L204">204</a><span class="code-text"><a-p>      * file I/O (8K buf size): 36342ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L205" href="#L205">205</a><span class="code-text"><a-p>        - `(36342 - 384)/99` -&gt; 363ms per read (after first)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L206" href="#L206">206</a><span class="code-text"><a-p>    + note: `(1000ms / 345ms) * 13795366173 bytes` comes out to 39.871 GB/s, matching the measured memory bandwidth for the system</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L207" href="#L207">207</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L208" href="#L208">208</a><span class="code-text"><a-p>  - _verdict_:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L209" href="#L209">209</a><span class="code-text"><a-p>    - after all the page faults have happened, regular page-sized `mmap`&#39;d memory is the fastest</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L210" href="#L210">210</a><span class="code-text"><a-p>    - hugeTLB `mmap`&#39;d pages are sometimes a bit slower? not sure why though...</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L211" href="#L211">211</a><span class="code-text"><a-p>      + caution: may be specific to `E5-2699 v4`, may be a NUMA side-effect, etc</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L212" href="#L212">212</a><span class="code-text"><a-p>    - file I/O is slower (extra syscall) but not by much...</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L213" href="#L213">213</a><span class="code-text"><a-p>      + as seen above for one shot file reads, its overhead is less than page fault/PTE setup (when using regular sized pages)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L214" href="#L214">214</a><span class="code-text"><a-p>      + even when using huge TLB pages its pretty close..</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L215" href="#L215">215</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L216" href="#L216">216</a><span class="code-text"><a-p>todo, comparison knobs:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L217" href="#L217">217</a><span class="code-text"><a-p>  - madv Sequential hint or not</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L218" href="#L218">218</a><span class="code-text"><a-p>  - no preread or manual preread or madv LinuxPopulateRead</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L219" href="#L219">219</a><span class="code-text"><a-p>  - thp or not</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L220" href="#L220">220</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L221" href="#L221">221</a><span class="code-text"><a-p>darwin mmap:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L222" href="#L222">222</a><span class="code-text"><a-p>  - note: [no darwin &quot;superpage&quot; support on apple silicon](https://gist.github.com/pankkor/8e6b87f914f5a6697469af85fbbbf1bf#macos-super-pages)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L223" href="#L223">223</a><span class="code-text"><a-p>  - see [guidance on `mmap`](https://developer.apple.com/library/archive/documentation/FileManagement/Conceptual/FileSystemAdvancedPT/MappingFilesIntoMemory/MappingFilesIntoMemory.html#//apple_ref/doc/uid/TP40010765-CH2-SW1)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L224" href="#L224">224</a><span class="code-text"><a-p>    + should try just reading the file in chunks instead of `mmap`-ing</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L225" href="#L225">225</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L226" href="#L226">226</a><span class="code-text"><a-p>  - findings:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L227" href="#L227">227</a><span class="code-text"><a-p>    + using one `mmap` (shared across threads) is faster than using one per thread</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L228" href="#L228">228</a><span class="code-text"><a-p>      * on Linux its about equivalent, separate mmap per thread is a bit faster</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L229" href="#L229">229</a><span class="code-text"><a-p>    + just reading the file (no mmap) is significantly faster!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L230" href="#L230">230</a><span class="code-text"><a-p>      * this is true on Linux as well, actually (though its less dramatic)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L231" href="#L231">231</a><span class="code-text"><a-p>      * page fault overhead is brutal I guess? reading the file data multiple times tips things in `mmap`s favor again (but on my M1 this is only true once you get up to &gt;=8 reads of the file!)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L232" href="#L232">232</a><span class="code-text"><a-p>        - (todo: get m1 numbers for each iteration to compare first and steady state numbers for mmap read vs file read)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L233" href="#L233">233</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L234" href="#L234">234</a><span class="code-text"><a-p>notes:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L235" href="#L235">235</a><span class="code-text"><a-p>  - perf events to assess cross-NUMA domain accesses:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L236" href="#L236">236</a><span class="code-text"><a-p>    </a-p><a-tl>```</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L237" href="#L237">237</a><span class="code-text"><a-p>    </a-p><a-tl>mem_load_uops_l3_miss_retired.local_dram</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L238" href="#L238">238</a><span class="code-text"><a-p>    </a-p><a-tl>mem_load_uops_l3_miss_retired.remote_dram</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L239" href="#L239">239</a><span class="code-text"><a-p>    </a-p><a-tl>mem_load_uops_l3_miss_retired.remote_fwd</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L240" href="#L240">240</a><span class="code-text"><a-p>    </a-p><a-tl>mem_load_uops_l3_miss_retired.remote_hitm</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L241" href="#L241">241</a><span class="code-text"><a-p>    ```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L242" href="#L242">242</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L243" href="#L243">243</a><span class="code-text"><a-p>##### </a-p><a-tt>linux page fault exploration</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L244" href="#L244">244</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L245" href="#L245">245</a><span class="code-text"><a-p>three profiles:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L246" href="#L246">246</a><span class="code-text"><a-p>  1. `250mb.2r.no-preload.ftf.gz`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L247" href="#L247">247</a><span class="code-text"><a-p>    + `NUM_THREADS=1 REPEAT=2`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L248" href="#L248">248</a><span class="code-text"><a-p>  2. `250mb.2r.manual-preread.ftf.gz`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L249" href="#L249">249</a><span class="code-text"><a-p>    + `NUM_THREADS=1 REPEAT=2 PREREAD=1`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L250" href="#L250">250</a><span class="code-text"><a-p>    + (has a background thread go and access each page)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L251" href="#L251">251</a><span class="code-text"><a-p>  3. `250mb.2r.madv-pop.ftf.gz`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L252" href="#L252">252</a><span class="code-text"><a-p>    + `NUM_THREADS=1 REPEAT=2 PREPOP=1`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L253" href="#L253">253</a><span class="code-text"><a-p>    + (uses madvise populate_read to eagerly load in all the pages)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L254" href="#L254">254</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L255" href="#L255">255</a><span class="code-text"><a-p>observations:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L256" href="#L256">256</a><span class="code-text"><a-p>  - the number of separate `asm_exc_page_fault` calls in the profile matches the number of minor faults we see in `perf stat`!</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L257" href="#L257">257</a><span class="code-text"><a-p>    + for `madv-pop` we don&#39;t see separate `asm_exc_page_fault` but we do see the `handle_mm_fault` calls that correspond (under `do_madvise`)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L258" href="#L258">258</a><span class="code-text"><a-p>  - comparing where the `handle_mm_fault` calls are across the profiles is (imo) instructive:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L259" href="#L259">259</a><span class="code-text"><a-p>    1. spread exclusively throughout the 1st execution of `process`</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L260" href="#L260">260</a><span class="code-text"><a-p>    2. a few in the start of the 1st execution of `process`, the vast majority grouped together in the background thread</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L261" href="#L261">261</a><span class="code-text"><a-p>    3. all under the `madvise` syscall, before `process` runs</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L262" href="#L262">262</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L263" href="#L263">263</a><span class="code-text"><a-c>&lt;!-- TODO: distribution of `handle_mm_fault` timings; aggregate timings --&gt;</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L264" href="#L264">264</a><span class="code-text"><a-p>  - comparing how long it takes the first `process` invocation vs the 2nd follows one&#39;s expectations:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L265" href="#L265">265</a><span class="code-text"><a-p>    1. 158.844ms vs. 90.881ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L266" href="#L266">266</a><span class="code-text"><a-p>    2. 117.508ms vs. 108.613ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L267" href="#L267">267</a><span class="code-text"><a-p>    3. 105.613ms vs. 112.253ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L268" href="#L268">268</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L269" href="#L269">269</a><span class="code-text"><a-c>&lt;!-- todo: graphs, graph script --&gt;</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L270" href="#L270">270</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L271" href="#L271">271</a><span class="code-text"><a-p>  - comparing page fault &quot;overhead&quot;:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L272" href="#L272">272</a><span class="code-text"><a-p>    1. comparing 1st run vs 2nd run timings above (158ms - 90ms) yields ~68ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L273" href="#L273">273</a><span class="code-text"><a-p>    2. manual pre-read (naive, manually reading pages) took 75.396ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L274" href="#L274">274</a><span class="code-text"><a-p>    3. `madvise` (foreground) took 65.954ms</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L275" href="#L275">275</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L276" href="#L276">276</a><span class="code-text"><a-c>&lt;!-- todo: switch to issuing the madvise in the background instead of manually hitting pages --&gt;</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L277" href="#L277">277</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L278" href="#L278">278</a><span class="code-text"><a-p>compare pre-read/pre-populate/no pre:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L279" href="#L279">279</a><span class="code-text"><a-p>```</a-p><a-tl>shell</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L280" href="#L280">280</a><span class="code-text"><a-p>bin=/home/rahul/.target/release/onebrc inp=/dev/shm/measurements.txt</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L281" href="#L281">281</a><span class="code-text"><a-p>hyperfine -P N 1 $(nproc) --export-json page_fault.bench.json \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L282" href="#L282">282</a><span class="code-text"><a-p>  &quot;NUM_THREADS={N} $bin $inp&quot; \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L283" href="#L283">283</a><span class="code-text"><a-p>  &quot;NUM_THREADS={N} PREREAD=1 $bin $inp&quot; \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L284" href="#L284">284</a><span class="code-text"><a-p>  &quot;NUM_THREADS={N} PREPOP=1 $bin $inp&quot; \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L285" href="#L285">285</a><span class="code-text"><a-p>  &quot;NUM_THREADS={N} BACKPOP=1 $bin $inp&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L286" href="#L286">286</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L287" href="#L287">287</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L288" href="#L288">288</a><span class="code-text"><a-p>compare runtimes for multiple repetitions:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L289" href="#L289">289</a><span class="code-text"><a-p>```</a-p><a-tl>shell</a-tl></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L290" href="#L290">290</a><span class="code-text"><a-p>bin=/home/rahul/.target/release/onebrc inp=/dev/shm/measurements.txt</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L291" href="#L291">291</a><span class="code-text"><a-p>hyperfine -P R 1 5 --export-json repeat.bench.json \</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L292" href="#L292">292</a><span class="code-text"><a-p>  &quot;NUM_THREADS=1 REPEAT={R} $bin $inp&quot;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L293" href="#L293">293</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L294" href="#L294">294</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L295" href="#L295">295</a><span class="code-text"><a-p>#### </a-p><a-tt>`io_uring`</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L296" href="#L296">296</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L297" href="#L297">297</a><span class="code-text"><a-p>links:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L298" href="#L298">298</a><span class="code-text"><a-p>  - Jens Axboe&#39;s original [`io_uring` talk](https://www.youtube.com/watch?v=-5T4Cjw46ys)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L299" href="#L299">299</a><span class="code-text"><a-p>  - https://unixism.net/loti/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L300" href="#L300">300</a><span class="code-text"><a-p>  - https://blog.cloudflare.com/missing-manuals-io_uring-worker-pool/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L301" href="#L301">301</a><span class="code-text"><a-p>  - https://kernel.dk/io_uring.pdf</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L302" href="#L302">302</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L303" href="#L303">303</a><span class="code-text"><a-c>&lt;!-- tons of wrong information in this thread: https://news.ycombinator.com/item?id=45132710 --&gt;</a-c></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L304" href="#L304">304</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L305" href="#L305">305</a><span class="code-text"><a-p>### </a-p><a-tt>hash table</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L306" href="#L306">306</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L307" href="#L307">307</a><span class="code-text"><a-p>can &quot;cheat&quot; (use a priori knowledge of the actual station names in the input to go faster) so long as we don&#39;t sacrifice correctness (for inputs that have other stations names we should still give the right answer, even if it comes at extreme performance cost)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L308" href="#L308">308</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L309" href="#L309">309</a><span class="code-text"><a-p>413 unique stations names in the actual input (~9 bits worth)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L310" href="#L310">310</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L311" href="#L311">311</a><span class="code-text"><a-p>&gt; [!NOTE]</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L312" href="#L312">312</a><span class="code-text"><a-p>&gt; (Julia)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L313" href="#L313">313</a><span class="code-text"><a-p>&gt; Using the [phf](https://docs.rs/phf) crate (attempted in 65c05cd) performs worse than</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L314" href="#L314">314</a><span class="code-text"><a-p>&gt; our custom hash function, even with the naive implementation. It ran around 15% slower</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L315" href="#L315">315</a><span class="code-text"><a-p>&gt; on both HAL and GLaDOS.</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L316" href="#L316">316</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L317" href="#L317">317</a><span class="code-text"><a-p>links:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L318" href="#L318">318</a><span class="code-text"><a-p>  - http://www.0x80.pl/notesen/2023-04-30-lookup-in-strings.html</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L319" href="#L319">319</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L320" href="#L320">320</a><span class="code-text"><a-p>### </a-p><a-tt>SIMD entry processing</a-tt></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L321" href="#L321">321</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L322" href="#L322">322</a><span class="code-text"><a-p>similar idea as above; imo we&#39;re allowed to tailor to patterns in the actual input so long as we&#39;re still correct (but slow) for other inputs</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L323" href="#L323">323</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L324" href="#L324">324</a><span class="code-text"><a-p>with newlines, distribution of entry lengths in the actual input:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L325" href="#L325">325</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L326" href="#L326">326</a><span class="code-text"><a-p>8 296680</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L327" href="#L327">327</a><span class="code-text"><a-p>9 13368845</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L328" href="#L328">328</a><span class="code-text"><a-p>10 56549519</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L329" href="#L329">329</a><span class="code-text"><a-p>11 126363662</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L330" href="#L330">330</a><span class="code-text"><a-p>12 200403848</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L331" href="#L331">331</a><span class="code-text"><a-p>13 157218545</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L332" href="#L332">332</a><span class="code-text"><a-p>14 130256624</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L333" href="#L333">333</a><span class="code-text"><a-p>15 100182128</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L334" href="#L334">334</a><span class="code-text"><a-p>16 61784198</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L335" href="#L335">335</a><span class="code-text"><a-p>17 58822394</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L336" href="#L336">336</a><span class="code-text"><a-p>18 37971047</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L337" href="#L337">337</a><span class="code-text"><a-p>19 19794500</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L338" href="#L338">338</a><span class="code-text"><a-p>20 11156550</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L339" href="#L339">339</a><span class="code-text"><a-p>21 4870157</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L340" href="#L340">340</a><span class="code-text"><a-p>22 11128531</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L341" href="#L341">341</a><span class="code-text"><a-p>23 3317775</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L342" href="#L342">342</a><span class="code-text"><a-p>24 1639407</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L343" href="#L343">343</a><span class="code-text"><a-p>25 35715</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L344" href="#L344">344</a><span class="code-text"><a-p>29 888692</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L345" href="#L345">345</a><span class="code-text"><a-p>30 1246628</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L346" href="#L346">346</a><span class="code-text"><a-p>31 559663</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L347" href="#L347">347</a><span class="code-text"><a-p>32 2142634</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L348" href="#L348">348</a><span class="code-text"><a-p>33 2258</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L349" href="#L349">349</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L350" href="#L350">350</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L351" href="#L351">351</a><span class="code-text"><a-p>[analysis](misc/entry-size-analysis.py) of how many entries can fit into a given vector width:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L352" href="#L352">352</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L353" href="#L353">353</a><span class="code-text"><a-p>&lt;vector width in bytes&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L354" href="#L354">354</a><span class="code-text"><a-p>   &lt;num entries that can fit in width&gt;: &lt;count&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L355" href="#L355">355</a><span class="code-text"><a-p>     - &lt;avg number of bytes&gt;</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L356" href="#L356">356</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L357" href="#L357">357</a><span class="code-text"><a-p>16</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L358" href="#L358">358</a><span class="code-text"><a-p>   0: 180641947</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L359" href="#L359">359</a><span class="code-text"><a-p>    - 16.30481090308443</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L360" href="#L360">360</a><span class="code-text"><a-p>   1: 843762726</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L361" href="#L361">361</a><span class="code-text"><a-p>    - 12.85910339917054</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L362" href="#L362">362</a><span class="code-text"><a-p>   2: 78</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L363" href="#L363">363</a><span class="code-text"><a-p>    - 16.0</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L364" href="#L364">364</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L365" href="#L365">365</a><span class="code-text"><a-p>32</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L366" href="#L366">366</a><span class="code-text"><a-p>   0: 2258</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L367" href="#L367">367</a><span class="code-text"><a-p>    - 33.0</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L368" href="#L368">368</a><span class="code-text"><a-p>   1: 75066439</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L369" href="#L369">369</a><span class="code-text"><a-p>    - 18.90311886247861</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L370" href="#L370">370</a><span class="code-text"><a-p>   2: 455687003</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L371" href="#L371">371</a><span class="code-text"><a-p>    - 26.846872602157582</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L372" href="#L372">372</a><span class="code-text"><a-p>   3: 4519099</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L373" href="#L373">373</a><span class="code-text"><a-p>    - 31.539677267526116</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L374" href="#L374">374</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L375" href="#L375">375</a><span class="code-text"><a-p>64</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L376" href="#L376">376</a><span class="code-text"><a-p>   1: 1</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L377" href="#L377">377</a><span class="code-text"><a-p>    - 32.0</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L378" href="#L378">378</a><span class="code-text"><a-p>   2: 426053</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L379" href="#L379">379</a><span class="code-text"><a-p>    - 46.05559636946577</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L380" href="#L380">380</a><span class="code-text"><a-p>   3: 18677350</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L381" href="#L381">381</a><span class="code-text"><a-p>    - 51.90815774186381</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L382" href="#L382">382</a><span class="code-text"><a-p>   4: 167686146</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L383" href="#L383">383</a><span class="code-text"><a-p>    - 56.34797425662106</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L384" href="#L384">384</a><span class="code-text"><a-p>   5: 54414955</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L385" href="#L385">385</a><span class="code-text"><a-p>    - 61.64345858597145</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L386" href="#L386">386</a><span class="code-text"><a-p>   6: 49414</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L387" href="#L387">387</a><span class="code-text"><a-p>    - 63.474379730440766</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L388" href="#L388">388</a><span class="code-text"><a-p>```</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L389" href="#L389">389</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L390" href="#L390">390</a><span class="code-text"><a-p>I&#39;m going to assume AVX2+ (sorry arm NEON processors); 32 bytes per vector means we can handle all but `2258` entries using the &quot;fast&quot; path (vectorized)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L391" href="#L391">391</a><span class="code-text"><a-p>  - i&#39;m comfortable selling this case out; we can have 2258 branch mispredicts and be okay I think</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L392" href="#L392">392</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L393" href="#L393">393</a><span class="code-text"><a-p>for AVX512 (64 byte vectors) we never need to fall back</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L394" href="#L394">394</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L395" href="#L395">395</a><span class="code-text"><a-p>links:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L396" href="#L396">396</a><span class="code-text"><a-p>  - https://mcyoung.xyz/2023/11/27/simd-base64/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L397" href="#L397">397</a><span class="code-text"><a-p>  - https://branchfree.org/2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L398" href="#L398">398</a><span class="code-text"><a-p>  - https://www.officedaytime.com/simd512e/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L399" href="#L399">399</a><span class="code-text"><a-p>    + https://www.officedaytime.com/tips/simd.html</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L400" href="#L400">400</a><span class="code-text"><a-p>  - http://users.atw.hu/instlatx64/</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L401" href="#L401">401</a><span class="code-text"><a-p>  - https://github.com/WojciechMula/man-intrinsics (todo: package)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L402" href="#L402">402</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L403" href="#L403">403</a><span class="code-text"><a-p>experiments:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L404" href="#L404">404</a><span class="code-text"><a-p>  - find character index w/`std::simd` (x86 &amp; arm): [godbolt](https://rust.godbolt.org/z/3TdefvWaP)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L405" href="#L405">405</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L406" href="#L406">406</a><span class="code-text"><a-p>---</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L407" href="#L407">407</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L408" href="#L408">408</a><span class="code-text"><a-p>file I/O execution strategies:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L409" href="#L409">409</a><span class="code-text"><a-p>  - mmap:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L410" href="#L410">410</a><span class="code-text"><a-p>    + one vs. per thread</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L411" href="#L411">411</a><span class="code-text"><a-p>    + manual preread vs madvise prepop vs none</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L412" href="#L412">412</a><span class="code-text"><a-p>    + (linux only) hugepages: thp vs hugetlbfs 2MB vs hugetlbfs 1GB vs none</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L413" href="#L413">413</a><span class="code-text"><a-p>  - regular file I/O:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L414" href="#L414">414</a><span class="code-text"><a-p>    + buffer size: 4K, 16K, 65K, 256K (sweet spot?), 1M, 4M</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L415" href="#L415">415</a><span class="code-text"><a-p>  - io_uring (linux only)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L416" href="#L416">416</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L417" href="#L417">417</a><span class="code-text"><a-p>---</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L418" href="#L418">418</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L419" href="#L419">419</a><span class="code-text"><a-p>impls:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L420" href="#L420">420</a><span class="code-text"><a-p>  - baseline</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L421" href="#L421">421</a><span class="code-text"><a-p>  - u16 instead of f32</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L422" href="#L422">422</a><span class="code-text"><a-p>  - &quot;branchless&quot; parse instead of regular</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L423" href="#L423">423</a><span class="code-text"><a-p>  - hash function change?</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L424" href="#L424">424</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L425" href="#L425">425</a><span class="code-text"><a-p>  - mmap</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L426" href="#L426">426</a><span class="code-text"><a-p>  - threading</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L427" href="#L427">427</a><span class="code-text"><a-p>  - (experiment) avx512 read max roofline test</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L428" href="#L428">428</a><span class="code-text"><a-p>  - ...</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L429" href="#L429">429</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L430" href="#L430">430</a><span class="code-text"><a-p>opts to try/things to look into:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L431" href="#L431">431</a><span class="code-text"><a-p>  - file read opts:</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L432" href="#L432">432</a><span class="code-text"><a-p>    + huge pages (probably not helpful?)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L433" href="#L433">433</a><span class="code-text"><a-p>    + NUMA-aware page cache set up?</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L434" href="#L434">434</a><span class="code-text"><a-p>      * duplicating pages across NUMA domains? (see: [replicated cache](https://lwn.net/Articles/223056/) in older kernels?)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L435" href="#L435">435</a><span class="code-text"><a-p>    + io_uring?</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L436" href="#L436">436</a><span class="code-text"><a-p>    + unmap memory maps in background while reducing?</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L437" href="#L437">437</a><span class="code-text"><a-p>  - tree reduce (very minor)</a-p></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L438" href="#L438">438</a><span class="code-text"></span><span class="code-break">
</span></span><span class="code-line"><a class="ln" id="L439" href="#L439">439</a><span class="code-text">todo: linux vm on m1 mac</span></span></pre></div></div>
</main>
</body>
</html>
