[jira] [Comment Edited] (AMQ-5825) Improve performance of Queue.addToConsumerList()

["Christopher L. Shannon (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/AMQ-5825?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14581062#comment-14581062 ] 

Christopher L. Shannon edited comment on AMQ-5825 at 6/10/15 8:56 PM:
----------------------------------------------------------------------

A TreeSet might work here to replace the ArrayList so that insertions are done in O(log n) and are sorted already.  The one issue is that the comparator would need to be updated to make sure that if priority is not set (aka returns 0), that the comparator could then compare the Subscriptions in some other way to find out if they are unique otherwise the Set would think two Subscriptions were a duplicate and not add the second one.  Would need to test out a bunch of cases to make sure a change like this wouldn't break anything.


was (Author: christopher.l.shannon):
A TreeSet might work here to replace the ArrayList so that insertions are done in O(log n).  The one issue is that the comparator would need to be updated to make sure that if priority is not set (aka returns 0), that the comparator could then compare the Subscriptions in some other way to find out if they are unique otherwise the Set would think two Subscriptions were a duplicate and not add the second one.  Would need to test out a bunch of cases to make sure a change like this wouldn't break anything.

> Improve performance of Queue.addToConsumerList()
> ------------------------------------------------
>
>                 Key: AMQ-5825
>                 URL: https://issues.apache.org/jira/browse/AMQ-5825
>             Project: ActiveMQ
>          Issue Type: Bug
>          Components: Broker
>    Affects Versions: 5.11.1
>            Reporter: Tim Bain
>            Priority: Minor
>              Labels: performance
>
> In a Users mailing list post (http://activemq.2283324.n4.nabble.com/More-ActiveMQ-hotspots-courtesy-of-continuous-profiling-td4697159.html), Kevin Burton noticed that Queue.addToConsumerList() was taking 5% of his CPU cycles because we're re-sorting after every insert, which is expensive when we have lots of consumers. His scenario's a little unique because he uses far more destinations (and far more consumers) than most installations, but it still highlighted a potential performance improvement.
> I think we can do a sorted insertion (iterate through the list till you find the right place based on the comparator, then insert) to skip the re-sort.  Either we'll be rolling the list or we won't, but either way the list will be in sorted order, except that the minimum element might not be the first one.  So we'd find the minimum element's index (which is O(log N), but can be optimized to O(1) for the not-rolling case), then do a sorted insert starting at that index and wrapping if necessary.
> Even better, we could implement rolling by just keeping the index of the current "first" element, which we would increment each time the list rolled.  Then instead of looking at element 0, we'd just get that element, which would spare us the O(N) operation to roll the list each time we did that.  And at that point, finding the minimum element's index becomes O(1), not O(log N), which is a nice benefit.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)