Самый быстрый способ закрепить реальное значение (фиксированная/плавающая точка)?

Ответ 1

Для представления 16.16 простой тройной вариант вряд ли будет улучшен по скорости.

И для двойников, потому что вам это нужно стандартно/переносимо C, бит-возиться любого рода закончится плохо.

Даже если бит-скрипт был возможен (что я сомневаюсь), вы будете полагаться на двоичное представление двойников. ЭТО (и их размер) ОСУЩЕСТВЛЯЕТСЯ В ЗАВИСИМОСТИ.

Возможно, вы могли бы "догадаться" об этом, используя sizeof (double), а затем сравнивая макет различных двойных значений с их общими двоичными представлениями, но я думаю, что вы скрываетесь ни к чему.

Лучшее правило - СКАЗАТЬ КОМПЬЮТЕР, ЧТО ВЫ ХОТИТЕ (т.е. тройной), и пусть он оптимизируется для вас.

РЕДАКТИРОВАТЬ: Скромное время пирога. Я только что опробовал идею quinmars (см. Ниже), и она работает - если у вас есть поплавки IEEE-754. Это привело к тому, что код ниже 20%. IO, очевидно, не переносимый, но я думаю, что может быть стандартизированный способ запросить ваш компилятор, если он использует форматы float IEEE754 С#IF...?

  double FMIN = 3.13;
  double FMAX = 300.44;

  double FVAL[10] = {-100, 0.23, 1.24, 3.00, 3.5, 30.5, 50 ,100.22 ,200.22, 30000};
  uint64  Lfmin = *(uint64 *)&FMIN;
  uint64  Lfmax = *(uint64 *)&FMAX;

    DWORD start = GetTickCount();

    for (int j=0; j<10000000; ++j)
    {
        uint64 * pfvalue = (uint64 *)&FVAL[0];
        for (int i=0; i<10; ++i)
            *pfvalue++ = (*pfvalue < Lfmin) ? Lfmin : (*pfvalue > Lfmax) ? Lfmax : *pfvalue;
    }

    volatile DWORD hacktime = GetTickCount() - start;

    for (int j=0; j<10000000; ++j)
    {
        double * pfvalue = &FVAL[0];
        for (int i=0; i<10; ++i)
            *pfvalue++ = (*pfvalue < FMIN) ? FMIN : (*pfvalue > FMAX) ? FMAX : *pfvalue;
    }

    volatile DWORD normaltime = GetTickCount() - (start + hacktime);

Ответ 2

Старый вопрос, но сегодня я работал над этой проблемой (с удвоениями/плаваниями).

Лучшим подходом является использование SSE MINSS/MAXSS для поплавков и SSE2 MINSD/MAXSD для удвоений. Они не требуют обслуживания и имеют один такт, каждый из которых прост в использовании, благодаря встроенным функциям компилятора. Они дают более чем на порядок увеличение производительности по сравнению с фиксацией с помощью std:: min/max.

Вы можете обнаружить это удивительно. Я, конечно, сделал! К сожалению, VС++ 2010 использует простые сравнения для std:: min/max, даже когда /arch: SSE2 и /FP: fast включены. Я не могу говорить за других компиляторов.

Здесь необходим код для этого в VС++:

#include <mmintrin.h>

float minss ( float a, float b )
{
    // Branchless SSE min.
    _mm_store_ss( &a, _mm_min_ss(_mm_set_ss(a),_mm_set_ss(b)) );
    return a;
}

float maxss ( float a, float b )
{
    // Branchless SSE max.
    _mm_store_ss( &a, _mm_max_ss(_mm_set_ss(a),_mm_set_ss(b)) );
    return a;
}

float clamp ( float val, float minval, float maxval )
{
    // Branchless SSE clamp.
    // return minss( maxss(val,minval), maxval );

    _mm_store_ss( &val, _mm_min_ss( _mm_max_ss(_mm_set_ss(val),_mm_set_ss(minval)), _mm_set_ss(maxval) ) );
    return val;
}

Код двойной точности тот же, что и вместо xxx_sd. ​​

Изменить: сначала я написал функцию зажима как комментарий. Но, глядя на выход ассемблера, я заметил, что компилятор VС++ недостаточно умен, чтобы отбросить избыточный ход. Еще одна инструкция.:)

Ответ 3

Оба GCC и clang генерируют красивую сборку для следующего простого, простого переносимого кода:

double clamp(double d, double min, double max) {
  const double t = d < min ? min : d;
  return t > max ? max : t;
}

> gcc -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c

Сгенерированная GCC сборка:

maxsd   %xmm0, %xmm1    # d, min
movapd  %xmm2, %xmm0    # max, max
minsd   %xmm1, %xmm0    # min, max
ret

> clang -O3 -march=native -Wall -Wextra -Wc++-compat -S -fverbose-asm clamp_ternary_operator.c

Сбор, созданный Clang:

maxsd   %xmm0, %xmm1
minsd   %xmm1, %xmm2
movaps  %xmm2, %xmm0
ret

Три инструкции (не считая ret), никаких ветвей. Отлично.

Это было протестировано с GCC 4.7 и clang 3.2 на Ubuntu 13.04 с Core i3 M 350. С одной стороны, простой код С++, вызывающий std:: min и std:: max, сгенерировал ту же сборку.

Это для парных. И для int, как GCC, так и clang генерируют сборку с пятью инструкциями (не считая ret) и без ветвей. Также отлично.

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

Ответ 4

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

min(a,b) = (a + b - abs(a-b)) / 2
max(a,b) = (a + b + abs(a-b)) / 2

Если одно из терминов равно нулю (как это часто бывает в случае зажима), код упрощается еще немного:

max(a,0) = (a + abs(a)) / 2

Когда вы комбинируете обе операции, вы можете заменить два /2 на один /4 или *0.25, чтобы сохранить шаг.

Следующий код более 3 раз быстрее, чем тройной на моем Athlon II X2, при использовании оптимизации для FMIN = 0.

double clamp(double value)
{
    double temp = value + FMAX - abs(value-FMAX);
#if FMIN == 0
    return (temp + abs(temp)) * 0.25;
#else
    return (temp + (2.0*FMIN) + abs(temp-(2.0*FMIN))) * 0.25;
#endif
}

Ответ 5

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

В частности, PPC и x86 с SSE2 имеют аппаратное обеспечение, которое может быть выражено как внутреннее что-то вроде этого:

double fsel( double a, double b, double c ) {
  return a >= 0 ? b : c; 
}

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

inline double clamp ( double a, double min, double max ) 
{
   a = fsel( a - min , a, min );
   return fsel( a - max, max, a );
}

Я настоятельно рекомендую вам избегать манипуляций с битами с использованием целых операций. На большинстве современных процессоров нет прямых средств перемещения данных между двойными и внутренними регистрами, кроме как путем совершения туда-обратно к dcache. Это приведет к сбою данных, называемому магазином с нагрузкой, который в основном освобождает конвейер процессора до завершения записи в память (обычно около 40 циклов или около того).

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

Ответ 6

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

Если у вас есть поплавки, хранящиеся в массивах, вы можете использовать некоторые расширения процессора, такие как SSE3, как сказал rkj. Вы можете взглянуть на liboil, он делает всю грязную работу для вас. Сохраняет вашу программу в переносном режиме и, если это возможно, использует более быстрые инструкции по процессору. (Я не уверен, что OS/компилятор-независимый liboil).

Ответ 7

Вместо тестирования и ветвления я обычно использую этот формат для зажима:

clampedA = fmin(fmax(a,MY_MIN),MY_MAX);

Хотя я никогда не делал анализ производительности скомпилированного кода.

Ответ 8

Реально, никакой достойный компилятор не будет иметь никакого отношения между выражением if() и выражением?:. Код достаточно прост, что они смогут определить возможные пути. Тем не менее, ваши два примера не идентичны. Эквивалентный код с использованием?: Был бы

a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);

поскольку это предотвращает A < MIN при a > MAX. Теперь это может иметь значение, поскольку компилятору в противном случае пришлось бы определить связь между двумя тестами.

Если зажим редок, вы можете проверить необходимость зажима с помощью одного теста:

if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ...

например. с MIN = 6 и MAX = 10, это сначала сдвинет вниз на 8, а затем проверяет, находится ли оно между -2 и +2. Независимо от того, что это экономит, все зависит от относительной стоимости ветвления.

Ответ 9

Здесь возможно более быстрая реализация, похожая на @Roddy answer:

typedef int64_t i_t;
typedef double  f_t;

static inline
i_t i_tmin(i_t x, i_t y) {
  return (y + ((x - y) & -(x < y))); // min(x, y)
}

static inline
i_t i_tmax(i_t x, i_t y) {
  return (x - ((x - y) & -(x < y))); // max(x, y)
}

f_t clip_f_t(f_t f, f_t fmin, f_t fmax)
{
#ifndef TERNARY
  assert(sizeof(i_t) == sizeof(f_t));
  //assert(not (fmin < 0 and (f < 0 or is_negative_zero(f))));
  //XXX assume IEEE-754 compliant system (lexicographically ordered floats)
  //XXX break strict-aliasing rules
  const i_t imin = *(i_t*)&fmin;
  const i_t imax = *(i_t*)&fmax;
  const i_t i    = *(i_t*)&f;
  const i_t iclipped = i_tmin(imax, i_tmax(i, imin));

#ifndef INT_TERNARY
  return *(f_t *)&iclipped;
#else /* INT_TERNARY */
  return i < imin ? fmin : (i > imax ? fmax : f); 
#endif /* INT_TERNARY */

#else /* TERNARY */
  return fmin > f ? fmin : (fmax < f ? fmax : f);
#endif /* TERNARY */
}

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

Плавающие и двойные форматы IEEE были спроектированы так, чтобы "лексикографически упорядочен", который - в словах архитектора IEEE Уильяма Кахан означает "если две плавающие точки номера в том же формате упорядочены (скажем, x < y), то они упорядочены так же, когда их биты переинтерпретируется как Sign-Magnitude целые".

Программа тестирования:

/** gcc -std=c99 -fno-strict-aliasing -O2 -lm -Wall *.c -o clip_double && clip_double */
#include <assert.h> 
#include <iso646.h>  // not, and
#include <math.h>    // isnan()
#include <stdbool.h> // bool
#include <stdint.h>  // int64_t
#include <stdio.h>

static 
bool is_negative_zero(f_t x) 
{
  return x == 0 and 1/x < 0;
}

static inline 
f_t range(f_t low, f_t f, f_t hi) 
{
  return fmax(low, fmin(f, hi));
}

static const f_t END = 0./0.;

#define TOSTR(f, fmin, fmax, ff) ((f) == (fmin) ? "min" :       \
                  ((f) == (fmax) ? "max" :      \
                   (is_negative_zero(ff) ? "-0.":   \
                    ((f) == (ff) ? "f" : #f))))

static int test(f_t p[], f_t fmin, f_t fmax, f_t (*fun)(f_t, f_t, f_t)) 
{
  assert(isnan(END));
  int failed_count = 0;
  for ( ; ; ++p) {
    const f_t clipped  = fun(*p, fmin, fmax), expected = range(fmin, *p, fmax);
    if(clipped != expected and not (isnan(clipped) and isnan(expected))) {
      failed_count++;
      fprintf(stderr, "error: got: %s, expected: %s\t(min=%g, max=%g, f=%g)\n", 
          TOSTR(clipped,  fmin, fmax, *p), 
          TOSTR(expected, fmin, fmax, *p), fmin, fmax, *p);
    }
    if (isnan(*p))
      break;
  }
  return failed_count;
}  

int main(void)
{
  int failed_count = 0;
  f_t arr[] = { -0., -1./0., 0., 1./0., 1., -1., 2, 
        2.1, -2.1, -0.1, END};
  f_t minmax[][2] = { -1, 1,  // min, max
               0, 2, };

  for (int i = 0; i < (sizeof(minmax) / sizeof(*minmax)); ++i) 
    failed_count += test(arr, minmax[i][0], minmax[i][1], clip_f_t);      

  return failed_count & 0xFF;
}

В консоли:

$ gcc -std=c99 -fno-strict-aliasing -O2 -lm *.c -o clip_double && ./clip_double 

Он печатает:

error: got: min, expected: -0.  (min=-1, max=1, f=0)
error: got: f, expected: min    (min=-1, max=1, f=-1.#INF)
error: got: f, expected: min    (min=-1, max=1, f=-2.1)
error: got: min, expected: f    (min=-1, max=1, f=-0.1)

Ответ 10

Я попробовал подход SSE к этому сам, и выход сборки выглядел немного чище, поэтому меня сначала поощряли, но после того, как он был рассчитан на тысячи раз, это было довольно немного медленнее. Это действительно похоже, что компилятор VС++ недостаточно умен, чтобы знать, что вы действительно намереваетесь, и, похоже, он перемещает вещи между XMM-реестрами и памятью, когда это не должно. Тем не менее, я не знаю, почему компилятор недостаточно умен, чтобы использовать инструкции SSE min/max для тернарного оператора, когда он, похоже, использует инструкции SSE для всех вычислений с плавающей точкой. С другой стороны, если вы компилируете PowerPC, вы можете использовать fsel intrinsic в регистрах FP и быстрее.

Ответ 11

Если я правильно понимаю, вы хотите ограничить значение "a" диапазоном между MY_MIN и MY_MAX. Тип "a" является двойным. Вы не указали тип MY_MIN или MY_MAX.

Простое выражение:

clampedA = (a > MY_MAX)? MY_MAX : (a < MY_MIN)? MY_MIN : a;

должен сделать трюк.

Я думаю, что может быть небольшая оптимизация, если MY_MAX и MY_MIN будут целыми числами:

int b = (int)a;
clampedA = (b > MY_MAX)? (double)MY_MAX : (b < MY_MIN)? (double)MY_MIN : a;

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

Ответ 12

Я думаю, вы могли бы использовать SSE3 или некоторые подобные технологии для этого, но не знаете точно, какие команды/как... Вы можете взглянуть на: Арифметика насыщения

Ответ 13

Если вы хотите использовать быстрые инструкции абсолютного значения, проверьте этот отредактированный код, который я нашел в minicomputer, который зажимает float для диапазон [0,1]

clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f);

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

fabs(x)

а другой, отраженный от 1,0 до < 1,0

1.0-fabs(x-1.0)

И мы берем среднее из них. Если он находится в диапазоне, то оба значения будут такими же, как и x, поэтому их среднее значение будет равно x. Если это вне диапазона, то одно из значений будет х, а другое будет перевернуто по "граничной" точке, поэтому их среднее значение будет точно границей.

Ответ 14

Как указывалось выше, функции fmin/fmax работают хорошо (в gcc, с -ffast-math). Хотя gfortran имеет шаблоны для использования инструкций IA, соответствующих max/min, g++ этого не делает. В icc нужно использовать вместо std:: min/max, потому что icc не позволяет сокращать спецификацию того, как fmin/fmax работает с не конечными операндами.

Ответ 15

Мои 2 цента на С++. Вероятно, не что иное, как использование тройных операторов и, надеюсь, не генерируется код ветвления

template <typename T>
inline T clamp(T val, T lo, T hi) {
    return std::max(lo, std::min(hi, val));
}