OrdMap & HashMap
- AVL is not worse than RBTree, and is also a feasible way to resolve Hash Collision Attack.
- This package expose two public structs:
OrdMap
which implemented by optimized AVL,HashMap
whose every index contains an AVL-Tree. - To improve performance, raw pointer is used frequently. Because Rust uses a similar memory model to C/C++, two classic macros
offset_of
andcontainer_of
are used to dereference member variables into main struct.Fastbin
is implemented to reduce the cost of memory allocation.
Usage
Notice the Trait. Usage of most functions is same as STL HashMap, you can find examples in test case.
impl<K, V, S> HashMap<K, V, S> where K: Ord + Hash, S: BuildHasher
impl<K, V> OrdMap<K, V> where K: Ord
Performance Test
Environment
Linux version 4.4.0-1049-aws (buildd@lcy01-amd64-001) (gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.5) )
Intel(R) Xeon(R) CPU E5-2676 v3 @ 2.40GHz
AVL Compare with RBTree
cargo run --release --example avl_cmp_rbtree
- Obviously, optimized AVL is not worse than RBTree, and with the advantage of smaller height, it works better in searching case.
It performs much better in clear case benefit from
Fastbin
avl tree
size 1000000
build time PT0.523259712S
contain count 1000000
find time PT0.462317294S
remove time PT0.456915364S
insert after remove time PT0.442013480S
clear time PT0.029607052S
rbtree
size 1000000
build time PT0.615952198S
contain count 1000000
find time PT0.570363857S
remove time PT0.641548505S
insert after remove time PT0.613216248S
clear time PT0.162732696S
--------------------------------------------
avl tree
size 10000000
build time PT11.083079762S
contain count 10000000
find time PT9.908204148S
remove time PT11.365612250S
insert after remove time PT11.503721610S
clear time PT0.474218222S
rbtree
size 10000000
build time PT12.478368807S
contain count 10000000
find time PT11.286116786S
remove time PT12.362542744S
insert after remove time PT12.062266663S
clear time PT2.479094958S
--------------------------------------------
HashMap Competition
Run commend
cargo run --release --example hash_map_cmp_string
- If the type of key is
String
, ours performs better in case ofinsert
andsearch
, Because Fastbin makes rehashing run faster and comparable hash node helps to reduce search time.
test hash avl map
insert time PT0.264062182S
max node num of single index: 7
find 1000000, time PT0.232942470S
remove time PT0.303657020S
test stl hash map
insert time PT0.382943597S
find 1000000, time PT0.254504066S
remove time PT0.297953633S
--------------------------------
test hash avl map
insert time PT1.623697494S
max node num of single index: 8
find 5000000, time PT1.374587816S
remove time PT1.712209458S
test stl hash map
insert time PT2.146439362S
find 5000000, time PT1.494242541S
remove time PT1.613802131S
--------------------------------
- However, if type is usize|isize|f32... , which means the cost of key comparing and memory copying are low, then
STL HashMap sometimes performs better in case of
insert
andremove
.
cargo run --release --example hash_map_cmp_usize
test hash avl map
insert time PT0.134678145S
max node num of single index: 8
find 1000000, time PT0.118454962S
remove time PT0.126796283S
test stl hash map
insert time PT0.126203898S
find 1000000, time PT0.099042480S
remove time PT0.104399187S
--------------------------------
test hash avl map
insert time PT0.996003799S
max node num of single index: 8
find 5000000, time PT0.774285169S
remove time PT0.836908472S
test stl hash map
insert time PT0.982269496S
find 5000000, time PT0.868572380S
remove time PT0.835186910S
--------------------------------
- When facing Collision Attack, the runtime complexity of STL HashMap can be O(n^2), but ours is O(n log n).
cargo run --release --example hash_map_cmp_collision
test hash avl map
insert time PT0.000739762S
max node num of single index: 10000
find 10000, time PT0.000690444S
remove time PT0.000497103S
test stl hash map
insert time PT0.093169479S
find 10000, time PT0.079600027S
remove time PT0.089153558S
--------------------------------
Conclusion
- Rust is called
zero cost abstraction
, of course that's true. But comparing with C/C++, its compiler optimization is not good enough. In C/C++, syntax likea = ( b < c ) ? d : e
may not generate branch, which means search operation on AVL could be better when the type of key is1~8 Bytes