TimeoutFactory update

[starksm64]

The original set of changes for http://jira.jboss.com/jira/browse/JBAS-2205 introduced a java.util.Timer that caused a huge transient memory usage due to the fact that cancelling a timer does not make it available for garbage collection due to the java.util.Timer/TimerTask implementation.

Redoing JBAS-2205 using the previous TimeoutFactory code (with the priority queue factored out) seems the way to go as java.util.Timer does not seem to be the best choice.

[starksm64]

The previous TimeoutFactory priority queue is not gernalized as its coupled to the TimeoutImpl details. There is a org.jboss.util.Heap which could be used instead.

[dimitris]

I looked at many generic Heap / PriorityQueue implementations and they all suffer from the inefficiency that removing an arbitrary object, other than the one on the "top" on the heap requires (a) a sequencial scan of the stored elements, until it is found & removed, (b) the heap restructured.

Ole's implementation avoids (a) because the stored elements keep an index back to Heap, that is updated whenever stored elemenets are swapped inside the Heap.

So generalizing this (factoring out the priority queue), without the performance hit it not possible, I think.

[starksm64]

Here is one acm article that claims an integer priority queue with O(log log n) delete operations:

http://portal.acm.org/citation.cfm?id=780566

We consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are in the range [0,N), we can also support delete in O(log log N) time.Even for the special case of monotone priority queues, where the minimum has to be non-decreasing, the best previous bounds on delete were O((log n)1/(3-?)) and O((log N)1/(4-?)). These previous bounds used both randomization and amortization. Our new bounds a deterministic, worst-case, with no restriction to monotonicity, and exponentially faster.As a classical application, for a directed graph with n nodes and m edges with non-negative integer weights, we get single source shortest paths in O(m+n log log n) time, or O(m+n log log C) if C is the maximal edge weight. The later solves an open problem of Ahuja, Mehlhorn, Orlin, and Tarjan from 1990.

[starksm64]

I can't tell from the link if this is an arbitrary delete or just the deleteMin. Given the time bound its probably just the deleteMin, not deletion of an arbitary element.

[dimitris]

I've checked-in in HEAD a restore of the previous implementation, enhanced with the new interface (ability to create new TimeoutFactories using a user provided ThreadPool, with graceful shutdown) if anyone wants to review. Needs testing.

[dimitris]

It looks ok to me so I'm porting this TimeoutFactory to 3.2.x/4.0.x