4 ms·

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 ma

by exDM69 13y 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.

humanrebar 13y 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.
- sixbrx 13y 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.
  - humanrebar 13y ago
    You can guarantee the heap will not be touched in any code that: - does not use malloc or new - does not call any function that uses malloc or new When you do that, you make allocation decisions orthogonal to the algorithm. This is how all the std algorithms are implemented. Haskell also separates allocation from algorithm, but it so by making decisions for the programmer -- by using GC. This is not an acceptable trade-off for a C++ developer or else she would be using a different language (or smart pointers).
    - sixbrx 13y ago
      > You can guarantee the heap will not be touched in any code > that: - does not use malloc or new - does not call any > function that uses malloc or new Which is extremely limiting, in the context of data analysis chains like the examples given.
      - humanrebar 13y ago
        No it isn't. You just need C++ libraries that do data analysis chains in a similar way. There are examples elsewhere in the comments here.
- exDM69 13y 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.
  - bronxbomber92 13y ago
    Luckily functions from <algorithm> don't only work with STL containers; they work with any class that adheres to the STL containers interfaces.
  - humanrebar 13y ago
    > But this example does not require any allocation space at all. That's not possible if you're comparing algorithms apples-to-apples. If you have an intermediate collection, it's in memory somewhere, even if the language does the allocation for you transparently.
    - exDM69 13y ago
      > If you have an intermediate collection, it's in memory somewhere, even if the language does the allocation for you transparently. This toy example algorithm, and many practical algorithms, do not need an intermediate collection to be stored in memory. Using some kind of laziness, you only need exactly one temporary element, not the whole collection. You can make this happen not only in Haskell but also using Python generators, Clojure lazy sequences or even in C++ using Folly. The lack of means of composition, the inability to pipe the output of one algorithm as the input of another, is in my opinion the greatest shortcoming of C++ <algorithm>.
nhaehnle 13y 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.
- humanrebar 13y 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.

by exDM69 13y ago

humanrebar 13y 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.

sixbrx 13y 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.
- humanrebar 13y ago
  You can guarantee the heap will not be touched in any code that: - does not use malloc or new - does not call any function that uses malloc or new When you do that, you make allocation decisions orthogonal to the algorithm. This is how all the std algorithms are implemented. Haskell also separates allocation from algorithm, but it so by making decisions for the programmer -- by using GC. This is not an acceptable trade-off for a C++ developer or else she would be using a different language (or smart pointers).
  - sixbrx 13y ago
    > You can guarantee the heap will not be touched in any code > that: - does not use malloc or new - does not call any > function that uses malloc or new Which is extremely limiting, in the context of data analysis chains like the examples given.
    - humanrebar 13y ago
      No it isn't. You just need C++ libraries that do data analysis chains in a similar way. There are examples elsewhere in the comments here.
exDM69 13y 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.
- bronxbomber92 13y ago
  Luckily functions from <algorithm> don't only work with STL containers; they work with any class that adheres to the STL containers interfaces.
- humanrebar 13y ago
  > But this example does not require any allocation space at all. That's not possible if you're comparing algorithms apples-to-apples. If you have an intermediate collection, it's in memory somewhere, even if the language does the allocation for you transparently.
  - exDM69 13y ago
    > If you have an intermediate collection, it's in memory somewhere, even if the language does the allocation for you transparently. This toy example algorithm, and many practical algorithms, do not need an intermediate collection to be stored in memory. Using some kind of laziness, you only need exactly one temporary element, not the whole collection. You can make this happen not only in Haskell but also using Python generators, Clojure lazy sequences or even in C++ using Folly. The lack of means of composition, the inability to pipe the output of one algorithm as the input of another, is in my opinion the greatest shortcoming of C++ <algorithm>.

nhaehnle 13y 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.

humanrebar 13y 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.