前言

2026-10-05 update

今天本来想做第一个homework的，顺手想提交project 0，没想到还需要提交到线上检查，一查果然有问题。而且他们的clang-format和clang-tidy都会严查，文章的代码就不改了，运行一下检查脚本能看到问题在哪。

上次做这种课程还是在24年，本准备在做完6.S081后一鼓作气把DB的课也看了，结果做完一个实验就丢到现在。刚好最近看到Andy Pavlo开始更新Fall 2026了，不如重启CMU15445，古法编程，启动！

选的是Fall 2025的课程，目前已经更新完毕：

课程实验都是基于bustub这样一个教学用DB来做的，可以根据课程网站内Schedule的最后一天来找到对应的commit切出来新建分支。这样就可以美美做上之前的实验了。

Project0: C++ Primer

其实每年的C++ Primer都不太一样，记得之前刷的是23年的，当时的任务还是实现一个巨难的COW的树，好像是一个上交毕业的老哥去CMU整的，有兴趣的朋友可以看看。今年的C++ Primer是要写一个Count-min sketch的结构，示例是用于统计访问IP的至多访问次数。原理可以看看这两个视频：

第二个视频还额外介绍了布隆过滤器和HyperLogLog算法，当然这里就不重复原理了。

Task1

通读下来不难发现，主要是让我们实现一个Count-min sktech的数据结构/类，这个数据结构支持以下操作：

1CountMinSketch(width, depth): constructor, creates a count-min sketch with width columns (buckets) and depth rows (hash functions).
2CountMinSketch(&&other): move constructor, transfers ownership of sketch resources from another instance.
3operator=(&&other): move assignment, moves sketch resources from another instance to this one.
4Insert(item): inserts the specified item into the count-min sketch. this is expected to be thread-safe
5Count(&item): returns the estimated frequency of the item.
6Clear(): resets the data structure from previous streams.
7Merge(&other): creates a new sketch by combining counter values from two compatible sketches.
8TopK(k, &candidates): practical usage of count-min sketch--given the candidates that have been stored in the count-min sktech, return the k candidates with the most estimated counts.

其额外要求就是要支持并发，并且不能一把大锁保平安，这里更推荐通过原子操作来实现。

构造

matrix倒是简单，一个双层的vector就搞定了，由于要尽可能快，对于这种纯内存结构，原子操作足够，所以内部存的肯定是atomic类型，于是有了：

            
            src/include/primer/count_min_sketch.h
        
 1template <typename KeyType>
 2class CountMinSketch {
 3  // ...
 4 private:
 5  /** Dimensions of the count-min sketch matrix */
 6  uint32_t width_;  // Number of buckets for each hash function
 7  uint32_t depth_;  // Number of independent hash functions
 8  /** Pre-computed hash functions for each row */
 9  std::vector<std::function<size_t(const KeyType &)>> hash_functions_;
10  // ...
11
12  // matrix
13  std::vector<std::vector<std::atomic<uint32_t>>> count_;
14};

每一行的hash function早就帮我们定义好了，结构也不必操心。那么首先，应该是确定hash function，针对每一行都应该有一个专用的hash function：

            
            src/include/primer/count_min_sketch.h
        
 1template <typename KeyType>
 2CountMinSketch<KeyType>::CountMinSketch(uint32_t width, uint32_t depth)
  : width_(width), depth_(depth), count_(depth_) {
if (width_ < 1 || depth_ < 1) {
  throw std::invalid_argument("Invalid width or depth specified.");
}
 7
/** @fall2025 PLEASE DO NOT MODIFY THE FOLLOWING */
// Initialize seeded hash functions
hash_functions_.reserve(depth_);
for (size_t i = 0; i < depth_; i++) {
  hash_functions_.push_back(this->HashFunction(i));
}
14
for (auto &row : count_) {
  row = std::vector<std::atomic<uint32_t>>(width_);
  for (auto &cell : row) {
    std::atomic_init(&cell, uint32_t{0});
  }
}
21}

HashFunction里调用的是他们自己捏的hash工具，考虑到最终要测试，这里也必须使用他们的实现，绝不能自己引入。另外有个小知识点，atomic是不能被拷贝构造的，所以用了这种奇怪的方式来做初始化。

移动构造和移动赋值

这俩基本是成对出现，所以放在一起讲了：

            
            src/primer/count_min_sketch.cpp
        
 1template <typename KeyType>
 2CountMinSketch<KeyType>::CountMinSketch(CountMinSketch &&other) noexcept : width_(other.width_), depth_(other.depth_) {
 3  count_ = std::move(other.count_);
 4  hash_functions_ = std::move(other.hash_functions_);
 5}
 6
 7template <typename KeyType>
 8auto CountMinSketch<KeyType>::operator=(CountMinSketch &&other) noexcept -> CountMinSketch & {
 9  count_ = std::move(other.count_);
10  hash_functions_ = std::move(other.hash_functions_);
11
12  depth_ = other.depth_;
13  width_ = other.width_;
14  return *this;
15}

对于堆上存储数据的结构，直接使用std::move即可。当然这里有个小bug，hash_functions_初始化时，其捕获函数是包含了this的，所以这里function其实不能move，必须要重新构造一遍。所以，更合理的结构是换成以下实现：

            
            src/primer/count_min_sketch.cpp
        
 1template <typename KeyType>
 2CountMinSketch<KeyType>::CountMinSketch(CountMinSketch &&other) noexcept
 3    : width_(other.width_), depth_(other.depth_), count_(std::move(other.count_)) {
 4
 5  hash_functions_.reserve(depth_);
 6  for (size_t i = 0; i < depth_; i++) {
 7    hash_functions_.push_back(this->HashFunction(i));
 8  }
 9}
10
11template <typename KeyType>
12auto CountMinSketch<KeyType>::operator=(CountMinSketch &&other) noexcept -> CountMinSketch & {
13  // 不要自己给自己赋值
14  if (this == &other) {
15    return *this;
16  }
17  count_ = std::move(other.count_);
18  depth_ = other.depth_;
19  width_ = other.width_;
20
21  hash_functions_.clear();
22  hash_functions_.reserve(depth_);
23  for (size_t i = 0; i < depth_; i++) {
24    hash_functions_.push_back(this->HashFunction(i));
25  }
26  return *this;
27}

Insert

使用原子操作即可，fetch_add可以认为就是atomic版本的自增。每一行都调用一遍对应的hash函数，再简单取模拿到下标即可。

            
            src/primer/count_min_sketch.cpp
        
1template <typename KeyType>
2void CountMinSketch<KeyType>::Insert(const KeyType &item) {
3  for (size_t i = 0; i < depth_; i++) {
4    size_t hash = hash_functions_[i](item);
5    count_[i][hash % width_].fetch_add(1);
6  }
7}

Count

Count则纯属统计，其实这里做的不是很完美，把UINT32_MAX当成了没找到，其实应该明确没找到的行为和最大值做区分。

            
            src/primer/count_min_sketch.cpp
        
 1template <typename KeyType>
 2auto CountMinSketch<KeyType>::Count(const KeyType &item) const -> uint32_t {
 3  uint32_t res = UINT32_MAX;
 4
 5  for (size_t i = 0; i < depth_; i++) {
 6    size_t hash = hash_functions_[i](item);
 7    res = std::min(res, count_[i][hash % width_].load());
 8  }
 9
10  if (res == UINT32_MAX) {
11    return 0;
12  }
13  return res;
14}

TopK

topk就更简单了，调用以上的Count即可，对传入的每个元素进行Count操作，再partial_sort选前k个，注意k也许比元素个数还要大

            
            src/primer/count_min_sketch.cpp
        
 1template <typename KeyType>
 2auto CountMinSketch<KeyType>::TopK(uint16_t k, const std::vector<KeyType> &candidates)
 3    -> std::vector<std::pair<KeyType, uint32_t>> {
 4  std::vector<std::pair<KeyType, uint32_t>> result;
 5  result.reserve(candidates.size());
 6
 7  for (size_t i = 0; i < candidates.size(); i++) {
 8    uint32_t up_bound = Count(candidates[i]);
 9    result.emplace_back(candidates[i], up_bound);
10  }
11
12  size_t real_size = std::min(candidates.size(), static_cast<size_t>(k));
13
14  std::partial_sort(
15      result.begin(), result.begin() + real_size, result.end(),
16      [](const std::pair<KeyType, uint32_t> &a, const std::pair<KeyType, uint32_t> &b) { return a.second > b.second; });
17
18  return std::vector<std::pair<KeyType, uint32_t>>{result.begin(), result.begin() + real_size};
19}

Clear

Clear操作只用把计数的矩阵重置为0即可。

            
            src/primer/count_min_sketch.cpp
        
1template <typename KeyType>
2void CountMinSketch<KeyType>::Clear() {
3  for (size_t i = 0; i < depth_; i++) {
4    for (size_t j = 0; j < width_; j++) {
5      count_[i][j] = 0;
6    }
7  }
8}

Merge

merge操作很有意思，针对两个hash function完全一样，且每个hash function的buckets数量也一样的两个相同的结构，显然可以做merge操作。把每个元素原位相加即可：

            
            src/primer/count_min_sketch.cpp
        
 1template <typename KeyType>
 2void CountMinSketch<KeyType>::Merge(const CountMinSketch<KeyType> &other) {
 3  if (width_ != other.width_ || depth_ != other.depth_) {
 4    throw std::invalid_argument("Incompatible CountMinSketch dimensions for merge.");
 5  }
 6
 7  for (size_t i = 0; i < depth_; i++) {
 8    for (size_t j = 0; j < width_; j++) {
 9      count_[i][j] += other.count_[i][j];
10    }
11  }
12}

正如上面看到的，merge一定是有前提条件的。

Test

当然别忘了跑跑测试：

 1# ./test/count_min_sketch_test
 2Running main() from gmock_main.cc
 3[==========] Running 13 tests from 1 test suite.
 4[----------] Global test environment set-up.
 5[----------] 13 tests from CountMinSketchTest
 6[ RUN      ] CountMinSketchTest.BasicTest1
 7[       OK ] CountMinSketchTest.BasicTest1 (0 ms)
 8[ RUN      ] CountMinSketchTest.BasicTest2
 9[       OK ] CountMinSketchTest.BasicTest2 (6 ms)
10[ RUN      ] CountMinSketchTest.EdgeTest1
11[       OK ] CountMinSketchTest.EdgeTest1 (0 ms)
12[ RUN      ] CountMinSketchTest.EdgeTest2
13[       OK ] CountMinSketchTest.EdgeTest2 (0 ms)
14[ RUN      ] CountMinSketchTest.MoveTest
15[       OK ] CountMinSketchTest.MoveTest (0 ms)
16[ RUN      ] CountMinSketchTest.ClearTest
17[       OK ] CountMinSketchTest.ClearTest (0 ms)
18[ RUN      ] CountMinSketchTest.MergeTest
19[       OK ] CountMinSketchTest.MergeTest (0 ms)
20[ RUN      ] CountMinSketchTest.ParallelTest
21[       OK ] CountMinSketchTest.ParallelTest (310 ms)
22[ RUN      ] CountMinSketchTest.ComplexParallelTest
23[       OK ] CountMinSketchTest.ComplexParallelTest (18 ms)
24[ RUN      ] CountMinSketchTest.TopKBasicTest
25[       OK ] CountMinSketchTest.TopKBasicTest (0 ms)
26[ RUN      ] CountMinSketchTest.TopKDynamicTest
27[       OK ] CountMinSketchTest.TopKDynamicTest (2 ms)
28[ RUN      ] CountMinSketchTest.TopKComprehensiveTest
29[       OK ] CountMinSketchTest.TopKComprehensiveTest (26 ms)
30[ RUN      ] CountMinSketchTest.ContentionRatioTest
31This test will see how your CMS insertion performance differs to one that is completely sequential.
32If your submission timeout, segfault, or you didn't implement the lock-free version, we will manually deduct all concurrent test points.
33<<< BEGIN
34Multithreaded Insertion Time: 22613 21497 22669 20840 20699 
35Serialized Insertion Time: 40543 41707 47791 46107 46196 
36Speedup: 2.0527
37>>> END
38[       OK ] CountMinSketchTest.ContentionRatioTest (331 ms)
39[----------] 13 tests from CountMinSketchTest (697 ms total)
40
41[----------] Global test environment tear-down
42[==========] 13 tests from 1 test suite ran. (697 ms total)
43[  PASSED  ] 13 tests.

15445: C++ Primer

前言

Project0: C++ Primer

Task1

构造

移动构造和移动赋值

Insert

Count

TopK

Clear

Merge

Test