[infinispan-issues] [JBoss JIRA] (ISPN-2067) The ConsistentHash implementation on the hotrod client is very inefficient

[Mircea Markus (JIRA)]

    [ https://issues.jboss.org/browse/ISPN-2067?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12695925#comment-12695925 ] 

Mircea Markus commented on ISPN-2067:
-------------------------------------

I've implemented the CH on the new Map approach, the performance is almost 10000 better:
It took 17510 millis for consistent hash ConsistentHashV1 to execute 1000000 operations 
It took 212 millis for consistent hash ConsistentHashV1_2 to execute 1000000 operations 

Looking at the figures the current CH implementation behaves even worse than I initially expected. (tests were run on an 15000 virtual nodes CH).

                
> The ConsistentHash implementation on the hotrod client is very inefficient
> --------------------------------------------------------------------------
>
>                 Key: ISPN-2067
>                 URL: https://issues.jboss.org/browse/ISPN-2067
>             Project: Infinispan
>          Issue Type: Feature Request
>    Affects Versions: 5.1.4.FINAL
>            Reporter: Mircea Markus
>            Assignee: Mircea Markus
>             Fix For: 5.1.5.FINAL, 5.2.0.ALPHA1
>
>
> Profiler snapshots show that a large amount of time is spent in the {{org.infinispan.client.hotrod.impl.consistenthash.ConsistentHashV1#getServer}} method (about 13%).
> The root cause of this is the fact that the size method invoked on an object returned by TreeMap.tail() is very expensive: TreeMap.tail() returns an instance of TreeMap.AscendingSubMap class for which the size method, in order to calculates the number of elements, iterates over the entire collection(O(n)). This is highly inefficient and not scalable especially since the number of virtual nodes was set to 50 by default, as not the size of the collection is quite high: e.g. 32 nodes with 50 virtual nodes each, size()'s iterates an average of ~750 elements.  

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.jboss.org/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira