如何准确地在x86_64上对未对齐的访问速度进行基准测试?

8
一个回答中,我已经表明在x86 / x86_64上,未对齐访问几乎与对齐访问具有相同的速度。我没有任何数据来支持这个说法,所以我为此创建了一个基准测试。
你是否看到此基准测试中的任何缺陷?你能否改进它(我的意思是,提高GB /秒,以更好地反映真相)?
#include <sys/time.h>
#include <stdio.h>

template <int N>
__attribute__((noinline))
void loop32(const char *v) {
    for (int i=0; i<N; i+=160) {
        __asm__ ("mov     (%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x04(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x08(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x0c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x10(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x14(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x18(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x1c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x20(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x24(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x28(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x2c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x30(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x34(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x38(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x3c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x40(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x44(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x48(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x4c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x50(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x54(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x58(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x5c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x60(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x64(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x68(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x6c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x70(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x74(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x78(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x7c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x80(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x84(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x88(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x8c(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x90(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x94(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x98(%0), %%eax" : : "r"(v) :"eax");
        __asm__ ("mov 0x9c(%0), %%eax" : : "r"(v) :"eax");
        v += 160;
    }
}

template <int N>
__attribute__((noinline))
void loop64(const char *v) {
    for (int i=0; i<N; i+=160) {
        __asm__ ("mov     (%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x08(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x10(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x18(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x20(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x28(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x30(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x38(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x40(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x48(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x50(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x58(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x60(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x68(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x70(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x78(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x80(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x88(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x90(%0), %%rax" : : "r"(v) :"rax");
        __asm__ ("mov 0x98(%0), %%rax" : : "r"(v) :"rax");
        v += 160;
    }
}

template <int N>
__attribute__((noinline))
void loop128a(const char *v) {
    for (int i=0; i<N; i+=160) {
        __asm__ ("movaps     (%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x10(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x20(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x30(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x40(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x50(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x60(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x70(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x80(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movaps 0x90(%0), %%xmm0" : : "r"(v) :"xmm0");
        v += 160;
    }
}

template <int N>
__attribute__((noinline))
void loop128u(const char *v) {
    for (int i=0; i<N; i+=160) {
        __asm__ ("movups     (%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x10(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x20(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x30(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x40(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x50(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x60(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x70(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x80(%0), %%xmm0" : : "r"(v) :"xmm0");
        __asm__ ("movups 0x90(%0), %%xmm0" : : "r"(v) :"xmm0");
        v += 160;
    }
}

long long int t() {
    struct timeval tv;
    gettimeofday(&tv, 0);
    return (long long int)tv.tv_sec*1000000 + tv.tv_usec;
}

int main() {
    const int ITER = 10;
    const int N = 1600000000;

    char *data = reinterpret_cast<char *>(((reinterpret_cast<unsigned long long>(new char[N+32])+15)&~15));
    for (int i=0; i<N+16; i++) data[i] = 0;

    {
        long long int t0 = t();
        for (int i=0; i<ITER*100000; i++) {
            loop32<N/100000>(data);
        }
        long long int t1 = t();
        for (int i=0; i<ITER*100000; i++) {
            loop32<N/100000>(data+1);
        }
        long long int t2 = t();
        for (int i=0; i<ITER; i++) {
            loop32<N>(data);
        }
        long long int t3 = t();
        for (int i=0; i<ITER; i++) {
            loop32<N>(data+1);
        }
        long long int t4 = t();

        printf(" 32-bit, cache: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3f%%\n", (double)N*ITER/(t1-t0)/1000, (double)N*ITER/(t2-t1)/1000, 100.0*(t2-t1)/(t1-t0)-100.0f);
        printf(" 32-bit,   mem: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3f%%\n", (double)N*ITER/(t3-t2)/1000, (double)N*ITER/(t4-t3)/1000, 100.0*(t4-t3)/(t3-t2)-100.0f);
    }

    {
        long long int t0 = t();
        for (int i=0; i<ITER*100000; i++) {
            loop64<N/100000>(data);
        }
        long long int t1 = t();
        for (int i=0; i<ITER*100000; i++) {
            loop64<N/100000>(data+1);
        }
        long long int t2 = t();
        for (int i=0; i<ITER; i++) {
            loop64<N>(data);
        }
        long long int t3 = t();
        for (int i=0; i<ITER; i++) {
            loop64<N>(data+1);
        }
        long long int t4 = t();

        printf(" 64-bit, cache: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3f%%\n", (double)N*ITER/(t1-t0)/1000, (double)N*ITER/(t2-t1)/1000, 100.0*(t2-t1)/(t1-t0)-100.0f);
        printf(" 64-bit,   mem: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3f%%\n", (double)N*ITER/(t3-t2)/1000, (double)N*ITER/(t4-t3)/1000, 100.0*(t4-t3)/(t3-t2)-100.0f);
    }

    {
        long long int t0 = t();
        for (int i=0; i<ITER*100000; i++) {
            loop128a<N/100000>(data);
        }
        long long int t1 = t();
        for (int i=0; i<ITER*100000; i++) {
            loop128u<N/100000>(data+1);
        }
        long long int t2 = t();
        for (int i=0; i<ITER; i++) {
            loop128a<N>(data);
        }
        long long int t3 = t();
        for (int i=0; i<ITER; i++) {
            loop128u<N>(data+1);
        }
        long long int t4 = t();

        printf("128-bit, cache: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3f%%\n", (double)N*ITER/(t1-t0)/1000, (double)N*ITER/(t2-t1)/1000, 100.0*(t2-t1)/(t1-t0)-100.0f);
        printf("128-bit,   mem: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3f%%\n", (double)N*ITER/(t3-t2)/1000, (double)N*ITER/(t4-t3)/1000, 100.0*(t4-t3)/(t3-t2)-100.0f);
    }
}

4
这个问题最好在SE Code Review上进行提问。 - user0042
1
@geza 如果您有可用的代码,那么将其提交到SE Code Review是一个不错的选择。 - user0042
2
@user0042:是的,但这次问题不是代码质量、算法或类似的东西。它非常低级。但谢谢,如果它被关闭,我会把它移到那里。 - geza
1
@harold:我一发布一个有用的答案,人们就意识到这不是那么糟糕的问题了。它看起来有点像应该在codereview上发表,但实际上它是在询问我在测试内存性能时错过了什么。它只用了几分钟就从-3变成了0 :P - Peter Cordes
2
说句题外话,uarch-bench有一个专门测试L1D中所有对齐方式的负载和存储吞吐量的测试。目前它只在Linux上运行(但是Windows版本应该很容易),通常可以得到精度为1%或更好的结果。对于每个测量的架构,肯定仍然存在一些未对齐的负载惩罚,尽管对于最近的英特尔处理器而言,只有跨越64字节边界的负载才会有影响。这里有更多的结果和讨论here - BeeOnRope
显示剩余8条评论
3个回答

26
计时方法。我可能会设置一个命令行参数来选择测试,这样我可以使用perf stat ./unaligned-test进行计时,并获得性能计数器结果,而不是每个测试的墙钟时间。这样,我就不必担心涡轮增压/省电,因为我可以测量核心时钟周期。 (除非您禁用了涡轮增压和其他频率变化,否则与gettimeofday / rdtsc参考周期不同。)
您只是在测试吞吐量,而不是延迟,因为没有负载相互依赖。您的缓存数字将比内存数字差,但您可能意识不到这是因为您的缓存数字可能由于处理跨越缓存行边界的分裂负载寄存器的数量受到瓶颈的影响。对于顺序读取,外层缓存仍然只会看到整个缓存行的请求序列。只有从L1D获取数据的执行单元才需要关心对齐方式。要测试非缓存情况下的不对齐性,可以进行散布加载,因此缓存行拆分将需要将两个缓存行带入L1。
缓存行宽度为64字节1,因此您总是在测试缓存行分裂和缓存行内访问的混合情况。测试总是分裂负载会更加依赖于分裂负载微架构资源的瓶颈。 (实际上,根据您的CPU,缓存获取宽度可能小于行大小。最近的Intel CPU可以从缓存行内提取任何未对齐的块,但这是因为它们有特殊的硬件使其快速。其他CPU可能只在提取自然对齐的16字节块或类似物时才能达到最高速度。@BeeOnRope说AMD CPU可能关心16字节和32字节的边界。)

您没有测试存储→加载转发。对于现有的测试以及可视化不同对齐方式的结果的好方法,请参阅此 stuffedcow.net 博客文章:x86 处理器中的存储到加载转发和内存消歧义

通过内存传递数据是一个重要的用例,而错位和缓存行分割可能会干扰某些 CPU 上的存储转发。为了正确测试这一点,请确保测试不同的错位,而不仅仅是 1:15(向量)或 1:3(整数)。 (您目前仅测试相对于 16 字节对齐的 +1 偏移量)。

我忘记了它是否仅适用于存储转发还是常规加载,但当负载均匀分布在缓存行边界上时(8:8 向量,可能还有 4:4 或 2:2 整数分割),惩罚可能会更少。您应该测试这个。(我可能在想 P4 lddqu 或 Core 2 movqdu

Intel的优化手册中有大量关于不对齐和从宽存储器到窄重载之间的存储转发表格,这些表格完全包含在其中。在某些CPU上,当宽存储器自然对齐时,即使它没有跨越任何缓存行边界,它也能在更多情况下起作用。(可能是在SnB/IvB上,因为它们使用具有16B银行的分行L1缓存,并且这些分割可以影响存储转发。如果您真的想进行实验测试,那么这是您应该寻找的内容。)


这提醒我,不对齐的负载更容易在SnB/IvB上引发高速缓存冲突(因为一个负载可以触及两个缓存)。但是你不会从单个流中看到这种负载,因为在同一周期内两次访问同一行的相同缓存是可以的。只有在不同行中访问相同缓存的情况下才不能在同一周期内进行。(例如,当两个内存访问相距128字节的倍数时。)
你没有尝试测试4k页面分裂。它们比常规缓存线分裂慢,因为它们还需要进行两个TLB检查。(Skylake将它们从普通的加载使用延迟之外的约100个周期的惩罚改进到了约5个周期的惩罚)

你没有在对齐的地址上测试 movups,因此即使在运行时内存对齐,你也无法检测到 movups 比 Core 2 及更早版本的 movaps 更慢的情况。(我认为在 Core 2 中,非对齐的 mov 负载最多可达8个字节,只要它们不跨越缓存线边界即可。我不知道你需要查看多旧的CPU才能找到在缓存行内的非矢量负载问题。这将是一个仅支持32位的CPU,但你仍然可以使用MMX或SSE甚至x87来测试8字节的负载。P5 Pentium及以后保证对齐的8字节负载/存储是原子性的,但是P6及更高版本保证缓存的8字节负载/存储是原子性的,只要不跨越缓存线边界。与AMD不同,在可缓存的内存中,8字节边界对于原子性保证很重要。为什么在x86上对自然对齐的变量进行整数赋值是原子性的?

我建议去看一下Agner Fog的内容,以了解非对齐加载如何变慢,并编写测试来测试这些情况。实际上,Agner可能不是最好的资源,因为他的微架构指南主要关注的是如何通过流水线获得uops。只有简要提到缓存行分裂的成本,没有深入探讨吞吐量与延迟之间的关系。
此外,还可以参考Cacheline splits, take two,这是Dark Shikari的博客(x264首席开发人员),讨论了Core2上的非对齐加载策略:检查对齐并使用不同的策略来处理块是值得的。
注1:现在64B缓存行是一个安全的假设。 Pentium 3及更早版本具有32B行。 P4具有64B行,但它们通常以128B对齐的方式传输。我记得读到P4实际上在L2或L3中有128B行,但也许那只是64B行成对传输的扭曲。7-CPU明确表示P4 130nm的两个缓存级别都具有64B行

现代Intel CPU的相邻行L2“空间”预取类似地倾向于拉入128字节对齐对的另一半,这可能会在某些情况下增加错误共享。 x86-64的缓存填充大小应该为128字节吗?展示了一个证明这一点的实验。


请参阅 uarch-bench 结果适用于Skylake。显然,已经有人编写了一个测试程序,检查相对于缓存行边界的每个可能的未对齐情况。


我在Skylake桌面电脑上的测试(i7-6700k)

寻址模式会影响加载使用延迟,正如英特尔在其优化手册中所述。我测试了整数mov rax,[rax+...]movzx/sx(在这种情况下将加载的值用作索引,因为它太窄而无法成为指针)。

;;;  Linux x86-64 NASM/YASM source.  Assemble into a static binary
;; public domain, originally written by peter@cordes.ca.
;; Share and enjoy.  If it breaks, you get to keep both pieces.

;;; This kind of grew while I was testing and thinking of things to test
;;; I left in some of the comments, but took out most of them and summarized the results outside this code block
;;; When I thought of something new to test, I'd edit, save, and up-arrow my assemble-and-run shell command
;;; Then edit the result into a comment in the source.

section .bss

ALIGN   2 * 1<<20   ; 2MB = 4096*512.  Uses hugepages in .bss but not in .data.  I checked in /proc/<pid>/smaps
buf:    resb 16 * 1<<20

section .text
global _start
_start:
    mov     esi, 128

;   mov             edx, 64*123 + 8
;   mov             edx, 64*123 + 0
;   mov             edx, 64*64 + 0
    xor             edx,edx
   ;; RAX points into buf, 16B into the last 4k page of a 2M hugepage

    mov             eax, buf + (2<<20)*0 + 4096*511 + 64*0 + 16
    mov             ecx, 25000000

%define ADDR(x)  x                     ; SKL: 4c
;%define ADDR(x)  x + rdx              ; SKL: 5c
;%define ADDR(x)  128+60 + x + rdx*2   ; SKL: 11c cache-line split
;%define ADDR(x)  x-8                 ; SKL: 5c
;%define ADDR(x)  x-7                 ; SKL: 12c for 4k-split (even if it's in the middle of a hugepage)
; ... many more things and a block of other result-recording comments taken out

%define dst rax



        mov             [ADDR(rax)], dst
align 32
.loop:
        mov             dst, [ADDR(rax)]
        mov             dst, [ADDR(rax)]
        mov             dst, [ADDR(rax)]
        mov             dst, [ADDR(rax)]
    dec         ecx
    jnz .loop

        xor edi,edi
        mov eax,231
    syscall

然后运行。
asm-link load-use-latency.asm && disas load-use-latency && 
    perf stat -etask-clock,cycles,L1-dcache-loads,instructions,branches -r4 ./load-use-latency

+ yasm -felf64 -Worphan-labels -gdwarf2 load-use-latency.asm
+ ld -o load-use-latency load-use-latency.o
 (disassembly output so my terminal history has the asm with the perf results)

 Performance counter stats for './load-use-latency' (4 runs):

     91.422838      task-clock:u (msec)       #    0.990 CPUs utilized            ( +-  0.09% )
   400,105,802      cycles:u                  #    4.376 GHz                      ( +-  0.00% )
   100,000,013      L1-dcache-loads:u         # 1093.819 M/sec                    ( +-  0.00% )
   150,000,039      instructions:u            #    0.37  insn per cycle           ( +-  0.00% )
    25,000,031      branches:u                #  273.455 M/sec                    ( +-  0.00% )

   0.092365514 seconds time elapsed                                          ( +-  0.52% )

在这个例子中,我正在测试 mov rax, [rax],自然对齐,因此循环次数 = 4*L1-dcache-loads。4c延迟。我没有禁用Turbo或其他任何东西。由于没有任何东西离开核心,核心时钟周期是衡量的最佳方式。
  • [base + 0..2047]:4c加载使用延迟,11c缓存行分裂,11c 4k页面拆分(即使在同一个大页面内)。有关更多详细信息,请参见当基址和偏移量不在同一页面时是否会有惩罚?:如果base+disp结果在与base不同的页面中,则必须重放加载uop。
  • 任何其他寻址模式:5c延迟,11c缓存行分裂,12c 4k分裂(即使在一个巨大页面内部)。这包括[rax - 16]。这不是disp8与disp32之间的区别。

因此:巨大页面不能帮助避免页面分裂惩罚(至少在TLB中两个页面都是热的时候不行)。缓存行分裂使寻址模式无关紧要,但“快速”寻址模式对于正常和页面分裂负载具有1c较低的延迟。

4k分裂处理比以前好得多,参见@harold的数据,其中Haswell在4k分裂方面具有大约32c的延迟。(而旧CPU可能比那还要糟糕。我认为在SKL之前它应该是大约100个周期的惩罚。)

吞吐量(无论寻址模式如何),通过使用除 rax 之外的目标来测量,以便加载是独立的:

  • 没有分裂:0.5c。
  • CL分裂:1c。
  • 4k分裂:〜3.8到3.9c(比Skylake以前的CPU好得多

movzx / movsx(包括字分裂)的吞吐量/延迟相同,因为它们在加载端口中处理(与一些AMD CPU不同,在那里还有一个ALU uop)。

Uops依赖于缓存行分裂负载从RS(保留站)重新播放。在另一个基本相同的循环中,对于uops_dispatched_port.port_2+port_3的计数= 2x mov rdi,[rdi]的数量。 (这是一个依赖于负载的情况,不是吞吐量限制。)CPU直到AGU生成线性地址后才能检测到分裂负载。
我之前认为分裂负载本身会被重新播放,但这是基于每个负载都依赖于先前负载的指针追踪测试。如果我们在循环中加入imul rdi,rdi,1,我们将得到额外的端口1 ALU计数,因为它会被重新播放,而不是负载。
分裂负载只需要分派一次,但我不确定它是否稍后借用同一负载端口中的周期来访问其他缓存行(并将其与保存在该负载端口内的分裂寄存器中的第一部分组合)。或者,如果L1d中不存在,则启动对另一行的需求加载。

无论细节如何,即使避免了读取重放,缓存行分裂负载的吞吐量也低于非分裂负载。(我们没有测试该过程中的指针追踪。)

关于uop重放,可以参考IvyBridge上在指针追踪循环中由附近相关存储器引起的奇怪性能影响。 添加额外的加载会加速它吗? (但注意,这是针对依赖于加载的操作码,而不是加载操作码本身。 在那个问答中,依赖性操作码也大多是加载操作码。)

缓存未命中的加载不需要自行回放以“接受”数据到来时的传入数据,只有依赖的uop才需要。请参阅Are load ops deallocated from the RS when they dispatch, complete or some other time?中的聊天讨论。这个i7-6700k上的NASM测试用例https://godbolt.org/z/HJF3BN显示无论是L1d hits还是L3 hits,在分派的负载uop数量方面都相同。但是分派的ALU uop的数量(不包括循环开销)从每个加载1个增加到每个加载约8.75个。调度器会在可能从L2高速缓存中到达的加载数据的周期内积极调度使用数据的uops的分派(然后似乎非常积极地继续进行操作),而不是等待一个额外的周期来查看是否已经到达。我们没有测试当存在其他独立但较年轻的工作可以在相同端口上完成且其输入肯定准备好时,回放的积极程度。
SKL有两个硬件页行走单元,这可能与4k分割性能的大幅提升有关。即使没有TLB缺失,老CPU也必须考虑到可能会有缺失。
有趣的是,4k分割吞吐量是非整数的。我认为我的测量具有足够的精度和重复性来证明这一点。请记住,这是每个负载都是4k分割,没有其他工作正在进行(除了在一个小的dec/jnz循环中)。如果你在真正的代码中遇到了这种情况,说明你做错了什么。
我没有任何确切的猜测为什么它可能是非整数的,但显然为了进行4k分割,需要进行许多微架构操作。它仍然是一个缓存行分割,并且必须检查TLB两次。

2
@CodyGray 请记住,缓存行大小并不一定是唯一有趣的边界:对于加载和存储,您通常还有其他更小的“缓存访问大小”边界(尽管在最近的Intel上这也似乎是64字节)。例如,在AMD上,16B和32B边界很重要。您可以在此处找到简短的讨论[http://www.realworldtech.com/forum/?threadid=168200&curpostid=168779]。 - BeeOnRope
1
@PeterCordes - 这里是Ryzen结果,显示对16B和32B边界的依赖性(在这里报告)。行为摘要从此帖子中的“我对Ryzen的看法”开始。 - BeeOnRope
1
顺便说一句,除了没有更新到新的CPU外,我认为这篇博客文章仍然是可视化加载和存储延迟的最佳方式。严格来说,它试图调查存储器到加载器的延迟,但是主对角线之外的条目不重叠,因此它成为存储器和加载器吞吐量测试(您可以清楚地看到即使回到许多代的英特尔只在64B边界的边缘遇到问题)。它清楚地显示了AMD在16B边界周围具有各种有趣的效果。 - BeeOnRope
1
@BeeOnRope:我为代码添加了公共领域声明,以防通常的SO CC-by-SA对任何人都构成问题。这太琐碎了,不值得GPL或其他任何事情的麻烦。 - Peter Cordes
1
@PeterCordes:我预计对于“4K分裂”(其中CPU必须能够容忍不同的缓存 - 例如,一半在“写回”页面上,一半在“非缓存”页面上);CPU的行为就像是完全独立的两次写入(成本增加了一倍)。此外(由于高级分页结构缓存),病态情况可能是“512 G分裂”;可能会出现包装(例如,写入4个字节,使得2个字节进入虚拟地址0xFFFFFFFFFFFFFFFE,另外2个字节进入0x0000000000000000),这是如此恶毒的问题,以至于我不能排除在某些CPU上遇到CPU勘误的可能性。 - Brendan
显示剩余10条评论

4

在测试不同偏移量的64位加载时(以下是代码),我在Haswell上得到的原始结果如下:

aligned L: 4.01115 T: 0.500003
ofs1 L: 4.00919 T: 0.500003
ofs2 L: 4.01494 T: 0.500003
ofs3 L: 4.01403 T: 0.500003
ofs7 L: 4.01073 T: 0.500003
ofs15 L: 4.01937 T: 0.500003
ofs31 L: 4.02107 T: 0.500002
ofs60 L: 9.01482 T: 1
ofs62 L: 9.03644 T: 1
ofs4092 L: 32.3014 T: 31.1967

根据需要进行四舍五入。大多数情况下应该明显地向下取整,但是页面边界跨越的0.3和0.2可能太重要而不是噪声。这只测试了具有简单地址的负载,并且仅限于“纯负载”,没有转发。

我得出结论,对于标量负载,缓存行内的对齐不相关,只有越过缓存行边界(特别是并且出于明显原因)越过页面边界才重要。在这种情况下,在缓存行边界正中间或其他地方越过没有区别。

AMD偶尔会出现一些有趣的16字节边界效果,但我无法测试。

这里是包括“pextrq”影响的原始(!) xmm矢量结果,因此请减去两个延迟周期:

aligned L: 8.05247 T: 0.500003
ofs1 L: 8.03223 T: 0.500003
ofs2 L: 8.02899 T: 0.500003
ofs3 L: 8.05598 T: 0.500003
ofs7 L: 8.03579 T: 0.500002
ofs15 L: 8.02787 T: 0.500003
ofs31 L: 8.05002 T: 0.500003
ofs58 L: 13.0404 T: 1
ofs60 L: 13.0825 T: 1
ofs62 L: 13.0935 T: 1
ofs4092 L: 36.345 T: 31.2357

测试代码是

global test_unaligned_l
proc_frame test_unaligned_l
    alloc_stack 8
[endprolog]
    mov r9, rcx
    rdtscp
    mov r8d, eax

    mov ecx, -10000000
    mov rdx, r9
.loop:
    mov rdx, [rdx]
    mov rdx, [rdx]
    add ecx, 1
    jnc .loop

    rdtscp
    sub eax, r8d

    add rsp, 8
    ret
endproc_frame

global test_unaligned_tp
proc_frame test_unaligned_tp
    alloc_stack 8
[endprolog]
    mov r9, rcx
    rdtscp
    mov r8d, eax

    mov ecx, -10000000
    mov rdx, r9
.loop:
    mov rax, [rdx]
    mov rax, [rdx]
    add ecx, 1
    jnc .loop

    rdtscp
    sub eax, r8d

    add rsp, 8
    ret
endproc_frame

对于向量,在延迟测试中与pextrq类似的向量。

准备了一些在不同偏移量下的数据,例如:

align 64
%rep 31
db 0
%endrep
unaligned31: dq unaligned31
align 4096
%rep 60
db 0
%endrep
unaligned60: dq unaligned60
align 4096
%rep 4092
db 0
%endrep
unaligned4092: dq unaligned4092

为了更加关注新标题,我将描述它的目的以及原因。
首先,进行延迟测试。从不在eax中的某个指针加载一百万个东西到eax中(与问题中的代码相同)测试吞吐量,这只是一半的画面。对于标量加载来说这很简单,对于向量加载来说,我使用了成对的:
movdqu xmm0, [rdx]
pextrq rdx, xmm0, 0
< p > pextrq 的延迟为2,这就是为什么矢量加载的延迟值都比实际高2个单位。

< p > 为了方便进行此延迟测试,数据是一个自引用指针。虽然这是一个相当非典型的场景,但它不应影响负载的定时特性。

< p > 吞吐量测试每个循环有两个负载,而不是一个,以避免被循环开销限制。可以使用更多的负载,但在Haswell(或我所能想到的任何东西,但理论上可能存在具有较低分支吞吐量或更高负载吞吐量的microarchitecture)上不必要。

< p > 我没有非常小心地围栏TSC读取或补偿其开销(或其他开销)。我也没有禁用Turbo,我只让它以Turbo频率运行并除以TSC速率和Turbo频率之间的比率,这可能会稍微影响计时。所有这些效果都与约为1E7的基准测试相比都很小,并且结果可以四舍五入。

所有时间都是30次中的最佳时间,在这些微基准测试中,诸如平均值和方差之类的东西是无意义的,因为基准测试的真实结果不是我们想要估计参数的随机过程,而是一些固定的整数1(或者对于吞吐量来说是整数倍的分数)。几乎所有的噪音都是正的,除了基准测试指令“泄漏”到第一个TSC读取之前的(相对理论上的)情况(如果必要,甚至可以避免这种情况),因此取最小值是适当的。

注1:除了显然跨越4k边界时,会发生一些奇怪的事情。


均等分配的事情可能只适用于存储转发,而不适用于负载。或者对于负载来说,在Core2或其他某些处理器上可能更有效率,但在Haswell上不是这样。 - Peter Cordes
关于汇编语言的风格问题。align指令可以在BSS段中使用,因此您可以使用resb指令。或者您也可以使用times 4092 db 0代替%rep指令。 - Peter Cordes
@PeterCordes,这似乎对延迟测试有用,我想我还可以将BSS中的一个零添加到指针中。 - harold
顺便提一下,如果你测试不同的寻址模式,你应该会发现[base + 0..2047]有4个时钟周期的加载使用延迟,而其他任何模式都有5个时钟周期的延迟。英特尔的手册上说了这个,我在SKL-S上也证实了这个。CL-split不关心寻址模式:对于缓存行分裂,有11个时钟周期的加载使用延迟。但是对于快速寻址模式,4k分裂的总加载使用延迟也是11个时钟周期,其他寻址模式则为12个时钟周期。(这些都是针对64位整数mov加载和movzx/sx字->双字或四字加载的)。 - Peter Cordes
@PeterCordes 把它放在你的答案里,否则没人会看到,那就浪费了。你有关于页面分裂的非整数时间来自哪里的任何理论吗? - harold
显示剩余8条评论

2
我在这里放置了我的一点改进后的基准测试结果。仍然只测量吞吐量(仅非对齐偏移1)。根据其他答案,我添加了测量64字节和4096字节分裂的功能。
对于4k分割,有很大的差异!但是如果数据不跨越64字节边界,则根本没有速度损失(至少对于我测试过的这两个处理器而言)。
从这些数字(以及其他答案中的数字)来看,我的结论是,非对齐访问通常很快(无论是吞吐量还是延迟),但有时可能会慢得多。但这并不意味着它们的使用被不鼓励。
我的基准测试产生的原始数字应该带有一定的保留(很可能一个正确编写的汇编代码优于它),但这些结果大多与哈罗德的Haswell答案(差异列)相符。
Haswell:

Full:
 32-bit, cache: aligned:  33.2901 GB/sec unaligned:  29.5063 GB/sec, difference: 1.128x
 32-bit,   mem: aligned:  12.1597 GB/sec unaligned:  12.0659 GB/sec, difference: 1.008x
 64-bit, cache: aligned:  66.0368 GB/sec unaligned:  52.8914 GB/sec, difference: 1.249x
 64-bit,   mem: aligned:  16.1317 GB/sec unaligned:  16.0568 GB/sec, difference: 1.005x
128-bit, cache: aligned: 129.8730 GB/sec unaligned:  87.9791 GB/sec, difference: 1.476x
128-bit,   mem: aligned:  16.8150 GB/sec unaligned:  16.8151 GB/sec, difference: 1.000x

JustBoundary64:
 32-bit, cache: aligned:  32.5555 GB/sec unaligned:  16.0175 GB/sec, difference: 2.032x
 32-bit,   mem: aligned:   1.0044 GB/sec unaligned:   1.0001 GB/sec, difference: 1.004x
 64-bit, cache: aligned:  65.2707 GB/sec unaligned:  32.0431 GB/sec, difference: 2.037x
 64-bit,   mem: aligned:   2.0093 GB/sec unaligned:   2.0007 GB/sec, difference: 1.004x
128-bit, cache: aligned: 130.6789 GB/sec unaligned:  64.0851 GB/sec, difference: 2.039x
128-bit,   mem: aligned:   4.0180 GB/sec unaligned:   3.9994 GB/sec, difference: 1.005x

WithoutBoundary64:
 32-bit, cache: aligned:  33.2911 GB/sec unaligned:  33.2916 GB/sec, difference: 1.000x
 32-bit,   mem: aligned:  11.6156 GB/sec unaligned:  11.6223 GB/sec, difference: 0.999x
 64-bit, cache: aligned:  65.9117 GB/sec unaligned:  65.9548 GB/sec, difference: 0.999x
 64-bit,   mem: aligned:  14.3200 GB/sec unaligned:  14.3027 GB/sec, difference: 1.001x
128-bit, cache: aligned: 128.2605 GB/sec unaligned: 128.3342 GB/sec, difference: 0.999x
128-bit,   mem: aligned:  12.6352 GB/sec unaligned:  12.6218 GB/sec, difference: 1.001x

JustBoundary4096:
 32-bit, cache: aligned:  33.5500 GB/sec unaligned:   0.5415 GB/sec, difference: 61.953x
 32-bit,   mem: aligned:   0.4527 GB/sec unaligned:   0.0431 GB/sec, difference: 10.515x
 64-bit, cache: aligned:  67.1141 GB/sec unaligned:   1.0836 GB/sec, difference: 61.937x
 64-bit,   mem: aligned:   0.9112 GB/sec unaligned:   0.0861 GB/sec, difference: 10.582x
128-bit, cache: aligned: 134.2000 GB/sec unaligned:   2.1668 GB/sec, difference: 61.936x
128-bit,   mem: aligned:   1.8165 GB/sec unaligned:   0.1700 GB/sec, difference: 10.687x

Sandy Bridge (processor from 2011)

Full:
 32-bit, cache: aligned:  30.0302 GB/sec unaligned:  26.2587 GB/sec, difference: 1.144x
 32-bit,   mem: aligned:  11.0317 GB/sec unaligned:  10.9358 GB/sec, difference: 1.009x
 64-bit, cache: aligned:  59.2220 GB/sec unaligned:  41.5515 GB/sec, difference: 1.425x
 64-bit,   mem: aligned:  14.5985 GB/sec unaligned:  14.3760 GB/sec, difference: 1.015x
128-bit, cache: aligned: 115.7643 GB/sec unaligned:  45.0905 GB/sec, difference: 2.567x
128-bit,   mem: aligned:  14.8561 GB/sec unaligned:  14.8220 GB/sec, difference: 1.002x

JustBoundary64:
 32-bit, cache: aligned:  15.2127 GB/sec unaligned:   3.1037 GB/sec, difference: 4.902x
 32-bit,   mem: aligned:   0.9870 GB/sec unaligned:   0.6110 GB/sec, difference: 1.615x
 64-bit, cache: aligned:  30.2074 GB/sec unaligned:   6.2258 GB/sec, difference: 4.852x
 64-bit,   mem: aligned:   1.9739 GB/sec unaligned:   1.2194 GB/sec, difference: 1.619x
128-bit, cache: aligned:  60.7265 GB/sec unaligned:  12.4007 GB/sec, difference: 4.897x
128-bit,   mem: aligned:   3.9443 GB/sec unaligned:   2.4460 GB/sec, difference: 1.613x

WithoutBoundary64:
 32-bit, cache: aligned:  30.0348 GB/sec unaligned:  29.9801 GB/sec, difference: 1.002x
 32-bit,   mem: aligned:  10.7067 GB/sec unaligned:  10.6755 GB/sec, difference: 1.003x
 64-bit, cache: aligned:  59.1895 GB/sec unaligned:  59.1925 GB/sec, difference: 1.000x
 64-bit,   mem: aligned:  12.9404 GB/sec unaligned:  12.9307 GB/sec, difference: 1.001x
128-bit, cache: aligned: 116.4629 GB/sec unaligned: 116.0778 GB/sec, difference: 1.003x
128-bit,   mem: aligned:  11.2963 GB/sec unaligned:  11.3533 GB/sec, difference: 0.995x

JustBoundary4096:
 32-bit, cache: aligned:  30.2457 GB/sec unaligned:   0.5626 GB/sec, difference: 53.760x
 32-bit,   mem: aligned:   0.4055 GB/sec unaligned:   0.0275 GB/sec, difference: 14.726x
 64-bit, cache: aligned:  60.6175 GB/sec unaligned:   1.1257 GB/sec, difference: 53.851x
 64-bit,   mem: aligned:   0.8150 GB/sec unaligned:   0.0551 GB/sec, difference: 14.798x
128-bit, cache: aligned: 121.2121 GB/sec unaligned:   2.2455 GB/sec, difference: 53.979x
128-bit,   mem: aligned:   1.6255 GB/sec unaligned:   0.1103 GB/sec, difference: 14.744x

这是代码:

#include <sys/time.h>
#include <stdio.h>

__attribute__((always_inline))
void load32(const char *v) {
    __asm__ ("mov     %0, %%eax" : : "m"(*v) :"eax");
}

__attribute__((always_inline))
void load64(const char *v) {
    __asm__ ("mov     %0, %%rax" : : "m"(*v) :"rax");
}

__attribute__((always_inline))
void load128a(const char *v) {
    __asm__ ("movaps     %0, %%xmm0" : : "m"(*v) :"xmm0");
}

__attribute__((always_inline))
void load128u(const char *v) {
    __asm__ ("movups     %0, %%xmm0" : : "m"(*v) :"xmm0");
}

struct Full {
    template <int S>
    static float factor() {
        return 1.0f;
    }
    template <void (*LOAD)(const char *), int S, int N>
    static void loop(const char *v) {
        for (int i=0; i<N; i+=S*16) {
            LOAD(v+S* 0);
            LOAD(v+S* 1);
            LOAD(v+S* 2);
            LOAD(v+S* 3);
            LOAD(v+S* 4);
            LOAD(v+S* 5);
            LOAD(v+S* 6);
            LOAD(v+S* 7);
            LOAD(v+S* 8);
            LOAD(v+S* 9);
            LOAD(v+S*10);
            LOAD(v+S*11);
            LOAD(v+S*12);
            LOAD(v+S*13);
            LOAD(v+S*14);
            LOAD(v+S*15);
            v += S*16;
        }
    }
};

struct JustBoundary64 {
    template <int S>
    static float factor() {
        return S/64.0f;
    }
    template <void (*LOAD)(const char *), int S, int N>
    static void loop(const char *v) {
        static_assert(N%(64*16)==0);
        for (int i=0; i<N; i+=64*16) {
            LOAD(v+64* 1-S);
            LOAD(v+64* 2-S);
            LOAD(v+64* 3-S);
            LOAD(v+64* 4-S);
            LOAD(v+64* 5-S);
            LOAD(v+64* 6-S);
            LOAD(v+64* 7-S);
            LOAD(v+64* 8-S);
            LOAD(v+64* 9-S);
            LOAD(v+64*10-S);
            LOAD(v+64*11-S);
            LOAD(v+64*12-S);
            LOAD(v+64*13-S);
            LOAD(v+64*14-S);
            LOAD(v+64*15-S);
            LOAD(v+64*16-S);
            v += 64*16;
        }
    }
};

struct WithoutBoundary64 {
    template <int S>
    static float factor() {
        return (64-S)/64.0f;
    }
    template <void (*LOAD)(const char *), int S, int N>
    static void loop(const char *v) {
        for (int i=0; i<N; i+=S*16) {
            if ((S* 1)&0x3f) LOAD(v+S* 0);
            if ((S* 2)&0x3f) LOAD(v+S* 1);
            if ((S* 3)&0x3f) LOAD(v+S* 2);
            if ((S* 4)&0x3f) LOAD(v+S* 3);
            if ((S* 5)&0x3f) LOAD(v+S* 4);
            if ((S* 6)&0x3f) LOAD(v+S* 5);
            if ((S* 7)&0x3f) LOAD(v+S* 6);
            if ((S* 8)&0x3f) LOAD(v+S* 7);
            if ((S* 9)&0x3f) LOAD(v+S* 8);
            if ((S*10)&0x3f) LOAD(v+S* 9);
            if ((S*11)&0x3f) LOAD(v+S*10);
            if ((S*12)&0x3f) LOAD(v+S*11);
            if ((S*13)&0x3f) LOAD(v+S*12);
            if ((S*14)&0x3f) LOAD(v+S*13);
            if ((S*15)&0x3f) LOAD(v+S*14);
            if ((S*16)&0x3f) LOAD(v+S*15);
            v += S*16;
        }
    }
};

struct JustBoundary4096 {
    template <int S>
    static float factor() {
        return S/4096.0f;
    }
    template <void (*LOAD)(const char *), int S, int N>
    static void loop(const char *v) {
        static_assert(N%(4096*4)==0);
        for (int i=0; i<N; i+=4096*4) {
            LOAD(v+4096*1-S);
            LOAD(v+4096*2-S);
            LOAD(v+4096*3-S);
            LOAD(v+4096*4-S);
            v += 4096*4;
        }
    }
};


long long int t() {
    struct timeval tv;
    gettimeofday(&tv, 0);
    return (long long int)tv.tv_sec*1000000 + tv.tv_usec;
}

template <typename TYPE, void (*LOADa)(const char *), void (*LOADu)(const char *), int S, int N>
void bench(const char *data, int iter, const char *name) {
    long long int t0 = t();
    for (int i=0; i<iter*100000; i++) {
        TYPE::template loop<LOADa, S, N/100000>(data);
    }
    long long int t1 = t();
    for (int i=0; i<iter*100000; i++) {
        TYPE::template loop<LOADu, S, N/100000>(data+1);
    }
    long long int t2 = t();
    for (int i=0; i<iter; i++) {
        TYPE::template loop<LOADa, S, N>(data);
    }
    long long int t3 = t();
    for (int i=0; i<iter; i++) {
        TYPE::template loop<LOADu, S, N>(data+1);
    }
    long long int t4 = t();

    printf("%s-bit, cache: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3fx\n", name, (double)N*iter/(t1-t0)/1000*TYPE::template factor<S>(), (double)N*iter/(t2-t1)/1000*TYPE::template factor<S>(), (float)(t2-t1)/(t1-t0));
    printf("%s-bit,   mem: aligned: %8.4f GB/sec unaligned: %8.4f GB/sec, difference: %0.3fx\n", name, (double)N*iter/(t3-t2)/1000*TYPE::template factor<S>(), (double)N*iter/(t4-t3)/1000*TYPE::template factor<S>(), (float)(t4-t3)/(t3-t2));
}

int main() {
    const int ITER = 10;
    const int N = 1638400000;

    char *data = reinterpret_cast<char *>(((reinterpret_cast<unsigned long long>(new char[N+8192])+4095)&~4095));
    for (int i=0; i<N+8192; i++) data[i] = 0;

    printf("Full:\n");
    bench<Full, load32, load32, 4, N>(data, ITER, " 32");
    bench<Full, load64, load64, 8, N>(data, ITER, " 64");
    bench<Full, load128a, load128u, 16, N>(data, ITER, "128");

    printf("\nJustBoundary64:\n");
    bench<JustBoundary64, load32, load32, 4, N>(data, ITER, " 32");
    bench<JustBoundary64, load64, load64, 8, N>(data, ITER, " 64");
    bench<JustBoundary64, load128a, load128u, 16, N>(data, ITER, "128");

    printf("\nWithoutBoundary64:\n");
    bench<WithoutBoundary64, load32, load32, 4, N>(data, ITER, " 32");
    bench<WithoutBoundary64, load64, load64, 8, N>(data, ITER, " 64");
    bench<WithoutBoundary64, load128a, load128u, 16, N>(data, ITER, "128");

    printf("\nJustBoundary4096:\n");
    bench<JustBoundary4096, load32, load32, 4, N>(data, ITER*10, " 32");
    bench<JustBoundary4096, load64, load64, 8, N>(data, ITER*10, " 64");
    bench<JustBoundary4096, load128a, load128u, 16, N>(data, ITER*10, "128");
}

在不显示每个周期或每秒钟的负载的情况下以GB/s打印数字并不那么有用,特别是对于整数负载而言。这只会使比较不同大小的数字更加困难。众所周知,在命中L1时,通常会出现负载端口uop吞吐量瓶颈,而不是带宽本身。 - Peter Cordes
你可能需要更长的热身时间或者其他什么,因为在不同的测试中,你的“对齐”数字是不同的。(这就是为什么我喜欢用 Perf 计数器来测量核心时钟周期,而不是时间或“参考周期”(其实也只是时间)。) - Peter Cordes
@PeterCordes:是的,看着这些数字,我现在知道瓶颈在哪里了。:) 我尝试了一个更长的测试(运行了30分钟),但对齐的数字仍然不同。是的,性能计数器是一种更好的方法,但我不知道如何在没有外部实用程序的情况下访问它们(也许我会研究一下这个问题)。我使用cpufreq-set将CPU频率设置为最大值,使用gettimeofday得到的数字对我来说还可以(它的变化小于1%)。 - geza
1
是的,perf stat 比使用 perf-counter 库要容易得多(我也从未尝试过)。这就是为什么我建议(在我的答案中)每次调用程序都进行一次测试,由命令行参数控制。因此,通过一个小的几乎恒定的启动开销(特别是对于静态二进制文件),您可以获得简单的性能计数器。这通常是我为微基准测试做的事情,例如,在 .c.cpp 中将 main(){ ... } 放在 #ifdef 中,并使用我正在调整的函数。 - Peter Cordes
1
请记住,与 CPU 绑定的测试相比,与内存相关的测试往往会显示出更多的变化。即使使用 perf 从外部测量,在关闭超线程和 Turbo 的情况下,CPU 绑定测试的变化率也很容易达到 0.1% 或 0.01%,但 L3 和内存是共享资源,我经常看到 10% 或更大的变化率。即使只是在后台打开一个浏览器也可能会产生很大的影响。您可能希望运行测试 100 次,这时“典型”的最大值就会变得明显。通过图形方式查看结果通常也可以明显地看出渐近线。 - BeeOnRope

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接