C++ – From goto to std::transform

https://github.com/Dobiasd/articles/blob/master/from_goto_to_std-transform.md

by jlemoine • 12 years ago

88 91 12 years ago

stormbrew6• 12 years ago

C++ is evolving at a kind of breakneck pace lately, and it's already a lot different from the language it used to be. Auto, range loops, and lambdas are making it much more pleasant to work in while still maintaining a lot of performance advantages.

I know it's pretty popular to hate on C++, but I'm pretty excited about where it's going, personally.

spoiler2• 12 years ago

I've recently started working in C++ (I've had some prior knowledge, but mostly basics) and whenever I try to Google stuff up, a few of the results are Don't use C++ because of X

I read a few of them out of curiosity, and realised that they are mostly religious reasons to hate C++, hardly any of them are proper, factual, or empirical reasons. So, my hypothesis is the following: They were unable to learn C++, and because of immaturity, decided it was stupid[0][1].

[0]: I'm no saint to this. I said on numerous occasions Erlang is shit because I couldn't wrap my head around the syntax.

[1]: I believe it's a phenomenon associated with Psychological Projection, but I might've confused it with something else.

lucian1900• 12 years ago

There are good arguments against C++, but they resume to its extreme complexity and lack of extra safety compared to C. Both are fair points and why I avoid it.

k00pa• 12 years ago

I have seen people giving up on C++ without actually even trying to learn it.

Somehow all these pointers are "scary" and "hard". And people are usually trying to learn C++ the wrong way. (Lets download this big library/framework and figure out by doing)

TillE• 12 years ago

C++ isn't the easiest language to work with, but what I find truly bizarre are all the internet people who apparently hate C++ while also praising C as wonderful and "elegant". I'm convinced that the vast majority of them have never written anything significant in C, which is a painful experience tolerated only by systems programmers who actually need something that's one step above a portable assembly language.

C++ only fails if you try to write it like C, and don't take advantage of all the lovely new tools it gives you. It's always been a more useful language for nontrivial projects, and C++11 elevates it so much further.

mattgreenrocks• 12 years ago

Most Internet hivemind (euphemistically called "conventional wisdom") behavior is more about belonging and less about discussing truth. It's similar to the rants about Perl's ugliness: it's up to the programmer to make it readable.

C++ can be a perilous language, but it affords a surprising amount of expressive power with a very low performance overhead. It requires you to be focused and think clearly about things like object lifetimes. It rewards thinking hard ahead of time to simply jumping in, writing code, and debugging it until it works.

crawshaw• 12 years ago

Readability improved from squareVec1 to squareVec4, then went downhill. Hiding loops behind new names doesn't make programming better.

rootlocus• 12 years ago

It does if you're familiar with the common high-order functions used in functional programming.

forrestthewoods• 12 years ago

If you are familiar with both C++ and common high-order functions used in functional programming I still think that squareVec4 is, by leaps and bounds, the most readable.

squareVec4 is simple, concise, and leaves little to no room for ambiguity. squareVec6 is a monstrosity that requires reading more text that contains more complicated ascii and involves more concepts.

And for the author to then claim that making use of "cool stuff" in <algorithm> is more maintainable code? That's just crazy talk man!

nly5• 12 years ago

At Going Native last year Sean Parent, from Adobe, gave a superb talk called 'C++ Seasoning' where his number one pro-tip for C++ was: no raw loops.

He made a good case that anywhere you have a non-trivial loop in C++, you're almost always going to be better off folding the problem in to a composition of algorithms. The code got more readable, more performant, and redundant code can often be removed.

Please take an hour to watch it here in glorious high quality:

http://channel9.msdn.com/Events/GoingNative/2013/Cpp-Seasoni...

agumonkey3• 12 years ago

And if someone has nothing better to do, may I suggest to watch anything by Sean Parent. Some old adobe talks might be in low-res, but they were still very interesting, on the abstraction side of things.

notacoward• 12 years ago

My thoughts exactly. It's simply not true that "everybody knows without thinking" what the std::accumulate version will do. It's specific not only to a particular pattern but to the expression of that pattern in a particular language. People new to C++ won't be able to parse "[](vector<int> acc" right away, and it's key to understanding the whole. By contrast, the range-based for loop is obvious even to a C++ novice and easily guessable even by those who don't know C++.

If you want something that's both concise and readable, try the Python list-comprehension version. That is an elegant solution. The C++ accumulate/transform solutions are the very opposite of elegant. In a code review, I would flag them as obfuscatory.

pathikrit• 12 years ago

After coding in languages in like Scala/Python for a while, it took me a while to parse this. Scala equivalent: `def square(a: List[Int]) = a map {i => i*i}`

douglasheriot• 12 years ago

After in coding in languages like C/C++/ObjC for a while, it took me a while to parse your Scale equivalent.

Personally I find the C++ much clearer – I don’t see either as that much better/worse.

heliumcraft2• 12 years ago

  def square(vector)
    vector.collect { |i| i**2 }
  end

adamnemecek• 12 years ago

Cool, it will also be probably 30x slower.

ICWiener2• 12 years ago

Does speed really matter? I still prefer the readable Lisp version (SBCL, no optimization):

  (defun square-vect (vect)
    (map 'vector (lambda (x) (* x x)) vect))

  (setq *vector*
        (map 'vector (lambda (x) (random 32767))
             (make-array 10000 :element-type 'integer)))

  (time
   (dotimes (i 1000)
     (square-vect *vector*)))

Results :

  0.084 seconds of real time
  0.084005 seconds of total run time (0.084005 user, 0.000000 system)
  100.00% CPU
  218,686,836 processor cycles
  79,876,912 bytes consed

On my system, the C++ version perform like this:

   ./main 1
   1: 270756377 - elapsed time: 0.022324s
   ~$ ./main 2
   2: 270756377 - elapsed time: 0.018883s
   ~$ ./main 3
   3: 270756377 - elapsed time: 0.016929s
   ~$ ./main 4
   4: 270756377 - elapsed time: 0.014268s
   ~$ ./main 5
   5: 270756377 - elapsed time: 0.016093s
   ~$ ./main 6
   6: 270756377 - elapsed time: 0.018651s
   ~$ ./main 7 # :-)
   7: -1455582645 - elapsed time: 5.3e-05s

heliumcraft2• 12 years ago

Likely not that much slower. I rather have slightly slower code that is easy to develop & maintain, than code that is fast but hard to read, hard to maintain and easy to introduce bugs in to.

spoiler2• 12 years ago

Y not map.

ptr2• 12 years ago

collect and map are the same thing, just different names. IIRC, collect was the name used in Smalltalk for map operations.

milliams• 12 years ago

I like the Python version of:

  def square(vector):
    return [v**2 for v in vector]

ptr2• 12 years ago

Haskell:

  let square = map (^ 2)

Real partial application and currying is something I'm longing for in other languages; it's easy to fall for the beauty of the Point Free Style.

cousin_it• 12 years ago

Or SQL:

    SELECT x*x FROM vector;

There's just so many things that SQL got right:

- Non-programmers actually read and modify SQL code. I swear, it happens. It doesn't happen very much even with Python, and it will never happen with C++.

- It can join multiple data structures in a single query, on arbitrary criteria.

- A query can be optimized as a whole. Optimizers freely reorder the parts and actually come up with good plans.

- The presence or absence of indexes (data structures used for acceleration) is transparent to the query. Can any other language do that?

A lot of the code I've seen would be 10x to 100x smaller if expressed in SQL, or an SQL-like language that can handle nested data structures (which is something that I really want).

enricosada• 12 years ago

f# multiple implementations (comprension, partial, parallel)

  //array comprehension
  let squareVec vector = [| for x in vector -> x ** 2.0 |]
  squareVec [| 1.0; 2.0; 3.0 |]
  [| 1.0; 2.0; 3.0 |] |> squareVec

  //inline function
  [| 1;2;3 |] |> Array.map (fun x -> x * x)

  //extract function
  let square x = x * x
  [| 1;2;3 |] |> Array.map square

  //partial
  let squareVec3 = Array.map square
  [| 1;2;3 |] |> squareVec3

  //partial
  let pow x y = y ** x
  [| 1.0; 2.0; 3.0 |] |> Array.map (pow 2.0)
 
  //parallel
  [| 1.0; 2.0; 3.0 |] |> Array.Parallel.map (pow 2.0)

  //can use SIMD on mono (next version on .NET too)
  //no first hand experience, but can also use GPU from F#

Jare2• 12 years ago

Convenience overloads for common use cases (iterating over the full vector, accumulating on a default-constructed accumulator, etc) would be great to have as standard. Are there and I have missed them? If not, what's the rationale? (this goes for the STL in general, not specifically these high order algos)

Negitivefrags• 12 years ago

Here is a blog post on this very issue:

http://herbsutter.com/2011/10/07/why-no-container-based-algo...

humanrebar8• 12 years ago

That's a valid technical reason why there isn't a std::sort that takes containers. It's not a valid reason why there can't be a std::range_sort or std::range::sort that takes container arguments.

shultays• 12 years ago

  but you still have to read the whole line

Oh the pain!

ajtulloch• 12 years ago

Using Facebook's `folly::gen` library [1], you can get it down to:

    vector<int> squareVec3(const vector<int>& v) {
      return from(v) | mapped([](int i){ return i * i; }) | as<vector>();
    }

which is pretty slick. There are a bunch of the usual LINQ/functional operators in `folly::gen` that are quite nice. As an example, to filter out the odd elements of `v`, you can do

    vector<int> squareVecFiltered(const vector<int>& v) {
      return from(v) 
           | filter([](int i){ return i % 2 == 0; })
           | mapped([](int i){ return i * i; })  
           | as<vector>();
    }

https://github.com/facebook/folly/tree/master/folly/gen

humanrebar8• 12 years ago

That's cool, but I'd rather not bitwise-or my functional operators together. Something like this would be better:

    vector<int> squareVecFiltered(const vector<int>& v) {
      return from(v
           filter([](int i){ return i % 2 == 0; }),
           mapped([](int i){ return i * i; }),
           as<vector>());
    }

stormbrew6• 12 years ago

That is actually really nice.

pfultz2• 12 years ago

Or using [Linq](https://github.com/pfultz2/Linq):

    vector<int> squareVec(const vector<int>& v)
    {
        return LINQ(from(i, v) select(i*i)) | linq::to_container;
    }

And also filtering out odd elements:

    vector<int> squareVecFiltered(const vector<int>& v)
    {
        return LINQ(from(i, v) where(i % 2 == 0) select(i*i)) | linq::to_container;
    }

jeorgun• 12 years ago

I'm not really sure why references are being used here, if you're just making a copy straight-away.

    vector<int> square(vector<int> vcopy)
    {
        for (int &i : vcopy)
            i *= i;
        return vcopy;
    }

is shorter, (IMO) much more readable, and on my tests, measurably faster than the reference version. If you really want the std::accumulate version,

    vector<int> square(vector<int> vcopy)
    {
        accumulate(begin(vcopy), end(vcopy), begin(vcopy),
                   [](int i) { return i * i; });
        return vcopy;
    }

works just as well.

Still, I guess it's beside the point.

humanrebar8• 12 years ago

I like your version better, but I suspect it would be significantly slower for many compilers that you are not testing.

Dobiasd2• 12 years ago

Awesome! It is more readable and makes it faster. Thank you very much. I changed my article accordingly.

Marat_Dukhan• 12 years ago

The author probably thinks that all versions are equally fast, but in fact they are just equally slow. Neither gcc 4.8 nor icc 14 can use vectorization for this loop (likely because of aliasing).

pbsd• 12 years ago

It's not because of aliasing, it's because of the push_back call inside the inner loop, which may potentially have to allocate (in this case we know it doesn't, but the compiler does not). If you replace squareVec6 with

    vector<int> squareVec6(const vector<int>& v)
    {
        vector<int> result(v.size()); // preallocate
        // result.reserve(v.size());
        transform(begin(v), end(v), begin(result), [](int i)
        {
            return i*i;
        });
        return result;
    }

the compiler will be happy to vectorize the loop.

exDM693• 12 years ago

What I find painful about writing pseudo-functional C++ using <algorithm> and other tricks is that you have to allocate storage for intermediate values. This makes C++ algorithms a lot less composable than similar things in other languages.

So if I wanted to do something like (in Haskell):

    sumOfOddSquares xs = sum . map (^2) . filter odd $ xs

In C++, I would need to allocate temporary storage for the intermediate values.

    std::vector odd_numbers;
    std::copy_if(xs.begin(), xs.end(), back_inserter(odd_numbers), isOdd);
    std::transform(odd_numbers.begin(), odd_numbers.end(), odd_numbers.begin(), square);
    std::accumulate(odd_numbers.begin(), odd_numbers.end(), 0, plus);

This becomes quite painful very quickly. You can use solutions like boost::filter_iterator, but soon you're knee deep in C++ templates and the long compile times and awful error messages that follow.

The example above is a bit contrived since it can be easily be done with a single accumulate, but you get the idea...

    std::accumulate(xs.begin(), xs.end(), 0,
        [](int sum, int i) { return sum + ((i&1) ? i*i : 0); });

So while you can have lots of fun with <algorithm>, it's quite limited in what it can do.

humanrebar8• 12 years ago

On the other hand, C++ has more flexibility. Since C++ allows you to specify your allocation scheme, you can guarantee a piece of code will never trigger an allocation, allocate in a special way to ensure cache coherence, etc.

For example, you could have written equivalent logic that allocates odd_numbers on the stack or from a special memory pool.

Sure, application developers shouldn't care about that kind of fine-grained control. However, they should care about having fast, small, safe, and high-quality libraries available. For library authors and developers in special domains (high-performance, safety-critical, etc.), these tools are essential.

sixbrx2• 12 years ago

you can guarantee a piece of code will never trigger an allocation

I'd be interested to see an example of this, if possible, say, with an application of flatMap and filtering in a chain or something similar (or just exDM69's example), without pre-scanning the collection.

I think C++ does really well when memory needs are known or can be bounded to something reasonable up front, but not as well as a good high performance GC when many temporary allocations need to be made where their size can't be known until runtime. I would love to be wrong about that though, the language has a lot going for it.

exDM693• 12 years ago

On the other hand, C++ has more flexibility. Since C++ allows you to specify your allocation scheme, you can guarantee a piece of code will never trigger an allocation, allocate in a special way to ensure cache coherence, etc.

This is true but the way C++ standard containers work with allocators is rather clumsy. So clumsy that often when custom allocation logic is required, standard containers are not used at all and custom containers are built instead. For example, EA has used a custom STL-esque container library to avoid memory allocation pressure in console and PC games.

For example, you could have written equivalent logic that allocates odd_numbers on the stack or from a special memory pool.

But this example does not require any allocation space at all. But there's no way of doing this with standard C++ algorithms without allocating additional space.

nhaehnle• 12 years ago

This is indeed painful. However, with C++11's move semantics, I suspect libraries will over time develop in ways that make this less painful. See nly's comment for an example.

humanrebar8• 12 years ago

It's mostly painful because of all the iterator pairs, not because of the allocation.

Though I agree that better libraries could clean this sort of trivial transformation up immensely.

nly5• 12 years ago

<algorithm> is so 90s. In C++14 you'll be able to do this:

    auto square_copy = [](auto v) {
       for (auto& e: v) { e *= e; }
       return v;
    };

Another option:

    auto square = [](auto& v) { v *= v; };

    auto map = [](auto range, auto fun) {
        transform (begin(range), end(range), fun); 
        return range;
    };

    vector<int> vec = {1,2,3,4,5,6};
    auto squared = map (vec, square);

Note that, in both of these cases, if you use std::move() to gift a container to these functions, they will not actually allocate any memory and will effectively operate in-place.

stormbrew6• 12 years ago

Am I missing something? I don't see anything beyond C++11 in here.

nly5• 12 years ago

Parameters can't be auto in C++11. Polymorphic lambdas are a C++14 feature.

Incidentally, are you Stormhawk on Freenodes #C++ ?

ww2• 12 years ago

The example is too trivial. you could have 100 ways to write "hello world", but it does not matter.

vinkelhake• 12 years ago

Just as a side note: if you're looking to write a convenience wrapper like the author's transformVec, do not have it take the function as `const function<T(T)>&`. Instead, do something like:

    template <typename T, typename F>
    vector<T> transformVec(const vector<T>& v, F op)

Using std::function in a case where you just want something callable just makes the optimizer's job a lot harder. Using std::function is a good idea if you actually need type erasure (for example if you want to pass something callable to a function that is not a template).

Dobiasd2• 12 years ago

Wow, awesome tip, thanks. This makes the wrapped version as fast as the others. I updated my article accordingly.

u124556• 12 years ago

`result = [i * i for i in v]` looks much more readable to me.

What if you need to square every other element? copy_if and transform then don't look so pretty anymore. `result = [i * i for i in v if i % 2 == 0]` is still more readable.

What if you need to do something else and you don't know if there is a transform like function for it?

alecbenzer• 12 years ago

What if you need to do something else and you don't know if there is a transform like function for it?

What about the same thing in python? As far as I know the two examples you gave exhausted list comprehensions' functionality.

geocar• 12 years ago

It seems like it's the loop itself that is redundant. Why couldn't I just do:

    squaredVec = vec * vec

    squaredVec = vec ^ 2

bstamour• 12 years ago

You can, but not with vector. Use valarray if you need to perform those kinds of computations.

GFK_of_xmaspast3• 12 years ago

Why were all the examples using iterators, and not square bracket indexing?

mytummyhertz• 12 years ago

am i the only one who thinks the std::transform version is LESS readable than the for loop?

C++ – From goto to std::transform

Related Stories