Comments (13)
commit 7fb4ff7 integrates color into lowest bit of parent pointer.
from rv32emu.
The expected improvements can be the followings:
-
Combining the color bit with the parent node pointer
This is done by alignment, sincemap_node_t
is defined to align withunsigned long
(8 Bytes).
The least three bits would be left unused, so we can integrate the color bit to the LSB. -
Indirect pointers
Indirect pointers can be used to decrease the number of branches to increase better performance in pipelines. -
Embed
map_node_t
into structures for better cache locality
Since the pointer we use to manipulate are embedded in the structure variable we are using, there would be one less layer of indirection and resulting to better cache locality.
from rv32emu.
- Indirect pointers
Indirect pointers can be used to decrease the number of branches to increase better performance in pipelines.
commit ff46dad and commit 09f4e65 lower the number of branches in red-black tree.
from rv32emu.
rbi is non-recursive, and has very little memory overhead (e.g. no parent pointer within the red-black tree node). Its features:
- 3 tree implementations: unordered; ordered but unbalanced; balanced
- memory allocation is done outside the library
- lookup, iteration and insertion is without recursion and with constant memory usage
- compact memory representation: parent pointers are not used
- compact memory representation: option to store the red-black bit of the balanced implementation in the least significant bit of the (right) pointer
- operations other than lookup, insertion and iteration are not implemented
We might learn from rbi.
from rv32emu.
Below is my proposal for the first change.
- store the red-black bit of the balanced implementation in the least significant bit of the (right) pointer
- Removing parent pointes and rewrite corresponding functions
I will also write testing to ensure the correctness of all functions.
What do you think?
from rv32emu.
The following result is recorded by the simple benchmark I created.
By inserting, searching, and deleting 10e6 random and not duplicated integers.
action type | map | rb |
---|---|---|
insert (sec) | 1.123425 | 0.446589 |
search (sec) | 1.000282 | 0.406894 |
delete (sec) | 0.173655 | 0.44963 |
from rv32emu.
The following result is recorded by the simple benchmark I created. By inserting, searching, and deleting 10e6 random and not duplicated integers.
You shall provide the corresponding benchmark programs for reference purpose.
In particular, rbi.c lacks of the ability to remove. rb.h is exactly used for comparison.
from rv32emu.
You shall provide the corresponding benchmark programs for reference purpose.
Repository: rbtree_bench
- 1. mention the machine specifications which you performed the experiments on.
- 2. provide a top-level CMakeLists.txt that describes the way to build both map and rb;
- 3. pull Google Tests automatically. See Quickstart: Building with CMake; and
- 4. rename the repository as rbtree-bench. There is no separation between rb and tree.
from rv32emu.
- 2. provide a top-level CMakeLists.txt that describes the way to build both map and rb;
- 3. pull Google Tests automatically. See Quickstart: Building with CMake; and
The following changes are required.
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,4 +1,4 @@
-cmake_minimum_required (VERSION 2.8.11)
+cmake_minimum_required (VERSION 3.14)
project (rbtree_bench)
@@ -10,6 +10,7 @@ FetchContent_Declare(
googletest
URL https://github.com/google/googletest/archive/03597a01ee50ed33e9dfd640b249b4be3799d395.zip
)
+FetchContent_MakeAvailable(googletest)
add_subdirectory (map)
add_subdirectory (rb)
diff --git a/map/CMakeLists.txt b/map/CMakeLists.txt
index 2701980..a67cbb5 100644
--- a/map/CMakeLists.txt
+++ b/map/CMakeLists.txt
@@ -1,4 +1,3 @@
-cmake_minimum_required(VERSION 3.5)
project(map)
enable_testing()
diff --git a/rb/CMakeLists.txt b/rb/CMakeLists.txt
index 06ab4d7..8bdf88d 100644
--- a/rb/CMakeLists.txt
+++ b/rb/CMakeLists.txt
@@ -1,10 +1,7 @@
-cmake_minimum_required(VERSION 3.5)
project(rbi)
enable_testing()
-find_package(GTest CONFIG REQUIRED)
-
set (CMAKE_CXX_STANDARD 11)
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
set(GCC_FLAGS "-s -Os -W -Wall -Werror")
from rv32emu.
The following result is recorded by the simple benchmark I created. By inserting, searching, and deleting 10e6 random and not duplicated integers.
Tested on eMag 8180, 64-bit 32-core Arm server.
action type | map | rb |
---|---|---|
insert (sec) | 2.341151 | 1.11663 |
search (sec) | 1.723217 | 0.851424 |
remove (sec) | 0.352333 | 1.13698 |
from rv32emu.
See also:
from rv32emu.
Action items for rbtree_bench:
- Unify the interface for accessing different rbtree implementations. You may wrap rb.h to fit the functions exposed by rv32emu's map.h.
- Shrink rb.h by replacing it with much smaller one I provided.
--> Done by commit - Utilize minibench for benchmarking -- simpler and more informative.
--> Done by commit1 and commit2 - Check existing rbtree benchmark programs and see if we can learn from the test scenarios. e.g., rbt_test.c from bind9 project and rb-bench.
- Not only average time but also worst-case behavior should be considered.
- Measure memory consumptions -- check Massif from Valgrind.
from rv32emu.
Close via commit 434c466
from rv32emu.
Related Issues (20)
- Potential uninitialized value read without initialization HOT 2
- Specialize JALR Instruction HOT 6
- Use the canonical order of RISC-V extension names in the repository description
- jit: Flush the code cache when it is full
- Build using emcc failed HOT 6
- Failed to build using emcc when ENABLE_SDL=1 is set outside macOS HOT 2
- Help with the Emulator HOT 13
- Filter out message-less demo programs from WebAssembly demo page HOT 1
- jit: Fail to run recursive programs
- smolnes.elf cannot be executed and no "inferior exit code 0" output to indicate that a process has completed in the rv32emu-demo
- CI: WebAssembly action failed when PR merged HOT 1
- Trigger WebAssembly CI when embedded ELF executables has been rebuilt
- Calling close() system call with fd < 3
- Crash when the memory on host is insufficient HOT 4
- Keep prebuilt ELF files up to date HOT 5
- CI: Setup self-hosted GitHub Actions runner HOT 6
- Don't check out softfloat if no F extension is configured HOT 4
- A segmentation fault occurs when running a simple ELF file HOT 9
- jit: bug if the registers of the source and linkage registers of `JALR`, `CJALR` instructions are same
- Improve the build system, making it more flexible
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from rv32emu.