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

Ответ 1

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

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

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

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

Ответ 2

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]);

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

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

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 устарел, потому что их код с плавающей запятой работает быстро, но дизассемблер покажет вам, что это необоснованно оптимистично. Even/fp: fast просто приводит к вызову _ftol_sse2, который, хотя быстрее, чем вопиющий _ftol, по-прежнему является вызовом функции, сопровождаемым скрытым SSE-операцией и, следовательно, излишне медленным.

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

Ответ 7

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

Ответ 8

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

Ответ 9

См. статью 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

Ответ 10

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

Ответ 11

Какой компилятор вы используете? В более поздних компиляторах C/С++ Microsoft есть опция под C/С++ → Code Generation → Floating point model, которая имеет опции: быстрый, точный, строгий. Я думаю, что точное значение по умолчанию и работает, в некоторой степени подражая операциям FP. Если вы используете компилятор MS, как этот параметр установлен? Помогает ли это установить "быстрый"? В любом случае, как выглядит разборка?

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

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

Ответ 12

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

Ответ 13

Я удивлен вашим результатом. Какой компилятор вы используете? Скомпилированы ли вы с оптимизацией? Подтвердили ли вы, используя 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];

Сделайте отчет с дополнительной информацией!

Ответ 14

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

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

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

Ответ 15

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

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

В IEEE 754
6755399441055744.0 =

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

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

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

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

Ответ 16

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

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

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

Ниже приведены некоторые результаты тестов для процессора Core 2 (Q6600). Теоретическая пропускная способность основной памяти для этого аппарата составляет 3,2 ГБ/с (пропускная способность L1 и L2 намного выше). Код был скомпилирован с Visual Studio 2008. Аналогичные результаты для 32-разрядных и 64-битных, а также с оптимизацией /O 2 или/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;
}