Многие «знают», что программирование на C/C++ позволяет получить программы, которые работают почти так же быстро, как программы, написанные на языке Assembler, а уж те, в свою очередь, быстры настолько, насколько это вообще возможно в теории.
На самом деле, конечно, это не совсем так (а в редких случаях — и совсем не так), но в целом программы на C/C++ действительно быстры, требуют немного памяти и запускаются мгновенно. Если их правильно написать.
Вот о том как правильно писать на C/C++ я и хотел бы немного поговорить. Сегодня я хочу обсудить вопрос о наборах строк. То есть о процедурах, позволяющих из числа получить строку, а из строки — число.
Где подобные списки встречаются? Ну, например, это могут быть списки токенов html, с которыми работает ваша программа. Или список команд, которые принимает ваш командный интерпретатор. Но, конечно, наиболее часто такие наборы возникают как списки всевозможных ошибок: strerror, gai_strerror, regerror и т.д. Думаю каждый программист встречался с подобной задачей хотя бы раз.
Хочу оговориться что дальнейшее описание впрямую применимо только к операционным системам, использующим формат ELF: Linux, MacOS, etc. В Windows или встраиваемых системах ситуация может быть слегка иной. Плюс я в этот раз ограничусь только прямой задачей (по числу получить строку) ибо она во-первых проще, а во-вторых многие решения обратной задачи содержат в себе прямую задачу как часть решения.
Итак, давайте поставим задачу. Мы хотим иметь функцию errstr, которая возвращает строку по номеру «ошибки». Как можно написать подобную функцию?
Ну например в лоб:
const char *errstr(int nr) {
switch (nr) {
case 0: return "X00000X";
case 1: return "X00001X";
…
case 9999: return "X09999X";
default: return "Unknown error";
}
}
Работает ли этот вариант? Вполне. Но вот сколько ресурсов он требует? Давайте посмотрим:
$ gcc -march=native -fPIC -O2 -shared -o libgen1.so gen1.c
$ strip --strip-unneeded libgen1.so
$ size libgen1.so
Мы потратили по 20 байт на каждую строку. Притом что собственно сама строка занимает 8 байт. Можно ли сделать лучше? Ммм… Да, конечно! Достаточно сделать список строк в виде массива и простенькую функцию для извелечения элементов. Указатели в массиве будут занимать по 4 байта и мы вместо 20 байт на строку получим только 12 — экономия 40%! Игра определённо стоит свеч.
Сказано — сделано:
static const char * const msgs[] = {
[0] = "X00000X",
[1] = "X00001X",
…
[9999] = "X09999X",
};
const char* errstr(int nr) {
if (nr<0 || nr>sizeof(msgs)/sizeof(msgs[0]))
return "Unknown error";
return msgs[nr];
}
$ gcc -march=native -fPIC -O2 -shared -o libgen2.so gen2.c
$ strip --strip-unneeded libgen2.so
$ size libgen2.so
Грандиозное достижение! Экономия в 6 байт? Что случилось? 80'000 байт занимает таблица (её нельзя модифицировать так что она защитана как text), но откуда у нас взялось ещё ~80'000 байт текста (мы-то рассчитывали на 40'000 байт) и ~40'000 байт данных (а их быть совсем не должно — у нас ведь все таблицы константные?). Давайте разберёмся:
$ relinfo libgen2.so
libgen2.so: 10007 relocations, 10002 relative (99%), 3 PLT entries, 0 for local syms (0%), 0 users
Ага. Теперь понятно! Компилятор не может рассчитать эту таблицу и записать её в библиотеку: для этого нужно знать адрес, по которому библиотека будет размещена в памяти во время исполнения — а как раз эта-то информация ему и неизвестна. Более того: как правило эта информация неизвестна и линкеру — поэтому он формирует таблицу не в сегменте текста, а в сегменте данных и создаёт ещё одну таблицу — уже для динамического линкера. Который в момент запуска программы её заполняет. Мдаа… И это всё — для таблицы, которая, скорее всего, вообще не будет использована! Кто там говорил про мгновенно запускающиеся программы?
Что же делать? Очевидно было бы неплохо реорганизовать таблицу так, чтобы вычисления производились не динамических линкером при каждом запуске программы, а нашей программой — и только там, где они нужны. Как это сделать? Не одни же мы сталкиваемся с этой проблемой? Как это сделано, скажем, в glibc? А вот так: все строки вынесены в отдельный файл, который используется основной программой.
Файл stringtab.h соедржит следующее:
_S(0, "X00000X")
_S(1, "X00001X")
…
_S(9999, "X09999X")
А программа — вот это:
#include <stddef.h>
#define MSGSTRFIELD(line) MSGSTRFIELD1(line)
#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 "Unknown error";
return msgstr.str + msgidx[nr];
}
$ gcc -march=native -fPIC -O2 -shared -o libgen3.so gen3.c
$ strip --strip-unneeded libgen3.so
$ size libgen3.so
Вот теперь — порядок. Осталься только один вопрос: мы перенесли вычисления из динамического линкера в нашу программу — насколько это отразилось на скорости? Иными словами: можно ли этот метод применять везде где нужны списки строк или только там где скорость не особенно важна (скажем в обратоке ошибок)?
Для этих целей я написал небольшую программу и, использовав gcc 4.2.2, исследовал её поведение на трёх системах: с AMD Opteron(tm) Processor 175, с Intel Core(TM)2 CPU 6600 и с Intel Pentium D CPU 3.00GHz.
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include «gen.h»
#define NUMTESTS 1000
#define NUMSTRINGS 10000
#ifdef __i386__
static inline unsigned long long read_tsc(void)
{
unsigned long long val;
__asm__ __volatile__("rdtsc": "=A" (val));
return val;
}
#endif
#ifdef __x86_64__
static inline 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 affinity;
CPU_ZERO(&affinity);
CPU_SET(1,&affinity);
sched_setaffinity(0, sizeof(cpu_set_t), &affinity);
unsigned long long testresults[NUMTESTS];
for (int i = 0; i < NUMTESTS; ++i) {
unsigned long long start = read_tsc();
for (int i = 0; i < NUMSTRINGS; ++i) {
// Do nothing — measure overhead
}
testresults[i] = read_tsc() — start;
}
unsigned long long overhead = testresults[0];
for (int i = 1; i < NUMTESTS; ++i) {
if (testresults[i] < overhead)
overhead = testresults[i];
}
for (int i = 0; i < NUMTESTS; ++i) {
unsigned long long start = read_tsc();
for (int i = 0; i < NUMSTRINGS; ++i) {
errstr(i);
}
testresults[i] = read_tsc() — start;
}
unsigned long long testrun = testresults[0];
for (int i = 1; i < NUMTESTS; ++i) {
if (testresults[i] < testrun)
testrun = testresults[i];
}
printf("errstr takes %g CPU cycles per call\n",
(testrun — overhead) / (NUMSTRINGS * 1.0));
return 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 takes 44.748 CPU cycles per call
$ LD_LIBRARY_PATH=. ./main2
errstr takes 12.9996 CPU cycles per call
$ LD_LIBRARY_PATH=. ./main3
errstr takes 13 CPU cycles per call
Результаты говорят сами за себя: вариант с выбором из списка имеет тенденцию конфликтовать с предсказателем ветвлений и потому работает весьма медленно, «стандартный» вариант, как правило, самый быстрый, но «экономный» варинт от него в половине случаев вообще не отстаёт, а там где отстаёт — теряет только один такт процессора, так что если вам эта функция нужна не в самом-самом «внутреннем» цикле, то его можно (а если строк много — то и нужно) рекомендовать к применению. Интересно, кстати, что в одном из вариантов (Intel Pentium D 64 bit) «экономный» вариант быстрее — что, скорее всего, объясняется тем, что он требует в два раза меньше памяти, а скорость доступа к кеш — небесконечна…
На самом деле, конечно, это не совсем так (а в редких случаях — и совсем не так), но в целом программы на C/C++ действительно быстры, требуют немного памяти и запускаются мгновенно. Если их правильно написать.
Вот о том как правильно писать на C/C++ я и хотел бы немного поговорить. Сегодня я хочу обсудить вопрос о наборах строк. То есть о процедурах, позволяющих из числа получить строку, а из строки — число.
Где подобные списки встречаются? Ну, например, это могут быть списки токенов html, с которыми работает ваша программа. Или список команд, которые принимает ваш командный интерпретатор. Но, конечно, наиболее часто такие наборы возникают как списки всевозможных ошибок: strerror, gai_strerror, regerror и т.д. Думаю каждый программист встречался с подобной задачей хотя бы раз.
Хочу оговориться что дальнейшее описание впрямую применимо только к операционным системам, использующим формат ELF: Linux, MacOS, etc. В Windows или встраиваемых системах ситуация может быть слегка иной. Плюс я в этот раз ограничусь только прямой задачей (по числу получить строку) ибо она во-первых проще, а во-вторых многие решения обратной задачи содержат в себе прямую задачу как часть решения.
Итак, давайте поставим задачу. Мы хотим иметь функцию errstr, которая возвращает строку по номеру «ошибки». Как можно написать подобную функцию?
Ну например в лоб:
const char *errstr(int nr) {
switch (nr) {
case 0: return "X00000X";
case 1: return "X00001X";
…
case 9999: return "X09999X";
default: return "Unknown error";
}
}
Работает ли этот вариант? Вполне. Но вот сколько ресурсов он требует? Давайте посмотрим:
$ gcc -march=native -fPIC -O2 -shared -o libgen1.so gen1.c
$ strip --strip-unneeded libgen1.so
$ size libgen1.so
| text | data | bss | dec | hex | filename |
| 201116 | 272 | 28 | 201416 | 312c8 | libgen1.so |
Мы потратили по 20 байт на каждую строку. Притом что собственно сама строка занимает 8 байт. Можно ли сделать лучше? Ммм… Да, конечно! Достаточно сделать список строк в виде массива и простенькую функцию для извелечения элементов. Указатели в массиве будут занимать по 4 байта и мы вместо 20 байт на строку получим только 12 — экономия 40%! Игра определённо стоит свеч.
Сказано — сделано:
static const char * const msgs[] = {
[0] = "X00000X",
[1] = "X00001X",
…
[9999] = "X09999X",
};
const char* errstr(int nr) {
if (nr<0 || nr>sizeof(msgs)/sizeof(msgs[0]))
return "Unknown error";
return msgs[nr];
}
$ gcc -march=native -fPIC -O2 -shared -o libgen2.so gen2.c
$ strip --strip-unneeded libgen2.so
$ size libgen2.so
| text | data | bss | dec | hex | filename |
| 161110 | 40272 | 28 | 201410 | 312c2 | libgen2.so |
Грандиозное достижение! Экономия в 6 байт? Что случилось? 80'000 байт занимает таблица (её нельзя модифицировать так что она защитана как text), но откуда у нас взялось ещё ~80'000 байт текста (мы-то рассчитывали на 40'000 байт) и ~40'000 байт данных (а их быть совсем не должно — у нас ведь все таблицы константные?). Давайте разберёмся:
$ relinfo libgen2.so
libgen2.so: 10007 relocations, 10002 relative (99%), 3 PLT entries, 0 for local syms (0%), 0 users
Ага. Теперь понятно! Компилятор не может рассчитать эту таблицу и записать её в библиотеку: для этого нужно знать адрес, по которому библиотека будет размещена в памяти во время исполнения — а как раз эта-то информация ему и неизвестна. Более того: как правило эта информация неизвестна и линкеру — поэтому он формирует таблицу не в сегменте текста, а в сегменте данных и создаёт ещё одну таблицу — уже для динамического линкера. Который в момент запуска программы её заполняет. Мдаа… И это всё — для таблицы, которая, скорее всего, вообще не будет использована! Кто там говорил про мгновенно запускающиеся программы?
Что же делать? Очевидно было бы неплохо реорганизовать таблицу так, чтобы вычисления производились не динамических линкером при каждом запуске программы, а нашей программой — и только там, где они нужны. Как это сделать? Не одни же мы сталкиваемся с этой проблемой? Как это сделано, скажем, в glibc? А вот так: все строки вынесены в отдельный файл, который используется основной программой.
Файл stringtab.h соедржит следующее:
_S(0, "X00000X")
_S(1, "X00001X")
…
_S(9999, "X09999X")
А программа — вот это:
#include <stddef.h>
#define MSGSTRFIELD(line) MSGSTRFIELD1(line)
#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 "Unknown error";
return msgstr.str + msgidx[nr];
}
$ gcc -march=native -fPIC -O2 -shared -o libgen3.so gen3.c
$ strip --strip-unneeded libgen3.so
$ size libgen3.so
| text | data | bss | dec | hex | filename |
| 121136 | 272 | 28 | 121436 | 1da5c | libgen3.so |
Вот теперь — порядок. Осталься только один вопрос: мы перенесли вычисления из динамического линкера в нашу программу — насколько это отразилось на скорости? Иными словами: можно ли этот метод применять везде где нужны списки строк или только там где скорость не особенно важна (скажем в обратоке ошибок)?
Для этих целей я написал небольшую программу и, использовав gcc 4.2.2, исследовал её поведение на трёх системах: с AMD Opteron(tm) Processor 175, с Intel Core(TM)2 CPU 6600 и с Intel Pentium D CPU 3.00GHz.
#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include «gen.h»
#define NUMTESTS 1000
#define NUMSTRINGS 10000
#ifdef __i386__
static inline unsigned long long read_tsc(void)
{
unsigned long long val;
__asm__ __volatile__("rdtsc": "=A" (val));
return val;
}
#endif
#ifdef __x86_64__
static inline 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 affinity;
CPU_ZERO(&affinity);
CPU_SET(1,&affinity);
sched_setaffinity(0, sizeof(cpu_set_t), &affinity);
unsigned long long testresults[NUMTESTS];
for (int i = 0; i < NUMTESTS; ++i) {
unsigned long long start = read_tsc();
for (int i = 0; i < NUMSTRINGS; ++i) {
// Do nothing — measure overhead
}
testresults[i] = read_tsc() — start;
}
unsigned long long overhead = testresults[0];
for (int i = 1; i < NUMTESTS; ++i) {
if (testresults[i] < overhead)
overhead = testresults[i];
}
for (int i = 0; i < NUMTESTS; ++i) {
unsigned long long start = read_tsc();
for (int i = 0; i < NUMSTRINGS; ++i) {
errstr(i);
}
testresults[i] = read_tsc() — start;
}
unsigned long long testrun = testresults[0];
for (int i = 1; i < NUMTESTS; ++i) {
if (testresults[i] < testrun)
testrun = testresults[i];
}
printf("errstr takes %g CPU cycles per call\n",
(testrun — overhead) / (NUMSTRINGS * 1.0));
return 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 takes 44.748 CPU cycles per call
$ LD_LIBRARY_PATH=. ./main2
errstr takes 12.9996 CPU cycles per call
$ LD_LIBRARY_PATH=. ./main3
errstr takes 13 CPU cycles per call
| Вариант 1 | Вариант 2 | Вариант 3 | |
|---|---|---|---|
| AMD Opteron (32bit): | 28.13 CPU cycles | 15 CPU cycles | 16 CPU CPU cycles |
| AMD Opteron (64bit): | 30.83 CPU cycles | 10 CPU cycles | 11 CPU CPU cycles |
| Intel Core 2 (32 bit): | 44.67 CPU cycles | 13 CPU cycles | 13 CPU CPU cycles |
| Intel Core 2 (64 bit): | 39.37 CPU cycles | 9 CPU cycles | 10 CPU CPU cycles |
| Intel Pentium D (32 bit): | 111.34 CPU cycles | 26 CPU cycles | 26 CPU CPU cycles |
| Intel Pentium D (64 bit): | 99.05 CPU cycles | 16 CPU cycles | 14 CPU CPU cycles |
Результаты говорят сами за себя: вариант с выбором из списка имеет тенденцию конфликтовать с предсказателем ветвлений и потому работает весьма медленно, «стандартный» вариант, как правило, самый быстрый, но «экономный» варинт от него в половине случаев вообще не отстаёт, а там где отстаёт — теряет только один такт процессора, так что если вам эта функция нужна не в самом-самом «внутреннем» цикле, то его можно (а если строк много — то и нужно) рекомендовать к применению. Интересно, кстати, что в одном из вариантов (Intel Pentium D 64 bit) «экономный» вариант быстрее — что, скорее всего, объясняется тем, что он требует в два раза меньше памяти, а скорость доступа к кеш — небесконечна…