Как ускорить преобразование чисел с плавающей запятой в целые числа?

Достаточно ли велико время, чтобы перевесить затраты на запуск пары потоков?

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

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

В наборе инструкций SSE3 есть инструкция FISTTP, которая делает то, что вы хотите, но я понятия не имею, можно ли ее использовать и давать более быстрые результаты, чем libc.

Какой компилятор вы используете? В более поздних компиляторах Microsoft C / C++ есть опция в C / C++ -> Генерация кода -> Модель с плавающей запятой, которая имеет параметры: быстрый, точный, строгий. Я думаю, что по умолчанию используется точное значение, которое в некоторой степени имитирует операции FP. Если вы используете компилятор MS, как этот параметр установлен? Помогает ли установка "быстро"? В любом случае как выглядит разборка?

Как было сказано выше, ЦП может преобразовать float<->int по существу в одну инструкцию, и он не работает быстрее этого (за исключением операции SIMD).

Также обратите внимание, что современные процессоры используют один и тот же блок FP как для одиночных (32-битных), так и для двойных (64-битных) чисел FP, поэтому, если вы не пытаетесь сэкономить память, храня много чисел с плавающей запятой, действительно нет причин отдавать предпочтение float над двойным.

inline int float2int( double d )
{
   union Cast
   {
      double d;
      long l;
    };
   volatile Cast c;
   c.d = d + 6755399441055744.0;
   return c.l;
}

// this is the same thing but it's
// not always optimizer safe
inline int float2int( double d )
{
   d += 6755399441055744.0;
   return reinterpret_cast<int&>(d);
}

for(int i = 0; i < HUGE_NUMBER; i++)
     int_array[i] = float2int(float_array[i]);

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

На Intel ваш лучший выбор - это встроенные вызовы SSE2.

В Visual C++ 2008 компилятор сам генерирует вызовы SSE2, если вы делаете сборку релиза с максимальными параметрами оптимизации и смотрите на разборку (хотя некоторые условия должны быть выполнены, поиграйте с вашим кодом).

Я удивлен твоим результатом. Какой компилятор вы используете? Вы компилируете с оптимизацией полностью? Подтвердили ли вы с помощью Valgrind и Kcachegrind, что именно здесь находится узкое место? Какой процессор вы используете? Как выглядит ассемблерный код?

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

for(int i = 0; i < HUGE_NUMBER-3; i += 4) {
     int_array[i]   = float_array[i];
     int_array[i+1] = float_array[i+1];
     int_array[i+2] = float_array[i+2];
     int_array[i+3] = float_array[i+3];
}
for(; i < HUGE_NUMBER; i++)
     int_array[i]   = float_array[i];

Если ваш компилятор действительно жалок, вам, возможно, придется помочь ему с общими подвыражениями, например,

int *ip = int_array+i;
float *fp = float_array+i;
ip[0] = fp[0];
ip[1] = fp[1];
ip[2] = fp[2];
ip[3] = fp[3];

Сообщите нам больше информации!

См. Эту статью Intel для ускорения преобразования целых чисел:

http://software.intel.com/en-us/articles/latency-of-floating-point-to-integer-conversions/

Согласно Microsoft, параметр компилятора / QIfist не рекомендуется в VS 2005, поскольку преобразование целых чисел было ускорено. Они забывают сказать, как это было ускорено, но просмотр списка разборки может дать ключ к разгадке.

http://msdn.microsoft.com/en-us/library/z8dh4h17(vs.80).aspx

Если у вас очень большие массивы (больше нескольких МБ - размер кеш-памяти ЦП), рассчитайте время своего кода и посмотрите, какова пропускная способность. Вы, вероятно, насыщаете шину памяти, а не блок FP. Посмотрите максимальную теоретическую пропускную способность для вашего процессора и посмотрите, насколько вы к ней близки.

Если вы ограничены шиной памяти, дополнительные потоки только усугубят ситуацию. Вам нужно лучшее оборудование (например, более быстрая память, другой процессор, другая материнская плата).

Вы правы: FPU является основным узким местом (а использование трюка xs_CRoundToInt позволяет очень близко подойти к насыщению шины памяти).

Вот некоторые результаты тестирования процессора Core 2 (Q6600). Теоретическая пропускная способность основной памяти для этого компьютера составляет 3,2 ГБ / с (пропускная способность L1 и L2 намного выше). Код был скомпилирован с помощью Visual Studio 2008. Аналогичные результаты для 32-битных и 64-битных версий и с оптимизацией / O2 или / Ox.

WRITING ONLY...
  1866359 ticks with 33554432 array elements (33554432 touched).  Bandwidth: 1.91793 GB/s
  154749 ticks with 262144 array elements (33554432 touched).  Bandwidth: 23.1313 GB/s
  108816 ticks with 8192 array elements (33554432 touched).  Bandwidth: 32.8954 GB/s

USING CASTING...
  5236122 ticks with 33554432 array elements (33554432 touched).  Bandwidth: 0.683625 GB/s
  2014309 ticks with 262144 array elements (33554432 touched).  Bandwidth: 1.77706 GB/s
  1967345 ticks with 8192 array elements (33554432 touched).  Bandwidth: 1.81948 GB/s

USING xs_CRoundToInt...
  1490583 ticks with 33554432 array elements (33554432 touched).  Bandwidth: 2.40144 GB/s
  1079530 ticks with 262144 array elements (33554432 touched).  Bandwidth: 3.31584 GB/s
  1008407 ticks with 8192 array elements (33554432 touched).  Bandwidth: 3.5497 GB/s

(Windows) исходный код:

// floatToIntTime.cpp : Defines the entry point for the console application.
//

#include <windows.h>
#include <iostream>

using namespace std;

double const _xs_doublemagic = double(6755399441055744.0);
inline int xs_CRoundToInt(double val, double dmr=_xs_doublemagic) { 
  val = val + dmr; 
  return ((int*)&val)[0]; 
} 

static size_t const N = 256*1024*1024/sizeof(double);
int    I[N];
double F[N];
static size_t const L1CACHE = 128*1024/sizeof(double);
static size_t const L2CACHE = 4*1024*1024/sizeof(double);

static size_t const Sz[]    = {N,     L2CACHE/2,     L1CACHE/2};
static size_t const NIter[] = {1, N/(L2CACHE/2), N/(L1CACHE/2)};

int main(int argc, char *argv[])
{
  __int64 freq;
  QueryPerformanceFrequency((LARGE_INTEGER*)&freq);

  cout << "WRITING ONLY..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = 13;
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  cout << "USING CASTING..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = (int)F[n];
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  cout << "USING xs_CRoundToInt..." << endl;
  for (int t=0; t<3; t++) {
    __int64 t0,t1;
    QueryPerformanceCounter((LARGE_INTEGER*)&t0);
    size_t const niter = NIter[t];
    size_t const sz    = Sz[t];
    for (size_t i=0; i<niter; i++) {
      for (size_t n=0; n<sz; n++) {
        I[n] = xs_CRoundToInt(F[n]);
      }
    }
    QueryPerformanceCounter((LARGE_INTEGER*)&t1);
    double bandwidth = 8*niter*sz / (((double)(t1-t0))/freq) / 1024/1024/1024;
    cout << "  " << (t1-t0) << " ticks with " << sz 
         << " array elements (" << niter*sz << " touched).  " 
         << "Bandwidth: " << bandwidth << " GB/s" << endl;
  }

  return 0;
}

большинство компиляторов c генерируют вызовы _ftol или чего-то еще для каждого преобразования типа float в int. установка уменьшенного переключателя соответствия с плавающей запятой (например, fp: fast) может помочь - ЕСЛИ вы понимаете И принимаете другие эффекты этого переключателя. кроме этого, поместите вещь в жесткую сборку или внутренний цикл sse, ЕСЛИ вы в порядке И понимаете другое поведение округления. для больших циклов, таких как ваш пример, вы должны написать функцию, которая устанавливает управляющие слова с плавающей запятой один раз, а затем выполняет массовое округление только с помощью инструкций fistp, а затем сбрасывает управляющее слово - ЕСЛИ вы в порядке с кодовым путем только x86, но по крайней мере вы не измените округление. Прочтите инструкции fld и fistp fpu и управляющее слово fpu.

Большинство других ответов здесь просто пытаются устранить накладные расходы на цикл.

Только ответ deft_code может понять суть проблемы, которая, вероятно, является реальной: преобразование чисел с плавающей запятой в целые числа шокирующе дорого обходится для процессора x86. Решение deft_code правильное, хотя он не дает никаких ссылок или объяснений.

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

Извините за ссылку, но на самом деле все, что здесь написано, кроме воспроизведения этой превосходной статьи, не проясняет ситуацию.

Ключ в том, чтобы избегать функции _ftol (), которая излишне медленная. Лучше всего для длинных списков таких данных использовать инструкцию SSE2 cvtps2dq для преобразования двух упакованных чисел с плавающей запятой в два упакованных int64. Сделайте это дважды (получая четыре int64 в двух регистрах SSE), и вы можете перемешать их вместе, чтобы получить четыре int32 (теряя верхние 32 бита каждого результата преобразования). Для этого вам не нужна сборка; MSVC предоставляет встроенные функции компилятора соответствующим инструкциям - _mm_cvtpd_epi32 (), если моя память мне не изменяет.

Если вы это сделаете, очень важно, чтобы ваши массивы float и int были выровнены по 16 байт, чтобы встроенные функции загрузки / сохранения SSE2 могли работать с максимальной эффективностью. Кроме того, я рекомендую вам немного программный конвейер и обрабатывать шестнадцать float сразу в каждом цикле, например (предполагая, что «функции» здесь на самом деле являются вызовами встроенных функций компилятора):

for(int i = 0; i < HUGE_NUMBER; i+=16)
{
//int_array[i] = float_array[i];
   __m128 a = sse_load4(float_array+i+0);
   __m128 b = sse_load4(float_array+i+4);
   __m128 c = sse_load4(float_array+i+8);
   __m128 d = sse_load4(float_array+i+12);
   a = sse_convert4(a);
   b = sse_convert4(b);
   c = sse_convert4(c);
   d = sse_convert4(d);
   sse_write4(int_array+i+0, a);
   sse_write4(int_array+i+4, b);
   sse_write4(int_array+i+8, c);
   sse_write4(int_array+i+12, d);
}

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

В случае сбоя этого SSE juju вы можете указать параметр / QIfist для MSVC, который заставит его выдать единственный код операции кулак вместо вызова _ftol; это означает, что он просто будет использовать любой режим округления, установленный в ЦП, не проверяя, является ли это специальной операцией усечения ANSI C. В документации Microsoft говорится, что / QIfist устарел, потому что их код с плавающей запятой теперь работает быстро, но дизассемблер покажет вам, что это неоправданно оптимистично. Даже / fp: fast просто приводит к вызову _ftol_sse2, который, хотя и быстрее, чем вопиющий _ftol, по-прежнему является вызовом функции, за которым следует скрытая операция SSE, и, следовательно, излишне медленная.

Я предполагаю, что вы используете архитектуру x86, кстати - если вы используете PPC, есть эквивалентные операции VMX, или вы можете использовать упомянутый выше трюк с умножением магических чисел, за которым следует vsel (чтобы замаскировать биты немантиссы) и выровненное хранилище.

Я провел несколько тестов о различных способах преобразования типа float в int. Краткий ответ - предположить, что у вашего клиента есть процессоры с поддержкой SSE2, и установить флаг компилятора / arch: SSE2. Это позволит компилятору использовать инструкции SSE скаляр, которые в два раза быстрее, чем даже метод магического числа.

В противном случае, если вам нужно измельчить длинные цепочки поплавков, используйте упакованные операции SSE2.

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

Технически это функция C99, но ваш компилятор, вероятно, предоставляет ее на C++. Хороший компилятор также встроит его в одну инструкцию (современный G ++ будет).

lrint документация

только округление отличный трюк, только использование 6755399441055743,5 (0,5 меньше) для округления не сработает.

6755399441055744 = 2 ^ 52 + 2 ^ 51 переполнение десятичных знаков с конца мантиссы, оставляя целое число, которое вы хотите, в битах 51-0 регистра fpu.

В IEEE 754
6755399441055744.0 =

знак экспоненты мантисса 0 10000110011 1000000000000000000000000000000000000000000000000000

6755399441055743,5 также будет компилироваться в 0100001100111000000000000000000000000000000000000000000000000000

0,5 выходит за пределы конца (округление в большую сторону), поэтому в первую очередь это работает.

чтобы выполнить усечение, вам нужно будет добавить 0,5 к своему двойному, затем сделайте это защитные цифры должны позаботиться о округлении до правильного результата, сделанного таким образом. также обратите внимание на 64-битный gcc linux, где long довольно досадно означает 64-битное целое число.