[jboss-jira] [JBoss JIRA] Commented: (JBRULES-3141) Replace BinaryHeapPriorityQueue Implementation with Java's PriorityBlockingQueue
[
https://issues.jboss.org/browse/JBRULES-3141?page=com.atlassian.jira.plug...
]
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