python - CPython 和 PyPy 如何决定何时调整集合的大小？

Question

在 CPython 和 PyPy 上向集合中添加元素时，何时调整它们的大小，以及底层容器的大小是多少？

这个问题在原理上与max_load_factor类似，as C++ describes it for their unordered_map .

Answer 1

CPython 使用this check决定何时调整大小:

if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))

这基本上意味着当 2/3 满时，容器将调整大小。

调整大小本身会使大集合的空间量增加一倍，而将小集合的空间量增加四倍:

return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);

Armin Rigo 在评论中指出 PyPy 使用字典实现其集合，因此 relevant resizing code是:

jit.conditional_call(d.resize_counter <= x * 3,
                     _ll_dict_resize_to, d, num_extra)

这是相同的策略，因为 resize_counter 是字典中剩余的空白空间。

<小时/>

在指出这一点之前，我诉诸了基准测试。您可以通过查找非常小的停顿来检测大小调整。对于小尺寸来说，这有点随机，因此您必须小心消除噪音。这是执行此操作的脚本:

from collections import Counter
import time

iterations = 100
internal_iterations = 100000

def main():
    resizes = Counter()

    for i in range(iterations):
        print("Completion: [{:3.0%}]\r".format(i/iterations), end="")

        s = set()
        maxtime_so_far = 0
        for j in range(internal_iterations):
            start = time.time()
            s.add(j)
            end = time.time()

            if end-start > maxtime_so_far:
                maxtime_so_far = end-start
                resizes[j] += 1

    print()

    format_string = "{0:<6} = 0b{0:<18b} [found %: {1:2.0%}]"

    for index in sorted(resizes):
        chance = resizes[index] / iterations

        if chance >= 0.05:
            print(format_string.format(index, chance))

main()

这是 CPython 的输出:

Completion: [99%]
0      = 0b0                  [found %: 100%]
5      = 0b101                [found %: 83%]
21     = 0b10101              [found %: 12%]
85     = 0b1010101            [found %: 94%]
341    = 0b101010101          [found %: 97%]
1365   = 0b10101010101        [found %: 100%]
5461   = 0b1010101010101      [found %: 100%]
21845  = 0b101010101010101    [found %: 100%]
87381  = 0b10101010101010101  [found %: 100%]

您可以看到 10101...2 模式，这是您从 2 的幂除以 3 得到的结果，此时对象将调整大小。 (此后会调整大小，因为脚本是 0 索引的)。

在 PyPy3 上，将迭代次数更改为更大(iterations = 1000；internal_iterations = 100000)，我得到

Completion: [100%]
0      = 0b0                  [found %: 78%]
5      = 0b101                [found %: 6%]
21     = 0b10101              [found %: 5%]
341    = 0b101010101          [found %: 24%]
1365   = 0b10101010101        [found %: 66%]
5461   = 0b1010101010101      [found %: 100%]
21845  = 0b101010101010101    [found %: 100%]
87381  = 0b10101010101010101  [found %: 71%]

这意味着 PyPy 的策略是相同的。

奇怪的是，可能是由于 JIT 或 GC，有时我会得到类似的东西:

Completion: [100%]
0      = 0b0                  [found %: 13%]
5      = 0b101                [found %: 11%]
21     = 0b10101              [found %: 22%]
22     = 0b10110              [found %: 6%]
23     = 0b10111              [found %: 5%]
24     = 0b11000              [found %: 5%]
341    = 0b101010101          [found %: 30%]
1365   = 0b10101010101        [found %: 66%]
5461   = 0b1010101010101      [found %: 98%]

取决于迭代次数。我想这是由于该点周围的迭代次数相对较少，而且可能意义不大。如果 GC 收集发生在第 20 项附近，则可能会导致这种压力。