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

Question

Я ищу чрезвычайно быструю реализацию atof() на IA32, оптимизированную для US-en locale, ASCII и ненаучных обозначений. Многопоточность CRT для Windows падает здесь с треском, поскольку он проверяет изменения локали при каждом вызове isdigit(). Наше лучшее из лучших получается из лучших решений perl + tcl atof и на порядок превосходит msvcrt.dll. Я хочу сделать лучше, но я не в идеях. Инструкции по x86, связанные с BCD, выглядели многообещающими, но я не мог заставить его превзойти код Perl/tcl C. Могут ли любые SO'ers найти ссылку на лучшее? Также приветствуются решения на основе сборки без архитектуры 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. Это также позволяет выполнять большую часть математики с целыми числами вместо поплавков.

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

Answer 2

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

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

Пример: 123.456

работает всего = 0, добавить 1 (теперь это 1) работает всего = 1 * 10 = 10, добавить 2 (теперь это 12) работает всего = 12 * 10 = 120, add 3 (теперь это 123) столкнулся с точкой, подготовьтесь к дробной части множитель = 0,1, умножьте на 4, получите 0,4, добавьте к общей сумме, составит 123, множитель = 0,1/10 = 0,01, умножьте на 5, получите 0,05 , прибавить к общей сумме, составляет 123.45 multipiler = 0.01/10 = 0.001, умножить на 6, получить 0.006, добавить в бег всего, составят 123.456

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

Answer 3

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

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

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

-Adam

Answer 4

Я реализовал что-то может оказаться полезными. По сравнению с atof это примерно на x5 быстрее, а при использовании с __forceinline примерно на x10 быстрее. Еще одна приятная вещь заключается в том, что она швы имеет точно такую ​​же арифметику, как реализация 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

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

ОБНОВЛЕНИЕ: Извините, что я должен отозвать свое требование в два раза быстрее. Это быстрее, если вещь, которую вы конвертируете, уже находится в строке, но если вы передаете ей строчные кодированные строковые литералы, это примерно то же самое, что и 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 6

Мне кажется, что вы хотите построить (вручную) то, что составляет конечный автомат, где каждое состояние обрабатывает 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» в индексированном смещении в режиме адресации.]

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

Я не реализовал вышеуказанное. Я реализовал ее версии с циклами, они довольно быстрые.