Performance of the STL idiom for list comprehension: Introduction

In my last post, I promised to consider the machine code generated from the STL idiom equivalent to a basic Python list comprehension. As I proceeded, the project expanded to a broader analysis of the idiom’s performance. I am shocked at how much effort this project took. I have spent much of the last five weeks generating and reading the output from g++ 6.2. So. Many. Alternatives. In this post, I’ll describe my baseline for comparison and the criteria I’ll use. In future posts, I’ll present the results.

A single STL statement equivalent to the basic Python list comprehension

In the last post, I described the structure of the basic Python list comprehension

[expression1(var) for var in expression2 if condition(var)]

and lamented that all the straightforward translations to the STL algorithms required two statements, one for the filter and one for the computation.

The limits of list comprehensions

I’ve spent my recent posts unfavourably comparing the STL design of containers/iterators/algorithms with Python list comprehensions and their close relatives in Haskell. This is an unfairly restrictive way to view the STL design, which addresses a wider range of use cases than the ones addressed by list comprehensions. But it is also unfair in that it ignores the limitations of list comprehensions themselves, limitations avoided by the more general structure provided by the STL. In this post, I’ll start from the other direction, considering the inherent limitations of Python list comprehensions. This in turn leads to an idiom in the STL that in fact provides virtually all the functionality of basic list comprehensions, with only slightly more complex syntax.

A simpler, fourth idiom for appending

This morning, I realized that there is a fourth approach to appending items to a vector that combines elements of the first and third. I’m embarrassed to have missed this one because it is a longstanding, well-understood approach that’s particularly applicable to the kinds of “list comprehension algorithms” I’m considering in this series.

Three idioms for appending values—a damaging decision?

Update: See also the next post, which adds a fourth idiom and mitigates some of the criticisms in the conclusion of this post.

The STL code for squaring the positive values, included the following lines to create the intermediate result t1 containing the positive values of the original list a: