gnulib - GNU portability library - News: Gnulib helps you write efficient algorithms

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:

• Lists (array, circ. array, link, tree, hash)
• Set (array, hash, linkedhash)
• Ordered set (array, tree)
• Map (array, hash, linkedhash)
• Ordered map (array, tree)

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).