Regarding BTreeMap's

[LoopyAshy]

I noticed in the latest version of Rhai that you have decided to use BTreeMaps for the dynamic objects, I was not 100% sure of the gains in performance and memory usage so I decided to benchmark it against the maps I have used previously in my other projects such as: BTreeMap (when largest and smallest are important to me) Rust's Base HashMap (secure but slower hash map) FxHashMap (less secure but faster hash map) IndexMap (ordered, secure and slower hash map) FxIndexMap (ordered, less secure and faster hash map)

I then proceeded to compare on my machine in several ways:

1. creating it
2. inserting lots of values (10000)
3. inserting few values (10)
4. finding a value in map with lots of values (10000)
5. 6. finding a value in map with few values (10)
6. iterating the whole map with lots of values (10000)
7. iterating the whole map with few values (10)

notes - each function for each is identical

I also ran the project to check the ram usage with each and was surprised by the results. all the results are attached.

I also included the source code of the tests to allow you to judge for yourself.

RAM Results.txt code.txt

crates used:

1. indexmap = "1.6.2"
2. fxhash = "0.2.1"
3. rand = "0.8.3"

reason I bring this up is purely in regards to performance and memory usage, I do admit without a doubt BTreeMap tends to beat HashMap for small collections, however FxHashMap usually wins the "get race", while IndexMap wins memory usage, I am curious if either of these options could be good candidates to improve performance and maybe even memory footprint.

EDIT - To be fairer considering the average size of a dynamic object I decided to redo but with the small set only doing 3 instead of 10:

[schungx]

The choice to move to BTreeMap is based on the following reasons:

• The average collection is very small. Sometimes they fit in one BTree node. In these majority of cases, the overhead of a hash table is material.

• Rhai tries to pull in as few dependencies as possible. A HshMap requires hashbrown for no-std. A completely new hashtable crate will be yet another dependency.

• Most internal Rhai collections are read-only so iteration and update speed is not important, only get and resident memory size is important.

• Very few object maps have lots of changing keys. In fact, this is the basic assumption of the V8 JavaScript engine. You get frequently changing values for fixed sets of keys. This makes insertion speed unimportant, but memory size and read speed is. Also because Rhai does a lot of cloning in the back, data objects wants to be as small as possible.

• I've benchmarked Rhai actually with the two implementations and BTreeMap won hands down for internal Rhai data structures. As dynamic user data, the results are not conclusive, but I assume that it should not do worse than a hashtable. This is the running benchmarks on GitHub: https://schungx.github.io/rhai/dev/bench/

• Rhai used to have a custom hasher so it performs better than standard implementations because it never rehash a u64... It just used the value as the final hash. So the entire hashing step is skipped. Still, BTreeMap outperforms it.

[schungx]

@LoopyAshy is there anything else on this issue?

[LoopyAshy]

Sorry I have been quite busy suddenly, regarding the issue, I have no complaints, I was merely showing the results I was getting with different map's, and was curious if you had similar results with the new implementation, as I am very fond of rhai and definitely see it becoming my go to script lang within rust, and even though it isn't the ultimate goal, any performance increase is superb.