"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.
>
> Indeed !
>
> > 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.
>
> I see.
> Is the following idea valuable in your opinion ?
> Say you have to wait 15 minutes for the first timeout to expire; you remove
> it from the queue and reinsert it immediately; in the meanwhile many
> timeouts created after it have been canceled (and when you cancel a timeout
> you put its expiration time to be less than now so that it is "expired"), so
> that the reinserted 15 minutes timeout will be now not on top of the queue
> (because all canceled ones "expires" before it) but in the middle. Then the
> normal doWork() will extract all canceled timeouts until it gets again on
> the 15 minutes one. You can decide to remove and reinsert it depending on
> the time left for it before expiring.
My first reaction to this was:
A) Changing expiration time of an element in the queue
could break the invariant.
B) Removing the front element and re-inserting it would
not ensure that all or some cancelled elements go to
the front of the queue. The cancelled node could be
in a branch of the tree that is touched neither by the
removal nor by the insertion.
Item A could be fixed: If the expiration time of a cancelled
entry is set to 0, we could create a more complex invariant
that would allow an expiration time of 0 anywhere in the tree.
The node addition algorithm should then be changed as it would
otherwise break the new invariant; and while it would still be
O(log(n)), the number of node swaps could be somewhat larger.
Item B is not as easily fixed. I did some calculations on the
probability that a given cancelled node would be moved to the
root of the tree by an insertion. A rough calculation says
that it is about 1/(2^D(node)) where D(node) is the distance
of node to the root. So we could significantly raise the
probability of cancelled nodes reaching the root by moving
the cancelled node a fixed small number of steps closer to
the root.
> Anyway, this discussion is to clarify to myself the timeout mechanism for
> transactions, and to have a comparison for the TimerTasks. But if you can
> avoid log(n) complexity when canceling a task (given the performance
> constraints for the tm package) from the ideas of this discussion thread,
> I'm glad share those ideas.
Problem is that even removal of the front entry has log(n)
complexity. So while we save some processor time at
cancellation we still have to use this time when the
cancelled node reaches the front of the queue.
And the queue would be larger due to unremoved cancelled
entries, which means more time spent in all queue
operations. This could be made smaller by using some more
time at cancellation due to the probability calculation
above.
So IMHO immediate removal of cancelled nodes would be
better.
> Maybe will help adding a remove method on the Heap class I'll check in (now
> it is not present).
There is a problem with removing an arbitrary node from
the queue:
Unless we know the position of the node in the tree, we
would have to do a search for it first. That would be a
O(n) operation. To avoid this I have a field in all
timeout nodes that contain the index of the node in the
queue array, and whenever a node is moved in the tree,
its index field is updated. But this means that the
priority queue must know about the nodes it holds, and
interact with them.
If possible I would prefer shared code here.
But a more generic heap-based priority queue could be
slower.
I guess it all comes down to how you intend to use
the priority queue: If most of your TimerTasks stay
in the queue until reaching the front and only a few
are cancelled, it would probably be better to have
seperate code. But if a lot of your TimerTasks are
cancelled, having a common priority queue could be
best.
> Maybe better leave timeouts as they are.
> Maybe better settle this thoughts, take a pause and rethink again.
> Anyway thanks for your time.
I think this is worth thinking about. If we could
have common code and a common queue here, footprint
would be reduced and processor caches better utilized.
Best Regards,
Ole Husgaard.
