Article Discussion
The Lazy Builder’s Complexity Lesson
Summary: 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.
9 posts.
The ability to add new comments in this discussion is temporarily disabled.
Most recent reply: January 4, 2007 0:31 PM by Thomas
    Bill
     
    Posts: 408 / Nickname: bv / Registered: January 17, 2002 4:28 PM
    The Lazy Builder’s Complexity Lesson
    October 9, 2006 11:10 AM      
    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?
    • Achilleas
       
      Posts: 98 / Nickname: achilleas / Registered: February 3, 2005 2:57 AM
      Re: The Lazy Builder’s Complexity Lesson
      October 10, 2006 3:14 AM      
      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.
      • Thomas
         
        Posts: 13 / Nickname: tag / Registered: November 16, 2004 7:25 PM
        Re: The Lazy Builder’s Complexity Lesson
        October 10, 2006 11:33 PM      
        > 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.
      • Nemanja
         
        Posts: 40 / Nickname: ntrif / Registered: June 30, 2004 1:10 AM
        Re: The Lazy Builder’s Complexity Lesson
        October 10, 2006 5:25 AM      
        >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?
        • Achilleas
           
          Posts: 98 / Nickname: achilleas / Registered: February 3, 2005 2:57 AM
          Re: The Lazy Builder’s Complexity Lesson
          October 12, 2006 4:46 AM      
          > >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.
    • m
       
      Posts: 3 / Nickname: mlimber / Registered: November 2, 2006 6:37 AM
      Re: The Lazy Builder’s Complexity Lesson
      November 2, 2006 0:42 PM      
      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
      • Thomas
         
        Posts: 13 / Nickname: tag / Registered: November 16, 2004 7:25 PM
        Re: The Lazy Builder’s Complexity Lesson
        November 3, 2006 0:39 AM      
        > 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.
        • bug
           
          Posts: 5 / Nickname: bugmenot / Registered: July 12, 2004 11:21 PM
          Re: The Lazy Builder’s Complexity Lesson
          November 11, 2006 0:15 PM      
          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?
          • Thomas
             
            Posts: 13 / Nickname: tag / Registered: November 16, 2004 7:25 PM
            Re: The Lazy Builder’s Complexity Lesson
            November 12, 2006 8:41 AM      
            > 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.
            • Thomas
               
              Posts: 13 / Nickname: tag / Registered: November 16, 2004 7:25 PM
              Re: The Lazy Builder’s Complexity Lesson
              January 4, 2007 0:31 PM      
              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.