C++ – From goto to std::transform
github.com
github.com
So if I wanted to do something like (in Haskell):
sumOfOddSquares xs = sum . map (^2) . filter odd $ xs
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);
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); });
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.
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.
- 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).
Which is extremely limiting, in the context of data analysis chains like the examples given.
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.
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.
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>.
Though I agree that better libraries could clean this sort of trivial transformation up immensely.
auto square_copy = [](auto v) {
for (auto& e: v) { e *= e; }
return v;
};
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);
Incidentally, are you Stormhawk on Freenodes #C++ ?
And nope, that's not me. I go by stormbrew on freenode as well and haven't been in a C++ focused channel since the late 90s on efnet. :)
vector<int> squareVec3(const vector<int>& v) {
return from(v) | mapped([](int i){ return i * i; }) | as<vector>();
}
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>();
}
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>());
} vector<int> squareVec(const vector<int>& v)
{
return LINQ(from(i, v) select(i*i)) | linq::to_container;
}
vector<int> squareVecFiltered(const vector<int>& v)
{
return LINQ(from(i, v) where(i % 2 == 0) select(i*i)) | linq::to_container;
}I know it's pretty popular to hate on C++, but I'm pretty excited about where it's going, personally.
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.
However the C unsafety is still present due to the compatibility compromises with C in C++'s design.
With teams it is very hard to control what each developer makes use of, even with static analysis.
For the other type of enterprise projects I rather use languages that follow Algol linage of memory safety.
When you do use pointers, we finally have a real null pointer literal now. (I believe the latest C spec has also received this.)
C++ is certainly crufty. The language has been around for a long time and many features in the specification exist to support legacy code. This is a side effect of being a living language with a huge user base.
Modern C++ tends to be fairly clean and reasonably easy to work in. Herb Sutter has some great talks and blog articles around the topic. For example: http://channel9.msdn.com/Events/Build/2014/2-661
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)
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.
Which incidentally also affect Objective-C for the same reasons.
Is it really necessary to start another language war thread?
Sincerely, a happy C developer.
Just stating the fact that when someone posts "C++ is horrible because of X", that X is either also available in "ANSI C", caused by compatibility with C semantics or compatibility with C toolchain.
The newest additions to C++ for functional programming and automatic typing are quite intriguing. Blaming everything wrong with C++ on C is as disingenuous as labeling everything about C++ as wrong because one thing about it is wrong.
I also mentioned compatibility with C semantics.
"The Design and Evolution of C++" contains lots of such examples.
There's also the issue that iostreams might be implemented on top of stdio for simplicity. Hard to make it faster in that case!
It's not that it's too heavy for a console app's output, really, but for things like converting numbers to strings and vice-versa (a-la boost::format) it is definitely a lot slower than atoi/sprintf.
C++ code tends also to have a lot of allocations and data copying going on. I know you can get around those, but it seems like C++ programmers don't.
C++ looks nicer at first sight, but when you want to make sure error handling is correct, there's practically little advantage compared to C. Sure, C++ does have STL, but programmers still seem to occasionally allocate function stack and return a pointer to it and manage to do buffer overflows.
C has much simpler flow of execution. C++ exceptions mean there are eventually a lot of different possible code execution paths. In C, flow of execution is almost always simple and predictable.
C++ invites style where logic is spread over many layers of abstraction. It's often hard to see the whole picture of what's going on because of that. Instead you have to check all those constructors, destructors, watch out for inheritance, etc. In C, most related logic tends to be in same source file.
A lot of bugs I've seen in legacy code are related to these issues.
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.
vector<int> square(vector<int> vcopy)
{
for (int &i : vcopy)
i *= i;
return vcopy;
}
vector<int> square(vector<int> vcopy)
{
accumulate(begin(vcopy), end(vcopy), begin(vcopy),
[](int i) { return i * i; });
return vcopy;
}
Still, I guess it's beside the point.
Personally I find the C++ much clearer – I don’t see either as that much better/worse.
http://herbsutter.com/2011/10/07/why-no-container-based-algo...
I was ok with that low level, low semantics design in the STL until I heard that stuff about integrating a graphics library. Now I'm just confused. :)
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!
return v.fold([], def (acc, i) { acc.push(i*i) });
return v.map(def(i) { i * i })
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...
A Possible Future of Software Development : www.youtube.com/watch?v=4moyKUHApq4
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.
template <typename T, typename F>
vector<T> transformVec(const vector<T>& v, F op)
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;
}
def square(vector)
vector.collect { |i| i**2 }
end (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*)))
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
./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-05sYes. C++ is chosen by developers who tend to choose performance over elegance.
When I was doing a lot more C++, I was intimately aware of the deep performance implications of choosing one data type and implementation technique over another.
C++ is viewed as the ultimate language when it comes to performance, for good reasons; of course, if I ever need a fast program, I will consider it.
But as an exercise, why not try to optimize the CL code, first?
By using type declarations and avoiding allocating memory, here is an optimized CL version that runs under 0.01s, beating the C++ code (note that the original C++ code could be optimized too; e.g. why check the command-line argument every time?).
(defpackage :test (:use :cl))
(in-package :test)
(defconstant +vector+
(map '(simple-array fixnum (10000))
(lambda (x) (declare (ignorable x)) (random 32767))
(make-array 10000 :element-type 'fixnum)))
(let ((result (make-array 10000 :element-type 'fixnum)))
(declare (type (simple-array fixnum (10000)) result))
(flet ((square (x)
(declare (optimize (speed 3) (safety 0) (debug 0))
(fixnum x))
(the fixnum (* x x))))
(defun square-vect ()
(declare (optimize (speed 3) (safety 0) (debug 0))
(type (simple-array fixnum (10000)) +vector+))
(loop for i from 0 to 9999
do (setf (aref result i) (square (aref +vector+ i))))
result)))
(time
(dotimes (i 1000)
(square-vect)))
Evaluation took:
0.009 seconds of real time
0.008000 seconds of total run time (0.008000 user, 0.000000 system)
88.89% CPU
22,650,364 processor cycles
0 bytes consed
Evaluation took:
0.009 seconds of real time
0.008000 seconds of total run time (0.008000 user, 0.000000 system)
88.89% CPU
22,789,708 processor cycles
0 bytes consed
Evaluation took:
0.009 seconds of real time
0.008001 seconds of total run time (0.008001 user, 0.000000 system)
88.89% CPU
22,418,566 processor cycles
0 bytes consed
Evaluation took:
0.009 seconds of real time
0.012001 seconds of total run time (0.012001 user, 0.000000 system)
133.33% CPU
22,498,018 processor cycles
0 bytes consed
But after all, there is no specification. In practice, one must deal with actual requirements and sensible measurments.
If I were doing fancy conditional transforms on maps with non-trivial modifications (ie, string manipulation) I'd almost always try to use Python first, though.
def square(vector):
return [v**2 for v in vector] let square = map (^ 2)
from functools import partial
square = partial(map, lambda i: i**2)
from functools import wraps, partial
def flip(func):
'Create a new function from the original with the arguments reversed'
@wraps(func)
def newfunc(*args):
return func(*args[::-1])
return newfunc
_pow = flip(pow) #Take Y, then X
# Then the equivalent would be
square = partial(map, partial(_pow, 2)
_pow = lambda y, x: pow(x, y) SELECT x*x FROM vector;
- 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).
//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#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?
What about the same thing in python? As far as I know the two examples you gave exhausted list comprehensions' functionality.
squaredVec = vec * vec
squaredVec = vec ^ 2 but you still have to read the whole line