Alexander Chemeris wrote: > Hello, > > Consider following as open discussion. I'm just want to show that linked > lists are not the best solution in all cases, and we should be careful > and see all possible variants and problems when changing something. > > On 2/7/07, Jaroslav Libák <[EMAIL PROTECTED]> wrote: > >> Have you considered using a sorted linked list for storing packets? >> > Short answer is no, because its only benefits are lesser memory consumption > and infinite length. Read below for longer description. > > >> Currently there is a circular queue in static array. With a sorted linked >> list, >> we could have different buffer length for different codecs, >> > This could be done with dynamic array too. It's matter of API, not internal JB > realization. With array we just allocate it once with requested size. > > >> and buffer size could change dynamically. For example if we detect that >> jitter >> is high and there are lots of missing frames we could extend the buffer a >> little >> bit and introduce small delay in playback. >> > It could change dynamically even with array. To change its size you may store > additional pointer to its 'virtual' size and take it into account when adding > new packet. So if virtual size is lesser then real there always will be free > 'real' space in buffer. Increasing and decreasing virtual size of array is as > cheap as icreasing and decreasing size of linked list, if not cheaper. > > >> Insertion into a linked list would be cheap if there are no missing frames, >> and slightly more expensive if there are some missing ones and arriving out >> of order (this is a constant operation right now). >> > For good implementation of array insertion will be always constant time. > > >> Pulling frames out of MprDejitter would be a constant operation in comparison >> to current code, which basically needs buffersize loops since it begins the >> loop after the newest frame (if frames arrive in order and there is no loss). >> > Current realization is ugly, :( pulling from array may be done much faster. > Just > keep pointer to eldest available packet, and you'll get constant time > for no loss > case and very little time in case of loss. > > >> Frames in linked list would be sorted according to rtp timestamp as sequence >> numbers could cause problems. >> > Vice versa. :) You could not use timestamps to sort packets, because there may > be several packets with same timestamp (e.g. video frame, splitted to several > RTP packets). Moreover, timestamp have undefined step. And sequence number is > different for all packets (inside long wrap period), and increased by 1 for > each > next packet even if it have same timestamp. > > >> It would simplify the code in MprDejitter and in the G711 u and A decoder >> decodeIn function substantialy. >> > So, I believe it could be simplified without linked lists. ;) > > >> If we use sorted linked list we can also compute statistics like how many >> frames in order (without missing slots) do we have in the list from the head. >> > In linked list it is done in linear time. So I propose using member integer > variable to compute this statistic - increase it when packet added to buffer > and > decrase when it is removed from list. > > >> For example if we detect that we only have some missing frames in next >> 100ms, we >> can increase the delay before playback until it improves >> > There more to do with good mathematics... You should be more concerned on > *when* > increase and decrease buffer size to get best voice quality. As I > already said it is > easy to implement in either case. > > >> (it would have to detect somehow when other side simply stops sending rtp >> packets). >> > Stream stop should be reported by higher levels. > > >> We would have to drop very old frames during insertion (the buffer would >> have to be >> notified about the minimum timestamp that it should accept - that would be >> the rtp >> timestamp of last played frame). It would be simpler than in the current >> implementation, as we would know that frames in the head would be certainly >> accepted >> by decoder, whereas currently we don't know this when we loop through the >> array as >> decoder decides whether it wants the frame or not. Deciding which frame >> should be >> played and which not should be the work of jitter buffer only, decoder >> should not >> interfere (only supply last played frame). >> > Yeah... There are codecs, wich provide their own jitter buffer and > PLC, so our dejitter > API should be designed to make them usable. All our efforts should be > put on increasing > audio quality. So all arrived packets should be reported to decoder, > even if packet > is out of order. However if you have an idea of better interface, you're > welcome > to suggest. > > >> I have some code that works using linked lists (not UtlSortedList, but custom >> implementation, I didn't want to add too much penalty) without the >> improvements. >> > Custom implementations are not very welcome. They may contain bugs, > already cleaned > from standard ones, they mey be less portable, they may be even worse > documented. > It would be better to adopt standard implementation to your needs. > > E.g. one of principles of realtime media processing in sipX is to > avoid dynamic memory > allocation during frame processing cycle. On embedded system it very > time consuming > operation. As you may see memory pools are used whenever possible. I > should say, that > memory pools are faster then dynamic memory allocation even on x86. > > >> I would like to hear whether you think that replacing fixed arrays with >> linked list >> is the way to go. >> > That's it. :) > I hope my criticism will not turn you away from improving jitter > buffer quality. It is > really one of critical parts of all VoIP applications. I believe > linked lists are not > better then (dynamic) array here, but I also believe that current > implementation should > be improved greatly. > > > Not at all, I agree with your decision, linked lists would add too much memory allocation/deallocation and we can also have dynamic circular buffer with virtual pointer. That's why I only tried basic modification which used linked list without any improvements just to see how it works. I read on http://sipx-wiki.calivia.com/index.php/Project_Roadmap_and_Feature_Wish_List that perhaps we could use spandsp for this + packet concealment or another library.
Jaro _______________________________________________ sipxtapi-dev mailing list [email protected] List Archive: http://list.sipfoundry.org/archive/sipxtapi-dev/
