[jboss-jira] [JBoss JIRA] Commented: (JBRULES-3141) Replace BinaryHeapPriorityQueue Implementation with Java's PriorityBlockingQueue

[Mark Proctor (JIRA)]

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

Mark Proctor commented on JBRULES-3141:
---------------------------------------

As previously mentioned we can't use the JDK PriorityQueue as random removal is search based. This makes it very slow for removing cancelled activations.

While the binary heap queue algorithm is pretty standard, reviewing the two implementations there is some very subtle differences. Our one is "1" based where as the JDK one is 0 based.  percolateUpMaxHeap  vs siftUpUsingComparator is ever so slightly different too, using shift operators instead of / etc.

My guess is you should be able to move ours to the same logic as JDK's, without copy pasting, and achieve similar results. While still being faster for random removal.

> Replace BinaryHeapPriorityQueue Implementation with Java's PriorityBlockingQueue
> --------------------------------------------------------------------------------
>
>                 Key: JBRULES-3141
>                 URL: https://issues.jboss.org/browse/JBRULES-3141
>             Project: Drools
>          Issue Type: Feature Request
>      Security Level: Public(Everyone can see) 
>            Reporter: Brad Davis
>            Assignee: Brad Davis
>         Attachments: BasePriorityQueue.java, BinaryHeapPriorityQueueTest.java
>
>
> Attached is a PriorityQueue implementation I wrote last night to replace our home grown implementation.  I think it must have preceded the PriorityBlockingQueue that is already part of Java 5 & 6.
> BinaryHeapPriorityQueueTest is where I plugged in this implementation.  Below are the results first running with our home grown BinaryHeapPriorityQueue, and then with the one I created, BasePriorityQueue.  There are numerous other benefits to using this as well, as it will fully implement the java.util.Collections API and therefore cleanup some other code elsewhere in our codebase.
> The result for 10000 objects inserted and retracted was: 
> BinaryHeapPriortyQueue
> elapsedEnqueue = 32
> elapsedDequeue = 294
> BasePriorityQueue
> elapsedEnqueue = 26
> elapsedDequeue = 167

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira