14

この投稿では、ソートされた配列をランダム配列よりも高速に処理する理由について、ブランチ予測がソートされた配列のパフォーマンス向上の理由であると述べています。

しかし、Pythonを使用して例を試しました。ソートされた配列とランダムな配列の間に違いはないと思います（bytearrayとarrayの両方を試し、line_profileを使用して計算のプロファイルを作成しました）。

私は何かが足りないのですか？

これが私のコードです：

from array import array
import random
array_size = 1024
loop_cnt = 1000
# I also tried 'array', and it's almost the same
a = bytearray(array_size)
for i in xrange(array_size):
    a.append(random.randint(0, 255))
#sorted                                                                         
a = sorted(a)
@profile
def computation():
    sum = 0
    for i in xrange(loop_cnt):
        for j in xrange(size):
            if a[j] >= 128:
                sum += a[j]

computation()
print 'done'
4

5 に答える 5

19

私は間違っているかもしれませんが、リンクされた質問とあなたの例の間に根本的な違いがあります。Pythonはバイトコードを解釈し、C++はネイティブコードにコンパイルします。

/シーケンスにif直接変換されるC++コードでは、CPU分岐予測子は、そのサイクルに固有の単一の「予測スポット」と見なすことができます。cmpjl

Pythonでは、その比較は実際にはいくつかの関数呼び出しであるため、（1）オーバーヘッドが大きくなり、（2）その比較を実行するコードは、他のすべての整数比較に使用されるインタープリターへの関数であると思います。したがって、これは「予測スポット」ではありません。現在のブロックに固有であり、分岐予測子が正しく推測するのがはるかに困難になります。

編集：また、このペーパーで概説されているように、インタープリター内にははるかに多くの間接ブランチがあるため、Pythonコードでのこのような最適化は、インタープリター自体のブランチの誤予測によって埋もれてしまう可能性があります。

于 2012-10-11T15:14:14.647 に答える
5

元のコードをPythonに移植し、PyPyで実行しました。ソートされた配列はソートされていない配列よりも高速に処理され、ブランチレスメソッドもソートされた配列と同様の実行時間で分岐を排除するように機能することを確認できます。これは、PyPyがJITコンパイラであり、分岐予測が行われているためだと思います。

[編集]

これが私が使用したコードです：

ランダムにインポート
インポート時間

def runme（data）：
  合計=0
  start = time.time（）

  xrange（100000）のiの場合：
    データ内のcの場合：
      c> = 128の場合：
        合計+=c

  end = time.time（）
  印刷終了-開始
  合計を印刷

def runme_branchless（data）：
  合計=0
  start = time.time（）

  xrange（100000）のiの場合：
    データ内のcの場合：
      t =（c-128）>> 31
      合計+=〜t＆c

  end = time.time（）
  印刷終了-開始
  合計を印刷

data = list（）

xrange（32768）のiの場合：
  data.append（random.randint（0、256））

ソートされたデータ=ソートされた（データ）
runme（sorted_data）
runme（データ）
runme_branchless（sorted_data）
runme_branchless（data）
于 2012-10-15T06:44:00.273 に答える
5

2つの理由：

  • 配列のサイズが小さすぎて効果を示しません。
  • PythonはCよりもオーバーヘッドが大きいため、全体的に影響が目立たなくなります。
于 2012-10-11T15:09:25.473 に答える
4

sorted()その場でソートするのではなく、ソートされた配列を返します。実際には、同じアレイを2回測定しています。

于 2012-10-11T15:10:47.703 に答える
-3

その他の回答や同様の質問を表示するには、ここをクリックしてください。Mysticialの回答で美しく説明されているように、データを並べ替えるとパフォーマンスが大幅に向上する理由は、分岐予測のペナルティが削除されるためです。

于 2014-06-16T13:32:47.410 に答える