NUMPY純粋なPythonより大幅に遅いAESの実装

Question

numlowのネイティブ配列サポートを利用するために、SlowAESコード（http://anh.cs.luc.edu/331/code/aes.py）を再実装することを検討しています。 SlowAESの純粋なPythonがnumpyを使用して実装された同じ関数よりもはるかに高速であるという逆の直感的な結果が出てきています。ここに私が持っている最も明瞭な例があります。

AESの主な操作の1つは、4x4要素バイト配列の各行がいくつかの位置（0行0、1行1など）だけシフトされたシフト行です。元のPythonコードは、その後、回転する仮想列を作成するスライスを使用して、一次元16要素のリストとして、この4×4バイトの状態列を扱う：

def rotate(word, n): 
    return word[n:] + word [0:n] 

def shiftRows(state): 
    for i in range(4): 
     state[i*4:i*4+4] = rotate(state[i*4:i*4+4], -i) 

は、時間的に16件の整数結果のリストを使用して、ShiftRows演算ではtimeitを実行します3.47マイクロ秒である。 4×4の整数入力配列を仮定

numpyの中に再実装この同じ機能は、単に次のようになります。

def shiftRows(state): 
    for i in range(4): 
     state[i] = np.roll(state[i],-i) 

ただし、はtimeitは、これは16.3マイクロ秒の実行時間を有することを示しています。

私は、numpyの最適化された配列演算がいくらか高速なコードをもたらすことを期待していました。どこが間違っていますか？そして、純粋なPythonよりも速いAES実装をもたらすいくつかのアプローチがありますか？途中で結果が出たいので、pycryptoは適用されないかもしれません（ただし、遅すぎる場合は、もう一度見直す必要があります）。

07年9月7日 - 回答ありがとうございます。 「なぜ」という質問に答えるために、数百万ではないにしても数十万のサンプルの平文/暗号文ペアを実行することを検討しています。したがって、単一の暗号化の時間差はほとんど違いはありませんが、私が得ることができる時間を節約することは、長期的には大きな違いを生み出す可能性があります。

Answer 1

単純な答えは、配列の作成には多くのオーバーヘッドがあるということです。したがって、小さなリストの操作は通常、配列の操作よりも高速です。アレイバージョンがリスト1のように反復的であるならば、特にそうです。大規模な配列の場合、コンパイルされたメソッドを使用する操作は高速になります。

これら4 'ロール' タイミングが小さなリストについては、この

を示しています。大きなもののため

In [93]: timeit x=list(range(16)); x=x[8:]+x[:8] 
100000 loops, best of 3: 2.75 µs per loop 
In [94]: timeit y=np.arange(16); y=np.roll(y,8) 
The slowest run took 40.90 times longer than the fastest. This could mean that an intermediate result is being cached. 
100000 loops, best of 3: 14.5 µs per loop 

：

In [95]: timeit x=list(range(1000)); x=x[500:]+x[:500] 
10000 loops, best of 3: 52.9 µs per loop 
In [96]: timeit y=np.arange(1000); y=np.roll(y,500) 
The slowest run took 28.91 times longer than the fastest. This could mean that an intermediate result is being cached. 
10000 loops, best of 3: 22.2 µs per loop 

我々はさらにrangeを抽出して、質問を絞り込むことができarangeはタイミングループから外れます。

np.roll

操作は、本質的に：

y[np.concatenate((np.arange(8,16), np.arange(0,8)))] 

4列、2 arange、concatenate、最終インデックス配列を構築します。