• Advertisement
Sign in to follow this  

Algorithms vs loops

This topic is 3308 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
You can sometimes get away from writing small discardable function objects by using what's available in <functional>. 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, " "));
}


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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".

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. ~_^

Share this post


Link to post
Share on other sites
Quote:
Original post by Raghar
"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.


You have a strange definition of "explicit". To me, for_each explicitly applies an operation to all elements, while for explicitly initializes, modifies, uses and checks a loop variable that implicitly happens to apply an operation to all elements.

Quote:
BTW functors are not guaranteed to be on each OS.
?

Quote:
In order execution is just a suggestion, as long as the elements are properly visited on average.
Right. And "2+2 = 4" is also just a suggestion, it doesn't matter if sometimes you get 2+2 = 3 or 2+2 = 5, does it? std::for_each means "apply this operation to these elements in order", which means that you can rely on the order of execution of elements (for instance, so that loading a texture happens before loading a mesh that uses that texture). If you need to "apply this operation to these elements in any order", and you expect there's a performance benefit to be gained by doing so, then you should use another primitive, such as one from OpenMP.

Share this post


Link to post
Share on other sites
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).
As for side effects in the functors, you are of course right. However, that's nothing new, nothing magical, and nothing you wouldn't have to deal with otherwise, too. If an operation on element N strictly depends on some action taken on elements N-1 and N-2 in a a particular order, then you have a problem anyway.

Regarding the "guarantee that elements are visited in order", I dissent. The standard says:
Quote:
1 Effects: Applies f to the result of dereferencing every iterator in the range [first, last), starting from first and proceeding to last-1.
2 Returns: f.
3 Complexity: Applies f exactly last-first times.
Notes: If f returns a result, the result is ignored.
In my opinion, "starting from first and proceeding to last-1" does not necessarily mean "must execute everything in order".
Sequential processing is certainly one possible way of doing this, and the easiest. However, the only real requirement is that it starts at the first element and eventually arrives at the last, and that it touches every element once, and only once.

If that was not the case, then sorted containers such as map would be violating the standard. These containers guarantee that iterators are in an order so their dereferenced values are in ascending sorted order. So, unless you insert your elements in sorted order, the order of processing of any algorithm that goes over iterators must necessarily be non-sequential.

Quote:
Because there's a lot more about threading than to parallelize some trivial loops.
That's right, but that's not my point. Parallelizing even a "trivial" loop is not quite so trivial if you have to do it by hand, even more so if you want to support more than one platform.
Having direct support from the compiler side to do this in an easy, portable, and unintrusive manner sure is no mistake. After all, that's what tools are for, they're there to make your life easier. Of course you still have to pay attention to some things, and of course it is no panacea, but then what is perfect?
In the end, if you feel uneasy about it, you can still hand-code all your threading. No problem with that either :-)

Share this post


Link to post
Share on other sites
Quote:
Original post by samothIn my opinion, "starting from first and proceeding to last-1" does not necessarily mean "must execute everything in order".
Sequential processing is certainly one possible way of doing this, and the easiest. However, the only real requirement is that it starts at the first element and eventually arrives at the last, and that it touches every element once, and only once.
I'd say executing everything in order is pretty much a literal consequence of "proceeding".

Quote:
If that was not the case, then sorted containers such as map would be violating the standard. These containers guarantee that iterators are in an order so their dereferenced values are in ascending sorted order. So, unless you insert your elements in sorted order, the order of processing of any algorithm that goes over iterators must necessarily be non-sequential.
I don't really understand what you're trying to say. Any container, including maps and sets, represents its contents as a sequence implemented as a [begin,end) pair of iterators. Applying for_each to these iterators will, as expected, operate on the values in the order in which they appear in the sequence. How that sequence changes as values are inserted or removed into the container are up to the container's definition, but has nothing to do with for_each.


Share this post


Link to post
Share on other sites
Quote:
Original post by samoth
If that was not the case, then sorted containers such as map would be violating the standard. These containers guarantee that iterators are in an order so their dereferenced values are in ascending sorted order. So, unless you insert your elements in sorted order, the order of processing of any algorithm that goes over iterators must necessarily be non-sequential.


This is nonsensical. The whole thing about iterators is that the order of traversal, as determined by starting with .begin() and repeatedly applying operator++, defines the "order" of the elements in the container. It doesn't matter when you insert them into a sorted container; they are ordered in a certain way, and you do not control "where" in the container the element ends up. The only other possibly meaningful interpretation of "order" would rely on the relative position in memory of the actual chunks of data, but that's effectively arbitrary and useless.

Proceeding from beginning to end means checking .begin(), using operator++ iteratively (the operative word!) to access each element in turn, and stopping when you get to .end(). There's simply no other way to interpret it that makes any kind of sense at all, given an understanding of the design intent.

Share this post


Link to post
Share on other sites
Quote:
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.

That's a bit overly harsh :) [Disclaimer: a colleague developed mcstl (Multi-Core STL), which has become the 'parallel mode']
Sure, by going parallel you enter an entirely different world, but the appendant assumptions and changes must be made somewhere. What's the problem with getting this started by providing a useful higher-level library that allows a wider range of developers to benefit from parallel algorithms? Example: mcstl provides several good parallel sorting routines. These are both immediately useful and definitely non-trivial to develop. I think the learning curve and constraints of the library (disallowing exceptions, ensuring that you don't have conflicting threading models and avoiding side effects) are worth the convenience and code reuse.

Quote:
Contrary to popular belief, OpenMP does not do object sync for you. You still have to make all involved objects thread safe by yourself.

This is true. However, there are a wide range of tasks involving built-in types that can trivially be parallelized by using this library; obviously the more complex cases require more caution.

Quote:
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.

That's fine and good for simple loops, but some of the mcstl algorithms are much more complicated. Even std::partition isn't exactly simple, and even more so than in sequential code, reinventing the (parallel) wheel is extremely expensive.

Quote:
People who would like theirs for loop to access all elements in order should specify this by volatile keyword. ~_^

Please read Volatile: Almost Useless for Multi-Threaded Programming; the title says it all.

Quote:
In my opinion, "starting from first and proceeding to last-1" does not necessarily mean "must execute everything in order".

hm, that wording is indeed a bit vague, but SGI's documentation states it unambiguously:
Applications are performed in forward order, i.e. from first to last.
Now I suppose it's possible for certain input iterators to define some permutation of elements, but for_each has to dereference them in "forward order" (which for pointer iterators means in order of increasing address).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement