Skip to content

Avoid repeatedly traversing list in a loop to append children

Jiří Techet requested to merge jiritechet/json-glib:performance_fix into master

g_list_append() requires traversing the whole list and inside the loop it leads to quadratic complexity. Instead, just prepend children to the list and revert it afterwards once.

I ran into this issue while implementing a LSP client plugin for Geany on top of jsonrpc-glib and json-glib. This problem appears for the "semantic tokens" call

https://microsoft.github.io/language-server-protocol/specifications/lsp/3.17/specification/#textDocument_semanticTokens

which returns a biggish (though nothing dramatic, just thousands of elements) array of integers. This often leads to a complete freeze of the plugin with the profile below.

After this patch, it's completely fixed. The change in json_to_gvariant_array() is sufficient to fix this problem but I looked for more uses of g_list_append() in the library and json_to_gvariant_tuple() seems to be the only other one so I made the change there too, it shouldn't hurt.

Screenshot_2023-11-12_at_10.40.03

Edited by Jiří Techet

Merge request reports