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

 
 
Latest News
Gnulib helps you porting to Android posted by haible, Sat 15 Apr 2023 10:31:06 PM UTC
Gnulib helps you get away from fork() + exec() posted by haible, Sun 20 Nov 2022 04:27:43 PM UTC
Gnulib provides versatile bit-set implementations posted by akim, Wed 13 Jan 2021 12:17:37 PM UTC
Gnulib supports portable multithreading posted by haible, Wed 30 Dec 2020 03:10:08 PM UTC
Gnulib helps you write efficient algorithms posted by haible, Wed 23 Dec 2020 01:42:02 PM UTC

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

 

Back to the top

Powered by Savane 3.12.
Corresponding source code