Почему бы не опубликовать правила.
Итак, правила замера бицепсов, то есть, скорости разбора битовых строк.
Числа Голомба
Представление чисел Голомба в виде таблицы:
Битовое представлениеКодируемые числа10011001x2,30001xx4,5,6,700001xxx8,9,10,11,12,13,14,15
Сперва идет len нулей, затем 1, затем (len-1) битов остатка (X). Для определенности, в случае len=0 число битов остатка тоже равно 0. Раскодированное число равно 2len+X.
Битовый поток
Мы ведем сравнение обмена данными внутри одного и того же языка и одной и той же библиотеки, поэтому на представление битовых последовательностей внутри потока ограничений не накладывается.
Генератор потока кодирует в представлении Голомба последовательность чисел N,X1,X2,...,XN. Первое число - количество чисел в потоке. На выходе - последовательность байт, записываемая в файл.
Xi генерируется из двух случайных чисел Li и Yi следующим выражением: Xi=Yi&(2Li mod 24-1). Это ограничивает числа диапазоном 0..224-1 и дает достаточную вариацию длин (средняя длина оказывается около 10.5).
Для контроля правильности необходимо предоставить сумму чисел Xi внутри потока, умноженную на количество повторений потока R (см. ниже). Желательно, чтобы это была сумма по модулю M>=224, большие модули разрешены (может повлиять на производительность).
Окружение тестирования
Тестовый код должен содержать в себе чтение созданного генератором битового потока и запуск R повторений раскодирования битового потока. Чтение выполняется один раз перед запуском подсчета.
Тестовый код должен вернуть подсчитанную сумму чисел всех запусков раскодирования. Она должна совпасть с результатом генератора.
Тестовый код также должен выдать время работы R повторений раскодирования. В подсчет времени входит только повторения раскодирования и ничто другое. Ленивость вычислений (expression elimination) должна быть убрана.
Параметры N и R должны быть подобраны так, чтобы время раскодирования R повторений выполнялось более одной секунды. Размер файла с битовым потоком должен быть в районе 4-6 килобайт.
Нельзя использовать код не на тестируемом ЯП (ассемблер в случае Си, Си в случае ЯВУ и тп).
Параметры компиляторов никак не ограничиваются. Единственное исключение - нельзя включать ленивые вычисления раскодирования. По константным данным его можно провести один раз, а затем просто добавлять к сумме вычисленный результат. Этот вариант (хотя и маловероятный) должен быть исключен.
Включение кода раскодирования в код функции тестирования или вынесение его в отдельный модуль никак не ограничивается.
Обработка результатов
Интересным является количество тактов процессора на раскодирование одного числа.
Подсчет их для известной тактовой частоты процессора F и времени T выполнения R раскодирований N чисел: C=F*T/(R*(N+1)).
Примерный код тестового окружения на языке Си
Код на языке Си:
#include ... // Стандартные файлы и прочие прелюдии.
// Где-то здесь decode_sum_portion.
#define BUFSIZE 7000
unsigned char buffer[BUFSIZE];
int main (void) {
FILE *f = fopen("golombStream","rb");
time_t start, end;
int i, bufLen, sum = 0;
if (!f) return 1;
bufLen = fread(buffer,1,BUFSIZE,f); // bufLen содержит количество байт.
if (bufLen >= BUFSIZE) return 1; // возможно переполнение буфера.
fclose(f);
start = clock();
for (i=0;i < R;i++)
sum += decode_sum_portion(buffer, bufLen);
end = clock();
printf("sum %d\ntime %.3g\n", sum, (end-start)/((double)CLK_TCK));
return 0;
} /* main*/Я думаю, получилось нормально.
Что надо, ограничено, что не надо - не ограничено.
Мой текущий результат - 2160 команд на число. От ориентировочного результата Эрланга в 244 команды на число отстаю в 9 раз.
PS
Ха!
Да я от сишной реализации (gcc -O3 -fomit-frame-pointer) отстаю всего в 9,1 раза. ;)
Числа Голомба
Представление чисел Голомба в виде таблицы:
Битовое представлениеКодируемые числа10011001x2,30001xx4,5,6,700001xxx8,9,10,11,12,13,14,15
Сперва идет len нулей, затем 1, затем (len-1) битов остатка (X). Для определенности, в случае len=0 число битов остатка тоже равно 0. Раскодированное число равно 2len+X.
Битовый поток
Мы ведем сравнение обмена данными внутри одного и того же языка и одной и той же библиотеки, поэтому на представление битовых последовательностей внутри потока ограничений не накладывается.
Генератор потока кодирует в представлении Голомба последовательность чисел N,X1,X2,...,XN. Первое число - количество чисел в потоке. На выходе - последовательность байт, записываемая в файл.
Xi генерируется из двух случайных чисел Li и Yi следующим выражением: Xi=Yi&(2Li mod 24-1). Это ограничивает числа диапазоном 0..224-1 и дает достаточную вариацию длин (средняя длина оказывается около 10.5).
Для контроля правильности необходимо предоставить сумму чисел Xi внутри потока, умноженную на количество повторений потока R (см. ниже). Желательно, чтобы это была сумма по модулю M>=224, большие модули разрешены (может повлиять на производительность).
Окружение тестирования
Тестовый код должен содержать в себе чтение созданного генератором битового потока и запуск R повторений раскодирования битового потока. Чтение выполняется один раз перед запуском подсчета.
Тестовый код должен вернуть подсчитанную сумму чисел всех запусков раскодирования. Она должна совпасть с результатом генератора.
Тестовый код также должен выдать время работы R повторений раскодирования. В подсчет времени входит только повторения раскодирования и ничто другое. Ленивость вычислений (expression elimination) должна быть убрана.
Параметры N и R должны быть подобраны так, чтобы время раскодирования R повторений выполнялось более одной секунды. Размер файла с битовым потоком должен быть в районе 4-6 килобайт.
Нельзя использовать код не на тестируемом ЯП (ассемблер в случае Си, Си в случае ЯВУ и тп).
Параметры компиляторов никак не ограничиваются. Единственное исключение - нельзя включать ленивые вычисления раскодирования. По константным данным его можно провести один раз, а затем просто добавлять к сумме вычисленный результат. Этот вариант (хотя и маловероятный) должен быть исключен.
Включение кода раскодирования в код функции тестирования или вынесение его в отдельный модуль никак не ограничивается.
Обработка результатов
Интересным является количество тактов процессора на раскодирование одного числа.
Подсчет их для известной тактовой частоты процессора F и времени T выполнения R раскодирований N чисел: C=F*T/(R*(N+1)).
Примерный код тестового окружения на языке Си
Код на языке Си:
#include ... // Стандартные файлы и прочие прелюдии.
// Где-то здесь decode_sum_portion.
#define BUFSIZE 7000
unsigned char buffer[BUFSIZE];
int main (void) {
FILE *f = fopen("golombStream","rb");
time_t start, end;
int i, bufLen, sum = 0;
if (!f) return 1;
bufLen = fread(buffer,1,BUFSIZE,f); // bufLen содержит количество байт.
if (bufLen >= BUFSIZE) return 1; // возможно переполнение буфера.
fclose(f);
start = clock();
for (i=0;i < R;i++)
sum += decode_sum_portion(buffer, bufLen);
end = clock();
printf("sum %d\ntime %.3g\n", sum, (end-start)/((double)CLK_TCK));
return 0;
} /* main*/Я думаю, получилось нормально.
Что надо, ограничено, что не надо - не ограничено.
Мой текущий результат - 2160 команд на число. От ориентировочного результата Эрланга в 244 команды на число отстаю в 9 раз.
PS
Ха!
Да я от сишной реализации (gcc -O3 -fomit-frame-pointer) отстаю всего в 9,1 раза. ;)