ARMプロセッサの文字列からスペースをすばやく削除する

比較的長い行を指定し、そこからすべてのスペースを削除するとします。 ASCIIでは、スペースをスペース文字（ ''）および行末（ '\ r'および '\ n'）として定義できます。 私が最も興味を持っているのは、アルゴリズムとパフォーマンスの問題です。そのため、タスクを簡素化し、32以下の値を持つすべてのバイトを削除できます。



速度のためにスペースを削除することについて尋ねた以前の記事で、最良の答えは128ビットレジスタ（SSE4）を使用したベクトル化を使用することでした。 それは正面からの5-10倍速いことが判明しました。



すべてのプロセッサに128ビットのベクトルレジスタとx64プロセッサがあることが非常に便利です。 ARMプロセッサはx64プロセッサと同じくらい高速ですか？



最初に、簡単なスカラー実装を見てみましょう。

size_t i = 0, pos = 0; while (i < howmany) { char c = bytes[i++]; bytes[pos] = c; pos += (c > 32 ? 1 : 0); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

値が32以下のすべての文字を削除し、データを書き戻します。 非常に高速に動作します。



ベクトル命令でさらに高速化することは可能ですか？



x64プロセッサでの最適な戦略は、16バイトのデータをキャプチャし、空の文字をすばやく比較し、16ビットから作成されたマスク値（またはビットセット）を文字ごとに1ビット抽出することです。各ビットは、空白文字が見つかったかどうかの値に対応します。 このmovemask



は、特別な命令（ movemask



）が存在するため、x64プロセッサで迅速に計算されます。 ARMプロセッサでは、このような命令はありません。 いくつかの指示でmovemask



をエミュレートできます。



したがって、x86プロセッサのようにARMでデータを処理することはできません。 何ができますか？



SS4がこれを行うと、バイト値が32以下であることをすばやく確認できるため、空の文字を特定できます。

 static inline uint8x16_t is_white(uint8x16_t data) { const uint8x16_t wchar = vdupq_n_u8(' '); uint8x16_t isw = vcleq_u8(data, wchar); return isw; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、16文字のいずれかをすばやく確認できます。2つの命令のみを使用して空になります。

 static inline uint64_t is_not_zero(uint8x16_t v) { uint64x2_t v64 = vreinterpretq_u64_u8(v); uint32x2_t v32 = vqmovn_u64(v64); uint64x1_t result = vreinterpret_u64_u32(v32); return result[0]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、有用な戦略を示唆しています。 文字を一度に1つずつ比較する代わりに、16文字すべてを一度に比較できます。 どれも空でない場合は、16文字を入力にコピーして先に進みます。 それ以外の場合は、遅いスカラーアプローチに移行しますが、ここで比較を繰り返す必要がないという追加の利点があります。

 uint8x16_t vecbytes = vld1q_u8((uint8_t *)bytes + i); uint8x16_t w = is_white(vecbytes); uint64_t haswhite = is_not_zero(w); w0 = vaddq_u8(justone, w); if(!haswhite) { vst1q_u8((uint8_t *)bytes + pos,vecbytes); pos += 16; i += 16; } else { for (int k = 0; k < 16; k++) { bytes[pos] = bytes[i++]; pos += w[k]; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このアプローチの利点は、空の文字のない16バイトのストリームを多数期待する場合に最も顕著になります。 原則として、これは多くのアプリケーションに当てはまります。



ランダムに散らばった少数の空の文字の入力に基づいて、スペースを1つずつ削除するのに必要な量を見積もるベンチマークを作成しました。 ソースコードは入手可能ですが、実行するにはARMプロセッサが必要です。 64ビットARMプロセッサ（A57コアで作成）で実行しました 。 John Regerには、同じマシン上でさらにいくつかのベンチマークがあります。 同じコアがNintendo Switchでも機能しているように思えます。

スカラー	1.40 ns
ネオン	1.04 ns

技術仕様は豊富ではありません 。 ただし、プロセッサは1.7 GHzの周波数で動作するため、 perf stat



を実行すれば誰もが確信できます。 必要なキャラクターが必要なサイクル数は次のとおりです。

スカラー	腕	最近のx64
スカラー	2.4サイクル	1.2サイクル
ベクトル化（NEONおよびSS4）	1.8サイクル	0.25サイクル

これに対し、x64プロセッサでは、スカラーバージョンは文字あたり1.2サイクルのようなものを使用し、ARMは文字あたりのサイクルで約半分の速度です。 A57コアはサイクルパフォーマンスでx64と競合する可能性が低いため、これは予想されることでした。 ただし、x64マシンでSS4を使用する場合、文字あたりわずか0.25サイクルのパフォーマンスを達成することができました。これは、ARM NEONの5倍以上の速度です。



このような大きな違いは、アルゴリズムの違いによるものです。 x64プロセッサでは、 movemask/pshufb



とmovemask/pshufb



と、ほとんど命令のないmovemask/pshufb



アルゴリズムを使用します。 ARM NEONのバージョンははるかに脆弱です。



ARMプロセッサには多くの素晴らしい点があります。 アセンブラコードは、x86 / x64プロセッサ向けの同様のコードよりもはるかにエレガントです。 ARM NEON命令でさえ、SSE / AVX命令よりもクリーンに見えます。 ただし、多くのタスクでは、 movemask



命令が完全に不足しているため、作業が制限される場合があります。



しかし、おそらくARM NEONを過小評価しています...私よりも効率的にタスクを完了できますか？



ご注意 この記事は編集されました。コメンテーターの1人が述べたように、64ビットARMプロセッサーでは、1つの命令で16ビットを再配置できます。