Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Почему бы не опубликовать правила.

Итак, правила замера бицепсов, то есть, скорости разбора битовых строк.

Числа Голомба

Представление чисел Голомба в виде таблицы:

Битовое представлениеКодируемые числа
10
011
001x2,3
0001xx4,5,6,7
00001xxx8,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 раза. ;)
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 66 comments