Pythonのリストがソートされると遅くなるのはなぜですか？

質問

次のコードでは、同じ値を持つ2つのリストを作成しています。1つはソートされていないリスト（s_not）、もう1つはソートされたリスト（s_yes）です。値はrandint()によって作成されます。それぞれのリストに対していくつかのループを実行し、時間を計っています。

import random
import time

for x in range(1,9):

    r = 10**x # do different val for the bound in randint()
    m = int(r/2)

    print("For rand", r)

    # s_not is non sorted list
    s_not = [random.randint(1,r) for i in range(10**7)]

    # s_yes is sorted
    s_yes = sorted(s_not)

    # do some loop over the sorted list
    start = time.time()
    for i in s_yes:
        if i > m:
            _ = 1
        else:
            _ = 1
    end = time.time()
    print("yes", end-start)

    # do the same to the unsorted list
    start = time.time()
    for i in s_not:
        if i > m:
            _ = 1
        else:
            _ = 1
    end = time.time()
    print("not", end-start)

    print()

出力あり。

For rand 10
yes 1.0437555313110352
not 1.1074268817901611

For rand 100
yes 1.0802974700927734
not 1.1524150371551514

For rand 1000
yes 2.5082249641418457
not 1.129960298538208

For rand 10000
yes 3.145440101623535
not 1.1366300582885742

For rand 100000
yes 3.313387393951416
not 1.1393756866455078

For rand 1000000
yes 3.3180911540985107
not 1.1336982250213623

For rand 10000000
yes 3.3231537342071533
not 1.13503098487854

For rand 100000000
yes 3.311596393585205
not 1.1345293521881104

つまり、randint() の bound を増やすと、ソートされたリストに対するループが遅くなるのです。なぜでしょうか？

どうすれば解決するのでしょうか？

キャッシュの取りこぼし。いつ N int オブジェクトが連続して割り当てられると、それらを保持するために予約されたメモリは連続したチャンクになる傾向があります。そのため、割り当て順にリストをクロールすると、int 型の値を保持するメモリにも順次、連続した、増加する順序でアクセスする傾向があります。

シャッフルすると、リストをクロールするときのアクセスパターンもランダムになります。キャッシュにすべて収まらないほど多くの異なる int オブジェクトがある場合、キャッシュミスが多発します。

で r==1 で、そして r==2 というように、CPython はこのような小さな int をシングルトンとして扱うので、例えば、リストに 1000 万の要素があるにもかかわらず、リスト内の r==2 には(せいぜい)100個の異なるintオブジェクトが含まれるだけです。これらのデータはすべて同時にキャッシュに収まります。

しかし、それを超えると、より多くの、より多くの、より多くの異なる int オブジェクトを取得する可能性があります。アクセス パターンがランダムである場合、ハードウェア キャッシュはますます役に立たなくなります。

図解します。

>>> from random import randint, seed
>>> seed(987987987)
>>> for x in range(1, 9):
...     r = 10 ** x
...     js = [randint(1, r) for _ in range(10_000_000)]
...     unique = set(map(id, js))
...     print(f"{r:12,} {len(unique):12,}")
...     
          10           10
         100          100
       1,000    7,440,909
      10,000    9,744,400
     100,000    9,974,838
   1,000,000    9,997,739
  10,000,000    9,999,908
 100,000,000    9,999,998