Consider using arrays and linear search for small hash maps.

[DartBot]

This issue was originally filed by @mdakin

---

Alex Tatumizer made some tests and reported better performance using arrays + linear serch for small maps: https://groups.google.com/a/dartlang.org/d/topic/misc/CjRvg2pyG3I/discussion

Idea is, for small hash maps, store keys, hashes for keys and values in separate arrays , and when doing lookups only do a linear search on key hashes. When same hash is found, check for key equality, if equals, return index, if not return null. During insertion it checks for (a very unlikely) hash collision and if there is one falls back to normal map implementation.

It is faster than currenct Compact hash map for lookups and insertions (https://code.google.com/p/dart/source/browse/branches/bleeding_edge/dart/runtime/lib/compact_hash.dart) because of its simplicity and guarantee of no collisions (It does at most 1 equals check)

It is 1.4-2x faster than current map implementation for small sizes (<16) , performances are same around map size of 30 (On Intel I7). Cut off is probably lower on older CPU's. 16 would be a good number.

Alex's original code: https://gist.github.com/tatumizer/91a887e802594becaa8c

Same code with my small changes: https://gist.github.com/mdakin/db6e0b780ccd11ea0b8b
My Results: https://gist.github.com/mdakin/12d9ac332f2cf5abfa46

We believe performance gains justified having a simple array based implementation inside current hashmap because small hashmaps are very common.

[mraleph]

cc @kodandersson.
Added Area-Library, Accepted labels.

[lrhn]

Removed Type-Defect label.
Added Type-Enhancement label.