Algorithms vs loops

Quote:

Original post by godmodder Hello, this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments? I understand that for medium-large loops, algorithms should almost always be preferred, because they're more efficient, more correct and better maintainable. (Effective STL seems to confirm this) However, in order to use for_each for example, I have to write appropriate functor objects for each task I want to perform. This really looks ugly and makes my code unreadable! Is there a way to avoid this bloat? BTW: I cannot use boost for this. I understand it's benefits, but for this I'm not allowed to use it. Jeroen

Even with boost, std::for_each can sometimes be much uglier, longer, complicated and a PITA to maintain. Especially when you make up an 11-lines-long lambda expression to fit the last argument of for_each

Myself, I just use whichever one is shorter and makes more sense to me. There are times when one-line std::something solution is much nicer than a for loop typed out full; other times, I just stuff a simple three-line loop in there (including the brackets) and I'm done with it.

So it boils down to the usual: use your common sense.

Sometimes one has no choice such as Intel's TBB.

I would go with STL as much as possible, with well documented classes to make the code more readable.

When C++0x comes into common use, complete with lambdas, the std library algorithms should become much more useful. Until that time, they are a PITA for the majority of situations, so I would tend to advocate using them only where they yield a noticeable increase in readability or performance.

I tend to use stl algortihms whenever it makes sense for the functor to be a seperate reuseable component. This is very often the case with predicates for find_if, for example. If you need to find an item in a collection in a certain way in one place, chances are sometime soon you'll need to find an item in that way somewhere else.

It could be argued that wrapping the loop and/or predicate in a simple function findFooByBar (or even more simply bool checkThisFoosBar) is more readable and equally reuseable.

Quote:

Original post by godmodder this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments? I understand that for medium-large loops, algorithms should almost always be preferred, because they're more efficient, more correct and better maintainable. (Effective STL seems to confirm this) However, in order to use for_each for example, I have to write appropriate functor objects for each task I want to perform. This really looks ugly and makes my code unreadable! Is there a way to avoid this bloat?

std::for_each versus a simple for loop over all items isn't really about efficiency (both are O(n)), it's about correctness and clarity. It's easier to get a manually written loop wrong. Also, though it should be clearer in some cases, if it isn't clearer for you in a given instance, then simply don't use it there.

C++ standard library algorithms become very important when doing things like set intersection. To do that naievely involves writing nested loops, making the algorithm you implement O(m * n) whereas the standard library implementation is more like O(m + n). It's things like that which mean you really need to use the standard library algorithms to get it to work very well at all.

Quote:

Is there a way to avoid this bloat?

BOOST_FOREACH

Quote:

Original post by TheUnbeliever Quote: Is there a way to avoid this bloat? BOOST_FOREACH

Quote:

BTW: I cannot use boost for this. I understand it's benefits, but for this I'm not allowed to use it.

!fail [grin]

While you're at it, Boost.Lambda would be an even better solution for in-place bloat-removal.

Aside: using standard library algorithms (please don't say "STL") often results in encouraging refactorings (i.e. extracting the loop body into a function) that turn out to be useful (i.e. the function can be used other places in the code) and that you might otherwise never have thought of doing.

Also, consider that some tasks can be simplified by writing a smarter iterator and then proceeding to use the algorithms.

Quote:

So it boils down to the usual: use your common sense.

I was kind of fearing that would be the answer ;)

Quote:

Aside: using standard library algorithms (please don't say "STL") often results in encouraging refactorings (i.e. extracting the loop body into a function) that turn out to be useful (i.e. the function can be used other places in the code) and that you might otherwise never have thought of doing.

I agree with you: there have been a number of cases where I could reuse the code in the body of the loop and algorithms worked very elegant. But most loops that I have to write involve 1-5 lines of code that are very specific and won't ever be reused. To mention a specific example: I have a list of rooms in a level editor and I need to add their ID's to a QT listwidget so the user can visually see it as a list. I thus need to iterate over every room and extract the ID. Then I add it to the listwidget. This amounts to 2 lines of code that aren't very reusable. Writing a functor makes the code very long and it separates the logic of the operation from the place where it get's used. What would you do in this kind of scenario?

Jeroen

IMO, for_each isn't particularly useful, as it does very little for you, which is probably the reason why they would add range-based for-loops in C++0x (for_each might still be useful in the rare cases where you need to iterate over part of a container, or perhaps if you have an array that has decayed to a pointer).

In your particular example, though, transform might be more suitable, assuming listwidget has a suitable iterator interface...

Quote:

Original post by visitor IMO, for_each isn't particularly useful, as it does very little for you

One thing it does for you is that it gives the compiler optimisation opportunities that don't exist in other code. It may end up producing the same code, or better code, however it will never produce worse code than anything you could do manually (with for() or while() or whatever).
Another thing it does for you is that if you have a decent compiler, then you can use one commandline switch or one #pragma, and the compiler will parallelize for_each without you having to worry about threads, synchronisation, or anything of that matter. It will just work, only faster.

Quote:

Original post by samoth Another thing it does for you is that if you have a decent compiler, then you can use one commandline switch or one #pragma, and the compiler will parallelize for_each without you having to worry about threads, synchronisation, or anything of that matter. It will just work, only faster.

Is this actually correct? I know OpenMP does something along these lines, but does any C++ implementation do this for std::algorithms, and is it even legal by the C++ standard?

Quote:

In your particular example, though, transform might be more suitable, assuming listwidget has a suitable iterator interface...

Even if listwidget has such a suitable interface, the problem of having to write lots of very small functors remains. The only thing different is that I now iterate over the listwidget instead of the rooms.

You can sometimes get away from writing small discardable function objects by using what's available in . E.g, if you need to call a member function on all contained objects you can use std::mem_fun_ref.

#include <iostream>#include <list>#include <algorithm>#include <functional>#include <iterator>class X{    std::string name;    int id;public:    X(const std::string& name, int id): name(name), id(id) {}    int get_id() const { return id; }    friend std::ostream& operator<<(std::ostream& os, const X& x) { return os << x.name << ' ' << x.id; }};int main(){    X x[] = { X("first", 1), X("second", 2), X("third", 3), X("fourth", 4)};    const unsigned max = sizeof(x) / sizeof(x[0]);    std::list<int> ids;    int p_ids[max];    //copy id's into std::list or array    std::transform(x, x + max, std::back_inserter(ids), std::mem_fun_ref(&X::get_id));    std::transform(x, x + max, p_ids, std::mem_fun_ref(&X::get_id));    std::copy(x, x + max, std::ostream_iterator<X>(std::cout, "\n"));    std::copy(ids.begin(), ids.end(), std::ostream_iterator<int>(std::cout, " "));    std::cout << '\n';    std::copy(p_ids, p_ids + max, std::ostream_iterator<int>(std::cout, " "));}

Quote:

Original post by godmodder Hello, this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments? I understand that for medium-large loops, algorithms should almost always be preferred, because they're more efficient, more correct and better maintainable. (Effective STL seems to confirm this) However, in order to use for_each for example, I have to write appropriate functor objects for each task I want to perform. This really looks ugly and makes my code unreadable! Is there a way to avoid this bloat? BTW: I cannot use boost for this. I understand it's benefits, but for this I'm not allowed to use it. Jeroen

I have a rule for that and it is that I use the shortest amount of code possible. That often results in that I almost never use std::for_each . Too bad you cannot use Boost.

Quote:

Original post by swiftcoder Is this actually correct? I know OpenMP does something along these lines, but does any C++ implementation do this for std::algorithms, and is it even legal by the C++ standard?

OpenMP is one thing of course, and there is for example this: http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html

I've used it a couple of times out of curiosity, and it works surprisingly well. In fact, it works so well that you almost have to ask yourself why you ever bothered learning about threads.

No doubt other compilers have something similar. Whether it's "legal" by the standard... no idea, but why would it not be legal? The standard doesn't say "your program must run in one thread", nor does it make any claims about how a particular algorithm in the STL is implemented. At best it makes statements and claims such as "insert takes constant time" or "search is guaranteed to be logarithmic time".

Quote:

Whether it's "legal" by the standard... no idea, but why would it not be legal?

Of course it's "illegal", parallel for_each breaks the guarantee that elements are visited in order.
As with OpenMP, you have to explicitly ask for parallel mode behavior and thereby promise that your functors have no side effects (and that no exceptions will leak out).

Quote:

Original post by samoth I've used it a couple of times out of curiosity, and it works surprisingly well. In fact, it works so well that you almost have to ask yourself why you ever bothered learning about threads.

Because there's a lot more about threading than to parallelize some trivial loops. OpenMP itself exposes only a tiny little part of what multithreading is capable of (although OpenMP is very convenient in some situations).

Anyway, I wouldn't touch that 'parallel STL' with a ten feet pole. Of course it completely breaks the C++ standard and introduces a whole set of assumptions that are not present in the standard. As Jan mentioned, elements not being visited in order is one thing. But what happens if that parallel implementation has to call your objects ctor, cctor or some operator, which is not thread safe ? What happens if a parallel loop itself is being threaded outside of its context ? It says it relies on OpenMP. Contrary to popular belief, OpenMP does not do object sync for you. You still have to make all involved objects thread safe by yourself.

If you want to parallelize a part of your program, then directly use OpenMP. At least it will make clear that you have to understand and deal with all possible synchronization issues that are relevant to the multithreaded part.

Quote:

Original post by godmodder this is an issue I regularly bump into when coding larger projects: do I need to prefer (STL) algorithms or manual loops for very small code fragments?

Algorithms? For loops are part of an algorithm, you can't separate loops and certain algorithms (you can just hide them under the carpet). Don't mistake programming with math, the skills required are vastly different. (Remember what Djiksra said...)

"for(i32..." is explicit, some recursive abomination isn't. As long as you would be only one to read the code it doesn't matter too much, but you'd learn bad style of coding.

BTW functors are not guaranteed to be on each OS.

Quote:

Original post by samoth One thing it does for you is that it gives the compiler optimisation opportunities that don't exist in other code. It may end up producing the same code, or better code, however it will never produce worse code than anything you could do manually (with for() or while() or whatever). Another thing it does for you is that if you have a decent compiler, then you can use one commandline switch or one #pragma, and the compiler will parallelize for_each without you having to worry about threads, synchronisation, or anything of that matter. It will just work, only faster.

It would be scary. Imagine a game which finally guarantees the highest spike would be under specifications, and anything which wouldn't finish under 30 ms would be either interrupted or dereferenced. That apply for Ex(n). Now imagine you have sudden Ex(n + 1) or higher that appeared out of nowhere and messes things up. GFX threads tend to be high priority, and with multicore CPUs they can run fairly independently, now the problem is a derived thread has priority of the original thread.

Quote:

Original post by Jan Wassenberg Quote: Whether it's "legal" by the standard... no idea, but why would it not be legal? Of course it's "illegal", parallel for_each breaks the guarantee that elements are visited in order. As with OpenMP, you have to explicitly ask for parallel mode behavior and thereby promise that your functors have no side effects (and that no exceptions will leak out).

In order execution is just a suggestion, as long as the elements are properly visited on average. People who would like theirs for loop to access all elements in order should specify this by volatile keyword. ~_^