GoogleTest 与 Benchmark 库使用：以位图 countOnes 函数为例

单元测试与性能测试都是我们实际进行项目开发中常见的需求，一个优秀的库能够帮助我们高效地完成上述需求，专注于项目本身逻辑的开发，而不是额外花费精力于单元测试库和性能测试库的编写。就 C++ 而言，最常用的单元测试和性能测试库应该就是 Google 开源的 GoogleTest 和 Benchmark 库了，二者源代码都可在 GitHub 获取。

本文中，我们以计算一块连续内存中的位 1 的数量为例（也就是实现位图 bitmap 的 countOnes 函数，这里为了简化，只考虑按字节连续存储的位图），来看看如何使用 GoogleTest 库进行单元测试以及如何使用 Benchmark 库进行性能测试。本文涉及的源码已经同步到 GitHub：UnpureRationalist/SWARBenchmark: Performance comparison of popCount function. (github.com)。

需要说明的是，本文仅仅是最基础的介绍，主要目的是说明如何使用 GoogleTest 和 Benchmark 这两个工具，不涉及它们的高级特性。需要使用这两个库高级功能的读者请参阅官方文档。

1. 目录组织

使用 tree 命令查看目录组织情况如下：

$ tree --gitignore
.
├── CMakeLists.txt
├── README.md
├── src
│   ├── benchmark.cpp
│   ├── genString.cpp
│   ├── genString.h
│   ├── swar.cpp
│   ├── swar.h
│   └── test.cpp
└── third_party
    └── CMakeLists.txt

2 directories, 9 files

其中，third_party 目录是依赖的 GoogleTest 和 Benchmark 库所在路径，src 目录是项目源代码。项目使用 cmake 进行构建，需要在 CMakeLists.txt 文件中指定对 GoogleTest 和 Benchmark 的依赖，具体内容如下：

cmake_minimum_required(VERSION 3.10)

project(learnBenchmark
        LANGUAGES C CXX
)

set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
set(BUILD_SHARED_LIBS OFF)
set(CMAKE_CXX_STANDARD 17)
set(CMAKE_CXX_STANDARD_REQUIRED ON)

add_subdirectory(third_party)

find_package(OpenMP REQUIRED)

set(SOURCES
    src/genString.h
    src/genString.cpp
    src/swar.h
    src/swar.cpp
)

add_executable("swarBenchmark" ${SOURCES} src/benchmark.cpp)
target_link_libraries("swarBenchmark" benchmark::benchmark OpenMP::OpenMP_CXX)

enable_testing()

add_executable("swarTest" ${SOURCES} src/test.cpp)
target_link_libraries("swarTest" gtest gtest_main OpenMP::OpenMP_CXX)

项目只会生成两个可执行文件：

swarTest：单元测试可执行文件
swarBenchmark：性能测试可执行文件

2. `countOnes` 函数实现

在本文中，共实现了 5 种 countOnes 函数，其中一个是 Redis 源码中采用的 SWAR 算法 + 手动循环展开。Redis 中的实现网上已经有很多介绍文章（可参考：https://ponder.work/2020/08/01/variable-precision-SWAR-algorithm/ ），这里就简单介绍下朴素的实现算法：

long long basicPopcount(const unsigned char *s, long count) {
  long long bits = 0;
  for (long i = 0; i < count; ++i) {
    for (int j = 0; j < 8; ++j) {
      bits += (s[i] & (1 << j)) > 0;
    }
  }
  return bits;
}

long long bitAndPopcount(const unsigned char *s, long count) {
  long long bits = 0;
  for (long i = 0; i < count; ++i) {
    unsigned char c = s[i];
    while (c) {
      bits++;
      c &= c - 1;
    }
  }
  return bits;
}

long long gccBuildinPopCount(const unsigned char *s, long count) {
  long long bits = 0;
  for (long i = 0; i < count; ++i) {
    bits += __builtin_popcount(s[i]);
  }
  return bits;
}

long long openmpBasicPopCount(const unsigned char *s, long count) {
  long long bits = 0;
  #pragma omp parallel for reduction(+:bits) num_threads(2)
  for (long i = 0; i < count; ++i) {
    for (int j = 0; j < 8; ++j) {
      bits += (s[i] & (1 << j)) > 0;
    }
  }
  return bits;
}

给出源码后，其实也没什么好解释的了，内部的实现不同点如下：

bits += (s[i] & (1 << j)) > 0;：朴素位运算
c &= c - 1;：稍高级的位运算，可参考剑指 offer、力扣等了解原理
bits += __builtin_popcount(s[i]);：使用 gcc 编译器内置函数
#pragma omp parallel for reduction(+:bits) num_threads(2)：使用 OpenMP 多线程加速朴素位运算

3. 单元测试

单元测试源码路径为 src/test.cpp，源码为：

#include "genString.h"
#include "gtest/gtest.h"
#include "swar.h"

#include <ctime>
#include <random>
#include <string>

class CountOnesTest : public testing::Test {
 protected:
  CountOnesTest() = default;

  ~CountOnesTest() override = default;
};

void doCountOnesTest(int n) {
  std::string str = generateRandomString(n);
  long long redisLen = redisPopcount((void *)str.c_str(), n);
  long long basicLen = basicPopcount((const unsigned char *)str.c_str(), n);
  long long bitAndLen = bitAndPopcount((const unsigned char *)str.c_str(), n);
  long long gccAndLen = gccBuildinPopCount((const unsigned char *)str.c_str(), n);
  long long openmpBasicLen = openmpBasicPopCount((const unsigned char *)str.c_str(), n);
  EXPECT_EQ(redisLen, basicLen);
  EXPECT_EQ(redisLen, bitAndLen);
  EXPECT_EQ(redisLen, gccAndLen);
  EXPECT_EQ(redisLen, openmpBasicLen);
}

TEST_F(CountOnesTest, BasicTest) {
  int n = 1000000;
  doCountOnesTest(n);
}

TEST_F(CountOnesTest, StrongTest) {
  int times = 1000;
  for (int i = 0; i < times; ++i) {
    int n = (i + 1) * (i + 1);
    doCountOnesTest(n);
  }
}

单元测试的编写其实很简单，只需要自定义一个基础自 Test 的类：class CountOnesTest : public testing::Test，然后使用宏指定 test suite 名和 test case 名，并在内部编写单元测试逻辑即可，比如上面的：

TEST_F(CountOnesTest, BasicTest) {
  int n = 1000000;
  doCountOnesTest(n);
}

CountOnesTest 是我们自定义的类名，BasicTest 是我们给测试用例取得名字。在内部调用 doCountOnesTest 函数进行单元测试。doCountOnesTest 函数内使用 EXPECT_EQ 宏，保证不同的 countOnes 实现得到的结果相同。

运行单元测试，我们能够得到下面的输出：

$ ./swarTest 
Running main() from /home/ubuntu/code/learn_benchmark/third_party/googletest/googletest/src/gtest_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from CountOnesTest
[ RUN      ] CountOnesTest.BasicTest
[       OK ] CountOnesTest.BasicTest (30 ms)
[ RUN      ] CountOnesTest.StrongTest
[       OK ] CountOnesTest.StrongTest (9999 ms)
[----------] 2 tests from CountOnesTest (10030 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (10030 ms total)
[  PASSED  ] 2 tests.

如果单元测试失败，输出会进行提示，我们需要对源码进行修复以通过单元测试。

4. 性能测试

性能测试源码路径为 src/benchmark.cpp，具体源码为：

#include "genString.h"
#include "swar.h"

#include "gtest/gtest.h"

#include <benchmark/benchmark.h>
#include <string>
#include <vector>

std::vector<std::string> inputStrings;

void inputInit() {
  int numStr = 1000;
  int strLen = 10000;
  inputStrings.reserve(numStr);
  for (int i = 0; i < numStr; ++i) {
    inputStrings.emplace_back(generateRandomString(strLen));
  }
}

static void BM_RedisPopcount(benchmark::State &state) {
  for (auto _ : state) {
    for (const std::string &str : inputStrings) {
      redisPopcount((void *)str.c_str(), str.size());
    }
  }
}
BENCHMARK(BM_RedisPopcount);

static void BM_BasicPopCount(benchmark::State &state) {
  for (auto _ : state) {
    for (const std::string &str : inputStrings) {
      basicPopcount((const unsigned char *)str.c_str(), str.size());
    }
  }
}
BENCHMARK(BM_BasicPopCount);

static void BM_BitAndPopCount(benchmark::State &state) {
  for (auto _ : state) {
    for (const std::string &str : inputStrings) {
      bitAndPopcount((const unsigned char *)str.c_str(), str.size());
    }
  }
}
BENCHMARK(BM_BitAndPopCount);

static void BM_GccBuiltinPopCount(benchmark::State &state) {
  for (auto _ : state) {
    for (const std::string &str : inputStrings) {
      gccBuildinPopCount((const unsigned char *)str.c_str(), str.size());
    }
  }
}
BENCHMARK(BM_GccBuiltinPopCount);

static void BM_OpenmpBasicPopCount(benchmark::State &state) {
  for (auto _ : state) {
    for (const std::string &str : inputStrings) {
      openmpBasicPopCount((const unsigned char *)str.c_str(), str.size());
    }
  }
}
BENCHMARK(BM_OpenmpBasicPopCount);

int main(int argc, char **argv) {
  inputInit();

  ::benchmark::Initialize(&argc, argv);
  ::benchmark::RunSpecifiedBenchmarks();
  ::benchmark::Shutdown();
  return 0;
}

性能测试的编写也很容易，只需要定义一个函数，输入参数类型为 benchmark::State &state，然后在函数体内编写性能测试需要执行的函数，最后进行函数的注册，如上面的：

static void BM_RedisPopcount(benchmark::State &state) {
  for (auto _ : state) {
    // 编写性能测试逻辑
    for (const std::string &str : inputStrings) {
      redisPopcount((void *)str.c_str(), str.size());
    }
  }
}
BENCHMARK(BM_RedisPopcount);	// 注册性能测试函数

性能测试结果如下：

$ ./swarBenchmark
2024-06-30T01:00:01+08:00
Running ./swarBenchmark
Run on (8 X 2500 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x8)
  L1 Instruction 32 KiB (x8)
  L2 Unified 4096 KiB (x8)
  L3 Unified 28160 KiB (x1)
Load Average: 0.10, 0.07, 0.11
-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
BM_RedisPopcount          3629826 ns      3629386 ns          192
BM_BasicPopCount         25606352 ns     25604317 ns           27
BM_BitAndPopCount        98210255 ns     98202993 ns            7
BM_GccBuiltinPopCount    36949327 ns     36947015 ns           19
BM_OpenmpBasicPopCount   14287040 ns     14286005 ns           49

可以看出，Redis 的实现要远远快于其他实现，由此我们可以感受到 SWAR 算法和循环展开的魅力。而面试中希望面试者给出的解答 a & (a - 1) 在我们的测试场景下，性能反而不如最朴素的逐位按位与，gcc 的内置函数在我们的场景下同样不如朴素算法。使用 OpenMP 2 个线程加速朴素位运算算法后，能减少时间开销，但还是与 Redis 中的实现有一定差距。

5. 总结

单元测试与性能测试都是实际工作和项目开发中常见的、甚至必须的需求，但是在学校中却较少接触到，导致了知识面的一些欠缺。本文以位图的 countOnes 函数的不同实现为例，介绍了 GoogleTest 和 Benchmark 的基本使用方法，补全程序员必备工具链的一小环。

工具

#GoogleTest #Benchmark #bitmap #countOnes

GoogleTest 与 Benchmark 库使用：以位图 countOnes 函数为例

https://arcsin2.cloud/2024/06/30/GoogleTest-与-Benchmark-库使用：以位图-countOnes-函数为例/

作者

arcsin2

发布于

2024年6月30日

许可协议

Dolphin DB 实习面经上一篇

LevelDB 源码阅读三：工具函数一览下一篇

GoogleTest 与 Benchmark 库使用：以位图 countOnes 函数为例

1. 目录组织

2. countOnes 函数实现

3. 单元测试

4. 性能测试

5. 总结

2. `countOnes` 函数实现