Month: February 2015

Quote of the week – shortcuts

… too tight a schedule will inevitably lead to the temptation to take shortcuts. These shortcuts might succeed in getting the system working on time – but only if everything goes right, which it rarely does.

Gerald Weinberg The Psychology of Computer Programming Silver Anniversary Edition p68

The Psychology of Computer Programming was originally published in 1971 but remains a great read and very relevant even in a very different computing world. I have the silver anniversary edition which reprints the original with additional commentary at the end of each chapter – what Weinberg calls “wisdom of hindsight remarks”. Weinberg’s comments – 25 years on – about the above quote state:

The wisdom of age has made me ashamed of this statement. “Rarely” is pussy footing; something always goes wrong. Shilly-shallying like this by authors like me has perpetuated the myth of the “optimistic” estimate – how long a project would take if everything went right. Such “estimating” might just as well be based on the assumption that the Laws of Thermodynamics will be repealed during the project.

Gerald Weinberg The Psychology of Computer Programming Silver Anniversary Edition 5.i

Quote of the week – 6 tools

I imposed on [Jack] Real the requirement that he try to design the helicopter so that it could be serviced with six simple tools – any six of his choice. This was more a challenge than an arbitrary decision. I think most good designers want to keep things simple, but sometimes, for the sheer engineering delight of creating, things become unnecessarily complex and cumbersome.

Clarence L. “Kelly” Johnson Kelly: More than My Share of It All

Kelly Johnson was the head of Lockheed’s Skunk Works and a renowned aeronautical engineer. His Wikipedia article contains many more details, including his 14 Rules of Management.

Kelly: More than My Share of It All is also worth reading. It includes stories of Amelia Earhart, the SR-71 Blackbird and a 400lb lion chasing Althea Johnson (Kelly Johnson’s wife) around a factory.

I am not going to search for a software equivalent of “six simple tools” – that would be an analogy too far, and as Johnson goes on to say, the “six tools” are less of a requirement than they are about setting up an attitude. Maintenance matters. Simplicity matters. What use is the best helicopter in the world if you can’t keep it running?

I think there is a software parallel in this comment from Chris Jaynes (commenting on Tim Bray’s post On Duct Tape, itself a response to Joel Spolsky’s post The Duct Tape Programmer that in turn was inspired by a chapter in the book Coders at Work profiling Jamie Zawinski):

Yes, shipping version 1 is a feature, but shipping version 2 is ALSO a feature!

To that I would add:

Being able to fix bugs is a feature.
Being able to maintain code is a feature.
Being able to add features is itself a feature.

Algorithms and Variations 1

In this talk, Alex Stepanov states “Science is about classification”.

This series is going to look at different ways we can classify the standard algorithms. Classification involves finding patterns, and with any luck the patterns will reveal things that we didn’t previously know.

I’ll start by listing all of the algorithms – 144 in total:

T accumulate (InputIterator, InputIterator, T)
T accumulate (InputIterator, InputIterator, T, BinaryOperation)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator, BinaryOperation)
ForwardIterator adjacent_find (ForwardIterator, ForwardIterator)
ForwardIterator adjacent_find (ForwardIterator, ForwardIterator, BinaryPredicate)
bool all_of (InputIterator, InputIterator, Predicate)
bool any_of (InputIterator, InputIterator, Predicate)
bool binary_search (ForwardIterator, ForwardIterator, T)
bool binary_search (ForwardIterator, ForwardIterator, T, Compare)
OutputIterator copy (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 copy_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
OutputIterator copy_if (InputIterator, InputIterator, OutputIterator, Predicate)
OutputIterator copy_n (InputIterator, Size, OutputIterator)
difference_type count (InputIterator, InputIterator, T)
difference_type count_if (InputIterator, InputIterator, Predicate)
bool equal (InputIterator1, InputIterator1, InputIterator2)
bool equal (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate)
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator, ForwardIterator, T)
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator, ForwardIterator, T, Compare)
void fill (ForwardIterator, ForwardIterator, T)
OutputIterator fill_n (OutputIterator, Size, T)
InputIterator find (InputIterator, InputIterator, T)
ForwardIterator1 find_end (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2)
ForwardIterator1 find_end (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate)
InputIterator find_first_of (InputIterator, InputIterator, ForwardIterator, ForwardIterator)
InputIterator find_first_of (InputIterator, InputIterator, ForwardIterator, ForwardIterator, BinaryPredicate)
InputIterator find_if (InputIterator, InputIterator, Predicate)
InputIterator find_if_not (InputIterator, InputIterator, Predicate)
Function for_each (InputIterator, InputIterator, Function)
void generate (ForwardIterator, ForwardIterator, Generator)
OutputIterator generate_n (OutputIterator, Size, Generator)
bool includes (InputIterator1, InputIterator1, InputIterator2, InputIterator2)
bool includes (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2)
void inplace_merge (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator)
void inplace_merge (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator, Compare)
void iota (ForwardIterator, ForwardIterator, T)
bool is_heap (RandomAccessIterator, RandomAccessIterator)
bool is_heap (RandomAccessIterator, RandomAccessIterator, Compare)
RandomAccessIterator is_heap_until (RandomAccessIterator, RandomAccessIterator)
RandomAccessIterator is_heap_until (RandomAccessIterator, RandomAccessIterator, Compare)
bool is_partitioned (InputIterator, InputIterator, Predicate)
bool is_permutation (ForwardIterator1, ForwardIterator1, ForwardIterator2)
bool is_permutation (ForwardIterator1, ForwardIterator1, ForwardIterator2, BinaryPredicate)
bool is_sorted (ForwardIterator, ForwardIterator)
bool is_sorted (ForwardIterator, ForwardIterator, Compare)
bool is_sorted_until (ForwardIterator, ForwardIterator)
bool is_sorted_until (ForwardIterator, ForwardIterator, Compare)
void iter_swap (ForwardIterator1, ForwardIterator2)
bool lexicographical_compare (InputIterator1, InputIterator1, InputIterator2, InputIterator2)
bool lexicographical_compare (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
ForwardIterator lower_bound (ForwardIterator, ForwardIterator, T)
ForwardIterator lower_bound (ForwardIterator, ForwardIterator, T, Compare)
void make_heap (RandomAccessIterator, RandomAccessIterator)
void make_heap (RandomAccessIterator, RandomAccessIterator, Compare)
const T& max (T, T)
const T& max (T, T, Compare)
T max (InitializerList)
T max (InitializerList, Compare)
ForwardIterator max_element (ForwardIterator, ForwardIterator)
ForwardIterator max_element (ForwardIterator, ForwardIterator, Compare)
OutputIterator merge (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator merge (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
const T& min (T, T)
const T& min (T, T, Compare)
T min (InitializerList)
T min (InitializerList, Compare)
ForwardIterator min_element (ForwardIterator, ForwardIterator)
ForwardIterator min_element (ForwardIterator, ForwardIterator, Compare)
pair<const T&, const T&> minmax (T, T)
pair<const T&, const T&> minmax (T, T, Compare)
pair<T, T> minmax (InitializerList)
pair<T, T> minmax (InitializerList, Compare)
pair<ForwardIterator, ForwardIterator> minmax_element (ForwardIterator, ForwardIterator)
pair<ForwardIterator, ForwardIterator> minmax_element (ForwardIterator, ForwardIterator, Compare)
pair<InputIterator1, InputIterator2> mismatch (InputIterator1, InputIterator1, InputIterator2)
pair<InputIterator1, InputIterator2> mismatch (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate)
OutputIterator move (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 move_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
bool next_permutation (BidirectionalIterator, BidirectionalIterator)
bool next_permutation (BidirectionalIterator, BidirectionalIterator, Compare)
bool none_of (InputIterator, InputIterator, Predicate)
void nth_element (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator)
void nth_element (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare)
void partial_sort (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator)
void partial_sort (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare)
RandomAccessIterator partial_sort_copy (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator)
RandomAccessIterator partial_sort_copy (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator, Compare)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator, BinaryOperation)
ForwardIterator partition (ForwardIterator, ForwardIterator, Predicate)
pair<OutputIterator1, OutputIterator2> partition_copy (InputIterator, InputIterator, OutputIterator1, OutputIterator2, Predicate)
ForwardIterator partition_point (ForwardIterator, ForwardIterator, Predicate)
void pop_heap (RandomAccessIterator, RandomAccessIterator)
void pop_heap (RandomAccessIterator, RandomAccessIterator, Compare)
bool prev_permutation (BidirectionalIterator, BidirectionalIterator)
bool prev_permutation (BidirectionalIterator, BidirectionalIterator, Compare)
void push_heap (RandomAccessIterator, RandomAccessIterator)
void push_heap (RandomAccessIterator, RandomAccessIterator, Compare)
void random_shuffle (RandomAccessIterator, RandomAccessIterator)
void random_shuffle (RandomAccessIterator, RandomAccessIterator, RandomNumberGeneratorenerator)
ForwardIterator remove (ForwardIterator, ForwardIterator, T)
OutputIterator remove_copy (InputIterator, InputIterator, OutputIterator, T)
OutputIterator remove_copy_if (InputIterator, InputIterator, OutputIterator, Predicate)
ForwardIterator remove_if (ForwardIterator, ForwardIterator, Predicate)
void replace (ForwardIterator, ForwardIterator, T, T)
OutputIterator replace_copy (InputIterator, InputIterator, OutputIterator, T, T)
OutputIterator replace_copy_if (InputIterator, InputIterator, OutputIterator, Predicate, T)
void replace_if (ForwardIterator, ForwardIterator, Predicate, T)
void reverse (BidirectionalIterator, BidirectionalIterator)
OutputIterator reverse_copy (BidirectionalIterator, BidirectionalIterator, OutputIterator)
ForwardIterator rotate (ForwardIterator, ForwardIterator, ForwardIterator)
OutputIterator rotate_copy (ForwardIterator, ForwardIterator, ForwardIterator, OutputIterator)
ForwardIterator1 search (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2)
ForwardIterator1 search (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate)
ForwardIterator search_n (ForwardIterator, ForwardIterator, Size, T)
ForwardIterator search_n (ForwardIterator, ForwardIterator, Size, T, BinaryPredicate)
OutputIterator set_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_intersection (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_intersection (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_symmetric_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_symmetric_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_union (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_union (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
void shuffle (RandomAccessIterator, RandomAccessIterator, URandomNumberGeneratorenerator)
void sort (RandomAccessIterator, RandomAccessIterator)
void sort (RandomAccessIterator, RandomAccessIterator, Compare)
void sort_heap (RandomAccessIterator, RandomAccessIterator)
void sort_heap (RandomAccessIterator, RandomAccessIterator, Compare)
BidirectionalIterator stable_partition (BidirectionalIterator, BidirectionalIterator, Predicate)
void stable_sort (RandomAccessIterator, RandomAccessIterator)
void stable_sort (RandomAccessIterator, RandomAccessIterator, Compare)
ForwardIterator2 swap_ranges (ForwardIterator1, ForwardIterator1, ForwardIterator2)
OutputIterator transform (InputIterator, InputIterator, OutputIterator, UnaryOperation)
OutputIterator transform (InputIterator1, InputIterator1, InputIterator2, OutputIterator, UnaryOperation)
ForwardIterator unique (ForwardIterator, ForwardIterator)
ForwardIterator unique (ForwardIterator, ForwardIterator, BinaryPredicate)
OutputIterator unique_copy (InputIterator, InputIterator, OutputIterator)
OutputIterator unique_copy (InputIterator, InputIterator, OutputIterator, BinaryPredicate)
ForwardIterator upper_bound (ForwardIterator, ForwardIterator, T)
ForwardIterator upper_bound (ForwardIterator, ForwardIterator, T, Compare)

The standard already classifies the algorithms in various ways – e.g. those included in the header <algorithm> vs. the header <numeric> or mutating vs. non-mutating algorithms. I am sure that we can find some more classifications that are interesting.

Our first classification will be a simple one – algorithms that guarantee that the input elements will be operated on in a particular order vs. algorithms that do not make that guarantee. Actually, this ended up not being as simple as I thought which makes it even more instructive.

All we need to do is search the standard for the phrases “and proceeding to” and “in order”. It turns out that there are 13 algorithms that guarantee their order of operation:

T accumulate (InputIterator, InputIterator, T)
T accumulate (InputIterator, InputIterator, T, BinaryOperation)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator, BinaryOperation)
OutputIterator copy (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 copy_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
Function for_each (InputIterator, InputIterator, Function)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2)
OutputIterator move (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 move_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator, BinaryOperation)

[ Edit: I should have included std::iota in this list. See my follow-up post. ]

No other algorithms guarantee the operation order. Of course there are some algorithms where we wouldn’t expect a guaranteed order – we want std::lower_bound to use whatever order is most efficient. What about an algorithm like std::find though? Since that returns the first occurrence of a value surely it must access its input range from beginning to end. The standard does not guarantee it. I can’t think of a sensible algorithm that would do anything other than go from begin to end (unless we get into parallelism which opens up another can of worms), but the standard does not specifically make that guarantee.

Here’s another example that does not guarantee the operation order – std::transform. At first glance, that seems to make sense. Take this example: 

std::vector< int > v0( { 1, 2, 3, 4, 5 } );
std::vector< int > v1( 5 );

std::transform( 
    std::begin( v0 ), 
    std::end( v0 ), 
    std::begin( v1 ), 
    []( int i )
{
    return i + 1;
} );

There are five results, each of which is computed entirely independently of the others. We know that the operation supplied to std::transform should not have any side effects so it doesn’t matter what order the results are computed in, they might even be computed in parallel. It doesn’t matter whether the result in position [0] is written before or after the result in position [1] (the results have to be written to the correct position but they don’t have to be written in a particular order).

Now let’s change the problem slightly. In this case we won’t pre-allocate the output vector and we’ll use std::back_inserter: 

std::vector< int > v0( { 1, 2, 3, 4, 5 } );
std::vector< int > v1;

std::transform( 
    std::begin( v0 ), 
    std::end( v0 ), 
    std::back_inserter( v1 ), 
    []( int i )
{
    return i + 1;
} );

Now it matters what order the results are written in – the order they are written in defines the position they are written to. Doesn’t this conflict with the lack of guarantee about the order of computation?

Given that std::back_inserter is a common idiom it’s obvious that the answer to the previous question is “no, there is no conflict”. It isn’t so obvious why there is no conflict.

Let’s go back to the first example I showed: 

std::vector< int > v0( { 1, 2, 3, 4, 5 } );
std::vector< int > v1( 5 );

std::transform( 
    std::begin( v0 ), 
    std::end( v0 ), 
    std::begin( v1 ), 
    []( int i )
{
    return i + 1;
} );

and the declaration of the single input range version of std::transform:

OutputIterator transform (InputIterator, InputIterator, OutputIterator, UnaryOperation)

My example is using std::vector – that gives us random access iterators that let us jump around all over the place. If you look at the declaration of std::transform though, it will work with input and output iterators. Input and output iterators do not allow random access – they don’t even allow you to iterate over the same range twice. Even though the algorithm will allow arbitrary access, the iterators don’t.

A quick look at the standard tells us that std::back_inserter returns std::back_insert_iterator which is an output iterator. If the destination of a std::transform call is an output iterator, the results must be written in the correct order. Internally they can still be calculated in any order (possible, even with input iterators, but unlikely to be efficient), but they must be written in the correct order.

So it is possible for a standard-conforming std::transform implementation to access the input elements in different orders depending on the type of iterators being used. There is definitely precedent for different algorithm implementations being used for different iterator types. Microsoft’s Stephan T. Lavavej demonstrates how template metaprogramnming can achieve this here.

However, in practice, I have never come across an implementation of std::transform that does anything other than iterate from beginning to end and I don’t expect to – at least not under the name std::transform. When I have been working with parallel code the parallelism has always been explicitly called out – I really don’t want the STL kicking off separate threads unless I tell it to. Intel’s TBB contains several explicitly parallel algorithms, but they all have the word “parallel” in their names.

In conclusion, I started off with what I though was going to be a simple classification. I went through a phase where I thought that it wasn’t so simple after all, then finally ended up at the simple place I started at – but perhaps a little wiser. I haven’t been able to find a lot of information about the access order of algorithms online, but I do recommend this 2001 DDJ article on the subject.