C / C +：これらの陰湿な文字列セット。

多くの人は、C / C ++でのプログラミングにより、アセンブラーで書かれたプログラムとほぼ同じ速度で動作するプログラムを取得できることを知っています。

実際、もちろん、これは完全に真実ではありません（まれなケースではまったくそうではありません）が、一般にC / C ++プログラムは非常に高速で、少しのメモリを必要とし、すぐに実行されます。 それらを正しく記述した場合。

それはC / C ++で書く方法についてであり、私は少し話をしたいです。 今日は、行セットの問題について説明します。 つまり、数値から文字列を取得し、文字列から数値を取得できるようにする手順についてです。

そのようなリストはどこで発生しますか？ たとえば、これらは、プログラムが動作するhtmlトークンのリストです。 または、シェルが受け入れるコマンドのリスト。 しかし、もちろん、ほとんどの場合、このようなセットはさまざまなエラーのリストとして表示されます：strerror、gai_strerror、regerrorなど。 すべてのプログラマーが少なくとも一度は同様の問題に遭遇したと思います。

次の説明は、ELF形式を使用するオペレーティングシステム（Linux、MacOSなど）にのみ直接適用されることを予約します。 Windowsまたは組み込みシステムでは、状況がわずかに異なる場合があります。 さらに、今回は直接的なタスク（数字で文字列を取得する）のみに制限します。これは、逆問題の多くの解決策が解決策の一部として直接的な問題を含んでいるためです。

それでは、タスクを設定しましょう。 エラー番号で文字列を返すerrstr関数が必要です。 同様の関数を作成するにはどうすればよいですか？

さて、例えば、額に：

const char * errstr （ int nr ） {
スイッチ （ nr ） {
ケース 0 ： "X00000X"を 返します。
ケース 1 ： 「X00001X」を 返す 。
...
ケース 9999 ： "X09999X"を 返します。
デフォルト ： 「不明なエラー」を 返し ます 。
}
}

このオプションは機能しますか？ かなり。 しかし、どのくらいのリソースが必要ですか？ 見てみましょう：
$ gcc -march = native -fPIC -O2 -shared -o libgen1.so gen1.c
$ strip --strip-unneeded libgen1.so
$ サイズlibgen1.so

テキスト	データ	bss	12月	ヘックス	ファイル名
201116	272	28	201416	312c8	libgen1.so

1行に20バイトを費やしました。 文字列自体が8バイトかかるという事実にもかかわらず。 もっと良くすることは可能ですか？ うーん...はい、もちろん！ 行のリストを配列の形式で作成し、要素を抽出するための単純な関数を作成すれば十分です。 配列内のポインターはそれぞれ4バイトを占有し、1行あたり20バイトの代わりに12のみを取得し、40％節約します！ ゲームは間違いなくろうそくの価値があります。

すぐに言ってやった：

静的 const char * const msgs [ ] = {
[ 0 ] = "X00000X" 、
[ 1 ] = "X00001X" 、
...
[ 9999 ] = "X09999X" 、
} ;

const char * errstr （ int nr ） {
if （ nr < 0 || nr> sizeof （ msgs ） / sizeof （ msgs [ 0 ] ） ）
「不明なエラー」を 返し ます 。
msgs [ nr ]を 返します。
}

$ gcc -march = native -fPIC -O2 -shared -o libgen2.so gen2.c
$ strip --strip-unneeded libgen2.so
$ サイズlibgen2.so

テキスト	データ	bss	12月	ヘックス	ファイル名
161110	40272	28	201410	312c2	libgen2.so

壮大な成果！ 6バイト節約しますか？ どうした テーブルは80'000バイト（テキストとして保護されるように変更することはできません）を占有しますが、どこで〜80'000バイトのテキスト（40'000バイトが必要でした）と〜40'000バイトのデータ（およびそれらはまったく存在すべきではありません-すべてのテーブルが一定ですか？）。 それを理解しましょう：
$ relinfo libgen2.so
libgen2.so：10007再配置、10002相対（99％）、3 PLTエントリ、ローカルsymsの0（0％）、0ユーザー
うん。 今では明らかです！ コンパイラはこのテーブルを計算してライブラリに書き込むことはできません。このため、実行時にライブラリがメモリ内に配置されるアドレスを知る必要があります。この情報は彼に知られていません。 さらに、原則として、この情報はリンカーにとっても不明です。したがって、テキストセグメントではなく、データセグメントでテーブルを形成し、動的リンカー用に別のテーブルを作成します。 これは、プログラムの開始時にそれを埋めます。 うーん...そしてそれはすべてです-テーブルのために、ほとんどの場合、まったく使用されません！ 誰がプログラムを即座に開始することについて話していましたか？

どうする？ 明らかに、プログラムが起動されるたびに動的リンカーによってではなく、プログラムによって計算が実行されるようにテーブルを再編成するとよいでしょう-そしてそれらが必要な場所でのみです。 どうやってやるの？ この問題に直面しているのは私たちだけではありませんか？ たとえば、glibcではこれはどのように行われますか？ そのため、すべての行は別のファイルに取り出され、メインプログラムで使用されます。
ファイルstringtab.hには以下が含まれます。
_S （ 0 、 "X00000X" ）
_S （ 1 、 "X00001X" ）
...
_S （ 9999 、 "X09999X" ）
そして、プログラムはこれです：
#include <stddef.h>

#define MSGSTRFIELD（行）MSGSTRFIELD1（行）
#define MSGSTRFIELD1（line）str ## line
static const union msgstr_t {
struct {
#define _S（n、s）char MSGSTRFIELD（__ LINE __）[sizeof（s）];
#include "stringtab.h"
#undef _S
} ;
char str [ 0 ] ;
} msgstr = { {
#define _S（n、s）s、
#include "stringtab.h"
#undef _S
} } ;
static const unsigned int msgidx [ ] = {
#define _S（n、s）offsetof（union msgstr_t、MSGSTRFIELD（__ LINE__））、
#include "stringtab.h"
#undef _S
} ;
const char * errstr （ int nr ） {
if （ nr < 0 || nr> sizeof （ msgidx ） / sizeof （ msgidx [ 0 ] ） ））
「不明なエラー」を 返し ます 。
return msgstr.str + msgidx [ nr ] ;
}
$ gcc -march = native -fPIC -O2 -shared -o libgen3.so gen3.c
$ strip --strip-unneeded libgen3.so
$ サイズlibgen3.so

テキスト	データ	bss	12月	ヘックス	ファイル名
121136	272	28	121436	1da5c	libgen3.so

これが注文です。 残る質問は1つだけです。計算を動的リンカーからプログラムに転送しました。これは速度にどの程度影響しましたか？ 言い換えると、このメソッドは、文字列のリストが必要な場所、または速度が特に重要でない場所（エラーリターンなど）にのみ適用できますか？

これらの目的のために、小さなプログラムを作成し、gcc 4.2.2を使用して、AMD Opteron（tm）Processor 175、Intel Core（TM）2 CPU 6600、Intel Pentium D CPU 3.00GHzの3つのシステムでの動作を調べました。

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include "gen.h"

#define NUMTESTS 1000
#define NUMSTRINGS 10000

#ifdef __i386__
静的 インライン unsigned long long read_tsc （ void ）
{
符号なし long long val;
__asm__ __volatile __ （ "rdtsc" ： "= A" （ val ） ） ;
return val;
}
#endif

#ifdef __x86_64__
静的 インライン unsigned long long read_tsc （ void ）
{
unsigned int __a、__d;
__asm__ __volatile __ （ "rdtsc" ： "= a" （ __a ） 、 "= d" （ __ d ） ） ;
return （ （ unsigned long ） __a ） | （ （ （ unsigned long ） __d ） << 32 ） ;
}
#endif

int main （ ）
{
cpu_set_tアフィニティ;
CPU_ZERO （ ＆アフィニティ） ;
CPU_SET （ 1 、＆​​アフィニティ） ;
sched_setaffinity （ 0 、 sizeof （ cpu_set_t ） 、＆​​affinity ） ;
符号なし long longテスト結果[ NUMTESTS ] ;
for （ int i = 0 ; i <NUMTESTS; ++ i ） {
符号なし long long start = read_tsc （ ） ;
for （ int i = 0 ; i <NUMSTRINGS; ++ i ） {
//何もしない-オーバーヘッドを測定する
}
testresults [ i ] = read_tsc （ ） -開始;
}
符号なし long longオーバーヘッド= testresults [ 0 ] ;
for （ int i = 1 ; i <NUMTESTS; ++ i ） {
if （ testresults [ i ] <オーバーヘッド）
オーバーヘッド= testresults [ i ] ;
}
for （ int i = 0 ; i <NUMTESTS; ++ i ） {
符号なし long long start = read_tsc （ ） ;
for （ int i = 0 ; i <NUMSTRINGS; ++ i ） {
errstr （ i ） ;
}
testresults [ i ] = read_tsc （ ） -開始;
}
unsigned long long testrun = testresults [ 0 ] ;
for （ int i = 1 ; i <NUMTESTS; ++ i ） {
if （ testresults [ i ] <testrun ）
testrun = testresults [ i ] ;
}
printf （ "errstr takes％g CPUcycle per call \ n " 、
（テスト実行オーバーヘッド） / （ NUMSTRINGS * 1.0 ） ）） ;
0を 返し ます 。
}
$ gcc -march = native -O2 -std = c99 -o main1 main.c -L。 -lgen1
$ gcc -march = native -O2 -std = c99 -o main2 main.c -L。 -lgen2
$ gcc -march = native -O2 -std = c99 -o main3 main.c -L。 -lgen3
$ LD_LIBRARY_PATH =。 ./main1
errstrは呼び出しごとに44.748 CPUサイクルかかります
$ LD_LIBRARY_PATH =。 ./main2
errstrは呼び出しごとに12.9996 CPUサイクルかかります
$ LD_LIBRARY_PATH =。 ./main3
errstrは呼び出しごとに13 CPUサイクルかかります

	オプション1	オプション2	オプション3
AMD Opteron（32ビット）：	28.13 CPUサイクル	15 CPUサイクル	16 CPU CPUサイクル
AMD Opteron（64ビット）：	30.83 CPUサイクル	10 CPUサイクル	11 CPU CPUサイクル
Intel Core 2（32ビット）：	44.67 CPUサイクル	13 CPUサイクル	13 CPU CPUサイクル
Intel Core 2（64ビット）：	39.37 CPUサイクル	9 CPUサイクル	10 CPU CPUサイクル
Intel Pentium D（32ビット）：	111.34 CPUサイクル	26 CPUサイクル	26 CPU CPUサイクル
Intel Pentium D（64ビット）：	99.05 CPUサイクル	16 CPUサイクル	14 CPU CPUサイクル

結果は一目瞭然です。リストから選択するオプションは分岐予測と競合する傾向があり、そのため非常に遅く動作します。「標準」オプションは原則として最速ですが、「経済的」バリアントは半分のケースで遅れません。遅れる場合、プロセッサの1クロックサイクルのみが失われるため、この機能がほとんどの「内部」サイクルにない場合は、そうすることができます（多くの行がある場合は、推奨する必要があります）。 ちなみに、オプションの1つ（Intel Pentium D 64ビット）では、「経済的」オプションの方が高速です。これは、メモリの半分を必要とし、キャッシュへのアクセス速度が無限であるためです。