Summary:
Adds a bitreverse function to Bits.h
AFAIK there is no great way to do this on x86, takes ~4-5ns.
arm has a single instruction we can drop in in the future.
Reviewed By: yfeldblum
Differential Revision:
D6459283
fbshipit-source-id:
129db196b2fac95386f601ae57843aa87523b915
}
}
+template <typename T>
+T bitReverse(T n) {
+ auto m = static_cast<typename std::make_unsigned<T>::type>(n);
+ m = ((m & 0xAAAAAAAAAAAAAAAA) >> 1) | ((m & 0x5555555555555555) << 1);
+ m = ((m & 0xCCCCCCCCCCCCCCCC) >> 2) | ((m & 0x3333333333333333) << 2);
+ m = ((m & 0xF0F0F0F0F0F0F0F0) >> 4) | ((m & 0x0F0F0F0F0F0F0F0F) << 4);
+ return static_cast<T>(Endian::swap(m));
+}
+
} // namespace folly
}
}
+BENCHMARK_DRAW_LINE();
+BENCHMARK(reverse, iters) {
+ uint64_t b = 0;
+ for (unsigned long i = 0; i < iters; ++i) {
+ b = folly::bitReverse(i + b);
+ folly::doNotOptimizeAway(b);
+ }
+}
+
int main(int argc, char** argv) {
gflags::ParseCommandLineFlags(&argc, &argv, true);
folly::runBenchmarks();
Benchmarks run on dual Xeon X5650's @ 2.67GHz w/hyperthreading enabled
(12 physical cores, 12 MB cache, 72 GB RAM)
-Benchmark Iters Total t t/iter iter/sec
-------------------------------------------------------------------------------
-* nextPowTwoClz 1000000 1.659 ms 1.659 ns 574.8 M
+============================================================================
+folly/test/BitsBenchmark.cpp relative time/iter iters/s
+============================================================================
+nextPowTwoClz 0.00fs Infinity
+----------------------------------------------------------------------------
+isPowTwo 731.61ps 1.37G
+----------------------------------------------------------------------------
+reverse 4.84ns 206.58M
+============================================================================
*/
#include <folly/Bits.h>
+#include <folly/Random.h>
#include <random>
#include <folly/portability/GTest.h>
EXPECT_NE(d, Endian::swap(d));
EXPECT_EQ(d, Endian::swap(Endian::swap(d)));
}
+
+uint64_t reverse_simple(uint64_t v) {
+ uint64_t r = 0;
+
+ for (int i = 0; i < 64; i++) {
+ r <<= 1;
+ r |= v & 1;
+ v >>= 1;
+ }
+ return r;
+}
+
+TEST(Bits, BitReverse) {
+ EXPECT_EQ(folly::bitReverse<uint8_t>(0), 0);
+ EXPECT_EQ(folly::bitReverse<uint8_t>(1), 128);
+ for (int i = 0; i < 100; i++) {
+ uint64_t v = folly::Random::rand64();
+ EXPECT_EQ(folly::bitReverse(v), reverse_simple(v));
+ uint32_t b = folly::Random::rand32();
+ EXPECT_EQ(folly::bitReverse(b), reverse_simple(b) >> 32);
+ }
+}