Memory access is O(N^[1/3])

In computer science, we often compare the efficiency of algorithms by describing their runtime as a function of the size of the input.

在计算机科学中，我们经常通过将算法的运行时间描述为输入大小的函数来比较算法的效率。

Sorting is O(n * log(n)), meaning that sorting a list of N items takes an amount of time proportional to the number of items multiplied by its logarithm.

排序的时间复杂度为 O(n * log(n))，这意味着对 N 个项目的列表进行排序所需的时间与项目数量乘以其对数成正比。

Matrix multiplication is somewhere between 2.37 and 2.8 , depending on the choice of algorithm.

矩阵乘法介于 2.37 和 2.8 之间，具体取决于算法的选择。

But these estimates are all relative to some model of how long it takes for the underlying machine to perform some basic underlying operations.

但这些估计都与底层机器执行一些基本底层操作所需时间的某种模型有关。

Typically, arithmetic operations (addition, multiplication, division...) are considered to take one unit of time for fixed-size numbers, and memory accesses are also considered to take one unit of time.

通常，算术运算（加法、乘法、除法...）被认为对于固定大小的数字需要一个单位时间，并且存储器访问也被认为需要一个单位时间。

In this post, I will argue that this choice for memory access is wrong.

在这篇文章中，我将论证这种内存访问的选择是错误的。

Memory access, both in theory and in practice, takes O(N^⅓) time: if your memory is 8x bigger, it will take 2x longer to do a read or write to it.

内存访问，无论是在理论上还是在实践中，都需要 O(N^⅓) 时间：如果内存增大 8 倍，则对其进行读取或写入所需的时间将增加 2 倍。

I will also show an example of an application where this concretely matters.

我还将展示一个具体重要的应用程序示例。

Imagine you have a processor sitting in the middle of a pile of memory.

想象一下，您有一个处理器位于一堆内存中间。

The processor's ability to talk to any individual piece of memory is bounded by the speed of light, ergo the delay is proportional to distance.

处理器与任何单独内存块通信的能力受到光速的限制，因此延迟与距离成正比。

In a three-dimensional world, you can fit 8x as much memory within 2x the distance from you.

在三维世界中，你可以在距离你 2 倍的距离内容纳 8 倍的内存。

This covers sequential access.

这涵盖了顺序访问。

In practice, of course, a CPU is not literally situated inside of a homogeneous cube of memory, and electrical signals don't travel exactly in a straight line (and, for that matter, are slower than light).

当然，实际上，CPU 并不真正位于同质的内存立方体内部，电信号也不会完全沿直线传播（就此而言，信号比光慢）。

But, as we will see later, the model is surprisingly close to accurate in practice.

但是，正如我们稍后将看到的，该模型在实践中惊人地接近准确。

For parallel access, things get more subtle and depend on the medium.

对于并行访问，事情变得更加微妙并且取决于媒介。

If you think of read and write as occupying a "wire" of the needed length for a fixed length of time, then you get the same result: 8x the memory, 2x the wire length * time.

如果您将读取和写入视为在固定时间长度内占用所需长度的“线路”，那么您会得到相同的结果：8 倍内存，2 倍线路长度 * 时间。

If you think of it as a signal made out of light that takes some amount of energy, where its intensity needs to take into account dispersal, then 8x the memory implies 2x the length which implies 4x the energy required for a single access.

如果您将其视为由需要一定能量的光组成的信号，其中其强度需要考虑扩散，那么 8 倍的内存意味着 2 倍的长度，这意味着单次访问所需的能量为 4 倍。

This can be mitigated by having repeaters repeat the signal in the middle, but that starts to get us closer again to wires.

这可以通过让中继器在中间重复信号来缓解，但这开始让我们再次接近电线。

So O(N^⅓) is probably the better model.

所以 O(N^⅓) 可能是更好的模型。

Computers in reality have different types of memory: registers, different levels of cache, and RAM.

现实中的计算机有不同类型的内存：寄存器、不同级别的缓存和 RAM。

We'll omit SSD/HDDs from here because they have additional requirements on top: persistent storage without energy requirements, and lower cost per bit.

我们将在这里省略 SSD/HDD，因为它们还有额外的要求：无能源要求的持久存储，以及较低的每比特成本。

We can ask a question: how long (in nanoseconds) does it take to access a type of memory of which an average laptop has N bytes?

我们可以问一个问题：访问普通笔记本电脑有 N 字节的内存类型需要多长时间（以纳秒为单位）？

Here's GPT's answer:

GPT 的回答如下：

As it turns out, a naive formula of treating access time as the cube root of the amount of memory accessed gets us surprisingly close.

事实证明，将访问时间视为访问内存量的立方根的简单公式让我们出人意料地接近。

Note that here the fit is considerably worse, which is to be expected: compared to latency, bandwidth is much less about fundamental application of physics principles and much more about architecture choices.

请注意，这里的拟合度要差得多，这是可以预料的：与延迟相比，带宽与物理原理的基本应用的关系要小得多，而与架构选择的关系要大得多。

L3 cache is not built for mass throughput in the same way that DRAM is, and so it has roughly identical mass throughput despite its much closer distance to the computation.

L3 缓存并不是像 DRAM 那样为海量吞吐量而构建的，因此尽管它与计算的距离更近，但它具有大致相同的海量吞吐量。

I can give a concrete example of why this all matters that I ran into myself a year ago: optimized implementations of various algorithms that precompute and reuse intermediate values .

我可以举一个具体的例子来说明为什么我一年前遇到的这一切都很重要：预先计算和重用中间值的各种算法的优化实现。

Often, especially in cryptography, it is the case that you have a mathematical procedure that involves N steps, where in each step, depending on one bit of the input, you either "mix in" a particular value or you don't.

通常，特别是在密码学中，您有一个涉及 N 个步骤的数学过程，其中在每个步骤中，根据输入的一位，您要么“混合”一个特定值，要么不“混合”一个特定值。

The "mixing in" is often an associative operation.

“混合”通常是关联操作。

Such a procedure can be done naively in N steps, in N/8 steps if you precompute 256 values for each step, in N/16 steps if you precompute 65536 values for each step, and so on.

这样的过程可以简单地通过 N 个步骤完成，如果为每个步骤预先计算 256 个值，则需要 N/8 个步骤；如果为每个步骤预先计算 65536 个值，则需要 N/16 个步骤，等等。

Examples of this include elliptic curve multiplication, binary field math (see eg.

这方面的例子包括椭圆曲线乘法、二进制域数学（参见例如

my implementation here ), and many other algorithms.

我的实现在这里），以及许多其他算法。

A surprisingly widely applicable way to optimize cryptography.

一种令人惊讶的广泛适用的优化密码学的方法。

How big should you make the precomputed table?

您应该将预计算表设置为多大？

If you treat a memory access as O(1), then the answer is clear: as big as your machine has memory.

如果将内存访问视为 O(1)，那么答案很明确：与机器的内存大小相同。

But if you treat memory access as O(N^⅓), then it becomes a more subtle tradeoff: you have to optimize N^⅓ / log(N) , and the optimal value is always some "interior solution" (ie.

但是如果你将内存访问视为 O(N^⅓) ，那么它就变成了一个更微妙的权衡：你必须优化 N^⅓ / log(N) ，并且最佳值始终是一些“内部解决方案”（即

not 1 and not "as much as you can") whose exact position depends on the constants involved.

不是 1 也不是“尽可能多”），其确切位置取决于所涉及的常数。

In my binary field code, I found that an 8-bit precomputation table (in that context, 2 24 items taking up 128 MB) led to faster computations than a 16-bit precomputation table (2 32 items taking up 8 GB): while the latter fit into RAM, the former could fit into cache, and the faster access time of the former was decisive.

在我的二进制字段代码中，我发现 8 位预计算表（在这种情况下，2 24 个项目占用 128 MB）比 16 位预计算表（2 32 个项目占用 8 GB）计算速度更快：后者适合 RAM，前者可以适合缓存，而前者更快的访问时间是决定性的。

In the longer term, we are in an era right now where we are approaching the limits of general-purpose CPUs, and people are increasingly exploring ASICs for various tasks.

从长远来看，我们现在正处于一个正在接近通用 CPU 极限的时代，人们越来越多地探索 ASIC 来执行各种任务。

Here, the structure of the ASIC matters.

在这里，ASIC 的结构很重要。

If you can break up a task into many parts, each of which is highly local, then memory access in each part will be O(1) .

如果您可以将一个任务分解为许多部分，每个部分都是高度本地化的，那么每个部分的内存访问将是 O(1) 。

GPUs are already often very good at getting precisely these kinds of efficiencies.

GPU 通常已经非常擅长精确地获得此类效率。

But if the task requires a lot of memory interdependencies, then you will get lots of O(N^⅓) terms.

但如果任务需要大量的内存相互依赖，那么你将得到很多 O(N^⅓) 项。

An open problem is coming up with mathematical models of computation that are simple but do a good job of capturing these nuances.

一个悬而未决的问题是提出简单的计算数学模型，但可以很好地捕捉这些细微差别。