This project aims to enhance the performance of rv32emu by addressing issue #29.
The original implementation of rv32emu utilizes a Linux-like red-black tree, providing a C++ std::map-like interface. As part of this project, the red-black tree implementation has been modified from jemalloc, resulting in improved performance for map insertion, find, and delete operations.
The following data represents the average time of 20 experiments, each involving the insertion, finding, and deletion of 10 million randomly generated nodes in a random order. The experiments were conducted on an Apple M1 Pro (10-core) processor.
10,000,000 random operations
| Type | Insert (ns) | Find (ns) | Remove (ns) |
|---|---|---|---|
| original | 824,515,450 | 21,132,350 | 925,074,950 |
| proposed | 535,518,250 | 10,032,300 | 602,755,100 |
| improvement | 35 % | 52 % | 35 % |
10,000,000 seqential operations
| Type | Insert (ns) | Find (ns) | Remove (ns) |
|---|---|---|---|
| original | 306,238,550 | 91,349,500 | 201,321,050 |
| proposed | 129,634,150 | 50,770,350 | 284,513,100 |
| improvement | 57 % | 44 % | -41% |
| Type | Total heap (B) | Useful heal (B) | Extra heap (B) |
|---|---|---|---|
| original | 7,294,976 | 3,124,664 | 3,645,304 |
| proposed | 6,241,680 | 2,597,592 | 3,117,096 |
| improvement | 14 % | 17 % | - |
C/Cpp
- CMake
- Make
Python
- matplot
- pandas
- numpy
Clone to your local directory
git clone https://github.com/ypaskell/rbtree_benchRun cmake
cmake .
Compile and create executables
make
Run bench
./bench.sh- Clone jemalloc rb.h
- Integrate map interface to match C++ std::map
- Create test for correctness
- Create bench plot
- Computational time and memory benchmark
- PR