This repository contains the code for two suffix array construction algorithms: Prefix Doubling (PD) and DCX. These algorithms have been implemented using KaMPIng (PD and DCX), Plain MPI (PD and DCX), and Thrill (PD).
The lines of code (LOC) necessary to implement the two algorithms using the different distributed memory programming frameworks are listed below.
We measured the lines of code using cloc 2.00.
All code files have been formatted using clang-format 14 using the default Google style (clang-format --style=Google).
| KaMPIng | plain MPI | Thrill | |
|---|---|---|---|
| PD | 163 | 426 (+1442) | 266 |
| DCX | 1264 | 1396 | --- |
Note that the prefix doubling implementations are copied from three different projects.
To keep the overhead of this repository small, we removed all code not directly part of the algorithm, e.g., main functions and benchmark utility.
Therefore, the code included here is not expected to be executed.
If you want to execute the algorithms, we refer to the corresponding repositories (KaMPIng implementation, plain MPI implementation, and Thrill implementation).
To reproduce the measured lines of code, you can use the following commands:
cd prefix_doubling_comparison/
echo -e "\e[32mLines of Code: PD KaMPIng Implementation\e[0m"
cloc kamping_prefix_doubling.hpp
echo -e "\e[32mLines of Code: PD Plain MPI Implementation\e[0m"
cloc mpi_prefix_doubling.hpp
echo -e "\e[32mLines of Code: Plain MPI Implementation MPI Wrapper\e[0m"
cloc dsss_mpi
echo -e "\e[32mLines of Code: PD Thrill Implementation\e[0m"
cloc thrill_prefix_doubling.cpp
cd ..Implementation of the DCX suffix array construction algorithm. The original implementation is by Timo Bingmann and consists of 1396 lines of code, when removing code shared with the KaMPIng implementation. In our KaMPIng implementation, we replaced all plain MPI calls with our wrapper. This mainly resulted in less boilerplate code and 1264 lines of code, i.e., 9.5% less code.
To reproduce the measured lines of code, you can use the following commands:
cd src/
echo -e "\e[32mLines of Code: DCX KaMPIng Implementation\e[0m"
cloc kamping_dc.cpp
echo -e "\e[32mLines of Code: Plain MPI Implementation\e[0m"
cloc mpi_dc.cpp
cd ..Since this repository is based on these two implementations, they can be build and executed.
cmake -B build
cmake --build build
mpirun -np <# MPI threads> ./build/src/[kampingDCX|pDCX] [3/7/13] <input_file>