This project focuses on benchmarking and optimizing the red-black tree-based map used in rv32emu. The goal is to improve performance, memory efficiency, and execution speed through profiling, algorithmic refinements, and potential jemalloc-style enhancements.
This project aims to enhance the performance of rv32emu by addressing issue #29.
- 🚀 Benchmarking & Profiling: Measure insert, delete, and lookup performance.
- 🔧 Optimizations: Improve memory usage and execution speed.
- ⚡ Integration with rv32emu: Enhance existing map structures.
- 📊 Comparative Analysis: Test against alternative data structures.
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 the repository and build the project:
git clone https://github.com/EagleTw/rv32emu-rbtree-optimization
cd rv32emu-rbtree-optimization
cmake
makeExecute the benchmark suite with:
./bench.shModify parameters in config.h to adjust benchmarking scenarios.
This project is licensed under the MIT License.
Special thanks to the rv32emu developers and the jemalloc community for inspiration on memory-efficient red-black tree implementations.