跳至主要内容

P0 - C++ Primer

Problem Description​

在這個 project 中，我們需要實現一個 key-value store 的 copy-on-write 的 trie，總共有 4 個 Task :

  • Copy-On-Write Trie : 修改 /src/primer/trie.cpp 來實現一個 copy-on-write trie，有 GET、PUT、DELETE 三個操作。
  • Concurrent Key-Value Store : 修改 /src/primer/trie_store.cpp 來將原本 single-thread 的 trie 改成 concurrent 的版本，一樣有 GET、PUT、DELETE 三個操作。
  • Debugging : 在 /test/primer/trie_debug_test.cpp 中練習使用 debugger 來 debug，並在 /src/include/primer/trie_answer.h 中填入答案。
  • SQL String Functions : 在 src/execution/expressions/string_expression.h 和 src/planner/plan_func_call 中實現 lower 和 upper 兩個 SQL function。

Learning Resource​

Environment Setup​

  1. 我使用的環境是 WSL (Ubuntu 22.04) 和 VSCode
  2. 安裝 VSCode 套件 C/C++ Extension Pack 跟 clangd
  3. 將 bustub clone 下來，並且回退到 2023 Fall 的 commit，建議至少回退到 2023 12/27 的 add request signature script (#674)
  4. 安裝 package 並編譯 :
sudo build_support/packages.sh

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Debug ..
make -j`nproc`

如果出現 compiler 的版本警告，可以將 cmake 改成以下指令 :

cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_C_COMPILER=/usr/bin/clang-14 -DCMAKE_CXX_COMPILER=/usr/bin/clang++-14 ..
  1. 安裝 clangd (通常 VSCode 會提示安裝)
  2. 設定 formatter，這樣就可以在 save 的時候自動格式化 :
.vscode/settings.json
{
  "C_Cpp.clang_format_path": "/usr/bin/clang-format-14",
  "C_Cpp.formatting": "clangFormat",
  "C_Cpp.clang_format_style": "file",
  "editor.formatOnSave": true
}
  1. 接著設定 debugger，需要先安裝 lldb，並在 VSCode 中設定 debugger
sudo apt-get install lldb-14
.vscode/launch.json
{
  "version": "0.2.0",
  "configurations": [
    {
      "name": "C/C++: clang++ build and debug active file",
      "type": "lldb",
      "request": "launch",
      "program": "${workspaceFolder}/build/test/${fileBasenameNoExtension}",
      "args": [],
      "cwd": "${fileDirname}"
    }
  ]
}

Solution​

Copy-On-Write Trie​

  • GET : 需要處理 root 是 nullptr 的情況，其餘的情況就是從 root 開始往下找，最後用 dynamic_cast 來轉型。
  • PUT : 需要處理 key 是空的情況 (在 root 上直接插入)，其餘的情況就是從 root 開始往下找，並新增一個 TrieNodeWithValue。
  • DELETE : 需要先遍歷到要刪除的 node，並記錄中途經過的 node，最後再沿途刪除沒有 value 的 node。

接著在本地進行 trie_test 的單元測試 :

cd build
make trie_test trie_noncopy_test -j$(nproc)

./test/trie_test
./test/trie_noncopy_test

Concurrent Key-Value Store​

  • GET : 使用 lock_guard 來讀取 root，並依據是否有這個 key 來決定要回傳 nullopt 或是 ValueGuard。
  • PUT : 使用 unique_lock 來獲取全局的 write_lock，並獲取 root_lock 來讀取 root 和寫入。
  • DELETE : 與 PUT 類似，也是使用 unique_lock 來獲取全局的 write_lock，並獲取 root_lock 來讀取 root 和刪除。

接著在本地進行 trie_store_test 的單元測試 :

cd build
make trie_store_test trie_store_noncopy_test -j$(nproc)

./test/trie_store_test
./test/trie_store_noncopy_test

Debugging​

前面兩題的答案可以在 VSCode 的 debugger 內看出，第三題可以直接 cout 得出答案，並在 /src/include/primer/trie_answer.h 中填入答案。

答案如下 :

  1. 10
  2. 1
  3. 25

SQL String Functions​

在 string_expression.h 中依據 expr_type 來判斷要執行哪個 function，並使用 std::transform 來將字串轉換成大寫或小寫。

在 plan_func_call.cpp 中依據 func_name 和參數數量來判斷要執行哪個 function。

可以直接使用 shell 來測試，會顯示錯誤是正常的 :

cd build
make -j`nproc` shell

./bin/bustub-shell
select upper('AbCd'), lower('AbCd');
+-------------+-------------+
| __unnamed#0 | __unnamed#1 |
+-------------+-------------+
| ABCD        | abcd        |
+-------------+-------------+

同樣可以進行單元測試 :

make -j`nproc` sqllogictest

./bin/bustub-sqllogictest ../test/sql/p0.01-lower-upper.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p0.02-function-error.slt --verbose
./bin/bustub-sqllogictest ../test/sql/p0.03-string-scan.slt --verbose

Submit​

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

  1. 首先修改 CMakeLists.txt，將 P0_FILES 設定為以下 ( 需要重新執行 cmake 指令來更新 makefile ):
CMakeLists.txt
set(P0_FILES
        "src/include/primer/trie_answer.h"
        "src/include/primer/trie_store.h"
        "src/include/primer/trie.h"
        "src/primer/trie_store.cpp"
        "src/primer/trie.cpp"
        "src/planner/plan_func_call.cpp"
        "src/include/execution/expressions/string_expression.h"
        "GRADESCOPE.md"
)
  1. 進行排版，確定消除所有 error 和 warning ( 特別是 check-clang-tidy-p0 ):
make format
make check-lint
make check-clang-tidy-p0
  1. 簽名，會產生一個 GRADESCOPE.md :
python3 gradescope_sign.py
  1. 繳交作業，可能需要先執行 sudo apt-get install zip 來安裝 zip，然後執行以下指令 :
make submit-p0
  1. 上傳 .zip 檔到 GradeScope