Summary:ASTERISK-04062: [patch] tailqueues to queue frames (O(1) instead of O(n) cost)
Reporter:Luigi Rizzo (rizzo)Labels:
Date Opened:2005-05-04 08:58:07Date Closed:2011-06-07 14:10:45
Versions:Frequency of
Environment:Attachments:( 0) framequeue.diff
Description:the attached patch implemens queues of frames (used in channels)
as tailqueues instead of simple lists. This gives O(1) instead of
O(n) cost for insertions and merges.

Disclaimer just faxed in.

Patch Modifies:

Comments:By: stevekstevek (stevekstevek) 2005-05-04 10:17:16

This seems like a good idea; I do (basically) the same thing in the jitterbuffer (where the queue length is generally much longer than in the channel queue).

Have you seen any real performance benefit from this?  I would think that the queue is usually (almost) empty, and it wouldn't make much of a difference;  I suppose the only time things really get queued is while you're changing apps in the dialplan, or if an app isn't reading from the channel..

By: Kevin P. Fleming (kpfleming) 2005-05-04 12:00:50

Yes, this is nice work. I'll verify the disclaimer and we'll proceed from here.

Once this is in, it could be used for the chanspy queues as well.

By: Mark Spencer (markster) 2005-05-04 15:41:34

Generally speaking, the queue should be extremely short (in fact generally there would be no more than one entry in it).  This patch increases the size of ast_channel by at least 8 bytes.  Anytime the queue is more than a few frames long, it's indicative of failure in the code, since that means the audio stream is being ignored for a long time.

I do not believe this code is a win given the particular circumstances regarding Asterisk's queues, even though clearly it would otherwise be in the general case.

By: Kevin P. Fleming (kpfleming) 2005-05-04 15:49:48

It seems that a reasonable course of action here might be for you (rizzo) to run a system with this patch in place and some additional logging for how often the queue length gets over 3-4 frames... that would at least start to provide some real-world documentation of the benefits or lack thereof.

By: Luigi Rizzo (rizzo) 2005-05-05 02:22:55

i don't run an active asterisk system, so even if i were willing to do the
experiment i could not provide any useful data.
I agree (and have seen) that the queue is never more than one entry here,
but still don't see the objection in using a better code to implement it,
especially given that this code can be used elsewhere (e.g. i just noticed
the  ast_queue_spy_frame() that you mentioned.

The comment on the ast_channel size increase does not seem very relevant.
The data structure is 1004 bytes before my patch, so the extra 8 bytes
hardly matter, and you can save 4 by removing len_voice, which I only
put in to implement what the comment in the code says about not
queueing more than 96 voice frames, but note that the original code
actually did something different i.e. do not queue voice frames if
the queue is longer than 96.

By: Michael Jerris (mikej) 2005-05-05 05:57:25

The issue here is not that 4 bytes is a lot of memory, it is 4 bytes * the number of channels but regardless, why do we want to add it for no benefit here.  Why does it need to be implemented here to implement in other areas of *.

By: Kevin P. Fleming (kpfleming) 2005-05-15 02:11:13

Agreed, we generally don't implement new things without a specific use for them at commit time. Given that the channel queues are always short, this patch does not seem to provide any tangible benefit. Feel free to reopen this bug if you can demonstrate some direct performance improvements from it :-)