Generic programming for structure-aware algorithms

Almost 2 decades ago, Matt Austern discussed a performance issue with STL algorithms when applied to hierarchically structured data (such as a deque) and sketched a solution using hierarchy-aware algorithms and "segmented iterators" [1]. In the age of increasingly powerful vector hardware like SSE and AVX, the modest performance gap observed by Austern has widened into a gulf.

Expanding on his ideas, we discuss different options for implementing generic "flattening iterators", which enable STL-type "flat" algorithms to operate on them. However, this comes at the performance penalty mentioned before. An interesting side aspect are the performance characteristics of flattening iterators, which cannot preserve random access properties of the underlying sequences.

 

Hierarchical versions of these algorithms exploit the internal structure of the data, and overcome the performance issues of flat algorithms. Looking closer, we can identify groups of algorithms for which we can implement generic structure-aware "meta algorithms".

Benchmarks show that these generic algorithms perform on par with ad-hoc implementations exploiting the hierarchical structure, making generic programming the preferred option also in these cases.

 

Finally, we look into further applications of the hierarchical approach, like algorithm animation and patterns for parallelization.

 

[1] Matthew H. Austern, Segmented Iterators and Hierarchical Algorithms, Proc. of International Seminar on Generic Programming, 1998.

Speaker: Guntram Berti

Slides: Generic programming for structure-aware algorithms


Go back