12

「WriteGreatCodeVolume 2」を読んでいますが、次のような強い影響があります。

int myStrlen( char *s )
{
    char *start;
    start = s;
    while( *s != 0 )
    {
        ++s;
    }
    return s - start;
}

この本は、この実装は経験の浅いCプログラマーにとって典型的なものであると述べています。私は過去11年間Cでコーディングしてきましたが、Cでこれよりも優れた関数を書く方法がわかりません（アセンブリでより良いものを書くことを考えることができます）。Cでこれよりも優れたコードを書くにはどうすればよいですか？glibcのstrlen関数の標準ライブラリ実装を調べましたが、そのほとんどを理解できませんでした。高度に最適化されたコードを書く方法に関するより良い情報はどこにありますか？

4

7 に答える 7

14

Colm MacCarthaigh によるブログ投稿のOptimizing strlen()から:

残念ながら、C では、最良のケースとして O(n) 実装に運命づけられていますが、まだ完了していません… n のサイズについて何かできることがあります。

スピードアップのためにどの方向に取り組むことができるかについての良い例を示しています。そして、そこからの別の引用

時々、本当に速く走ると、本当に気が狂ってしまうことがあります。

于 2011-07-05T14:41:04.173 に答える
3

ビクター、これを見てください:
http://en.wikipedia.org/wiki/Strlen#Implementation

PS glibc のバージョンがわからないのは、\0 を見つけるためにビット シフトを使用しているからでしょう。

于 2011-07-05T14:36:05.273 に答える
3

他の人が指摘したように、より高速なアルゴリズムは、個々の文字ではなく単語全体を読み取り、ビット単位の演算を使用して終端の null を見つけます。一部の CPU アーキテクチャでは、アライメントされていないアドレスからワードを読み取ることができないため、このアプローチを採用する場合は、ポインターのワードアライメントに注意してください (アライメントを必要としないアーキテクチャでもセグメンテーション違反をトリガーする優れた方法です)。

結論:

優れたコードは、パフォーマンスが最も重要な場合を除いて、速度よりも読みやすさを重視します。コードをできる限り明確に記述し、ボトルネックとなる部分のみを最適化します。

于 2011-07-05T15:08:34.707 に答える
3

まず第一に、これは UTF-8 のようなエンコーディングでは意味がありません...つまり、UTF-8 文字列の文字数の計算はより複雑ですが、バイト数の計算はもちろん、 、たとえばASCII文字列。

一般に、一部のプラットフォームでは、より大きなレジスターに読み取ることで最適化できます。これまでに投稿された他のリンクにはその例がないため、下位エンディアンの疑似擬似コードを次に示します。

int size = 0;
int x;
int *caststring = (int *) yourstring;
while (int x = *caststring++) {
  if (!(x & 0xff)) /* first byte in this int-sized package is 0 */ return size;
  else if (!(x & 0xff00)) /* second byte etc. */ return size+1;
  /* rinse and repeat depending on target architecture, i.e. twice more for 32 bit */
  size += sizeof (int);
}
于 2011-07-05T14:42:32.623 に答える
1

以下は単純なアルゴリズムよりも高速で、32/64 ビットで動作するはずです。

union intptr {
    char* c;
    long* l;
#define LSIZE sizeof(long)
};

#define aligned_(x, a) \
    ((unsigned long) (x) % (a) == 0)

#define punpktt_(x, from, to) \
    ((to) (-1)/(from) (-1)*(from) (x))
#define punpkbl_(x) \
    punpktt_(x, unsigned char, unsigned long)

#define plessbl_(x, y) \
    (((x) - punpkbl_(y)) & ~(x) & punpkbl_(0x80))
#define pzerobl_(x) \
    plessbl_(x, 1)

static inline unsigned long maskffs_(unsigned long x)
{
    unsigned long acc = 0x00010203UL;
    if (LSIZE == 8)
       acc = ((acc << 16) << 16) | 0x04050607UL;
    return ((x & -x) >> 7) * acc >> (LSIZE*8-8);
}

size_t strlen(const char* base)
{
    union intptr p = { (char*) base };
    unsigned long mask;

    for ( ; !aligned_(p.c, LSIZE); p.c++ )
        if (*p.c == 0)
            return p.c - base;

    while ( !(mask = pzerobl_(*p.l)) )
        p.l++;
    return p.c - base + maskffs_(mask);
}
于 2014-10-26T20:20:38.700 に答える
1

マシンのデータ バス サイズと同じサイズではない変数を読み取ると、マシンはそのサイズの変数しか読み取ることができないため、負荷が高くなります。したがって、サイズの異なるもの (より小さいとしましょう) が要求されるたびに、マシンは要求されたサイズの変数のように見えるようにする作業を行う必要があります (ビットをシフトするなど)。そのため、マシン サイズのワードでデータを読み取り、AND 演算を使用して 0 をチェックすることをお勧めします。また、文字列をスキャンするときは、アラインされた開始アドレスから開始するようにしてください。

于 2011-07-05T14:45:16.883 に答える
1

パフォーマンスのためにコードを書く方法の提案を見つける場所についての OP の質問に答えるには、最適化された C コードの記述に関する MIT OpenCourse へのリンクがあります (ページの左側にある「マテリアル」リンクを探してください)。

于 2011-07-06T12:58:15.430 に答える