セット操作の奇妙なパフォーマンス

Question

これらの結果はすべて、CPython 3.5.2で得られています。

setクラスの一部の操作で奇妙なパフォーマンスが発生したことに気付きました。

整数だけを含む2つのセットの和集合を実行するのに必要な時間を測定しました。今回は、セットのサイズにもよります。意外にも、これは整数の「密度」にも依存します。

X軸は（それぞれの経験のため、互いからランダムかつ独立に選択された）二組のサイズの合計である：ここでのプロットです。 y軸は秒単位（ログスケール）です。

濃度がdであることは、合計がN/dの整数からNの整数をサンプリングすることによってセットがインスタンス化されたことを意味します。言い換えれば、密度が0.5の場合、ある間隔の整数の半分を取る一方、密度が0.1の場合、ある（より大きい）間隔の整数の1/10を取る。

いくつかの結果を得るための最小限のコードです（必要に応じて、私がプロットに使用した完全なコードを投稿できますが、それは長くなります）。

import time 
import random 
import numpy 

def get_values(size, density): 
    return set(random.sample(range(int(size/density)), size)) 

def perform_op(size, density): 
    values1 = get_values(size, density) 
    values2 = get_values(size, density) 
    t = time.time() 
    result = values1 | values2 
    return time.time()-t 

size = 10000000 
for density in [0.05, 0.1, 0.5, 0.99]: 
    times = [perform_op(size, density) for _ in range(10)] 
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times))) 

ユニオン：

density: 0.05, time: 0.9846, standard deviation: 0.0440 
density: 0.10, time: 1.0141, standard deviation: 0.0204 
density: 0.50, time: 0.5477, standard deviation: 0.0059 
density: 0.99, time: 0.3440, standard deviation: 0.0020 

セット同じサイズを有する、略最速と最も遅いとの間の計算時間の要因3があります。 また、低密度ではさらにばらつきがあります。

面白いことに（perform_op機能にvalues1 & values2でvalues1 | values2を置き換える）交差点のために、我々はまた、非一定のパフォーマンスを持っていますが、パターンが異なっている、ということである：

density: 0.05, time: 0.3928, standard deviation: 0.0046 
density: 0.10, time: 0.4876, standard deviation: 0.0041 
density: 0.50, time: 0.5975, standard deviation: 0.0127 
density: 0.99, time: 0.3806, standard deviation: 0.0015 

私は他のセットの操作をテストしていません。

なぜこのような違いがあるのか​​わかりません。私が知っていることから、Pythonのセットはハッシュテーブルで実装されているので、ハッシュがよく広がっている限り、整数の密度は重要ではありません。

これらの異なるパフォーマンスの原因は何ですか？

Answer 1

二つの主要な要因はここにあります

1. あなたは、異なるサイズの出力を生成しています。密な入力では、大部分の値が重なり合うので、より小さな出力を生成することになります。
2. intには非常に単純なハッシュコードがあります。それはちょうどintの値です。だからhash(1234) == 1234。密な入力の場合、値が常にsetバケットの数よりも小さいので、オーバーラップのないほぼ連続したハッシュコードがあることを意味します（たとえば、値が100,000、バケットが262,144、値が密な場合はハッシュコード0から101,010までの範囲であるので、モジュロ262,144で実際のラップアラウンドは発生しません）。さらに、ハッシュコードは大部分がシーケンシャルであるということは、メモリが主にシーケンシャルなパターンでアクセスされることを意味します（CPUキャッシュフェッチヒューリスティックを助けます）。まばらな入力については、これは当てはまりません。同じバケットにハッシュする多くの非等しい値を持ちます（0.05ケースの200万の値のそれぞれには、バケットが262,144個ある場合に同じバケットにハッシュする7-8の異なる値があるためです）。 Pythonはクローズドハッシング（open addressingとも呼ばれます）を使用しているため、バケットの衝突が等しくないと、メモリ全体がジャンプして（CPUキャッシュがそれほど役に立たなくなります）、新しい値のバケットが見つかります。

バケット衝突問題を証明するには、次のように、

>>> import random 
>>> vals = random.sample(xrange(int(100000/0.99)), 100000) 
>>> vals_sparse = random.sample(xrange(int(100000/0.05)), 100000) 

# Check the number of unique buckets hashed to for dense and sparse values 
>>> len({hash(v) % 262144 for v in vals}) 
100000 # No bucket overlap at all 
>>> len({hash(v) % 262144 for v in vals_sparse}) 
85002 # ~15% of all values generated produced a bucket collision 

衝突が空いてバケツを探してsetの周りにホップする必要があり、密度の高い値は全く衝突しないそれらの値の一人一人を彼らはこのコストを完全に避けます。

あなたは（まだ密と疎の入力を使用している間）の両方の問題を修正し、テストをしたい場合は、floatハッシュはにint同等floatをハッシュしようとするため、int値と等価ではないこと（float秒でそれを試してみてくださいintと同じ値）。実際に等しい値の異なるレベルを避けるには、オーバーラップしない値から入力を選択します。したがって、疎と稠密は結果の共用体のサイズを変更しません。これは私が使用したコードで、密度にかかわらずかなり均一な時間で終了します。

import time 
import random 
import numpy 

def get_values(size, density, evens=True): 
    if evens: 
     # Divide by 100. to get floats with much more varied hashes 
     vals = random.sample([x/100. for x in xrange(0, int(size/density * 2), 2)], size) 
    else: 
     vals = random.sample([x/100. for x in xrange(1, int(size/density * 2), 2)], size) 
    return set(vals) 

def perform_op(size, density): 
    values1 = get_values(size, density) 
    values2 = get_values(size, density, False) # Select from non-overlapping values 
    t = time.time() 
    result = values1 | values2 
    return time.time()-t, len(result) 

size = 100000 
for density in [0.05, 0.1, 0.5, 0.99]: 
    times = [perform_op(size, density) for _ in range(10)] 
    resultlens = [r for _, r in times] 
    times = [t for t, _ in times] 
    print('density: %.2f, mean time: %.4f, standard deviation: %.4f' % (density, numpy.mean(times), numpy.std(times))) 
    print(numpy.mean(resultlens))