実際の（固定/浮動小数点）値をクランプする最速の方法は？
https://stackoverflow.com/questions/427477
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
ifステートメントや三項演算子を使用するよりも、実数をクランプするより効率的な方法はありますか？ doubleと32ビットフィックスポイント実装（16.16）の両方でこれを実行したいと思います。私は両方のケースを処理できるコードを 求めていません。それらは別々の関数で処理されます。
明らかに、次のようなことができます：
double clampedA;
double a = calculate();
clampedA = a > MY_MAX ? MY_MAX : a;
clampedA = a < MY_MIN ? MY_MIN : a;
または
double a = calculate();
double clampedA = a;
if(clampedA > MY_MAX)
clampedA = MY_MAX;
else if(clampedA < MY_MIN)
clampedA = MY_MIN;
フィックスポイントバージョンでは、比較に関数/マクロを使用します。
これは、コードのパフォーマンスクリティカルな部分で行われるため、可能な限り効率的な方法を探しています（ビット操作が必要だと思われます）
編集：標準/ポータブルCである必要があり、プラットフォーム固有の機能はここでは重要ではありません。また、MY_MINおよびMY_MAXは、クランプする値と同じ型です（上記の例では2倍）。
解決
16.16表現の場合、単純な3項が速度的に改善される可能性は低いです。
また、ダブルスの場合、標準/ポータブルCが必要なため、あらゆる種類のビットいじりはひどく終わります。
ビットフィドルが可能であったとしても（疑わしい）、doubleのバイナリ表現に依存することになります。これ（およびそのサイズ）は実装に依存します。
おそらく<！> quot; guess <！> quot;これは、sizeof（double）を使用して、さまざまなdouble値のレイアウトをそれらの一般的なバイナリ表現と比較しますが、何も隠していないと思います。
最良のルールは、コンパイラを希望するもの（つまり3項）を伝え、最適化することです。
編集：控えめなパイ時間。 quinmarsのアイデア（下）をテストしましたが、IEEE-754のフロートがあれば動作します。これにより、以下のコードの速度が約20％向上しました。明らかに移植性はありませんが、＃IF ...でIEEE754フロート形式を使用するかどうかをコンパイラに問い合わせる標準化された方法があるかもしれないと思います。
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);
他のヒント
古い質問ですが、今日はこの問題に取り組んでいました（doubles / floatsを使用）。
最良のアプローチは、フロートにSSE MINSS / MAXSSを使用し、ダブルにSSE2 MINSD / MAXSDを使用することです。これらは分岐せず、それぞれ1クロックサイクルかかり、コンパイラ組み込み関数のおかげで使いやすいです。 std :: min / maxを使用したクランプと比較して、パフォーマンスが1桁以上向上します。
驚くかもしれません。確かにやった！残念ながら、VC ++ 2010は、/ arch：SSE2および/ FP：fastが有効になっている場合でも、std :: min / maxの単純な比較を使用します。他のコンパイラについて話すことはできません。
VC ++でこれを行うために必要なコードは次のとおりです。
#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を除いて同じです。
編集：最初、コメントどおりにクランプ関数を作成しました。しかし、アセンブラーの出力を見ると、VC ++コンパイラーが冗長な動きを排除するほど賢くないことがわかりました。 1つ少ない命令。 ：）
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
3つの命令（retをカウントしない）、分岐なし。素晴らしい。
これは、Core i3 M 350を搭載したUbuntu 13.04のGCC 4.7およびclang 3.2でテストされました。 補足として、std :: minおよびstd :: maxを呼び出す単純なC ++コードは同じアセンブリを生成しました。
これはダブル用です。また、intの場合、GCCとclangの両方が、5つの命令（retをカウントしない）と分岐なしのアセンブリを生成します。優れています。
現在、固定小数点を使用していないため、固定小数点について意見を述べません。
（x86のように）プロセッサに絶対値の高速命令がある場合、ifステートメントまたは3項演算よりも高速なブランチレスの最小値と最大値を実行できます。
min(a,b) = (a + b - abs(a-b)) / 2
max(a,b) = (a + b + abs(a-b)) / 2
用語の1つがゼロの場合（クランプしている場合によくあることです）、コードはさらに単純化されます：
max(a,0) = (a + abs(a)) / 2
両方の操作を組み合わせる場合、2つの/2を単一の/4または*0.25に置き換えて、ステップを保存できます。
FMIN = 0の最適化を使用している場合、次のコードはAthlon II X2の3進数よりも3倍以上高速です。
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
}
3項演算子は、実際の方法です。ほとんどのコンパイラは、分岐の代わりに条件付き移動を使用するネイティブハードウェア操作にコンパイルできるためです（したがって、予測ミスのペナルティやパイプラインのバブルなどを回避します）。 ビット操作により、ロードヒットストアが発生する可能性が高い。
特に、SSE2を搭載したPPCおよびx86には、次のような本質的なものとして表現できるハードウェアopがあります。
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 );
}
整数演算を使用したdoubleのビット操作を避けることを強くお勧めします。最近のほとんどのCPUでは、dcacheへのラウンドトリップ以外に、doubleレジスタとintレジスタ間でデータを直接移動する手段はありません。これにより、メモリへの書き込みが完了するまで（通常約40サイクル程度）CPUパイプラインを空にする、ロードヒットストアと呼ばれるデータハザードが発生します。
これの例外は、double値が既にレジスターではなくメモリー内にある場合です。その場合、ロードヒットストアの危険性はありません。ただし、この例では、doubleを計算して関数から返しただけであり、XMM1にまだ存在している可能性が高いことを示しています。
IEEE 754浮動小数点のビットは、整数として解釈されたビットを比較すると、浮動小数点として直接比較した場合と同じ結果が得られるように順序付けられています。したがって、整数をクランプする方法を見つけたり知っている場合は、（IEEE 754）浮動小数点にも使用できます。申し訳ありませんが、私はより速い方法を知りません。
floatを配列に格納している場合、rkjが言ったように、SSE3のようなCPU拡張機能を使用することを検討できます。あなたはあなたのためにすべての汚い仕事をするliboilを見ることができます。プログラムの移植性を保ち、可能であればより高速なCPU命令を使用します。 （OS /コンパイラに依存しないliboilがどのようになっているかはわかりません）。
テストと分岐ではなく、通常、この形式をクランプに使用します。
clampedA = fmin(fmax(a,MY_MIN),MY_MAX);
コンパイルされたコードのパフォーマンス分析を行ったことはありませんが。
現実的には、まともなコンパイラーはif（）ステートメントと？：式を区別しません。コードは、可能なパスを見つけることができるほど単純です。ただし、2つの例は同一ではありません。 ？：を使用した同等のコードは次のようになります
a = (a > MAX) ? MAX : ((a < MIN) ? MIN : a);
A <！> lt; <！> gt;マックス。コンパイラーは2つのテスト間の関係を見つける必要があるため、これで違いが生じる可能性があります。
クランプがまれな場合は、単一のテストでクランプの必要性をテストできます：
if (abs(a - (MAX+MIN)/2) > ((MAX-MIN)/2)) ...
E.g。 MIN = 6およびMAX = 10の場合、最初にaを8シフトダウンしてから、-2と+2の間にあるかどうかを確認します。これが何かを節約するかどうかは、分岐の相対的なコストに大きく依存します。
これはに類似した、おそらくより高速な実装です。 @Roddyの答え：
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 */
}
最小（最小）または最大（最大）分岐のない2つの整数および浮動小数点数の比較
IEEE floatおよびdouble形式は 数字が <！>＃8220;辞書的に順序付けられた<！>＃8221 ;、これは<！>＃8211; IEEE建築家ウィリアムの言葉で Kahanは、<！>＃8220; 2つの浮動小数点の場合 同じ形式の番号が順序付けられます （たとえば、x <！> lt; y）、それらは順序付けられます ビットが同じ場合 サインマグニチュードとして再解釈 整数。<！>＃8221;
テストプログラム：
/** 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)
私はこれにSSEアプローチを試しましたが、アセンブリの出力はかなりきれいに見えたので、最初は励まされましたが、数千回計った後、実際にはかなり遅くなりました。実際、VC ++コンパイラは、あなたが本当に意図していることを知るほどスマートではないように見えます。また、XMMレジスタとメモリとの間で物事をやり取りするべきではありません。とはいえ、コンパイラーが、とにかくすべての浮動小数点計算にSSE命令を使用しているように見えるとき、三項演算子でSSE min / max命令を使用するほど賢くない理由はわかりません。一方、PowerPC用にコンパイルしている場合は、FPレジスタでfsel組み込み関数を使用できます。これははるかに高速です。
適切に理解していれば、値を制限したい<！> quot; a <！> quot; MY_MIN〜MY_MAXの範囲に。 <！> quot; a <！> quot;のタイプダブルです。 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;
整数比較に変更することで、速度がわずかに向上する可能性があります。
高速な絶対値の指示を使用する場合は、ミニコンピューターで見つけたコードの抜粋をご覧ください。フロートを[0,1]の範囲に固定します
clamped = 0.5*(fabs(x)-fabs(x-1.0f) + 1.0f);
（コードを少し簡略化しました）。 2つの値をとると考えることができます。1つは<！> gt; 0
と反映されますfabs(x)
およびその他は約1.0を反映して<！> lt; 1.0
1.0-fabs(x-1.0)
そしてそれらの平均を取ります。範囲内にある場合、両方の値はxと同じになるため、それらの平均は再びxになります。範囲外の場合、値の1つはxになり、もう1つの値は<！> quot; boundary <！> quotでx反転します。ポイントなので、それらの平均は正確に境界点になります。
上で指摘したように、fmin / fmax関数はうまく機能します（gccでは-ffast-mathを使用）。 gfortranにはmax / minに対応するIA命令を使用するパターンがありますが、g ++にはありません。 iccでは、代わりにstd :: min / maxを使用する必要があります。これは、iccではfmin / fmaxが非有限オペランドでどのように機能するかの仕様のショートカットを許可していないためです。
C ++での私の2セント。おそらく三項演算子を使用することと何の違いもなく、うまくいけば分岐コードは生成されません
template <typename T>
inline T clamp(T val, T lo, T hi) {
return std::max(lo, std::min(hi, val));
}
