Details
-
Bug
-
Status: Resolved
-
Major
-
Resolution: Fixed
-
None
-
None
-
None
-
Patch Available
Description
Bug description:
If original map contains keys: 1,2,3,4 .. and we creates headMap(-1) we should get empty map as result.
isEmpty for such map equals true, but method firstKey() returns the first key from original map instead of throwing NoSuchElementException. The situation with tailMap and lastKey() methods.
Checking of that is added into TreeMap unit tests.
Perfromance improvements:
1. Current implementation has a big inefficiency in SubMap iterations. Each element of subMap is compared with upper bound key. It leads to a big amount of unnecessary calls of compareTo(). Changed to classical log(N) amount of compareTo()
2. The second improvement is more related to architectural details of all modern computers. It is obvoius that SortedMap can be implemented not as a tree data structure, but as sorted array. Such way is not widely used, because of in case of insertion/deletion into such array we should constantly move a lot of data. However, for small trees such way has a big performance advantage against classical tree. The improvement is obtained because of all modern processors uses caches for memory access. Thus, 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. New implementation provides Tree's representation as sorted array for small maps and dynamic switching to classical tree when size exceeds limit.