Где я могу найти самую быструю в мире реализацию?

Question

Я ищу чрезвычайно быструю реализацию atof () на IA32, оптимизированную для американской локали, ASCII и ненаучной нотации. Многопотоковая CRT-система Windows здесь с треском проваливается, так как она проверяет изменения локали при каждом вызове isdigit (). Наш текущий лучший результат получен из лучших реализаций atof в perl + tcl и на порядок превосходит atof msvcrt.dll. Я хочу сделать лучше, но у меня нет идей. Связанные с BCD инструкции x86 казались многообещающими, но я не смог заставить их превзойти C-код perl / tcl. Может ли кто-нибудь найти ссылку на лучшее из того, что есть? Также приветствуются решения, не основанные на сборке x86.

Разъяснения, основанные на первоначальных ответах:

Неточности в ~ 2 ulp прекрасно подходят для этого приложения.
Преобразуемые числа будут поступать в сообщениях ascii по сети небольшими партиями, и наше приложение должно преобразовывать их с минимально возможной задержкой.

Answer 1

Какова ваша точность требования? Если вам действительно нужно «исправить» (всегда получает ближайшее значение с плавающей запятой к указанному десятичному числу), вероятно, будет сложно превзойти стандартные версии библиотеки (кроме удаления поддержки локали, которое вы уже сделали), так как это требует выполнения произвольной арифметики точности. Если вы готовы допустить ошибку ulp или two (и даже больше, чем у субнормалей), такой подход, предложенный cruzer, может работать и может быть быстрее, но он определенно не даст выход <0.5ulp. Вам будет лучше точнее вычислять целую и дробную части по отдельности и вычислять дробь в конце (например, для 12345.6789, вычислите ее как 12345 + 6789 / 10000.0, а не 6 * .1 + 7 * .01 + 8). * .001 + 9 * 0,0001), поскольку 0,1 - иррациональная двоичная дробь, и ошибка будет быстро накапливаться при вычислении 0,1 ^ n. Это также позволяет вам делать большую часть математики с целыми числами, а не с плавающей точкой. </p>

Инструкции BCD не были реализованы аппаратно с (IIRC) 286, и в настоящее время просто микрокодированы. Они вряд ли будут особенно высокопроизводительными.

Answer 2

Эта реализация, которую я только что закончил, выполняет кодирование в два раза быстрее, чем встроенный atof на моем рабочем столе. Он преобразует 1024 *1024* 39 числовых входов за 2 секунды, по сравнению с 4 секундами со стандартным gnu 'atof' моей системы. (Включая время установки и получение памяти и все такое).

UPDATE: Извините, я должен отозвать свою в два раза быстрее заявку. Это быстрее, если то, что вы конвертируете, уже находится в строке, но если вы передаете это жестко закодированные строковые литералы, это примерно так же, как atof. Однако я собираюсь оставить это здесь, так как, возможно, с некоторыми изменениями файла ragel и конечного автомата, вы сможете генерировать более быстрый код для определенных целей.

https://github.com/matiu2/yajp

Интересные файлы для вас:

https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp

https://github.com/matiu2/yajp/blob/master/number.hpp

Также вас может заинтересовать конечный автомат, который выполняет преобразование:

Answer 3

Мне кажется, что вы хотите построить (вручную) то, что составляет конечный автомат, где каждое состояние обрабатывает N-ую входную цифру или цифры экспоненты; этот конечный автомат будет иметь форму дерева (без петель!). Цель состоит в том, чтобы делать целочисленную арифметику везде, где это возможно, и (очевидно) запоминать переменные состояния («ведущий минус», «десятичная точка в позиции 3») в состояниях неявно, чтобы избежать присваиваний, хранения и последующей выборки / проверки таких значений , Реализуйте конечный автомат с простыми старыми операторами «if» только на входных символах (чтобы ваше дерево стало набором вложенных ifs). Встроенный доступ к символам буфера; Вы не хотите, чтобы вызов функции getchar замедлял вас.

Ведущие нули могут быть просто подавлены; Вам может понадобиться цикл для обработки смехотворно длинных ведущих нулевых последовательностей. Первая ненулевая цифра может быть собрана без обнуления аккумулятора или умножения на десять. Первые 4-9 ненулевых цифр (для 16-битных или 32-битных целых чисел) можно собрать с помощью целочисленных умножений на постоянное значение десять (большинство компиляторов превращают их в несколько сдвигов и сложений). [Вверху: нулевые цифры не требуют никакой работы, пока не будет найдена ненулевая цифра, а затем требуется умножить 10 ^ N на N последовательных нулей; Вы можете подключить все это в конечный автомат]. Цифры, следующие за первыми 4-9, могут быть получены с использованием 32- или 64-битных умножений в зависимости от размера слова вашей машины. Поскольку вам не важна точность, вы можете просто игнорировать цифры после того, как вы собрали 32- или 64-битные значения; Я предполагаю, что вы действительно можете остановиться, когда у вас есть фиксированное число ненулевых цифр на основе того, что ваше приложение на самом деле делает с этими числами. Десятичная точка, найденная в строке цифр, просто вызывает ветвь в дереве конечного автомата. Эта ветвь знает неявное местоположение точки и, следовательно, как правильно масштабировать ее до десяти. Приложив усилия, вы сможете комбинировать некоторые поддеревья конечного автомата, если вам не нравится размер этого кода.

[Вверху: целые и дробные части следует хранить как отдельные (маленькие) целые числа. Это потребует дополнительной операции с плавающей точкой в ​​конце для объединения целых и дробных частей, вероятно, не стоит].

[Вверху: соберите 2 символа для пар цифр в 16-битное значение, найдите 16-битное значение. Это позволяет избежать увеличения количества регистров в обмене на доступ к памяти, вероятно, не является выигрышем на современных машинах].

При обнаружении "E", получить показатель степени как целое число, как указано выше; найдите в таблице предварительно вычисленных множителей точно рассчитанные / масштабированные степени десяти (обратные значения, если знак «-» присутствует в показателе степени) и умножьте собранную мантиссу. (никогда не делайте поплавок). Поскольку каждая подпрограмма сбора показателей находится в отдельной ветви (листе) дерева, она должна корректироваться с учетом явного или фактического расположения десятичной точки, смещая степень десяти индекса.

[Сверху: вы можете избежать стоимости ptr++, если знаете, что символы для числа хранятся в буфере линейно и не пересекают границу буфера. В состоянии k вдоль ветви дерева вы можете получить доступ к символу k как *(start+k). Хороший компилятор обычно может скрыть "... + k" в индексированном смещении в режиме адресации.]

Совершенно верно, эта схема делает примерно одно дешевое умножение-добавление на ненулевую цифру, одно приведение к плавающей запятой мантиссы и одно умножение с плавающей запятой для масштабирования результата по экспоненте и расположению десятичной точки.

Я не реализовал вышеизложенное. Я реализовал его версии с помощью циклов, они довольно быстрые.

Answer 4

Я реализовал кое-что, что вы можете найти полезным. По сравнению с atof он примерно в 5 раз быстрее, а при использовании __forceinline примерно в 10 раз быстрее. Еще одна приятная вещь заключается в том, что она имеет ту же арифметику, что и реализация crt. Конечно, у него есть и минусы:

• поддерживает только плавающую одинарную точность,
• и не сканирует никакие специальные значения, такие как #INF и т. Д. *

__forceinline bool float_scan(const wchar_t* wcs, float* val)
{
int hdr=0;
while (wcs[hdr]==L' ')
    hdr++;

int cur=hdr;

bool negative=false;
bool has_sign=false;

if (wcs[cur]==L'+' || wcs[cur]==L'-')
{
    if (wcs[cur]==L'-')
        negative=true;
    has_sign=true;
    cur++;
}
else
    has_sign=false;

int quot_digs=0;
int frac_digs=0;

bool full=false;

wchar_t period=0;
int binexp=0;
int decexp=0;
unsigned long value=0;

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
    if (!full)
    {
        if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
        {
            full=true;
            decexp++;
        }
        else
            value=value*10+wcs[cur]-L'0';
    }
    else
        decexp++;

    quot_digs++;
    cur++;
}

if (wcs[cur]==L'.' || wcs[cur]==L',')
{
    period=wcs[cur];
    cur++;

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (!full)
        {
            if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
                full=true;
            else
            {
                decexp--;
                value=value*10+wcs[cur]-L'0';
            }
        }

        frac_digs++;
        cur++;
    }
}

if (!quot_digs && !frac_digs)
    return false;

wchar_t exp_char=0;

int decexp2=0; // explicit exponent
bool exp_negative=false;
bool has_expsign=false;
int exp_digs=0;

// even if value is 0, we still need to eat exponent chars
if (wcs[cur]==L'e' || wcs[cur]==L'E')
{
    exp_char=wcs[cur];
    cur++;

    if (wcs[cur]==L'+' || wcs[cur]==L'-')
    {
        has_expsign=true;
        if (wcs[cur]=='-')
            exp_negative=true;
        cur++;
    }

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (decexp2>=0x19999999)
            return false;
        decexp2=10*decexp2+wcs[cur]-L'0';
        exp_digs++;
        cur++;
    }

    if (exp_negative)
        decexp-=decexp2;
    else
        decexp+=decexp2;
}

// end of wcs scan, cur contains value's tail

if (value)
{
    while (value<=0x19999999)
    {
        decexp--;
        value=value*10;
    }

    if (decexp)
    {
        // ensure 1bit space for mul by something lower than 2.0
        if (value&0x80000000)
        {
            value>>=1;
            binexp++;
        }

        if (decexp>308 || decexp<-307)
            return false;

        // convert exp from 10 to 2 (using FPU)
        int E;
        double v=pow(10.0,decexp);
        double m=frexp(v,&E);
        m=2.0*m;
        E--;
        value=(unsigned long)floor(value*m);

        binexp+=E;
    }

    binexp+=23; // rebase exponent to 23bits of mantisa


    // so the value is: +/- VALUE * pow(2,BINEXP);
    // (normalize manthisa to 24bits, update exponent)
    while (value&0xFE000000)
    {
        value>>=1;
        binexp++;
    }
    if (value&0x01000000)
    {
        if (value&1)
            value++;
        value>>=1;
        binexp++;
        if (value&0x01000000)
        {
            value>>=1;
            binexp++;
        }
    }

    while (!(value&0x00800000))
    {
        value<<=1;
        binexp--;
    }

    if (binexp<-127)
    {
        // underflow
        value=0;
        binexp=-127;
    }
    else
    if (binexp>128)
        return false;

    //exclude "implicit 1"
    value&=0x007FFFFF;

    // encode exponent
    unsigned long exponent=(binexp+127)<<23;
    value |= exponent;
}

// encode sign
unsigned long sign=negative<<31;
value |= sign;

if (val)
{
    *(unsigned long*)val=value;
}

return true;
}

Answer 5

Я помню, что у нас было приложение Winforms, которое работало так медленно при разборе некоторых файлов обмена данными, и мы все думали, что это перебивает сервер БД, но наш умный босс фактически обнаружил, что узким местом было вызов, который преобразовывал разобрал строки в десятичные!

Самое простое - выполнить цикл для каждой цифры (символа) в строке, сохранить промежуточный итог, умножить сумму на 10, а затем добавить значение следующей цифры. Продолжайте делать это, пока не дойдете до конца строки или не встретите точку. Если вы встретите точку, отделите целую числовую часть от дробной, а затем умножьте ее на 10 для каждой цифры. Продолжайте добавлять их, пока вы идете.

Пример: 123,456

промежуточный итог = 0, добавьте 1 (теперь это 1) промежуточный итог = 1 * 10 = 10, добавьте 2 (теперь это 12) итоговое значение = 12 * 10 = 120, добавьте 3 (сейчас 123) натолкнулся на точку, готовимся к дробной части множитель = 0,1, умножить на 4, получить 0,4, прибавить к итоговой сумме, составляет 123,4 множитель = 0,1 / 10 = 0,01, умножить на 5, получить 0,05, прибавить к итоговой сумме, составляет 123,45 умножитель = 0,01 / 10 = 0,001, умножить на 6, получить 0,006, прибавить к итоговой сумме, составляет 123,456

Конечно, проверка на правильность числа и отрицательных чисел усложнит его. Но если вы можете «предположить», что введенные данные верны, вы можете сделать код намного проще и быстрее.

Answer 6

Рассматривали ли вы, чтобы GPU выполнял эту работу? Если вы можете загружать строки в память графического процессора и обрабатывать их все, вы можете найти хороший алгоритм, который будет работать значительно быстрее, чем ваш процессор.

Альтернативно, делайте это в ПЛИС. Существуют платы ПЛИС PCI-E, которые вы можете использовать для создания произвольных сопроцессоров. Используйте DMA, чтобы указать FPGA на часть памяти, содержащую массив строк, которые вы хотите преобразовать, и пропустите его через них, оставив преобразованные значения позади.

Вы смотрели на четырехъядерный процессор? Реальным узким местом в большинстве этих случаев является доступ к памяти в любом случае ...

-Adam