BTreeMap vs HashMap

[godofdream]

I have tested an implementation where I replaced the hashmap with btreemap. (https://github.com/godofdream/ramhorns/tree/btreemap)
It seems that in most cases the btreemap is faster on my machine (AMD Ryzen 5 3600 6-Core Processor).
Theoretically also the ramusage should be smaller.

test a_simple_ramhorns            ... bench:          85 ns/iter (+/- 6) = 1141 MB/s
test a_simple_ramhorns_btree            ... bench:          81 ns/iter (+/- 5) = 1197 MB/s
test b_simple_askama              ... bench:         209 ns/iter (+/- 14) = 464 MB/s
test c_simple_tera                ... bench:         485 ns/iter (+/- 9) = 200 MB/s
test c_simple_tera_from_serialize ... bench:         735 ns/iter (+/- 13) = 131 MB/s
test d_simple_mustache            ... bench:         570 ns/iter (+/- 10) = 170 MB/s
test e_simple_handlebars          ... bench:       1,097 ns/iter (+/- 24) = 88 MB/s
test pa_partials_ramhorns         ... bench:          83 ns/iter (+/- 9) = 1168 MB/s
test pa_partials_ramhorns_btree         ... bench:          77 ns/iter (+/- 8) = 1259 MB/s
test pb_partials_askama           ... bench:         218 ns/iter (+/- 14) = 444 MB/s
test pc_partials_mustache         ... bench:         758 ns/iter (+/- 13) = 127 MB/s
test pd_partials_handlebars       ... bench:         991 ns/iter (+/- 16) = 97 MB/s
test xa_parse_ramhorns             ... bench:         196 ns/iter (+/- 7) = 795 MB/s
test xa_parse_ramhorns_btree            ... bench:         143 ns/iter (+/- 2) = 1090 MB/s
test xb_parse_mustache           ... bench:       3,925 ns/iter (+/- 75) = 39 MB/s
test xe_parse_handlebars          ... bench:       8,862 ns/iter (+/- 126) = 17 MB/s

Would it make sense to make the btreemap/hashmap switchable by feature?

[maciejhirsz]

The performance gain you have is not from replacing HashMap with BTreeMap, it's from removing the hash from a Field and forcing string compares everywhere. Why exactly is that faster isn't perfectly clear to me, but it's probably just leaving an extra register free.

The benchmarks won't reflect it since they only use two fiends and the names have different lengths, but this will be a performance degradation one you have more fields, and especially when you have two or more fields with names of the same length. I've explained the purpose of the hash in a blog post.