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

Ответ 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 и в настоящее время просто микрокодированы. Они вряд ли будут особенно высокоэффективными.

Ответ 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

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

Ответ 3

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

• он поддерживает только одинарный прецизионный float,
• и не сканирует никаких специальных значений, таких как #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 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;
}

Ответ 4

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

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

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

Ответ 5

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

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

Пример: 123.456

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

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

Ответ 6

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

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

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

-Adam