6 Replies Latest reply on Jan 30, 2006 3:48 AM by Dimitris Andreadis

    TimeoutFactory update

    Scott Stark Master

      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.

        • 1. Re: TimeoutFactory update
          Scott Stark Master

          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.

          • 2. Re: TimeoutFactory update
            Dimitris Andreadis Master

            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.

            • 3. Re: TimeoutFactory update
              Scott Stark Master

              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.



              • 4. Re: TimeoutFactory update
                Scott Stark Master

                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.

                • 5. Re: TimeoutFactory update
                  Dimitris Andreadis Master

                  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.

                  • 6. Re: TimeoutFactory update
                    Dimitris Andreadis Master

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