Re: scalable event scheduling

Henrik Nordström <henrik_at_henriknordstrom.net> writes:
> mån 2013-01-28 klockan 22:29 +0000 skrev Rainer Weikusat:
>> Since Mr Rousskov was so kind to publically question my honesty and/or
>> mental sanity when I claimed that replacing the O(n) event scheduler
>> with a more scalable implementation would be easy (and in fact, so
>> easy that even using the STL implementation wouldn't be worth the
>> effort) and since I need this anyway for connection timeouts and
>> possibly other stuff in the squid fork I will be maintaining for at
>> least some time to come and had an hour of free time for some
>> recreational programming yesterday, I thought I could just do that.
>
> How large event queue are you expecting to see?

I'm using this in a squid variant where 'connect timeouts' are also
scheduled via eventAdd and a patch I sent last week was "trampled into
the ground by an orchestrated rhinoceros stampede" because 'someone'
believed the delays caused by the O(n) insertion and deletion of
events would be prohibitively large. This is not actually my opinion
for connection amounts I consider to be realistic (less than 100,000
concurrent half-open connections).

> The code was designed using a linear list becase
> a) Simplicity
> b) Expected queue length is relatively short.

OTOH, I've stopped using sorted, linked-lists for timer subsystems a
while ago because using a binary heap in an array is not significantly
more complicated (for my idea of 'significant', at least) and this
means I don't have to worry about 'expected scheduling patterns'
anymore (the difference won't matter for 'low frequency' events and
the same code will still perform well in face of 'high frequency'
additions and deletions).
Received on Wed Jan 30 2013 - 13:47:26 MST