Re: scalable event scheduling

On 31/01/2013 3:12 p.m., Rainer Weikusat wrote:
> Alex Rousskov <rousskov_at_measurement-factory.com> writes:
>> On 01/30/2013 09:30 AM, Rainer Weikusat wrote:
>>> Alex Rousskov <rousskov_at_measurement-factory.com> writes:
>>>> On 01/28/2013 03:29 PM, Rainer Weikusat wrote:
>>>>> so easy that even using the STL implementation wouldn't be worth the
>>>>> effort
>>>> Can you clarify why we should not just use one of the STL queues
>>>> instead?
>>> I agree with your opinion that "the STL doesn't contain an 'obviously
>>> good' choice for a priority queue implementation in the given
>>> context".
>> I am glad we agree on this, but I think that STL must be seriously
>> considered before we add something custom.
> It is not suitable in this case and reading through the documentation
> should also show that as the comparable 'STL thing' lacks a 'delete
> any object' interface. I'm also no more convinced of the merits of the
> STL approach than the people who wrote (or didn't change) all the
> other existing code which could theoretically use it, up to the
> linked-list based events.cc itself.
>
> [...]
>
>>>>> the event scheduler will store a value at the
>>>>> pointed-to location which can be passed to eventDelete to cancel a pending
>>>>> event 'safely' in logarithmic time, meaning, even if the event was
>>>>> possibly already put onto the async queue.
>>> The purpose of the eventDelete routine is not to cancel a call the
>>> event scheduler already put onto the async call queue but to prevent
>>> such a call from being put onto this queue if this is still
>>> possible. And I didn't intend change that.
>> Noted, but I am still missing something: Why add a new event tag API if
>> the existing eventDelete() code can already cancel events outside the
>> async queue?
> I already explained this in my first mail on this topic and I will
> gladly answer (reasonable) questions based on what I wrote there.
>
> [...]
>
>> I do not think such "occasionally working" cancellation is a good idea
>> though.
> There are two different queueing subsystems involved here and because
> of this, users of the code will have to deal with both. This may be
> regarded as unfortunate design choice but in any case, it wasn't my
> choice[*].

This is a good argument for doing the event AsyncCall conversion before
the engine conversion.

That way the cancellation from the outside perspective is a uniform
AsyncCall cancellation whichever engine is used. We just end up with a
(brief?) period of inefficiency as we use a linked-list filled with
events waiting to schedule already cancelled Calls. This is not a big
problem IMO.

Both are relatvely small simple steps when taken individually.

>
> [*] In order to get stuff done, one has to start with something
> reasonably simple that it can be accomplished relatively easily on its
> own and deal with the remaining deficits of 'the universe in the
> pitiful state it generally happens to be in' afterwards. At least, it
> will be a somewhat less pitiful state then.
>
> [...]
>
>> I also think that the need for explicit destruction of the event "tag"
>> by the caller is a serious downside because it increases the risk of
>> memory leaks.
> No more serious than all the existing situations where this is already
> necessary, including kernel objects like file descriptors [*].

IMHO the cancellation should be an optimization not a memory leak
prevention.
Proper use of the Pointer patterns please in all new code where it makes
sense.

>
>> FWIW, here is how I think the event cancellation should be supported
>> instead:
>>
>> 1. Another form of eventAdd() should be added to accept caller's async
>> call. New code, especially async jobs, should use that form (jobs will
>> and avoid call wrappers that way). Old code that wants to cancel events
>> should use this new form as well.
> This would imply keeping cancelled events on the event scheduler queue
> until they expire 'on their own' because the metainformation necessary
> to remove them efficiently from this queue is not available in this
> way. That's another thing I used to do in the past but the amount of
> code which doesn't need to be written because of this (essentially, a
> single if-statement) doesn't warrant the runtime overhead of not
> providing this functionality, especially in the case of a 'universal'
> timer subsystem which is both useful for tasks which are usually
> expected to be executed and tasks which usually won't run (like
> timeouts).
>
> A better idea would be to add an interface which takes a call instead
> of the function pointer + argument pointer as argument so that all
> options would be available to be used whenever their use happens to
> make sense (an even better idea would be to integrate these two
> separate things in some 'closure-like' object and to relieve users
> from the burden of worrying about two pointers instead of one but
> that's sort of a digression).

Uhm, that is what Alex just said in the first sentence of (1).

The implication of leaving events queued until they expire only stands
for old code which did that already.
Old code which needs to remove events should be updated to holding the
Call they scheduled in the event queue, and cancelling it.

This is a good argument supporting my assertion that we should drop the
wrappr API all at once when adding a better one.

> [...]
>
>> The current event scheduler already creates an async call object for
>> nearly all events anyway, so this does not add CPU overhead. The only
>> overhead is that we will consume the same [small] amount of RAM
>> sooner.
> It actually does this for all events. This kind of double-indirection
> is what makes getting rid of an even which is possibly still on the
> event-scheduler queue so difficult (as I wrote in my reply to
> Amos). Unless there's (again) something I'm missing, running event
> scheduler events directly from the EventScheduler::checkEvents routine
> should be considered as 'general case'. 'Running async calls' could be
> provided on top of that using a suitable, general 'event running
> routine'.

Each of the Calls listed in the events queue may schedule regular
AsyncCall's in the Call queue. Which need to have the same relationship
guarantees needing to be held to.
Also, each of the events Calls (particularly the heavy ones) may result
in a new 0-delay event being scheduled before it completes running.

To resolve that problem one needs to build a temporary list of 'now'
events before running any of them. The AsyncCall queue is used as that
temporary list, AND provides the guarantee that the events Calls
interlact correctly with any sub-Calls they may schedule. Without
duplicating the Dialer operation code in both Call queue and event queue.

Amos
Received on Thu Jan 31 2013 - 02:54:05 MST