harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Sergey Kuksenko (JIRA)" <j...@apache.org>
Subject [jira] Created: (HARMONY-5232) [classlib][luni] TreeMap bug fixing and performance improvements.
Date Fri, 30 Nov 2007 13:21:43 GMT
[classlib][luni] TreeMap bug fixing and performance improvements.
-----------------------------------------------------------------

                 Key: HARMONY-5232
                 URL: https://issues.apache.org/jira/browse/HARMONY-5232
             Project: Harmony
          Issue Type: Bug
          Components: Classlib
            Reporter: Sergey Kuksenko


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.


-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message