python - 为什么使用 np.empty 进行分配而不是 O(1)

Question

官方上是这么说的numpy docs

Return a new array of given shape and type, without initializing entries.

为 np.empty ，这意味着创建(分配)这个数组所花费的时间将是 O(1)，但在 timeit 中进行了一些简单的测试表明情况并非如此:

>>> timeit.timeit(lambda: np.empty(100000000 ), number=10000)
0.2733485999999914
>>> timeit.timeit(lambda: np.empty(1000000000), number=10000)
0.8293009999999867

作为一个附带问题，未触及 np.empty 中存在的值是什么？大批？它们都是非常小的值，但我希望它们只是该地址内存中存在的任何值。 (示例数组: np.empty(2) = array([-6.42940774e-036, 2.07409447e-117]) 。这些看起来不像存储在内存中的东西)

Answer 1

首先，我尝试在我的机器上用各种尺寸重现这种行为。以下是原始结果:

np.empty(10**1)   # 421 ns ± 23.7 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**2)   # 406 ns ± 1.44 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**3)   # 471 ns ± 5.8 ns per loop     (on 7 runs, 1000000 loops each)
np.empty(10**4)   # 616 ns ± 1.56 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**5)   # 620 ns ± 2.83 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**6)   # 9.61 µs ± 34.2 ns per loop   (on 7 runs, 100000 loops each)
np.empty(10**7)   # 11.1 µs ± 17.6 ns per loop   (on 7 runs, 100000 loops each)
np.empty(10**8)   # 22.1 µs ± 173 ns per loop    (on 7 runs, 10000 loops each)
np.empty(10**9)   # 62.8 µs ± 220 ns per loop    (on 7 runs, 10000 loops each)
np.empty(10**10)  # => Memory Error

因此，您是对的:这没有完成是 O(1) (至少在我的 Windows 机器和你的系统上也是如此)。请注意，在这么短的时间内无法(热切地)初始化这些值，因为这意味着 RAM 吞吐量超过 127 TB/s，而我的机器上显然没有这种吞吐量。

for np.empty, which would imply that the time taken to create (allocate) this array would be O(1)

分配在 O(1) 中完成的假设不完全正确 .为了检查这一点，我构建了一个简单的 C 程序，执行一个简单的 malloc + free循环并测量时间。以下是原始结果:

./malloc.exe 10           # Average time:  41.815 ns (on 1 run, 1000000 loops each)
./malloc.exe 100          # Average time:  45.295 ns (on 1 run, 1000000 loops each)
./malloc.exe 1000         # Average time:  47.400 ns (on 1 run, 1000000 loops each)
./malloc.exe 10000        # Average time: 122.457 ns (on 1 run, 1000000 loops each)
./malloc.exe 100000       # Average time: 123.032 ns (on 1 run, 1000000 loops each)
./malloc.exe 1000000      # Average time:   8.351 us (on 1 run, 1000000 loops each)
./malloc.exe 10000000     # Average time:   9.342 us (on 1 run, 100000 loops each)
./malloc.exe 100000000    # Average time:  18.972 us (on 1 run, 10000 loops each)
./malloc.exe 1000000000   # Average time:  64.527 us (on 1 run, 10000 loops each)
./malloc.exe 10000000000  # => Memory error

如您所见，结果与 Numpy 的结果匹配(除了由于在 CPython 中调用 Python 函数的开销较小的结果)。因此，问题不是来自 Numpy，而是标准 libc 中的分配算法或操作系统本身。

As a side question, what are the values present in an untouched np.empty array?

是 未初始化的数据 .在实践中，它通常是零初始化(但并非总是如此)，因为主流平台出于安全原因清理分配的内存(以便密码等关键数据在之前存储在另一个进程的内存中时不会泄漏)。 你不应该依赖这个 .
malloc更深入的解释时间:
如您所见，100K 项和 1M 项的分配之间存在差距。这可以通过使用 来解释。快速用户空间分配器 (在Unix和Linux系统上称为 sbrk):当数据较小时，大多数主流平台的libc不会直接向操作系统请求内存。它宁愿使用快速 预分配的本地内存池 .实际上，在大多数主流平台上，预先分配了多个不同大小的池，libc 根据分配的大小选择“正确的”，因此小数据大小的时间变化。注意这个过程是为了提高分配速度同时考虑到 memory fragmentation .这种策略要快得多，因为内核调用(如 mmap )非常昂贵(在我的机器上至少需要几微秒)。
此外，大多数操作系统 (OS) 看起来像多个内存池。 Linux、MacOS 和 Windows 将虚拟内存拆分为小页面(通常为 4KB)。由于在处理 GB/TB 的已分配数据时处理太小的页面会带来显着的开销，因此这些操作系统还提供称为 super 页面或大页面(通常为 2MB 到几 GB)的大页面。操作系统中采用的路径可能会根据分配的内存量和大多数 发生变化。操作系统针对分配小块进行了优化 虚拟内存而不是大内存。
请注意，用于管理系统内存的数据结构的大小通常受 RAM 大小的限制，而 RAM 大小通常在运行时保持不变。此外，在给定操作系统中用于管理内存碎片的算法的复杂性理论上可能是 O(1) (或接近那个)。因此，有些人认为分配/释放数据是在恒定时间内完成的。但这引起争议，因为人们应该考虑实际结果而不仅仅是理论 渐近界 .

有关更多信息，您可以查看以下帖子:

Time complexity of memory allocation

What is the time complexity of free?

Why does malloc initialize the values to 0 in gcc?

Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?

Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?