[Bug 773770] rtpjitterbuffer: high CPU usage with low latency audio

[GStreamer (GNOME Bugzilla)]

https://bugzilla.gnome.org/show_bug.cgi?id=773770

--- Comment #10 from Petr Kulhavy <brain at jikos.cz> ---
Some analysis of rtpjitterbuffer.c and gstrtpjitterbuffer.c:
------------------------------------------------------------
1) RTPJitterBufferItem allocation - every single insert/remove triggers
malloc/free
    -> it is not necessary, because normally the buffer stabilizes at certain
number of frames and periodically a frame is added or removed. So the items
could be left in the data structure, just marked as unused and reused on the
next insert.

2)  gstrtpjitterbuffer.c:wait_next_timeout() for every single timeout
allocates/frees a new clock.
    -> since there is only one timer waiting at a time this is redundant and
can be done outside of the thread loop
    -> unfortunately it seems to be not that trivial due to timer unschedule,
which says the clock ID cannot be used afterwards :-(

3) the data structure in rtpjitterbuffer.c (linked list) is not very efficient:
* insert() is O(n) due to the initial sort-in and update_buffer_level()
* get_buffer_level/update_buffer_level is O(n)
    -> I will see if I can think of a better data structure, which is more
memory-friendly

4) the data structure for timers is not very efficient either and seems to be
even more intensively used.
    -> this could be an issue, see more below

5) The timers are stored in an array and one TimerData structure has a size of
just a little bit more than a cache line. I have tried to reduce it to exactly
one cache line (64B) but if there was any effect seen with perf it was <1%,
which I consider a measurement error.

In general the objects are not very cache optimal. There are holes and items
are not sorted by hotness. I have tried to cache-optimize
GstRtpJitterBufferPrivate, which has  a 4kB window array in the middle of the
structure :-o but that didn't seem to have any effect either...

Analysis of the timer array usage
---------------------------------
The array is used in:

* find_timer()
    - operation: linear search for seqno
    - complexity: O(n)
    - called from: jitter_buffer_chain (called JBC below), set_timer,
calculate_expected (called by JBC)
* add_timer()
    - operation expand and add to the end
    - complexity:  O(1) ? but calls realloc?
    - called from: update_timers (called by JBC), set_timer (called by JBC,
update_est_eos), calculate_expected (called by JBC)
* remove_timer()
    - operation: remove_index_fast
    - complexity: O(1) ?
* remove_all_timers()
    - operation: set len to 0, i.e. discard all elements
    - complexity: O(1) ?
* already_lost()
    - operation: linear search
    - complexity: O(n)
    - called from: jitter_buffer_chain
* update_timers()
    - operation: linear processing of all timers
    - complexity: O(n)
    - called from: jitter_buffer_chain
* wait_next_timeout()
    - operation: linear search for the lowest time/lowest seqno + remove lost
timers
    - complexity: O(n)

-- 
You are receiving this mail because:
You are the QA Contact for the bug.
You are the assignee for the bug.