好的,为了“解决”哪个更快/更慢等争论,我把所有代码放到一个程序中[我“希望”我已经正确地归功于每个代码片段的原作者]。
下面可以找到代码,以检查我在将其转换为函数时是否正确解释了代码。我确实运行了它,没有适当的输出,并检查了每个函数是否给出相同的结果[请注意,在某些情况下,顺序略有不同 - 因此,我进行了变化,以使我的代码运行另一种方式,只是为了看到它是否给出了“正确”的结果]。因此,废话不多说,以下是结果:
mats1 time in clocks per iteration 10.3457
mats2 time in clocks per iteration 10.4785
mats3 time in clocks per iteration 10.5538
viraptor time in clocks per iteration 6.24603
lemees time in clocks per iteration 14.4818
npe time in clocks per iteration 13.1455
alex time in clocks per iteration 24.8272
mats1 time in clocks per iteration 7.62338
mats2 time in clocks per iteration 7.36226
mats3 time in clocks per iteration 7.45361
viraptor time in clocks per iteration 2.09582
lemees time in clocks per iteration 9.43744
npe time in clocks per iteration 7.51016
alex time in clocks per iteration 19.3554
(来自viraptor的结果,基于core i5和clang++ 3.2)
mats1 time in clocks per iteration 12.956
mats2 time in clocks per iteration 13.4395
mats3 time in clocks per iteration 13.3178
viraptor time in clocks per iteration 2.12914
lemees time in clocks per iteration 13.9267
npe time in clocks per iteration 16.2102
alex time in clocks per iteration 13.8705
这是在3.4GHz的AMD Athlon2上的时钟周期 - 我没有现代的英特尔机器 - 如果有人希望在那上运行代码,我很想看看它的样子。我相当确定所有的东西都在缓存中良好运行 - 也许除了获取一些值以进行检查之外。
因此,赢家显然是viraptor,大约比“我的”代码快40%。Alex的代码没有任何跳转/分支,但似乎仍然比其他选择运行得慢。不确定为什么npe的结果比我的慢那么多 - 它几乎做了同样的事情(当从g ++的汇编器输出查看代码时,代码看起来非常相似)。
#include <iostream>
#include <fstream>
#include <cstdint>
using namespace std;
const int SIZE = 1000000;
uint64_t g_val[SIZE];
ofstream nulloutput;
static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
#define BITA_TO_B(x, a, b) (((x) >> (a-b)) & (1 << b))
unsigned char get_col_mats1(uint64_t val, int col)
{
return BITA_TO_B(val, 56+col, 7) |
BITA_TO_B(val, 48+col, 6) |
BITA_TO_B(val, 40+col, 5) |
BITA_TO_B(val, 32+col, 4) |
BITA_TO_B(val, 24+col, 3) |
BITA_TO_B(val, 16+col, 2) |
BITA_TO_B(val, 8+col, 1) |
BITA_TO_B(val, 0+col, 0);
}
unsigned char get_col_mats2(uint64_t val, int col)
{
return BITA_TO_B(val, 63-col, 7) |
BITA_TO_B(val, 55-col, 6) |
BITA_TO_B(val, 47-col, 5) |
BITA_TO_B(val, 39-col, 4) |
BITA_TO_B(val, 31-col, 3) |
BITA_TO_B(val, 23-col, 2) |
BITA_TO_B(val, 15-col, 1) |
BITA_TO_B(val, 7-col, 0);
}
unsigned char get_col_viraptor(uint64_t board, int col) {
const uint64_t column_mask = 0x8080808080808080ull;
const uint64_t magic = 0x2040810204081ull ;
uint64_t column = board & (column_mask >> col);
column <<= col;
column *= magic;
return (column >> 56) & 0xff;
}
unsigned char get_col_alex(uint64_t bitboard, int col)
{
unsigned char result;
result |= (bitboard & (1ULL << 63-col)) ? 0x80 : 0;
result |= (bitboard & (1ULL << 55-col)) ? 0x40 : 0;
result |= (bitboard & (1ULL << 47-col)) ? 0x20 : 0;
result |= (bitboard & (1ULL << 39-col)) ? 0x10 : 0;
result |= (bitboard & (1ULL << 31-col)) ? 0x08 : 0;
result |= (bitboard & (1ULL << 23-col)) ? 0x04 : 0;
result |= (bitboard & (1ULL << 15-col)) ? 0x02 : 0;
result |= (bitboard & (1ULL << 7-col)) ? 0x01 : 0;
return result;
}
unsigned char get_col_lemees(uint64_t val, int column)
{
int result = 0;
int source_bitpos = 7 - column;
for (int target_bitpos = 0; target_bitpos < 8; ++target_bitpos)
{
bool bit = (val >> source_bitpos) & 1;
result |= bit << target_bitpos;
source_bitpos += 8;
}
return result;
}
int get(uint64_t board, int row, int col) {
return (board >> (row * 8 + col)) & 1;
}
uint8_t get_col_npe(uint64_t board, int col) {
uint8_t ret = 0;
for (int i = 0; i < 8; ++i) {
ret = (ret << 1) + get(board, i, col);
}
return ret;
}
#define BITA_TO_B2(x, a, b) (((x) >> (a-b)) & (1 << b))
unsigned char get_col_mats3(uint64_t val, int col)
{
return BITA_TO_B2(val, 63-col, 7) |
BITA_TO_B2(val, 55-col, 6) |
BITA_TO_B2(val, 47-col, 5) |
BITA_TO_B2(val, 39-col, 4) |
BITA_TO_B2(val, 31-col, 3) |
BITA_TO_B2(val, 23-col, 2) |
BITA_TO_B2(val, 15-col, 1) |
BITA_TO_B2(val, 7-col, 0);
}
template<unsigned char (*f)(uint64_t val, int col)>
void runbench(const char *name)
{
unsigned char col[8] = {0};
uint64_t long t = rdtsc();
for(int j = 0; j < SIZE; j++)
{
uint64_t val = g_val[j];
for(int i = 0; i < 8; i++)
{
col[i] += f(val, i);
}
}
t = rdtsc() - t;
for(int i = 0; i < 8; i++)
{
nulloutput<< "col " << i << " has bits " << hex << (int)col[i] << endl;
}
cout << name << " time in clocks per iteration " << dec << t / (8.0 * SIZE) << endl;
}
#define BM(name) void bench_##name() { runbench<get_col_##name>(#name); }
BM(mats1);
BM(mats2);
BM(mats3);
BM(viraptor);
BM(lemees);
BM(npe);
BM(alex);
struct function
{
void (*func)(void);
const char *name;
};
#define FUNC(f) { bench_##f, #f }
function funcs[] =
{
FUNC(mats1),
FUNC(mats2),
FUNC(mats3),
FUNC(viraptor),
FUNC(lemees),
FUNC(npe),
FUNC(alex),
};
int main()
{
unsigned long long a, b;
int i;
int sum = 0;
nulloutput.open("/dev/nul");
for(i = 0; i < SIZE; i++)
{
g_val[i] = rand() + ((long)rand() << 32L);
}
unsigned char col[8];
for(i = 0; i < sizeof(funcs)/sizeof(funcs[0]); i++)
{
funcs[i].func();
}
}