為什么我的IntelSkylake/KabyLakeCPU在簡單的哈希表實作中會導致神秘的因子3減速？

簡而言之：

我已經實作了一個簡單的（多鍵）哈希表，其中包含完全適合快取行的存盤桶（包含多個元素）。插入快取行桶非常簡單，也是主回圈的關鍵部分。

我已經實作了三個產生相同結果并且應該表現相同的版本。

謎

然而，盡管所有版本都具有完全相同的快取行訪問模式并導致相同的哈希表資料，但我發現性能差異驚人地大 3。

與我的 CPU (i7-7700HQ) 上的 insert_bad 和 insert_alt 相比，最佳實作 insert_ok 的速度降低了大約 3 倍。一個變體 insert_bad 是對 insert_ok 的簡單修改，它在快取行中添加了額外的不必要的線性搜索以找到要寫入的位置（它已經知道）并且不會遭受這種 x3 速度減慢。

與其他 CPU（AMD 5950X (Zen 3)、Intel i7-11800H (Tiger Lake)）insert_ok相比，完全相同的可執行檔案顯示速度提高了 1.6 倍。insert_badinsert_alt

# see https://github.com/cr-marcstevens/hashtable_mystery
$ ./test.sh
model name      : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
==============================
CXX=g      CXXFLAGS=-std=c  11 -O2 -march=native -falign-functions=64
tablesize: 117440512 elements: 67108864 loadfactor=0.571429
- test insert_ok : 11200ms
- test insert_bad: 3164ms
  (outcome identical to insert_ok: true)
- test insert_alt: 3366ms
  (outcome identical to insert_ok: true)

tablesize: 117440813 elements: 67108864 loadfactor=0.571427
- test insert_ok : 10840ms
- test insert_bad: 3301ms
  (outcome identical to insert_ok: true)
- test insert_alt: 3579ms
  (outcome identical to insert_ok: true)

編碼

// insert element in hash_table
inline void insert_ok(uint64_t k)
{
    // compute target bucket
    uint64_t b = mod(k);
    // bounded linear search for first non-full bucket
    for (size_t c = 0; c < 1024;   c)
    {
        bucket_t& B = table_ok[b];
        // if bucket non-full then store element and return
        if (B.size != bucket_size)
        {
            B.keys[B.size] = k;
            B.values[B.size] = 1;
              B.size;
              table_count;
            return;
        }
        // increase b w/ wrap around
        if (  b == table_size)
            b = 0;
    }
}
// equivalent to insert_ok
// but uses a stupid linear search to store the element at the target position
inline void insert_bad(uint64_t k)
{
    // compute target bucket
    uint64_t b = mod(k);
    // bounded linear search for first non-full bucket
    for (size_t c = 0; c < 1024;   c)
    {
        bucket_t& B = table_bad[b];
        // if bucket non-full then store element and return
        if (B.size != bucket_size)
        {
            for (size_t i = 0; i < bucket_size;   i)
            {
                if (i == B.size)
                {
                    B.keys[i] = k;
                    B.values[i] = 1;
                      B.size;
                      table_count;
                    return;
                }
            }
        }
        // increase b w/ wrap around
        if (  b == table_size)
            b = 0;
    }
}
// instead of using bucket_t.size, empty elements are marked by special empty_key value
// a bucket is filled first to last, so bucket is full if last element key != empty_key
uint64_t empty_key = ~uint64_t(0);
inline void insert_alt(uint64_t k)
{
    // compute target bucket
    uint64_t b = mod(k);
    // bounded linear search for first non-full bucket
    for (size_t c = 0; c < 1024;   c)
    {
        bucket_t& B = table_alt[b];
        // if bucket non-full then store element and return
        if (B.keys[bucket_size-1] == empty_key)
        {
            for (size_t i = 0; i < bucket_size;   i)
            {
                if (B.keys[i] == empty_key)
                {
                    B.keys[i] = k;
                    B.values[i] = 1;
                      table_count;
                    return;
                }
            }
        }
        // increase b w/ wrap around
        if (  b == table_size)
            b = 0;
    }
}

我的分析

I've tried various modifications to the loop C , but inherently it's so simple, the compiler will produce the same assembly. It's really not obvious from the resulting assembly what the factor 3 loss might cause. I've tried measuring with perf, but I can't seem to pinpoint any meaningful difference.

Comparing the assembly of the 3 versions which are all just relatively small loops, there is nothing that suggests anything close that may cause a factor 3 loss between these versions.

Hence, I presume the 3x slow down is a weird effect of automatic prefetching, or branch prediction, or instruction/jump alignment or maybe a combination of those.

Does anybody have better insights or ways to measure what effects might actually be at play here?

Details

I've created a small working C 11 example that demonstrates the problem. The code is available at

The performance of all the variants is basically identical for small region sizes. Everything up to 256 KiB takes 2 cycles/iteration, limited simply by the 8 uops in the loop and the

The problem becomes very clear. Up to regions of 4096 KiB, performance is identical, and MLP is high (for very small region sizes there is "no" MLP since there are no L1D misses at all). Suddenly at 8192 KiB, the MLP for the dependent case drops to 1 and stays there, while in the independent case the MLP goes to almost 10. That alone basically explains the 10x performance difference: the dependent case is not able to overlap loads, at all.

Why? The problem seems to be TLB misses. What happens at 8192 KiB is that the benchmark starts missing the TLB. Specifically, each Skylake core has 1536 STLB (second-level TLB) entries which can cover 1536 × 4096 = 6 MiB of 4K pages. So right between the 4 and 8 MiB region sizes, TLB misses go to 1 per iteration based on dtlb_load_misses.walk_completed, leading to this almost-too-perfect-is-it-fake plot:

So that's what happens: when address-unknown stores are in the store buffer, loads that take STLB misses can't overlap: they go one-at-a-time. So you suffer the full memory latency for every access. This also explains why the 2MB page case was fast: 2 MB pages can cover 3 GiB of memory, so there are no STLB misses/page walks for these region sizes.

Why

This behavior seems to stem from the fact that Skylake and other earlier Intel processors implement page table coherence, even though the x86 platform does not require it. Page table coherence means that if a store which modifies an address mapping (for example) a subsequent load that uses a virtual address affected by the remapping will consistently see the new mapping without any explicit flushes.

This insight comes from Henry Wong who reports in his

Huh! The 4K dependent shows two started walks, only one of which completes successfully. That's two walks for every load. This aligns with the theory that the page walk starts for the load in iteration N 1, but it finds the store from iteration N still sitting in the store buffer (since the load for iteration N provides its address, and it is still in progress). Since the address is unknown, the page walk is canceled as Henry describes. Further page walks are delayed until the store address is resolved. The upshot is all the loads complete in a serialized fashion because the page walk for load N 1 must wait for the result of load N.

Why the "bad" and "alt" methods are fast

Finally, there is one remaining mystery. The above explains why the original hash access was slow, but not why the other two were fast. The key is that both of the fast methods don't have address-unknown stores, because the data dependency with the load is replaced by a speculative control dependency.

Take a look at the inner loop for the insert_bad approach:

for (size_t i = 0; i < bucket_size;   i)
{
    if (i == B.size)
    {
        B.keys[i] = k;
        B.values[i] = 1;
          B.size;
          table_count;
        return;
    }
}

Note that the stores use the loop index i. Unlike the insert_ok case, where the index [B.size] comes from a store, i is a simply a calculated value in a register. Now i is related to the loaded value B.size since its final value will be equal to it, but that is established via a comparison which is a speculated control dependency. It doesn't cause any problem with page walk cancellation. This scenario does have a lot of mis-predictons (since the loop exit is unpredictable) but for the large region case these aren't actually too harmful because the bad path usually makes the same memory accesses as the good path (specifically, the next value inserted is always the same) and memory access behavior dominates.

The same is true for the alt case: the index to write at is established by using a calculated value i to load a value, check if it is the special marker value and then writing at that location using index i. Again, no delayed store address, just a quickly calculated register value and a speculated control dependency.

What About Other Hardware

Like the question author, I found the effect on Skylake, but I also observed the same behavior on Haswell. On Ice Lake, I can't reproduce: both the dep and indep have almost identical performance. However user Noah reported he could reproduce on Tigerlake using the original benchmark. More investigation needed.

Run It Yourself

You can run the benchmark I describe above yourself. It's part of uarch-bench. On Linux (or WSL, but performance counters aren't available) you can run the following command to collect the results:

for s in 2M-dep 4K-dep 4K-indep; do ./uarch-bench --timer=perf --test-name="studies/memory/tlb-fencing/*$s" --extra-events=dtlb_load_misses.miss_causes_a_walk#walk_s,dtlb_load_misses.walk_completed#walk_c,l1d_pend_miss.pending#l1d_p,l1d_pend_miss.pending_cycles#l1d_pc; done

Some systems may not have enough free performance counters available (if you have hyperthreading enabled), so you can do two runs using different sets of counters each time.

¹ In this case, rdx is always zero (the region is entirely full of zeros) so the store address happens to be the same as if this register wasn't included in the addressing expression, but the CPU doesn't know that!

² Here, the 2M dep case also starts to show better performance than the 4K indep case, although the gap is modest.

³ Note the "while any miss is outstanding" part: you could also calculate MLP as l1d_pend_miss.pending / cycles, which would be the average MLP over a period of time, regardless of whether any misses were outstanding. Each is useful in their own way, but in a case like this with misses constantly outstanding they give almost identical values.

⁴ Yes, there are many differences between this and the original example. We store to a single fixed location, whereas the original loop stored near the load location, which varies every iteration. We store 0 not 1. We don't check B.size to see if it is too large. In our test the loaded value is always 0. There is no search loop for when the bucket is full. We don't load a random value to address, but just do a linear stride. However, these are not material: the same effect occurs in both cases and you can incrementally modify the original example by removing complexity until you reach this simple case.

標籤：c performance gcc x86-64 hashtable

上一篇：逐行讀取檔案的最快方法是什么？

下一篇：尾遞回函式的性能