14

OK、少し複雑に聞こえるかもしれませんが、これが私がやろうとしていることです:

  • 例えば取る10101010101
  • そして戻り値{ 0, 2, 4, 6, 8, 10 }- 設定されたビットのすべての位置を含む配列

これは私のコードです:

UINT DQBitboard::firstBit(U64 bitboard)
{
    static const int index64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5  };

    static const U64 debruijn64 = 0x07EDD5E59A4E28C2ULL;

    #pragma warning (disable: 4146)
    return index64[((bitboard & -bitboard) * debruijn64) >> 58];  
}

vector<UINT> DQBitboard::bits(U64 bitboard)
{
    vector<UINT> res;

    while (bitboard)
    {
        UINT first = DQBitboard::firstBit(bitboard);
        res.push_back(first);

        bitboard &= ~(1ULL<<first);
    }

    return res;
}

そして、コードは確実に機能します。

私のポイントは：

  • あなたが考えているより速い実装はありますか？
  • 最適化できるものはありますか? もしそうなら、何？

ヒント ：

  • UINTのtypedefですunsigned int
  • U64のtypedefですunsigned long long
  • どちらの方法もstatic inline.
4

8 に答える 8

10

プロファイリングできる別の提案を次に示します (さらに最適化するために、他の提案と組み合わせることができます)。ここでのループはO(number of set bits).

vector<UINT> bits_set (UINT64 data) 
{
    UINT n;
    vector<UINT> res;
    res.reserve(64);
    for (n = 0; data != 0; n++, data &= (data - 1))
    {
        res.push_back(log2(data & ~(data-1)));
    }
    return res;
}
于 2012-12-30T00:05:29.077 に答える
7

ビットシフトは本当に安いです。ルックアップ テーブルはキャッシュ スペースを消費し、ルックアップにも整数乗算があります。巧妙なテクニックよりも、ブルートフォースだけの方が速いと思います。

vector<UINT> DQBitboard::bits(U64 bitboard)
{
    vector<UINT> res;
    res.reserve(64);
    uint_fast8_t pos = 1;

    do {
        if (bitboard & 1) res.push_back(pos);
        ++pos;
    } while (bitboard >>= 1);

    return res;
}

ループを少し展開すると、さらに高速になる可能性があります。

これstd::vectorまでで最も高価な部品です。ビットボードを直接使用することを検討してください。例えば：

struct bitboard_end_iterator{};
struct bitboard_iterator
{
    U64 value;
    uint_fast8_t pos;

    bitboard_iterator(U64 bitboard) : value(bitboard), pos(0)
    {
        ++(*this);
    }
    UINT operator*() const { return pos + 1; }
    bool operator==( bitboard_end_iterator ) const { return pos == 64; }
    operator bool() const { return pos < 64; }
    bitboard_iterator& operator++()
    {
        while (U64 prev = value) {
            value >>= 1;
            ++pos;
            if (prev & 1) return *this;
        }
        pos = 64;
        return *this;
    }
};

今、あなたは書くことができます

for( bitboard_iterator it(bitboard); it; ++it )
    cout << *it;

ビットのリストが表示されると思います。

バージョン 2:

class bitboard_fast_iterator
{
    U64 value;
    uint_fast8_t pos;

public:
    bitboard_fast_iterator(U64 bitboard = 0) : value(bitboard), pos(__builtin_ctzll(value)) {}
    UINT operator*() const { return pos + 1; }
    operator bool() const { return value != 0; }
    bitboard_iterator& operator++()
    {
        value &= ~(1ULL << pos);
        pos = __builtin_ctzll(value);
        return *this;
    }
};
于 2012-12-29T23:42:05.477 に答える
6

bst アセンブリ命令を使用すると、より高速に動作するかどうか疑問に思っていました。そのため、3 つの実装を試し、1,000 万回の反復で次の結果を得ました。

あなたの実装 (Dr.Kameleon) 1.77 秒

log2() の実装 (icepack) 2.17 秒

私のアセンブリ実装 (私) 0.16 秒

出力：

bits version:
Function started at 0
           ended at 177
              spent 177 (1.770000 seconds)
c version:
Function started at 177
           ended at 394
              spent 217 (2.170000 seconds)
c version:
Function started at 394
           ended at 410
              spent 16 (0.160000 seconds)

C/C++ についての 1 つのポイント、静的は恐ろしいです。実際には、CPU命令のリストでコンパイルされます（私が期待するものでもありません!!!）代わりに、名前のない名前空間で関数の外側の配列を使用してください。そうすれば期待通りの効果が得られます。アセンブリでは、.long (または他のサイズ) を使用してから %rip を使用して、IP からのデータを参照できます。

注: コンパイルすると、アセンブリ バージョンで使用されているサイズ (n) が表示されないため、返された配列が有効かどうかはわかりません。それ以外では、コード自体が 5 つのアセンブリ命令のループになるため、速度がわずかに向上します (約 10 倍)。

log2() が遅い理由は、数値を xmm レジスタに変換してから別の関数を呼び出すためです。次に、xmm レジスターを通常のレジスターに戻します。

#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <unistd.h>
#include <sys/times.h>
#include <string.h>
#include <math.h>
#include <vector>

using namespace std;

namespace
{
const int index64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5  };
const uint64_t debruijn64 = 0x07EDD5E59A4E28C2ULL;
}

int firstBit(uint64_t bitboard)
{
    return index64[((bitboard & -bitboard) * debruijn64) >> 58];  
}

vector<int> bits(uint64_t bitboard)
{
    vector<int> res;
    res.reserve(64);

    while(bitboard)
    {
        int first = firstBit(bitboard);
        res.push_back(first);

        bitboard &= ~(1ULL << first);
    }
    return res;
}



vector<int> bits_c(uint64_t bitboard)
{
    int n;
    vector<int> res;
    res.reserve(64);
    for (n = 0; bitboard != 0; n++, bitboard &= (bitboard - 1))
    {
        res.push_back(log2(bitboard & ~(bitboard - 1)));
    }
    return res;
}


vector<int> bits_asm(uint64_t bitboard)
{
    int64_t n(0);
    int res[64];
    asm(
    "bsf %[b], %%rax\n\t"
    "je exit\n\t"
    ".align 16\n"
"loop:\n\t"
    "mov %%eax, (%[r],%[n],4)\n\t"
    "btr %%rax, %[b]\n\t"
    "inc %[n]\n\t"
    "bsf %[b], %%rax\n\t"
    "je loop\n"
"exit:\n\t"
    : /* output */ "=r" (n)
    : /* input */ [n] "r" (n), [r] "r" (res), [b] "r" (bitboard)
    : /* state */ "eax", "cc"
    );
    return vector<int>(res, res + n);
}




class run_timer
{
public:
    run_timer()
    {
    }

    void start()
    {
        times(&f_start);
    }

    void stop()
    {
        times(&f_stop);
    }

    void report(const char *msg)
    {
        printf("%s:\n"
               "Function started at %ld\n"
               "           ended at %ld\n"
               "              spent %ld (%f seconds)\n",
               msg,
               f_start.tms_utime,
               f_stop.tms_utime,
               f_stop.tms_utime - f_start.tms_utime,
               (double)(f_stop.tms_utime - f_start.tms_utime)/(double)sysconf(_SC_CLK_TCK));
    }

    struct tms f_start;
    struct tms f_stop;
};


int main(int argc, char *argv[])
{
    run_timer t;

    t.start();
    for(int i(0); i < 10000000; ++i)
    {
        bits(rand());
    }
    t.stop();
    t.report("bits version");

    t.start();
    for(int i(0); i < 10000000; ++i)
    {
        bits_c(rand());
    }
    t.stop();
    t.report("c version");

    t.start();
    for(int i(0); i < 10000000; ++i)
    {
        bits_asm(rand());
    }
    t.stop();
    t.report("c version");

    return 0;
}

次のコマンド ラインを使用して g++ でコンパイルします。

c++ -msse4.2 -O2 -o bits -c bits.cpp

-msse4.2 が log2() バージョンの問題である可能性があると思われるかもしれませんが、それなしで試してみたところ、log2() は遅くなりました。

ところで、この方法は移植性がないためお勧めしません。これらの命令を理解できるのは、Intel ベースのコンピューターだけです。

于 2012-12-30T02:22:24.510 に答える
5

or命令をfirstBit使用して関数を組み込み関数に置き換えて、大幅な高速化を実現します。BSFBSR

gcc では__builtin_ffsll、__builtin_ctzll

Visual C+ を使用_BitScanForwardし、_BitScanReverse

于 2012-12-30T00:36:04.290 に答える
3 
const size_t size = sizeof(U64)*8;
U64 val = 1;

vector<UINT> res;
res.reserve(size);

for ( size_t i = size; i > 0; --i ) {
  if ( ( val & bitboard ) != 0 ) {
    res.push_back(i);
  }
  val <<= 1;
}
于 2012-12-29T23:36:34.433 に答える
3

私が今考えることができる最も速いのは、事前に生成されたmapすべての数値の配列 (すべての数値である必要はありません。たとえば、数値を 8 ビットまたは 16 ビットの部分に分割し、返された配列を適​​切な追加で連結して、ビットの実際の位置を考慮することができます) ）。

于 2012-12-29T23:33:11.213 に答える
3

私は単純なバージョンを試してみました。これは約 2 ～ 3 倍速くクロックインしましたが、最初にベクトルを予約 () しました。リザーブを元のアルゴリズムに適用すると、素朴なアルゴリズムを打ち負かしました。

したがって、ここでは、ビット操作 (または次のビット関数で使用される乗算) よりも、ベクトル演算の方が大きなコストであると思われます。

設定された最下位ビットの検索に関しては、他にもスピードアップが必要です。私のローカルの log2 バージョンは貧弱で、元の投稿で指定された機能はそれほど安くはありません。

これが私の最善の試みです：

void bits(uint64 bitboard, vector<int> &res)
{
    res.resize(64);
    int i = 0;
    while (bitboard)
    {
        int first;
        _BitScanForward64((DWORD *)&first, bitboard);
        res[i++] = first;
        bitboard &= ~(1ULL<<first);
    }
    res.resize(i);
}

firstBit 関数を asm 組み込み関数に置き換えました。組み込み関数を使用すると、ここで大きな効果が得られました。(これは明らかに移植可能なコードではありませんが、GCC の変種はあまりトリッキーではないと思います)。

また、ベクトルが常に動的に割り当て/コピーされるのではなく、適度に永続的であると想定し、適切にサイズ変更します。

于 2012-12-29T23:46:28.343 に答える
2

実際には、最も速くて簡単な方法は単純にループすることだと思いますが、後でコピーを作成する代わりにベクターを渡すと、少し速くなるはずです。

void DQBitboard::bits(U64 bitboard, vector<UINT> &res)
{
    res.clear();   // Make sure vector is empty. Not necessary if caller does this!
    int bit = 0;
    while (bitboard)
    {
        if (bitboard & 1) 
            res.push_back(bit);
        bit++;
        bitboard >>= 1;
    }

    return res;
}

findfirst の乗算には少しコストがかかるため、本当に価値があるとは思えません。

于 2012-12-29T23:46:54.397 に答える