Inefficient O(n^2) HTTP/2 chunk receiving
From: gvfs#697 (closed)
soup_body_input_stream_http2_add_data()
in libsoup/libsoup/http2/soup-body-input-stream-http2.c
appends to priv->chunks
every time it being called. However, priv->chunks
is a GSList
, and it does not store its tail. As a result, glib has to iterate the linked list every time it appends, making it an expensive O(n^2) function instead of O(n). This probably causes the performance issue inside gvfsd-dav when opening very large files.
Using GQueue
can workaround this -- at the cost of an extra unused prev pointer in every item in GList
. GLib seems to have no struct with GSList
+ GSList *tail
.