"Bordet, Simone" wrote:
>
> Hey Ole,
>
> since we have a similar issues (you with Timeouts, me with TimerTasks), I
> would like to go more in deep, if you don't mind.
Not at all. Very interesting discussion.
> Below my point.
>
> > Such a structure is quite useful, and I wonder why it has never
> > become part of the library. I will most definitely have a look
> > at it when you commit it, but I am afraid that it is hard to
> > get around the problem that prohibited me from factoring out the
> > priority queue into a seperate class in the first place:
> > To remove an arbitrary node from the queue in time O(log(n))
> > you have to know the position of the node in the heap tree, and
> > since the heap is shuffled on inserts and removals, information
> > in the node will have to be shuffled along with it. For this I
> > have a field in the node that contains the node index in the
> > queue array. Whenever the heap is shuffled, I update this field
> > to keep it current. Without this field and the cooperation of
> > the priority queue to keep it updated, I would have to do a linear
> > search to find the index of the node.
>
> Well, I had the same problem; I solved it just marking the node as CANCELED;
> the time does the rest (ie when it comes the time for it to be executed, I
> see that it is canceled and I remove it from the top of the heap - very
> cheap).
> If I have well unserstood, you cannot do anything with a Timeout but
> cancel() it. You cannot re-queue it. So there is no issue on removing
> immediately the timeout, it can be done later. Am I missing something ?
No. Your point is absolutely valid.
The only problem I see with this is that most transactions are a lot
shorter than the timeout value so the queue could become quite big.
Consider a system doing 20 transactions per second, and almost all
transactions being very short but a few being long. Oleg Nitz would
like to set a 10-30 minute timeout as he has some long running
transactions. In case of a 30 minute timeout we would have
20*30*60=36000 entries in the queue, most of whom would be cancelled
and waiting to reach the queue head. And we cannot start reusing
Timeout instances until they are out of the queue.
If just we had pointer arithmetic so we could effectively find the
index in the queue array...
Guess I have done too much C programming after all ;-)
Honestly, I think that the lack of pointers is one of the
great advantages of Java.
Best Regards,
Ole Husgaard.
