P0 - C++ Primer

Problem Description

這個版本是 2024 Fall 的版本，目標是實現一個常見的資料結構 Hyperloglog，並熟悉 C++ 的語法。

如果想要快速上手專案架構，可以使用 AI，譬如 deepwiki。

Learning Resource

Environment Setup

我使用的環境是 WSL (Ubuntu 24.04) 和 VSCode
安裝 VSCode 套件 C/C++ Extension Pack、clangd、CMake Tools、Clang-Format
將 bustub clone 下來，並且回退到 2024 Fall 的 commit，這樣可以避免一些不必要的問題

git clone https://github.com/cmu-db/bustub.git
cd bustub
git checkout f97256b88b20468c01023928b63f5693d697674c

接著可以把 .git 檔案移除並接上自己的 git repo (注意不要公開 repo 在 github 上並且把 github action 關掉)

rm -rf .git

git init
git add .
git commit -m "init"
git remote add origin <your-git-repo>
git push -u origin main

由於我使用的是 24.04，所以需要修改一下 packages.sh 的內容，並順便安裝 clangd 的套件。

build_support/packages.sh
install_linux() {
  # Update apt-get.
  apt-get -y update
  # Install packages.
  apt-get -y install \
      build-essential \
      clang-14 \
      clang-format-14 \
      clang-tidy-14 \
      clangd-14 \
      cmake \
      doxygen \
      git \
      pkg-config \
      zlib1g-dev \
      libelf-dev \
      libdwarf-dev
}

install() {
  set -x
  UNAME=$(uname | tr "[:lower:]" "[:upper:]" )

  case $UNAME in
    DARWIN) install_mac ;;

    LINUX)
      version=$(cat /etc/os-release | grep VERSION_ID | cut -d '"' -f 2)
      case $version in
        18.04) install_linux ;;
        20.04) install_linux ;;
        22.04) install_linux ;;
        # add this line
        24.04) install_linux ;;
        *) give_up ;;
      esac
      ;;

    *) give_up ;;
  esac
}

安裝套件

sudo build_support/packages.sh

嘗試編譯一下，看看有沒有問題

cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_C_COMPILER=/usr/bin/clang-14 -DCMAKE_CXX_COMPILER=/usr/bin/clang++-14 -B build

cd build

make -j`nproc`

設定 formatter 以及 cmake、clangd 等等

.vscode/settings.json
{
  "C_Cpp.clang_format_path": "/usr/bin/clang-format-14",
  "C_Cpp.formatting": "clangFormat",
  "C_Cpp.clang_format_style": "file",
  "clang-format.executable": "/usr/bin/clang-format-14",
  "clangd.path": "/usr/bin/clangd-14",
  "cmake.configureSettings": {
    "CMAKE_C_COMPILER": "/usr/bin/clang-14",
    "CMAKE_CXX_COMPILER": "/usr/bin/clang++-14"
  },
  "editor.formatOnSave": true
}

接著設定 debugger，我使用的 debugger 是 GDB

sudo apt install gdb

以下這個設定可以幫助我們顯示 STL 容器的內容 :

.vscode/launch.json
{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "C/C++: g++ build and debug active file",
      "type": "cppdbg",
      "request": "launch",
      "program": "${workspaceFolder}/build/test/${fileBasenameNoExtension}",
      "args": [],
      "cwd": "${workspaceFolder}",
      "stopAtEntry": true,
      "MIMode": "gdb",
      "miDebuggerPath": "/usr/bin/gdb",
      "setupCommands": [
        {
          "description": "Test",
          "text": "python import sys;sys.path.insert(0, '/usr/share/gcc/python');from libstdcxx.v6.printers import register_libstdcxx_printers;register_libstdcxx_printers(None)",
          "ignoreFailures": false
        },
        {
          "description": "Enable pretty-printing for gdb",
          "text": "-enable-pretty-printing",
          "ignoreFailures": true
        }
      ]
    }
  ]
}

之後如果要執行 debug，設定好斷點對著 test file 按 F5 即可。

Solution

P0 主要有兩個 task，第一個是實作基本的 Hyperloglog，第二個是實作 Presto 的 Hyperloglog，.h 和 .cpp 的檔案分別在 src/include/primer 和 src/primer 裡面。

我認為比較需要注意的是 C++ 中 std::bitset 的使用，這個資料結構可以用來儲存二進位的數字，並且可以用 << 和 >> 來做位移運算，也需要特別注意 std::bitset 的 [0] 指的是最右邊的 bit，而不是最左邊的 bit。

Task 1: Hyperloglog

大致說明一下 Hyperloglog 的實作，這個資料結構主要是用來估計不重複的元素的數量，並且可以在 O(1) 的時間和固定的空間內完成。

首先我們會將所有的元素 hash 成一個 64 bits 的整數，然後將這個整數分成兩個部分，前面的 n_bits 代表桶的 index (總共有 $2^{nbits}$ 個桶)，在這些數字之後，我們就要開始數 leading zeros 的數量直到遇到第一個 1 為止 (包含 1)，再把 leading zeros 取最大值之後放進桶裡面，最後再用這些桶來估計不重複的元素的數量。

這個 task 有四個 function 需要實作，分別是 HyperLogLog(inital_bits), PositionOfLeftmostOne(), AddElem(val), 和 ComputeCardinality()，並且有兩個寫好的 function，分別是 ComputeBinary(hash_t hash) 和 CalculateHash(...)，這兩個 function 分別是用來將 hash 值轉成二進位的數字和計算 hash 值的。

HyperLogLog(int initial_bits) : 這個 constructor 會初始化桶的數量，並且將所有的桶的值設成 0，需要注意的是需要處理傳進來的 n_bits 有可能會是負數的情況
PositionOfLeftmostOne() : 這個 function 會計算二進位表示法中從 bucket_index 結束後的下一個 bit 開始到第一個 1 的位置，要特別注意的是 1 的位置也需要計算，並且如果 n_bits 為 0，也需要保留第一個 bit 當作 index
AddElem(val) : 這個 function 會將傳進來的 val 做 hash，然後將這個 hash 值轉成二進位的數字，接著計算桶的 index 和 leading zeros 的數量，最後取最大值放進桶裡面
ComputeCardinality() : 這個 function 會回傳計算後的 cardinality，依照公式來寫即可，最後記得用 std::floor 來取整數，並且要注意 n_bits 為 0 的情況

Task 2: Presto Hyperloglog

這個 task 主要是要實作 Presto 的 Hyperloglog，是一種 Hyperloglog 的修改版。

在這個修改版中，leading zeros 的儲存和計算方式都有所改變。儲存會分成兩個部分，分別是 4 bits 的 dense_bucket_ 跟 3 bits 的 overflow_bucket_。計算方式是將 leading zeros 改成從最右邊開始取值到第一個 1 的位置 (不包含 1)，然後將這個值放進 dense_bucket_ 裡面，如果這個值超過 4 bits，再把多餘的部分放到 overflow_bucket_ 裡面。

這個 task 主要有三個 function 需要實作，分別是 PrestoHyperLogLog(initial_bits)、AddElem(val) 和 ComputeCardinality()，這三個 function 的邏輯和 Hyperloglog 的差不多，只是要注意 dense_bucket_ 和 overflow_bucket_ 的處理。

PrestoHyperLogLog(int initial_bits) : 與 task 1 類似，只是改成要初始化 dense_bucket_
AddElem(val) : 與 task 1 類似，只是要注意將 leading zeros 的計算方式改成從最右邊開始取值到第一個 1 的位置 (不包含 1)
ComputeCardinality() : 與 task 1 類似，只是將 overflow_bucket_ 左移 4 bits 再相加

Submit

如果要註冊 GradeScope，可以參考這個網站跟官網。

將 /test/primer/hyperloglog_test.cpp 的所有 test case 中的 DISABLE_ 都移除，舉例來說 :

test/primer/hyperloglog_test.cpp
TEST(HyperLogLogTest, DISABLE_BasicTest1) {}

改成

test/primer/hyperloglog_test.cpp
TEST(HyperLogLogTest, BasicTest1) {}

這樣就可以執行所有的 test case 了。

重新編譯並測試所有的 test case

cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/usr/bin/clang-14 -DCMAKE_CXX_COMPILER=/usr/bin/clang++-14 -B build

cd build

make -j$(nproc) hyperloglog_test

./test/hyperloglog_test

並確認所有的 test case 都能通過，代表成功完成了這個作業。

修改 CMakeLists.txt，將 P0_FILES 設定為以下 (需要重新執行 cmake 指令來更新 makefile) :

CMakeLists.txt
set(P0_FILES
        "src/include/primer/hyperloglog.h"
        "src/include/primer/hyperloglog_presto.h"
        "src/primer/hyperloglog.cpp"
        "src/primer/hyperloglog_presto.cpp"
        "GRADESCOPE.md"
)

進行排版，確定消除所有 error 和 warning (特別是 check-clang-tidy-p0) :

make format
make check-lint
make check-clang-tidy-p0

簽名，會產生一個 GRADESCOPE.md :

python3 gradescope_sign.py

繳交作業，可能需要先執行 sudo apt-get install zip 來安裝 zip，然後執行以下指令 :

make submit-p0

上傳 .zip 檔到 GradeScope

Problem Description​

Learning Resource​

Environment Setup​

Solution​

Task 1: Hyperloglog​

Task 2: Presto Hyperloglog​

Submit​