123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113 |
- /*
- * Copyright 2011-present Facebook, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- #include <folly/container/BitIterator.h>
- #include <algorithm>
- #include <glog/logging.h>
- #include <folly/Benchmark.h>
- #include <folly/init/Init.h>
- #include <folly/small_vector.h>
- using namespace folly;
- namespace {
- template <class BaseIter>
- BitIterator<BaseIter> simpleFFS(
- BitIterator<BaseIter> begin,
- BitIterator<BaseIter> end) {
- return std::find(begin, end, true);
- }
- template <class FFS>
- void runFFSTest(FFS fn) {
- constexpr size_t const maxblocks = 3;
- constexpr size_t const bpb = 8 * sizeof(uint64_t);
- for (size_t nblocks = 1; nblocks <= maxblocks; ++nblocks) {
- small_vector<uint64_t, maxblocks> data(nblocks, 0);
- size_t nbits = nblocks * bpb;
- auto begin = makeBitIterator(data.cbegin());
- auto end = makeBitIterator(data.cend());
- DCHECK_EQ(nbits, end - begin);
- DCHECK(begin != end);
- // Try every possible combination of first bit set (including none),
- // start bit, end bit
- for (size_t firstSet = 0; firstSet <= nbits; ++firstSet) {
- data.assign(nblocks, 0);
- if (firstSet) {
- size_t b = firstSet - 1;
- data[b / bpb] |= (1ULL << (b % bpb));
- }
- for (size_t startBit = 0; startBit <= nbits; ++startBit) {
- for (size_t endBit = startBit; endBit <= nbits; ++endBit) {
- auto p = begin + startBit;
- auto q = begin + endBit;
- p = fn(p, q);
- doNotOptimizeAway(p);
- if (firstSet < startBit + 1 || firstSet >= endBit + 1) {
- DCHECK_EQ(endBit, p - begin)
- << " firstSet=" << firstSet << " startBit=" << startBit
- << " endBit=" << endBit << " nblocks=" << nblocks;
- } else {
- DCHECK_EQ(firstSet - 1, p - begin)
- << " firstSet=" << firstSet << " startBit=" << startBit
- << " endBit=" << endBit << " nblocks=" << nblocks;
- }
- }
- }
- }
- }
- }
- void runSimpleFFSTest(int iters) {
- while (iters--) {
- runFFSTest([](auto first, auto last) { return simpleFFS(first, last); });
- }
- }
- void runRealFFSTest(int iters) {
- while (iters--) {
- runFFSTest([](auto first, auto last) { return findFirstSet(first, last); });
- }
- }
- } // namespace
- BENCHMARK(SimpleFFSTest, iters) {
- runSimpleFFSTest(iters);
- }
- BENCHMARK(RealFFSTest, iters) {
- runRealFFSTest(iters);
- }
- /* --bm_min_iters=10 --bm_max_iters=100
- Benchmark Iters Total t t/iter iter/sec
- ------------------------------------------------------------------------------
- runSimpleFFSTest 10 4.82 s 482 ms 2.075
- runRealFFSTest 19 2.011 s 105.9 ms 9.447
- */
- int main(int argc, char** argv) {
- folly::init(&argc, &argv);
- folly::runBenchmarks();
- return 0;
- }
|