🐸

C++でlog2(自然数)を高速計算

2022/07/04に公開

2件

0. はじめに

log2(2) = 1
log2(4) = 2
log2(8) = 3
...
みたいなlog2(自然数）を高速に計算する方法。

log2(3) = 1.5..みたいに、端数が出た場合は1にする（最大整数に丸める）ものとする。
要は、自然数を表現する所要ビット数を求める。

1. 更新

2022/07/06 初稿
2022/07/08 std::bit_widthを使う方法、処理速度の計測結果を追加

2. 実装

例を3つ紹介する。
例2はコンパイラに依存した実装。
例3はC++のバージョンに依存した実装。

例1: ビット演算を使う方法

int log2_with_bm(int x)
{
  assert(x > 0);
  int ret = 0;
  if (x & 0xffff0000)
  {
    x >>= 16;
    ret += 16;
  }
  if (x & 0x0000ff00)
  {
    x >>= 8;
    ret += 8;
  }
  if (x & 0x000000f0)
  {
    x >>= 4;
    ret += 4;
  }
  if (x & 0x0000000c)
  {
    x >>= 2;
    ret += 2;
  }
  if (x & 0x00000002)
  {
    x >>= 1;
    ret += 1;
  }
  return ret;
}

例2: CLZ(Gnu系コンパイラ依存)を使う方法

#ifdef __GNUC__
int log2_with_clz(int x)
{
  assert(x > 0);
  return 31 - __builtin_clz(x);
}
#endif

例3: std::bit_width(C++20依存)を使う方法

#if __cplusplus >= 202002L
#include <bit>
using namespace std;
int log2_with_bw(int x)
{
  assert(x > 0);
  return bit_width(static_cast<uint32_t>(x)) - 1;
}
#endif

3. テスト

浮動小数で計算した結果をリファレンスとして一致することを確認した。
浮動小数計算での実装は以下。

#include <cmath>
using namespace std;
int log2_with_float(int x)
{
  assert(x > 0);
  const float fl2f = floor(log2(x));
  return static_cast<int>(fl2f);
}

テストコード

floorlog2.hは、2節で説明した関数のプロトタイプ宣言。
GoogleTest使った。

#include <gtest/gtest.h>
#include "floorlog2.h"

TEST(FloorLog2, WithFloat)
{
  EXPECT_EQ(1, log2_with_float(2)); // floor( log2(2) ) = floor(   1   ) = 1
  EXPECT_EQ(1, log2_with_float(3)); // floor( log2(3) ) = floor( 1.5.. ) = 1
  EXPECT_EQ(2, log2_with_float(4)); // floor( log2(4) ) = floor(   2   ) = 2
  EXPECT_EQ(2, log2_with_float(5)); // floor( log2(5) ) = floor( 2.3.. ) = 2
  EXPECT_EQ(2, log2_with_float(7)); // floor( log2(7) ) = floor( 2.8.. ) = 2
  EXPECT_EQ(3, log2_with_float(8)); // floor( log2(8) ) = floor(   3   ) = 3
}

TEST(FloorLog2, WithBm)
{
  for (int i = 1; i < INT_MAX; ++i)
    EXPECT_EQ(log2_with_float(i), log2_with_bm(i));
}

#ifdef __GNUC__
TEST(FloorLog2, WithClz)
{
  for (int i = 1; i < INT_MAX; ++i)
    EXPECT_EQ(log2_with_float(i), log2_with_clz(i));
}
#endif

#if __cplusplus >= 202002L
TEST(FloorLog2, WithBw)
{
  for (int i = 1; i < INT_MAX; ++i)
    EXPECT_EQ(log2_with_float(i), log2_with_bw(i));
}
#endif

コンパイル

g++ -std=c++20 -O2 -MMD -MP -o fl2ut fl2ut.cpp floorlog2.cpp -llibgtest -llibgmock -llibgmock_main

実行結果

OKってでたのでOK（語彙力無）

$ ./fl2ut.exe
Running main() from gmock_main.cc
[==========] Running 4 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 4 tests from FloorLog2
[ RUN      ] FloorLog2.WithFloat
[       OK ] FloorLog2.WithFloat (0 ms)
[ RUN      ] FloorLog2.WithBm
[       OK ] FloorLog2.WithBm (65968 ms)
[ RUN      ] FloorLog2.WithClz
[       OK ] FloorLog2.WithClz (62592 ms)
[ RUN      ] FloorLog2.WithBw
[       OK ] FloorLog2.WithBw (62513 ms)
[----------] 4 tests from FloorLog2 (191074 ms total)

[----------] Global test environment tear-down
[==========] 4 tests from 1 test suite ran. (191074 ms total)
[  PASSED  ] 4 tests.

4. 処理速度

浮動小数計算での実装をリファレンスとし、どれくらい高速化できるか結果を示す。
関数の1回あたりの平均処理時間で比較する。単位はclock cycle。

計測環境

OS: Windows10 Pro
CPU: i7-7800X@3.50GHz
コンパイラ: gcc version 11.2.0@x86_64-w64-mingw32
CPUの動作周波数の揺らぎが少ないように消費電力設定で固定クロックモードにした。

結果

例1は、リファレンスより約9.7倍速。
例2と例3は、リファレンスより約15.5倍速。

$ ./fl2sp.exe
               float: 85.19 [clk]　// リファレンス
    bit manipulation: 8.76 [clk]   // 例1
       __builtin_clz: 5.50 [clk]   // 例2
      std::bit_width: 5.50 [clk]   // 例3

計測コード

#include "floorlog2.h"
#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
#include <cstdio>
#include <cstdint>

static constexpr int L = 1000;

template<class F>
double get_fl2_clk(F f)
{
  uint64_t beg, end;
  uint32_t tmp;

  beg = __rdtscp(&tmp);
  for (int i = 1; i < L; ++i)
    f(i);
  end = __rdtscp(&tmp);

  return static_cast<double>(end - beg) / (L - 1);
}

int main(int argc, char **argv)
{
  printf("%20s: %.2f [clk]\n",
         "float",
         get_fl2_clk(log2_with_float)); 
  printf("%20s: %.2f [clk]\n",
         "bit manipulation",
         get_fl2_clk(log2_with_bm));
#ifdef __GNUC__
  printf("%20s: %.2f [clk]\n",
         "__builtin_clz",
         get_fl2_clk(log2_with_clz));
#endif
#if __cplusplus >= 202002L
  printf("%20s: %.2f [clk]\n",
         "std::bit_width",
         get_fl2_clk(log2_with_bw));
#endif
}

コンパイルは以下

$ g++ -std=c++20 -O2 -MMD -MP -o fl2sp fl2sp.cpp floorLog2.cpp

例2と例3の処理時間が同じ理由

結論だけ言えば、std::bit_widthも__builtin_clzを使ってるから。

gccのstd::bit_widthのコードを読むとstd::__countl_zero()を呼び出している。

std::__countl_zero()の実装を見ると以下。

5. まとめ

C++20が使える環境なら、std::bit_widthが簡潔で早いので一番お勧め
コンパイラなどの環境を気にする人なら、ビット演算でも約9倍くらい早くなるのでお勧め
速さはそれ自体に価値がある

Discussion

tani

C++20では bit 標準ライブラリが使えるので以下のように書くと高速です．

#include<bit>
#include <cassert>
int main() {
    assert(std::bit_width(2ull) - 1 == 1);
    return 0;
}

ありがとうございます。知りませんでした。
この内容も記事に反映したので、よかったら読んでみてください。