2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #include <folly/Bits.h>
21 #include <type_traits>
24 #include <folly/Benchmark.h>
25 #include <folly/portability/GFlags.h>
26 #include <folly/portability/GTest.h>
28 using namespace folly;
29 using namespace folly::bititerator_detail;
33 template <class INT, class IT>
34 void checkIt(INT exp, IT& it) {
35 typedef typename std::make_unsigned<INT>::type utype;
36 size_t bits = std::numeric_limits<utype>::digits;
38 for (size_t i = 0; i < bits; ++i) {
45 template <class INT, class IT>
46 void checkRange(INT exp, IT begin, IT end) {
47 typedef typename std::make_unsigned<INT>::type utype;
50 auto bitEnd = makeBitIterator(end);
51 for (BitIterator<IT> it = makeBitIterator(begin); it != bitEnd; ++it, ++i) {
60 TEST(BitIterator, Simple) {
64 auto bi(makeBitIterator(v.begin()));
67 checkRange(0x0000004200000010ULL, v.begin(), v.end());
77 *++bi = true; // 128 (note pre-increment)
82 TEST(BitIterator, Const) {
86 auto bi(makeBitIterator(v.cbegin()));
93 template <class BaseIter>
94 BitIterator<BaseIter> simpleFFS(BitIterator<BaseIter> begin,
95 BitIterator<BaseIter> end) {
96 return std::find(begin, end, true);
100 void runFFSTest(FFS fn) {
101 static const size_t bpb = 8 * sizeof(uint64_t);
102 std::vector<uint64_t> data;
103 for (size_t nblocks = 1; nblocks <= 3; ++nblocks) {
104 size_t nbits = nblocks * bpb;
105 data.resize(nblocks);
106 auto begin = makeBitIterator(data.cbegin());
107 auto end = makeBitIterator(data.cend());
108 EXPECT_EQ(nbits, end - begin);
109 EXPECT_FALSE(begin == end);
111 // Try every possible combination of first bit set (including none),
112 // start bit, end bit
113 for (size_t firstSet = 0; firstSet <= nbits; ++firstSet) {
114 data.assign(nblocks, 0);
116 size_t b = firstSet - 1;
117 data[b / bpb] |= (1ULL << (b % bpb));
119 for (size_t startBit = 0; startBit <= nbits; ++startBit) {
120 for (size_t endBit = startBit; endBit <= nbits; ++endBit) {
121 auto p = begin + startBit;
122 auto q = begin + endBit;
124 if (firstSet < startBit + 1 || firstSet >= endBit + 1) {
125 EXPECT_EQ(endBit, p - begin)
126 << " firstSet=" << firstSet << " startBit=" << startBit
127 << " endBit=" << endBit << " nblocks=" << nblocks;
129 EXPECT_EQ(firstSet - 1, p - begin)
130 << " firstSet=" << firstSet << " startBit=" << startBit
131 << " endBit=" << endBit << " nblocks=" << nblocks;
139 void runSimpleFFSTest(int iters) {
140 auto fn = simpleFFS<std::vector<uint64_t>::const_iterator>;
146 void runRealFFSTest(int iters) {
147 auto fn = findFirstSet<std::vector<uint64_t>::const_iterator>;
155 TEST(BitIterator, SimpleFindFirstSet) {
159 TEST(BitIterator, FindFirstSet) {
163 BENCHMARK(SimpleFFSTest, iters) {
164 runSimpleFFSTest(iters);
166 BENCHMARK(RealFFSTest, iters) {
167 runRealFFSTest(iters);
170 /* --bm_min_iters=10 --bm_max_iters=100
172 Benchmark Iters Total t t/iter iter/sec
173 ------------------------------------------------------------------------------
174 runSimpleFFSTest 10 4.82 s 482 ms 2.075
175 runRealFFSTest 19 2.011 s 105.9 ms 9.447
179 int main(int argc, char** argv) {
180 testing::InitGoogleTest(&argc, argv);
181 gflags::ParseCommandLineFlags(&argc, &argv, true);
182 auto ret = RUN_ALL_TESTS();
183 if (!ret && FLAGS_benchmark) {
184 folly::runBenchmarks();