Description
Attached patch is further development of idea shown in HARMONY-5232.
As it was obtained using sorted arrays for small trees gives a boost over classical trees.
"In case of small SortedMap storing data in sorted array leads to significant increasing of cache hits. Practical measurements shows that operation get() became 10-30% faster and operation put is 3-10% faster. Even additional overhead for moving data for put() operation is smaller then obtained benefit and as result we got speedup."
HARMONY-5232 splitted internal tree representation into two parts: sorted array for small tree and classical tree for all other cases.
The attached patch implements the idea that we can store the origival tree structure, but instead of storing one key in the tree node (classical tree) each tree node contains small sorted array of keys. As result we:
- utilize performance benefits from "small sorted array" not only for small trees (as it was done in
HARMONY-5232), but for all trees. - avoid internal dynamic switching between two kinds of internal tree representation and makes code simple.
The latest fact has a big advantage for bug fixing, so fixing bugs described in HARMONY-5248 is much easier.
The current patch fixes all problems with EUT (HARMONY-5248).
Attachments
Attachments
Issue Links
- is related to
-
HARMONY-5248 [classlib][luni][EUT] r599829 caused regression in 5 suites
-
- Closed
-