This article investigates the complexity guarantees made by the C++ Standard Library. By analyzing and measuring the performance of alternative solutions to the same problem it shows how this library allows us to write code that is both simple and efficient.

http://www.artima.com/cppsource/lazy_builder.html

To what extent do you consider algorithmic complexity in your day to day coding tasks?

I am confused. The article says:

we wouldn’t be using C++ if we didn’t care about performance.

But then there are many who insist that other languages (Java, Haskell, Eiffel etc) are on par with C++.

So what gives? is C++ better performance-wise or not?

My opinion is that C++ is better performance-wise, provided that you know what you are doing.

>other languages (Java, Haskell, Eiffel etc) are on par with C++.

Haskell??? Even on the Haskell advocacy page http://www.haskell.org/complex/why_does_haskell_matter.html they say: "As a general rule C++ should be faster than Haskell, there's no point claiming anything else."

Maybe you mean OCaml?

> I am confused. The article says:
>
> we wouldn’t be using C++ if we didn’t care about
> performance.
>

What I meant was that for many jobs I prefer to use a high-level language; but in situations where processor cycles -- and other low-level resources -- need careful monitoring, then C++ is an excellent choice.

> But then there are many who insist that other languages
> (Java, Haskell, Eiffel etc) are on par with C++.
>
> So what gives? is C++ better performance-wise or not?

On paper, for example, an NlogN algorithm in Python will always beat an N^2 algorithm in C++, as N gets large. All things being equal, though, C++ will get more from the machine.

I'm not sure if C++ is best placed to exploit multi-processor architectures though.

> My opinion is that C++ is better performance-wise,
> provided that you know what you are doing.

Agreed.

> >other languages (Java, Haskell, Eiffel etc) are on par
> with C++.
>
> Haskell??? Even on the Haskell advocacy page
> http://www.haskell.org/complex/why_does_haskell_matter.html
> they say: "As a general rule C++ should be faster than
> Haskell, there's no point claiming anything else."
>
> Maybe you mean OCaml?

But they also say that For the vast majority of applications the speed difference will be negligible, however (copy-paste from the site you posted).

I do not buy 'negligible'. I haven't seen Haskell sorting equal to C/C++...I can not imagine how one could sort, let's say, thousands of records with functional languages...and sorting is a fairly common task.

I think it's funny how he says, "The rule of thumb—to use std::vector unless there’s good reason not to—applies here." But then in the very next section, he uses a raw array instead of a vector with no apparent good reason:

unsigned job_widget_counts[widget::max_value];
std::fill(job_widget_counts,
job_widget_counts + widget::max_value, 0);

Cheers! --M

> I think it's funny how he says, "The rule of thumb—to use
> std::vector unless there’s good reason not to—applies
> here." But then in the very next section, he uses a raw
> array instead of a vector with no apparent good reason:

Good point. My reason here was the usual one: the storage space required is known at compile time, so we can avoid dynamic allocation by using an array. An std::tr1::array would also do the job. And, as you say, so would a vector.

I dislike the benchmarks:

> perhaps the random widget generator gave significantly different inputs.
> Clearly, the algorithm runs so fast that our test results are subject to timing jitter.

Well, if you know that, why don't you run them for sensible times/input sizes?

> I dislike the benchmarks:

And I like them. I think they yield some interesting points.

> > perhaps the random widget generator gave significantly
> different inputs.
> > Clearly, the algorithm runs so fast that our test
> results are subject to timing jitter.
>
> Well, if you know that, why don't you run them for
> sensible times/input sizes?

I didn't know that before I ran the benchmarks! My timing tests ran the same inputs the same number of times through the variant algorithms. But you're right, given this initial result, I could have run more tests.

In an email from Christopher Vogt I got an interesting correction to this article. It turns out that my analysis of the complexity of the first (and worst) brute force algorithm wasn't correct. I wanted it to be O(N*N), but in fact in the worst case it performs O(N*N*log(N)).

This worst case occurs when both the job and the toolback contain N instances of a single widget. The "used" set will also grow to size N, and repeatedly searching through this set is what causes the additional log(N) factor.

More details can be found at: http://www.wordaligned.org/lazy_builder/index.html

Thanks again to Christopher for his help.