[Asterisk-Dev] sched.c::schedule function can be a bottleneck and is optimised backwards

[Steve Kann]

Chris Wade wrote:

> Steve Kann wrote:
>
>> If you end up with thousands of schedulings in the first 100ms or so, 
>> and then a thousand or so things spread over the next 30ms, then it 
>> might make sense to split it up into two queues: a "short" queue, and 
>> a "long" queue, or something like that.
>
>
> Why not simply choose the schedule search algorithm at time of 
> insertion?  I'm sure both algorithm's have their place -- let the 
> developer needed to schedule something choose the better algorithm for 
> what they are scheduling.  I may be talking out of my @$$ here but 
> it's just a stupid suggestion.
>
Because, even with a doubly-linked list, you still would have only two 
choices:  start looking for the right place at the beginning, or start 
looking at the end.

My suspicion is that the scheduler queue actually has two different 
types of scheduling events:  short-term events, and long-term events.

The short term events might be 50% of the total, and might all be 
scheduled for the next 500ms or so (not sure what that number would be), 
and relatively evenly-distributed over that time.   These short-term 
events would include:

a) New Jitterbuffer pulls (these are actually all generally scheduled to 
happen every 20-30ms or so).
  (OR, old jitterbuffer delivery scheduled packets, probably evenly 
distributed over <jitter>-ms).
b) IAX2 retransmits (2xRTT or so, probably around 30-60ms or so).
c) other things like this (?)

The long term events might also be 50% of the total, but evenly 
distributed over 30s or 60s or so.
a) pings (once every 10s?)
b) lagrq (once every 30s? -- these probably should just go away, IMHO).
c) Real-time auto-clear (?)
d) call timeouts (auto-congest?)
e) registration-refresh
f) registry-expiration
g) auth-reject?
h) auto-hangup
i) poke stuff

So, if you want to schedule something long-term, you need to search 
through _all_ the events to find the right spot to put it in the list.  
That's definately bad, and you can pretty much solve that by starting 
your search from the end of the queue.

But, it doesn't help for the short-term events.  For these, it would be 
ideal to start from the "middle", and work back, or something, which 
isn't really an option.  That's why it might make sense to have two 
queues, and have the scheduler just maintain them separately:

When you schedule something, if you're scheduling it to happen within X 
ms (where X might be 200, 500, or 2000, for example), it would go into 
the short-term queue, and you'd start looking for the right place at the 
end.  If it's long-term, you'd look at the end of the long-term queue, 
to find the right place.

You can probably implement this as follows:

1) Modify ast_sched_XXX to follow the same API, except use a 
double-linked list, and search from the end of the list when adding.

2) Modify chan_iax2, so that "short-term" scheduled things use 
"sched_short", and long term things use "sched_long", instead of both 
using the same scheduler.

3) Modify the 5 line area at the bottom of network_thread in chan_iax2 
to check both scheduler queues and use the earlier value when it calls 
ast_io_wait.

-SteveK