プログラミング言語で算術演算を行う場合、ビット単位の演算を利用して最適化するという難解な技術があります。もちろん、ビット ハックについて話しています。
1 から awk までの読みやすさと保守性のランキングについて Bit Hacks は Brainfuck のレベルに達します。しかし、操作のパフォーマンスの最後のビットを微調整するのに役立つ信じられないほど低レベルの最適化になる可能性がありますが、正しく行うのは難しく、100% 移植可能です。
この記事では、比較的簡単な関数 clz(x) を見ていきます。 unsigned の先行ゼロ ビットの数を返します 整数型 x .特に、GCC の __builtin_clz() を適切にラップする方法を紹介します。 .
モチベーション
人々は通常、頭の中で実行する計算で基数 10 を使用する傾向があります。
10 による乗算または除算、100 などの 10 を底とする演算は簡単です。適切な数のゼロを追加または削除するだけです。正確には、小数点を特定の量だけシフトします。同様に、10 を底とする整数対数を計算します (つまり、小数点以下の桁数) は、数字の桁数を数えることです。
通常、コンピューターは基数 2 を使用する傾向があるため、これらの演算はすべて 2 の累乗または基数 2 の対数の計算で簡単です。たとえば、2 の累乗による乗算/除算は単なるビット シフトです。
そして ilog2() 、整数の基数 2 の対数は、特定の整数値に必要な 2 進数の桁数を数えているだけです。それらを数えるには、clz() を使用できます。 :整数の幅 (つまり、ビット数) を取るだけです。先頭のゼロの数を減算し、それが 2 のべき乗であるかどうか、およびシーリングまたはフローリングの実装が必要かどうかに応じて、1 を加算/減算します (つまり、 ilog2(3)かどうか 1 である必要があります または 2; log2(3) 1.xxx になります ).
整数のビット数 x ちょうど sizeof(x) * CHAR_BIT です . sizeof(x) x の「バイト」数を返します . CHAR_BIT <climits> のマクロです char のビット数を提供する .
数値が 2 のべき乗であるかどうかの検出は、別のビット ハックで簡単に実行できるため、残っているのは clz() です。 .
チャレンジ
関数 clz() 任意の unsigned を取ります 整数型であり、その値のバイナリ表現で先頭のゼロ ビットの数を返します。
例として、 clz(4) を考えてみましょう . 4 バイナリでは 100 です .しかし、先頭の 0 はいくつありますか? 0? 13? 29? 1334?
場合によります。
4 の場合 100 の前に 13 個の未使用のゼロがあるため、結果は 16 ビット整数で格納されます。 .
4 の場合 は 32 ビット整数で格納され、さらに 16 個のゼロがあるため、結果は 29 になります。
clz() 指定されたサイズの整数、つまり指定されたビット数に対してのみ適切に定義できます。ポータブルを取得するには 一貫性 その結果、固定サイズの整数が必要です - std::uintX_t <cstdint> の型 .
これを念頭に置いて、 clz() を宣言できます 次のように機能します:
unsigned clz(std::uint8_t x);
unsigned clz(std::uint16_t x);
unsigned clz(std::uint32_t x);
unsigned clz(std::uint64_t x);
整数サイズごとにオーバーロードされ、そのサイズの先行ゼロの数を返します。
手動実装
マニュアルを書くのは退屈なので、詳しくは説明しません。 .
すべてのビットに対してループを実行できますが、これは遅すぎます。代わりに、バイナリ検索を使用しました。整数は、上半分と下半分の 2 つの半分に分割されます。上半分がゼロでない場合、最初の 1 は上半分なので、clz() を返します それ以外の場合は、最初の 1 は下半分にあります - 上半分はすべてゼロなので、結果は上半分の幅に clz() を加えたものになります 下半分に。
これは、4 つの clz() に非常によく対応しています。 整数を 2 つの小さい整数型に分割し、clz() を呼び出します。 小さい型では、オーバーロードの解決により、別の実装が自動的に選択されます:
unsigned clz(std::uint32_t x)
{
// shift upper half down, rest is filled up with 0s
auto upper = std::uint16_t(x >> 16);
// mask upper half away
auto lower = std::uint16_t(x & 0xFFFF);
// their type is std::uint16_t so a smaller overload is chosen
return upper ? clz(upper) : 16 + clz(lower);
}
// similar for std::uint64_t and std::uint16_t
std::uint8_t の最終的なオーバーロード それを 4 ビット半分に分割し、ルックアップ テーブルを使用します:
unsigned clz(std::uint8_t x)
{
static constexpr std::uint8_t clz_lookup[16] = { 4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 };
auto upper = x >> 4;
auto lower = x & 0x0F;
return upper ? clz_lookup[upper] : 4 + clz_lookup[lower];
}
ここまではとても遅いです。
__builtin_clz()
ほとんどのアーキテクチャには、これらの計算を行うための特別な命令があります.しかし、アセンブラを書くことは完全に移植可能ではありません.幸いなことに、多くのコンパイラはそれらを最適なアセンブラに変換される組み込み関数にラップします.
GCC および clang などの互換コンパイラでは、__builtin_clz() と呼ばれます。 .次のバリエーションがあります。
int __builtin_clz(unsigned int x);
int __builtin_clzl(unsigned long x);
int __builtin_clzll(unsigned long long x);
これらのビルトインが利用可能であれば、clz() の実装でそれらを使用できます。 関数。
しかし、例えば。最初のバージョンは clz() を返します unsigned int の場合 .そのサイズはプラットフォームごとに変わる可能性があり、それに伴い clz() の結果になります !
各固定サイズの整数を適切なビルトインに移植可能にマップする必要があります。ビルトインの引数の型は、少なくとも固定サイズの整数のサイズである必要があるため、オーバーフローが発生しません。しかし、最大のものだけを使用することはできません - long long - バージョン:あまり効果的ではないかもしれません.
このマッピングを手動で移植可能に行うことはできません。代わりに、コンパイラをだましてそれを実行させます。
私はお気に入りのテクニックでそれを行います:(ab)オーバーロード解決を使用します。
ビルトインのラッピング
オーバーロードの解決を使用するための最初のステップは、オーバーロードされた関数のセットを作成することです。したがって、組み込み関数を単純に unsigned int/long/long long を取る関数にラップします。 そして転送:
// real code would put those into a namespace
unsigned clz_impl(unsigned int x)
{
return __builtin_clz(x);
}
unsigned clz_impl(unsigned long x)
{
return __builtin_clzl(x);
}
unsigned clz_impl(unsigned long long x)
{
return __builtin_clzll(x);
}
わかりました。これで、それらはすべて同じ名前になり、オーバーロードされました。
しかし、コンパイラが行うデフォルトの解像度は十分ではありません。 clz_impl() を呼び出す std::uint8_t の中 version はあいまいなエラーを返します:どの候補も std::uint8_t を取りません すべてのプロモーションは同じように優れています。
コンパイラは、私たちが彼に何を求めているかを理解するまで、さらに子守をする必要があります.
SFINAE が救助に
完全一致を取得するには、実装関数をテンプレート化する必要があります。 整数型、サイズが組み込みの引数サイズより大きくない整数型のみ。
特定のテンプレートを条件付きで無効にすることは SFINAE によく似ているので、それを使用します。
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned int)>::type>
unsigned clz_impl(T x)
{
return __builtin_clz(x);
}
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned long)>::type>
unsigned clz_impl(T x)
{
return __builtin_clzl(x);
}
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned long long)>::type>
unsigned clz_impl(T x)
{
return __builtin_clzll(x);
}
何も機能せず、コンパイラは再定義について不平を言います.条件は相互に排他的ではなく、すべてが最後のオーバーロードに一致します.貧弱なコンパイラはどうすればよいでしょうか!
レスキューをレスキューするためのタグ ディスパッチ
ビルトインは、その引数の型より小さいか等しい型のみを取る必要があります。enable_if でそれをすでに表現しました。
ただし、最小が必要です 最も効果的であるために、機能する引数タイプ。したがって、優先順位があります オーバーロードで:最初は、すべて unsigned int を使用する必要があります バージョン。型が大きい場合のみ、unsigned long バージョンを考慮する必要があります。型がさらに大きい場合のみ、unsigned long long バージョンは最後の手段として使用する必要があります。
この優先度 タグのディスパッチを通じて表現できます。タグは、次のようなクラス階層のタイプです:
struct clzll_tag {};
struct clzl_tag : clzll_tag {};
struct clz_tag : clzl_tag {};
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned int)>::type>
unsigned clz_impl(clz_tag, T x)
{
return __builtin_clz(x);
}
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned long)>::type>
unsigned clz_impl(clzl_tag, T x)
{
return __builtin_clzl(x);
}
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned long long)>::type>
unsigned clz_impl(clzll_tag, T x)
{
return __builtin_clzll(x);
}
各オーバーロードは、名前のない最初の引数として、対応するタグ タイプを受け取るようになりました。これは、コンパイラが適切なオーバーロードを選択できるようにすることだけを目的としています。ここで重要なのは、階層 です。 タグ タイプの逆です。優先度が最も低いタグがベースであり、優先度が最も高いタグが最も派生したクラスです。
これで、ようやく clz() でラッパーを使用できるようになりました 関数:
unsigned clz(std::uint8_t x)
{
return clz_impl(clz_tag{}, x);
}
unsigned clz(std::uint16_t x)
{
return clz_impl(clz_tag{}, x);
}
// exactly the same for the other two overloads
最も優先度の高いタグのインスタンスを最初の引数として渡します。これは、unsigned int version が最も一致します - タグのタイプが完全に一致します。テンプレート パラメータのタイプが unsigned int より大きいため、使用できない場合 、SFINAE が開始され、それが無効になります。現在 - そして今だけ - コンパイラは、派生からベースへの変換を必要とする他のオーバーロードの 1 つを選択するため、完全一致よりも悪いものになります。unsigned long version は、タグを 1 塩基深く変換するだけで済み、残りのバージョンの 2 塩基を変換する必要がないため、2 番目に優れています。この unsigned long long SFINAE が unsigned long を無効にする場合にのみ選択されます
バグ修正
コンパイラは正しいビルトインを選択するようになりました.しかし、結果は常に正しいとは限りません.
たとえば、clz(std::uint16_t(1)) の呼び出し 31 を返します .
コンパイラが 31 個のゼロを 16 ビットに収めることができるか、バグがあります。
最初に言ったことを覚えていますか? clz() の結果 タイプの幅に依存しますか?
ええ、正しいビルトインを選択するかもしれませんが、clz() を返すだけです。 ビルトインの引数の型のために!上記の呼び出しは unsigned int を選択します バージョンは、十分な大きさの最小のタイプであるためです。しかし、それは clz() を返すだけです のために - ここに！ - 32 ビット整数。
結果を調整する必要があります。
正確には、実装の引数の型と呼び出し側の引数の型の幅の差を差し引く必要があります:
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned int)>::type>
unsigned clz_impl(clz_tag, T x)
{
return __builtin_clz(x) - (sizeof(unsigned int) * CHAR_BIT - sizeof(T) * CHAR_BIT);
}
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned long)>::type>
unsigned clz_impl(clzl_tag, T x)
{
return __builtin_clzl(x) - (sizeof(unsigned long) * CHAR_BIT - sizeof(T) * CHAR_BIT);
}
template <typename T, typename = typename std::enable_if<sizeof(T) <= sizeof(unsigned long long)>::type>
unsigned clz_impl(clzll_tag, T x)
{
return __builtin_clzll(x) - (sizeof(unsigned long long) * CHAR_BIT - sizeof(T) * CHAR_BIT);
}
sizeof(unsigned XXX) * CHAR_BIT 引数の型の幅、sizeof(T) * CHAR_BIT 引数型の幅。SFINAE は、最初の値が常に 2 番目の値以上であることを保証するため、単純にこれら 2 つの幅を減算して、結果から減算する必要がある差を取得できます。
16 ビット整数の場合、32 ビット整数との幅の差は 16 です。 、したがって、結果の 31 からそれを減算します 正しい答えを得る:15 最初の 1 はゼロ .
結論
比較的移植性の高い clz() を作成しました
GCC ビルトインは、SFINAE と優先タグ ディスパッチの助けを借りてラップされます。これにより、指定された整数型に最適なバージョンが常に選択され、unsigned int/long/long long に動的に適応します。 各プラットフォームのサイズ
GCC バージョンの完全なコードは、ここにあります。欠けているのは、ビルトインのサポートのチェックです。これは、まったく別の課題です。互換性ライブラリの形式で、そのための 1 つのソリューションを作成しました。 CMake を使用して機能のサポートを確認し、結果に基づいて自動化された回避策を提供します。その clz() 実装はここにありますが、CMake ボイラープレートにラップされています。