Где я могу найти самый быстрый в мире способ реализации?
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужна чрезвычайно быстрая реализация atof() на IA32, оптимизированная для локали US-en, ASCII и ненаучных обозначений.Многопоточный CRT Windows здесь терпит неудачу, поскольку он проверяет изменения локали при каждом вызове isdigit().Наше нынешнее лучшее решение основано на лучшей реализации atof из perl + tcl и на порядок превосходит atof из msvcrt.dll.Я хочу добиться большего, но у меня нет идей.Инструкции x86, связанные с BCD, казались многообещающими, но мне не удалось заставить их превзойти код Perl/tcl C.Может ли кто-нибудь из SO'еров найти ссылку на лучшее?Также приветствуются решения, не основанные на сборке x86.
Разъяснения, основанные на первоначальных ответах:
Неточности в ~2 ulp вполне подходят для этого приложения.
Числа, подлежащие преобразованию, будут поступать в виде ascii-сообщений по сети небольшими партиями, и нашему приложению необходимо преобразовать их с минимально возможной задержкой.
Решение
Каковы ваши требования к точности?Если вам действительно нужно, чтобы это было «правильно» (всегда получает ближайшее к указанному десятичному значению значение с плавающей запятой), вероятно, будет трудно превзойти версии стандартной библиотеки (кроме удаления поддержки локали, что вы уже сделали), поскольку для этого требуется выполнение арифметических действий произвольной точности.Если вы готовы терпеть одну или две ошибки (и более того для субнормальных значений), подход, предложенный Cruzer, может работать и может быть быстрее, но он определенно не будет давать результат <0,5ulp.С точки зрения точности вам будет лучше вычислить целую и дробную части отдельно и вычислить дробь в конце (например,для 12345,6789 вычислите его как 12345 + 6789/10000,0, а не 6*,1 + 7*,01 + 8*,001 + 9*0,0001), поскольку 0,1 — иррациональная двоичная дробь, и ошибка будет быстро накапливаться при вычислении 0,1^ н.Это также позволяет выполнять большую часть математических вычислений с целыми числами вместо чисел с плавающей запятой.
Инструкции BCD не были реализованы аппаратно со времен (IIRC) 286, и в настоящее время просто микрокодируются.Вряд ли они будут особенно высокопроизводительными.
Другие советы
Эта реализация, которую я только что закончил писать, работает в два раза быстрее, чем встроенная «atof» на моем рабочем столе.Он преобразует 1024*1024*39 числовых входов за 2 секунды, по сравнению со стандартным gnu 'atof' моей системы за 4 секунды.(Включая время настройки и получения памяти и все такое).
ОБНОВЛЯТЬ:Извините, мне приходится отозвать свое заявление, отправленное в два раза быстрее.Это быстрее, если преобразуемый объект уже находится в строке, но если вы передаете ему жестко запрограммированные строковые литералы, это примерно то же самое, что и 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
Также вас может заинтересовать конечный автомат, выполняющий преобразование:
Я реализовал кое-что, что может оказаться вам полезным.По сравнению с 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;
}
Мне кажется, вы хотите построить (вручную) то, что представляет собой конечный автомат, в котором каждое состояние обрабатывает N-ю входную цифру или цифры экспоненты;этот конечный автомат будет иметь форму дерева (без петель!).Цель состоит в том, чтобы выполнять целочисленную арифметику там, где это возможно, и (очевидно) запоминать переменные состояния («ведущий минус», «десятичная точка в позиции 3») в состояниях неявно, чтобы избежать присвоений, сохранений и последующей выборки/тестирования таких значений. .Реализуйте конечный автомат с помощью простых старых операторов «if» только для входных символов (так что ваше дерево станет набором вложенных if).Встроенный доступ к символам буфера;вам не нужен вызов функции getchar чтобы замедлить тебя.
Ведущие нули можно просто подавить;здесь вам может понадобиться цикл для обработки смехотворно длинных последовательностей начальных нулей.Первую ненулевую цифру можно получить без обнуления аккумулятора или умножения на десять.Первые 4–9 ненулевых цифр (для 16-битных или 32-битных целых чисел) можно собрать с помощью целочисленного умножения на постоянное значение десять (превращаемое большинством компиляторов в несколько сдвигов и сложений).[Сверху:нулевые цифры не требуют никаких действий до тех пор, пока не будет найдена ненулевая цифра, а затем требуется умножение 10^N для N последовательных нулей;вы можете подключить все это к конечному автомату].Цифры, следующие за первыми 4–9, могут быть собраны с использованием 32- или 64-битного умножения в зависимости от размера слова вашей машины.Поскольку вас не заботит точность, вы можете просто игнорировать цифры после того, как собрали 32 или 64 бита;Я предполагаю, что вы действительно можете остановиться, когда у вас есть некоторое фиксированное количество ненулевых цифр, в зависимости от того, что ваше приложение на самом деле делает с этими числами.Десятичная точка, найденная в строке цифр, просто вызывает ветвь в дереве конечного автомата.Эта ветвь знает неявное местоположение точки и, следовательно, позже, как правильно масштабировать ее в десятичной степени.Приложив усилия, вы сможете объединить некоторые поддеревья конечного автомата, если вам не нравится размер этого кода.
[Сверху:сохраняйте целую и дробную части как отдельные (маленькие) целые числа.Это потребует дополнительной операции с плавающей запятой в конце для объединения целой и дробной частей, вероятно, оно того не стоит].
[Сверху:соберите 2 символа для пар цифр в 16-битное значение, найдите 16-битное значение.Это позволяет избежать умножения регистров в обмен на доступ к памяти, что, вероятно, не является выигрышем на современных машинах].
При обнаружении «E» соберите показатель степени как целое число, как указано выше;найдите точно предварительно вычисленные/масштабированные степени десяти в таблице предварительно вычисленных множителей (обратные величины, если в экспоненте присутствует знак «-») и умножьте собранную мантиссу.(никогда не делайте деление с плавающей запятой).Поскольку каждая процедура сбора экспоненты находится в отдельной ветви (листе) дерева, она должна корректироваться с учетом кажущегося или фактического местоположения десятичной точки путем смещения индекса степени десяти.
[Сверху:вы можете избежать затрат на ptr++ если вы знаете, что символы числа хранятся в буфере линейно и не пересекают границу буфера.В k-м состоянии по ветке дерева вы можете получить доступ к k-му символу как *(start+k).Хороший компилятор обычно может скрыть «...+k» в индексированном смещении в режиме адресации.]
Если все сделано правильно, эта схема выполняет примерно одно дешевое умножение-сложение на каждую ненулевую цифру, одно приведение мантиссы к числу с плавающей запятой и одно плавающее умножение для масштабирования результата по показателю степени и местоположению десятичной точки.
Я не реализовал вышесказанное.Я реализовал его версии с циклами, они довольно быстрые.
Я помню, что у нас было приложение Winforms, которое работало так медленно при анализе некоторых файлов обмена данными, и мы все думали, что это сбой сервера БД, но наш умный начальник на самом деле обнаружил, что узкое место было в вызове, который преобразовывал проанализированные строки в десятичные дроби!
Самый простой — выполнить цикл для каждой цифры (символа) в строке, сохранить промежуточную сумму, умножить сумму на 10, а затем добавить значение следующей цифры.Продолжайте делать это, пока не дойдете до конца строки или не встретите точку.Если вы встретите точку, отделите целую часть числа от дробной части и получите множитель, который делится на 10 для каждой цифры.Продолжайте добавлять их по ходу дела.
Пример:123,456
Запуск Total = 0, добавьте 1 (теперь 1) Запуск Total = 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
Конечно, проверка правильности чисел, а также отрицательных чисел усложнит задачу.Но если вы сможете «предполагать», что введенные данные верны, вы сможете сделать код намного проще и быстрее.
Рассматривали ли вы возможность использования графического процессора для выполнения этой работы?Если вы можете загрузить строки в память графического процессора и заставить его обработать их все, вы можете найти хороший алгоритм, который будет работать значительно быстрее, чем ваш процессор.
Альтернативно, сделайте это в FPGA. Существуют платы FPGA PCI-E, которые можно использовать для создания произвольных сопроцессоров.Используйте DMA, чтобы указать FPGA на часть памяти, содержащую массив строк, которые вы хотите преобразовать, и позволить ей пройти через них, оставив преобразованные значения позади.
Вы смотрели на четырехъядерный процессор?Реальным узким местом в большинстве этих случаев в любом случае является доступ к памяти...
-Адам
