是什么导致从数组的 RAM 中查找 log(N) 时间？

Question

O(log(n)) 检索 RAM 中的项目

我一直在运行一些计时实验，以确定i从alength数组中检索随机元素需要多长时间n，并且发现我的硬件大约需要 log(n)。我试图推断是硬件\架构的哪一点导致了这个，或者可能是负责任的。（理想情况下，可引用的技术参考是我所追求的）。

代码是什么样的

它是类似于以下内容的 C 代码：

unsigned long long int n; // Some very big number!
double * lookup_table = malloc(sizeof(double) * n); // So big it only fits in RAM
unsigned long long int i = UNIFORM_RNG(0, n); // Integer in [0, n)
double x = lookup_table[i];

关键思想是有一个大数组lookup_table，我将随机需要其条目（因此我可以有信心地预期缓存/页面未命中）。数组太大了，我知道需要从 RAM 中挖掘出该值。

上面的部分代码包含在一个 for 循环中，所以我有一定的信心我正在计时我认为我计时并具有所需的精度。

相关问题

程序访问 RAM 需要多长时间？（提到 O(1) 和 O(log(n)) 但似乎没有提供任何指向硬件的解释）。

我一直在使用的硬件

64 位 x86 Intel Xeon Gold 6140 CPU，在 Ubuntu 16.04.3 LTS 发行版下的 GNU/Linux 4.13.0-25-generic 下以 2.3GHz 运行。C代码使用英特尔的C编译器在编译icc18.0.0与标志 mkl，std=c11，qopenmp，qopt-report，O2，march=skylake-avx512， xCORE-AVX512，和qopt-zmm-usage=high。

Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              72
On-line CPU(s) list: 0-71
Thread(s) per core:  2
Core(s) per socket:  18
Socket(s):           2
NUMA node(s):        2
Vendor ID:           GenuineIntel
CPU family:          6
Model:               85
Model name:          Intel(R) Xeon(R) Gold 6140 CPU @ 2.30GHz
Stepping:            4
CPU MHz:             1000.410
BogoMIPS:            4600.00
Virtualisation:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            1024K
L3 cache:            25344K
NUMA node0 CPU(s):   0-17,36-53
NUMA node1 CPU(s):   18-35,54-71
Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb cat_l3 cdp_l3 invpcid_single pti intel_ppin ssbd mba ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm cqm mpx rdt_a avx512f avx512dq rdseed adx smap clflushopt clwb intel_pt avx512cd avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local dtherm ida arat pln pts hwp_epp pku ospke md_clear flush_l1d