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

 
 
Latest News
Gnulib provides versatile bit-set implementations posted by akim, Wed 13 Jan 2021 12:17:37 PM UTC - 0 replies
Gnulib supports portable multithreading posted by haible, Wed 30 Dec 2020 03:10:08 PM UTC - 0 replies
Gnulib helps you write efficient algorithms posted by haible, Wed 23 Dec 2020 01:42:02 PM UTC - 0 replies
Gnulib can help your C++ programs posted by haible, Wed 16 Dec 2020 08:31:05 PM UTC - 0 replies

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

No messages in Gnulib helps you write efficient algorithms

 

Back to the top


Powered by Savane 3.5