Project 0: C++ Primer

• Assigned: Wednesday, March 31
• Due: 9pm Friday, April 9
• Collaboration: This is an individual assignment

Overview

The next three programming projects this term will be written on the BusTub database management system. This system is written in C++. The purpose of this project is to get a development environment set up and start learning C++ if you haven’t used it before.

While I will go over some aspects of C++ in lab, I will not be covering it in the lecture videos. The expectation is that you will learn it on your own as we go along. Learning a new language independently is a valuable skill (and one that you will be expected to have in the real world), as is programming in a language you don’t know very well.

That said, independently doesn’t necessarily mean alone! I hope this class can become a community of learners when it comes to C++ (and databases too). I have set up Moodle forums for C++ Quesions and questions/discussion about the Homeworks & Projects. The former is a great place to ask for help with syntax, compiler errors, etc. (the latter is for all other assignment related questions). If you’re new to C++, I’d strongly recommend working through one of these tutorials as part of this project:

• C++ Language Tutorial (from cplusplus.com, generally a great reference)
• C++ for Java Programmers (a nice tutorial from a Java perspective, includes practice exercises)
• C++ for C Programmers (if you are specifically interested in how C++ differs from C)

Pre-Lab Activities

We will go over how to get started on this project in lab on April 2. Before lab, you are expected to

• Read this entire project writeup
• Spend a couple hours on any relevant tutorials/resources linked from this writeup (C++, git, Linux)

Lab

1. Download VS Code
2. Install the Remote - SSH extension (View > Extensions, search for ssh)
3. F1 to bring up command palette (or Ctrl/Cmd-Shift-P), type in “ssh” and select “Remote-SSH: Connect to Host…”
4. Select “Add New SSH Host…” and then enter ssh YOUR_CARLETON_USERNAME@mantis.mathcs.carleton.edu as the ssh command
   • You will need to be on campus or on the Carleton VPN to connect to mantis
5. Select the first option for which config file you want to modify
6. Click “Connect” on the dialog that pops up in the lower right (or go to the Remote Explorer tab along the left side, and then right click on mantis and connect in current window)
7. Use the terminal within VS Code to follow the Setup Instructions.
   • There have been some small changes to the public repo, so if you previously set up your repo, pull from the public one to get those updates
8. Then View > Explorer, Open Folder, enter the path where you cloned your private repo
9. Install the C/C++ and CMake Tools extensions (this will install them on mantis, so they’ll always be there for you)
10. When it asks, choose the Clang 8 compiler

• Buttons along the bottom allow you to configure, build, and run the project
  • A target is what comes after make when doing this via the terminal
• Looking at src/include/primer/p0_starter.h
  • Turns out there’s no rule against having implementations in header (.h) files, so to keep things simple everything is in the header for this project
  • TODOs where you need to do things
  • Abstract superclass Matrix, keeps track of # of rows, # of columns, and a linear version of the array
    • Abstract class is a partially implemented class, needs to be extended to actually be instantiated
  • Set methods = 0 to indicate they have no implementation
  • template <typename T> is how C++ does generics
  • ~Matrix() is the destructor—called when the object is freed, responsible for freeing any internal data structures
  • RowMatrix has an array of pointers, data_, that each point to the first element of a matrix row
    • So RowMatrix constructor should allocate an array of T* for the number of rows, and then initialize each element to the appropriate offset from linear_
• Testing your code will be an important part of the projects in this class. Some tests will be provided to you, but they will not be all the tests the autograder will run.
• For this project, you are given tests for adding and multiplying matrices, but not for the GEMM operation
• Making sure you have tests that at least call every function you’re implementing is essential, otherwise you won’t know if your code will compile
• Write GEMM test
• unique_ptr: only one scope can have access to this pointer (no copying), so if we want to pass it as an argument, we have to explicitly move it via std::move
  • Not doing this generates an error message about an unimplemented copy constructor

TEST(StarterTest, GemmMatricesTest) {
  // Multiply
  int arr1[6] = {1, 2, 3, 4, 5, 6};
  std::unique_ptr<RowMatrix<int>> mat1_ptr{new RowMatrix<int>(2, 3)};
  mat1_ptr->MatImport(&arr1[0]);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 3; j++) {
      EXPECT_EQ(arr1[i * 3 + j], mat1_ptr->GetElem(i, j));
    }
  }

  int arr2[6] = {-2, 1, -2, 2, 2, 3};
  std::unique_ptr<RowMatrix<int>> mat2_ptr{new RowMatrix<int>(3, 2)};
  mat2_ptr->MatImport(&arr2[0]);
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 2; j++) {
      EXPECT_EQ(arr2[i * 2 + j], mat2_ptr->GetElem(i, j));
    }
  }

  int arr3[4] = {1, 2, 3, 4};
  std::unique_ptr<RowMatrix<int>> mat3_ptr{new RowMatrix<int>(2, 2)};
  mat3_ptr->MatImport(&arr3[0]);
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      EXPECT_EQ(arr3[i * 2 + j], mat3_ptr->GetElem(i, j));
    }
  }

  int arr4[4] = {1, 16, -3, 36};
  std::unique_ptr<RowMatrix<int>> result_ptr =
      RowMatrixOperations<int>::GemmMatrices(std::move(mat1_ptr), std::move(mat2_ptr), std::move(mat3_ptr));
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      EXPECT_EQ(arr4[i * 2 + j], result_ptr->GetElem(i, j));
    }
  }
}

• Starting HW1
  • The built-in SQLite on mantis is too old, so if you work there, download a newer version from the SQLite website and use that
    • wget https://www.sqlite.org/2021/sqlite-tools-linux-x86-3350400.zip
    • unzip sqlite-tools-linux-x86-3350400.zip
    • Use ./sqlite-tools-linux-x86-3350400/sqlite3 musicbrainz-cs334-s21.db instead of sqlite3 musicbrainz-cs334-s21.db
  • Follow assignment directions to download database, checksum, extract
  • Visual schema provided in assignment
  • Can use .table to list tables and .schema TABLE to display the structure of a table (replace TABLE with the name of the table)
  • Can use .read FILE to read in and execute a query from a file

Setup Instructions

Acquiring the Repository

If the below git concepts (e.g., repository, merge, pull, fork) do not make sense to you, I recommend checking out the git resources on the course webpage.

Tutorials one and two from this set of UNIX tutorials may be helpful if you have not used a Linux terminal before.

If you don’t have a GitHub account, head over to https://github.com/ and create one. You will probably also need to add an SSH key to your GitHub account, as described here.

Follow these instructions to create your own PRIVATE repository and your own development branch. If you have previuosly forked the repository through the GitHub UI (by clicking Fork), PLEASE DO NOT PUSH ANY CODE TO YOUR PUBLIC FORKED REPOSITORY! Make sure your repository is PRIVATE before you git push any of your code.

Building the Project

Use the commands show here to build the project from the command line. The lab recording shows how to build the project from VS Code.

Project Specification

In this project, you will implement three classes: Matrix, RowMatrix, and RowMatrixOperations. These matrices are simple two-dimensional matrices that must support addition and matrix multiplication, as well as a simplified General Matrix Multiply (GEMM) operation (given matrices A, B, and C, compute A × B + C). mathisfun.com has a nice little guide to matrix multiplication.

You will only need to modify a single file: p0_starter.h. You can find the file in the BusTub repository at src/include/primer/p0_starter.h.

In this header file, we have defined the three classes that you will need to implement. The Matrix abstract class defines the common functions for the derived class RowMatrix. The RowMatrixOperations class will use RowMatrix objects to achieve the operations mentioned above. The function signatures and member variables are specified in the file. The project requires you to fill in the implementations of all the constructors, deconstructors, and member functions. Do not add any additional function prototypes or member variables. You only need to modify the defined functions that we provide you.

Testing

You can test the individual components of this assignment using our testing framework. We use GTest for unit test cases. There is one file that contain tests for all three classes: test/primer/starter_test.cpp.

You can compile and run each test individually from the command-line:

$ mkdir build
$ cd build
$ make starter_test
$ ./test/starter_test

You can also run make check-tests to run ALL of the test cases. Note that some tests are disabled as you have not implemented future projects. Tests in GTest can be disabled by adding a DISABLED_ prefix to the test name. All tests in the repo start off as disabled.

These tests are only a subset of the all the tests that we will use to evaluate and grade your project. You should write additional test cases on your own to check the complete functionality of your implementation. In particular, a function that is never called is ignored for compilation. The provided tests only call AddMatrices and MultiplyMatrices, so you’ll need to write your own test case for GemmMatrices.

Your code will also be evaluated for memory errors. These include problems such as array overflows and failing to deallocate memory. We will use the command

$ valgrind --leak-check=full --suppressions=../build_support/valgrind.supp ./test/starter_test

to check for these errors (run from the build directory). See this guide for information about interpreting valgrind output.

Logging

Instead of using printf statements for debugging, use the LOG_* macros for logging information like this:

LOG_INFO("# Pages: %d", num_pages);
LOG_DEBUG("Fetching page %d", page_id);

To enable logging in your project, you will need to reconfigure it like this (or select a build variant with debug info in VS Code):

$ mkdir build
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=DEBUG ..
$ make

The different logging levels are defined in src/include/common/logger.h. After enabling logging, the logging level defaults to LOG_LEVEL_INFO. Any logging method with a level that is equal to or higher than LOG_LEVEL_INFO (e.g., LOG_INFO, LOG_WARN, LOG_ERROR) will emit logging information. Note that you will need to add #include "common/logger.h" to any file that you want to use the logging infrastructure.

Style

Your code must follow the Google C++ Style Guide. We use clang to automatically check the quality of your source code. The style part of project grade will be zero if your submission fails any of these checks.

Execute the following commands to check your syntax. The format target will automatically correct the formatting of your code. The check-lint and check-clang-tidy targets will print errors and instruct you how to fix it to conform to our style guide.

$ make format
$ make check-lint
$ make check-clang-tidy

Submission

You will submit your work for this project via Gradescope.

Gradescope lets you submit via GitHub, which is probably the easiest method (assuming you created a private GitHub repo following the Setup Instructions). All you’ll need to do is connect your GitHub account (the Gradescope submission page has a button for this) and select the repository and branch you wish to submit. Alternatively, you can create a zip file of the src directory and upload that.

When you submit, the autograder will compile your code, run the test cases, check your code for style, and use valgrind to check for memory errors. The only file it will use is p0_starter.h (all other submitted files will be discarded). This file must be at src/include/primer/p0_starter.h in your submission.

Although you are allowed submit your answers as many times as you like, you should not treat Gradescope as your only debugging tool. Many people may submit their projects near the deadline, and thus it will Gradescope take longer to process the requests. You may not get feedback in a timely manner to help you debug problems.

Grading

This project will be graded out of 50 points, as shown in the table below. No tests will be run for a submission that does not compile. While the autograder will assign 0 points for a test that doesn’t pass, partial credit can be earned for evidence of a good-faith effort. Comments explaining your approach can help earn partial credit.