strncmpの実装

Question

私のCスキルを磨くために、eglibcのソースコードをダウンロードしてstrncpyを見つけました。私はなぜ彼がn < = 4の場合を区別して4つのテストをしたのかわかりません。

int 
STRNCMP (const char *s1, const char *s2, size_t n) 
{ 
    unsigned char c1 = '\0'; 
    unsigned char c2 = '\0'; 

    if (n >= 4) 
    { 
     size_t n4 = n >> 2; 
     do 
    { 
     c1 = (unsigned char) *s1++; 
     c2 = (unsigned char) *s2++; 
     if (c1 == '\0' || c1 != c2) 
     return c1 - c2; 
     c1 = (unsigned char) *s1++; 
     c2 = (unsigned char) *s2++; 
     if (c1 == '\0' || c1 != c2) 
     return c1 - c2; 
     c1 = (unsigned char) *s1++; 
     c2 = (unsigned char) *s2++; 
     if (c1 == '\0' || c1 != c2) 
     return c1 - c2; 
     c1 = (unsigned char) *s1++; 
     c2 = (unsigned char) *s2++; 
     if (c1 == '\0' || c1 != c2) 
     return c1 - c2; 
    } while (--n4 > 0); 
     n &= 3; 
    } 

    while (n > 0) 
    { 
     c1 = (unsigned char) *s1++; 
     c2 = (unsigned char) *s2++; 
     if (c1 == '\0' || c1 != c2) 
    return c1 - c2; 
     n--; 
    } 

    return c1 - c2; 
} 

私は知らないメモリレイアウトと関係があるかもしれませんが、私に教えてください。

Answer 1

unrolled loopです。バイナリを少し大きくするというコストを犠牲にして、比較する4バイトごとに3つのデクリメント、3つの分岐、3つの条件を取り除いて文字列の比較を高速化します。

Duff's deviceと同じ手法を使用して最適化をさらに進めることもできましたが、これは実際には高速であることは明らかではありません。リンク先のページから、

余りのこの自動処理は、すべてのシステムおよびコンパイラで最適なソリューションではないかもしれない - いくつかのケースでは二つのループは、実際にメインコピーを行うには、アンロール、一つのループ（速いかもしれ、残りの部分を処理するための第2のループ）。この問題は、コンパイラがデバイスを正しく最適化できるかどうかに左右されます。一部のアーキテクチャでは、パイプライン化や分岐予測を妨げる可能性があります。 Duffのデバイスの多くのインスタンスがバージョン4.0のXFree86 Serverから削除されたとき、パフォーマンスが向上し、実行可能ファイルのサイズが大幅に減少しました。したがって、このコードの使用を検討する場合は、目的のコンパイラを使用して、ターゲット最適化レベルで実際にターゲットアーキテクチャ上で最速のコードであることを検証するために、いくつかのベンチマークを実行する価値があります。