newsgnulib - GNU portability library - News

 
 

Gnulib helps you write efficient algorithms

Item posted by Bruno Haible <haible> on Wed 23 Dec 2020 01:42:02 PM UTC.

When writing algorithmic code, the classical approach is to define the data structures, write the algorithm, debug it, and then profile it. It often occurs that you notice that a certain list, set, or map can get large and that this costs CPU time. Then, you change the data structure, adapt the code (often substantial changes), debug it again, and finally profile it again.

Gnulib has a set of container types, that you can use for your data structures, and that can make this process easier. With these types, changing the data structure is a one-liner change, no second debugging is needed, and you can proceed to the final profiling right away.

How does this work? The Gnulib container types have the same API across different implementations, each with different performance characteristics. Since 2018, the available container types are:


The performance characteristics are documented. So, a typical change replaces


  result->entries_reversed =
    gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode,
                          NULL, true);


with


  result->entries_reversed =
    gl_list_create_empty (GL_RBTREEHASH_LIST, entry_equals, entry_hashcode,
                          NULL, true);


and the corresponding commit message was: Speed up from O(n²) to O(n).

Back to the top

Powered by Savane 3.13-f8d8.
Corresponding source code