6 ms·

Next permutation: When C++ gets it right

58 points by r11t 17y ago

rbranson 17y ago
This is one of the most truly balanced, well-written, pragmatic articles I've read on HN. Instead of the typical dogmatic spew that is nearly epidemic in blog posts, it reads more like a scientific paper, but without all the dryness.
- djcapelis 17y ago
  I've been trying to do my part to get rid of the dryness found in most science papers but they keep rejecting the ones I send in wet.
- jrockway 17y ago
  I know a lot of blog posts that read like this, but they usually don't get modded up because there is apparently nothing exciting about learning something. Much better if you start some sort of flamewar... I have personally observed that "Why I hate xxx" often gets many more views than "Why I like yyy". (They both attract the same amount of hate, however. When I say "I hate Java", I get comments like "DIE IN A FIRE RTARD". When I say "I like Perl", I am told that I am "the dumbest person alive".)
  - stonemetal 17y ago
    >> When I say "I like Perl", I am told that I am "the dumbest person alive" Not the dumbest person alive, that would be a Perl maintainer, more like the second dumbest person alive. Joking. I think it is probably related to the whole bicycle shed issue it is easy to rag on and have an opinion on "hate' and "like" because they themselves are opinion statements. Factual stuff like the above is infinitely more interesting than "I like beans" but it also provides less emotional reaction rating, commenting, etc.
  - jerf 17y ago
    I am inescapably drawn to the conclusion that the internet is telling you that you should die in a fire, you dumbest person alive. Don't dare to like something else or it'll just add another clause to your doom. Don't feel bad. The internet pretty much says that to us all, at least those of us who post anything. Ever. On any topic whatsoever.
DanielBMarkham 17y ago
Nicely done. Interesting (but true) jab at FP towards the end. Sometimes C++ is still the best tool for the job.
- viraptor 17y ago
  Not sure about that. It is true that no space overhead might be a good thing, but other reasons simply don't look that good. "algorithms which loop rather than recurse" - something like (primitive example, I know) `f(a, x): f(a+x, x-1); f(a, 0): a` with a tail call should be compiled into a loop he's talking about. There is no difference. There is no overhead. (single `jmp f` at the end and even the arguments should be in the right place) "Sometimes it’s about shuffling, nudging and swapping" - apart from the situations where by simply inlining/analysing some functions which do the swap you can eliminate the swap completely and simply specialise the function to swap the places it reads the values from. Sometimes you don't need to swap - you just want the values in the right places and don't care how it is done under the hood. Swap done directly with a machine operation in C++ has to do the actual swap. It was a cheap shot at FP tbh :/ Still right that C++ sometimes gets things right, but for 2 wrong reasons this time.
  - eru 17y ago
    Yes. And I guess if you choose a strict language like Ocaml, even the space overhead isn't that bad. With a lazy language like Haskell the unevalutad thunks can eat a lot of memory. But you can always make your Haskell programs strict, if you know enough magic.
wglb 17y ago
Very good tutorial on one of the recent Code Jam problems. The solution does at first seem mysterious, but the article does show how it works nicely. Browsing through some of the solutions to the code jam, c++ seems frequently used. It is also sort of amusing to see how many participants apparently have a stock set of utility code. There is a lot of use of the STL to do things just as the article mentions. The inventor of STL did have some fairly scathing words to say about OO programming. Also, speed does sometimes matter, as occasionally the large data sets do require a bit of computational power, and you are under a time limit.
- mquander 17y ago
  I'd point out that C++ might be overrepresented in the GCJ solutions. Many of the successful GCJ competitors come from TopCoder, where the only available languages are Java, C# 2.0, and C++, so C++ is the favorite there by a wide margin. If languages like Python, Perl, etc. were available in TopCoder, I bet you would see more people using them both there and here.
  - wglb 17y ago
    Ah, I wasn't aware of that. I did read of one participant, however, who used Python and his solution would not finish in the 8 minute time limit for the large data set, but it worked for the small. So that would certainly be a consideration. And the ones i did see in C++ were light use of C++ features, with STL.
chadaustin 17y ago
Back when I competed regularly in TopCoder for food money in college, std::next_permutation saved my bacon. I got so good at whipping out <algorithm> in C++ that every other language's standard library felt deficient. Python's basically caught up with itertools and the built-in set type. Often you can replace dozens of lines of for loops and if statements with set subtraction and some generator comprehensions. Sometimes the code ends up faster, to boot!
- loup-vaillant 17y ago
  Then you will absolutely love Haskell's and Ocaml's standard libraries (if you can spare some CPU cycles). Paranoid static typing with easy genericness (more flexible than C++ templates), and they don't have the one show stopping flaw C++'s <algorithm> still have sometimes: lack of locality. Until C++ has closures, a loop will often look like this: body(…){ code_of_body; } fun(…) { // (Big) blob of code std::loop(begin, end, body) … } I have done it. Lack of locality kills readability, so I still use loops even when std::accumulate or std::foreach would do.
  - eru 17y ago
    Since the root comment talked about Python's set, you might want to have a look at Haskell's Data.Set. Haskell's Data.Map is more or less equivalent to Python's dict. You can also map and fold over Sets and Maps. There is no built-in function for applying a function to a set to get a map, but you can easily add one.
  - jemfinch 17y ago
    Since C++ templates are Turing-complete, and at least OCaml's type system is not, I'm fairly confident that the claim that OCaml's "easy genericness" is "more flexible than C++ templates" is demonstrably false.
    - loup-vaillant 17y ago
      In theory. In practice, I found that translating from OCaml to C++ is often painful, while the reverse is quite easy. When I deal with generic code, this difficulty is largely attributable to the differences between Hindley-Milner and templates. My conclusion is that where it really matters, C++'s templates are less flexible than OCaml's genericness. I dare you to try and prove me wrong with production code without being fired… upon.

58 points by r11t 17y ago

This is one of the most truly balanced, well-written, pragmatic articles I've read on HN. Instead of the typical dogmatic spew that is nearly epidemic in blog posts, it reads more like a scientific paper, but without all the dryness.

djcapelis 17y ago
I've been trying to do my part to get rid of the dryness found in most science papers but they keep rejecting the ones I send in wet.
jrockway 17y ago
I know a lot of blog posts that read like this, but they usually don't get modded up because there is apparently nothing exciting about learning something. Much better if you start some sort of flamewar... I have personally observed that "Why I hate xxx" often gets many more views than "Why I like yyy". (They both attract the same amount of hate, however. When I say "I hate Java", I get comments like "DIE IN A FIRE RTARD". When I say "I like Perl", I am told that I am "the dumbest person alive".)
- stonemetal 17y ago
  >> When I say "I like Perl", I am told that I am "the dumbest person alive" Not the dumbest person alive, that would be a Perl maintainer, more like the second dumbest person alive. Joking. I think it is probably related to the whole bicycle shed issue it is easy to rag on and have an opinion on "hate' and "like" because they themselves are opinion statements. Factual stuff like the above is infinitely more interesting than "I like beans" but it also provides less emotional reaction rating, commenting, etc.
- jerf 17y ago
  I am inescapably drawn to the conclusion that the internet is telling you that you should die in a fire, you dumbest person alive. Don't dare to like something else or it'll just add another clause to your doom. Don't feel bad. The internet pretty much says that to us all, at least those of us who post anything. Ever. On any topic whatsoever.

DanielBMarkham 17y ago

Nicely done. Interesting (but true) jab at FP towards the end. Sometimes C++ is still the best tool for the job.

viraptor 17y ago
Not sure about that. It is true that no space overhead might be a good thing, but other reasons simply don't look that good. "algorithms which loop rather than recurse" - something like (primitive example, I know) `f(a, x): f(a+x, x-1); f(a, 0): a` with a tail call should be compiled into a loop he's talking about. There is no difference. There is no overhead. (single `jmp f` at the end and even the arguments should be in the right place) "Sometimes it’s about shuffling, nudging and swapping" - apart from the situations where by simply inlining/analysing some functions which do the swap you can eliminate the swap completely and simply specialise the function to swap the places it reads the values from. Sometimes you don't need to swap - you just want the values in the right places and don't care how it is done under the hood. Swap done directly with a machine operation in C++ has to do the actual swap. It was a cheap shot at FP tbh :/ Still right that C++ sometimes gets things right, but for 2 wrong reasons this time.
- eru 17y ago
  Yes. And I guess if you choose a strict language like Ocaml, even the space overhead isn't that bad. With a lazy language like Haskell the unevalutad thunks can eat a lot of memory. But you can always make your Haskell programs strict, if you know enough magic.

wglb 17y ago

Very good tutorial on one of the recent Code Jam problems. The solution does at first seem mysterious, but the article does show how it works nicely. Browsing through some of the solutions to the code jam, c++ seems frequently used. It is also sort of amusing to see how many participants apparently have a stock set of utility code. There is a lot of use of the STL to do things just as the article mentions. The inventor of STL did have some fairly scathing words to say about OO programming. Also, speed does sometimes matter, as occasionally the large data sets do require a bit of computational power, and you are under a time limit.

mquander 17y ago
I'd point out that C++ might be overrepresented in the GCJ solutions. Many of the successful GCJ competitors come from TopCoder, where the only available languages are Java, C# 2.0, and C++, so C++ is the favorite there by a wide margin. If languages like Python, Perl, etc. were available in TopCoder, I bet you would see more people using them both there and here.
- wglb 17y ago
  Ah, I wasn't aware of that. I did read of one participant, however, who used Python and his solution would not finish in the 8 minute time limit for the large data set, but it worked for the small. So that would certainly be a consideration. And the ones i did see in C++ were light use of C++ features, with STL.

chadaustin 17y ago

Back when I competed regularly in TopCoder for food money in college, std::next_permutation saved my bacon. I got so good at whipping out <algorithm> in C++ that every other language's standard library felt deficient. Python's basically caught up with itertools and the built-in set type. Often you can replace dozens of lines of for loops and if statements with set subtraction and some generator comprehensions. Sometimes the code ends up faster, to boot!

loup-vaillant 17y ago
Then you will absolutely love Haskell's and Ocaml's standard libraries (if you can spare some CPU cycles). Paranoid static typing with easy genericness (more flexible than C++ templates), and they don't have the one show stopping flaw C++'s <algorithm> still have sometimes: lack of locality. Until C++ has closures, a loop will often look like this: body(…){ code_of_body; } fun(…) { // (Big) blob of code std::loop(begin, end, body) … } I have done it. Lack of locality kills readability, so I still use loops even when std::accumulate or std::foreach would do.
- eru 17y ago
  Since the root comment talked about Python's set, you might want to have a look at Haskell's Data.Set. Haskell's Data.Map is more or less equivalent to Python's dict. You can also map and fold over Sets and Maps. There is no built-in function for applying a function to a set to get a map, but you can easily add one.
- jemfinch 17y ago
  Since C++ templates are Turing-complete, and at least OCaml's type system is not, I'm fairly confident that the claim that OCaml's "easy genericness" is "more flexible than C++ templates" is demonstrably false.
  - loup-vaillant 17y ago
    In theory. In practice, I found that translating from OCaml to C++ is often painful, while the reverse is quite easy. When I deal with generic code, this difficulty is largely attributable to the differences between Hindley-Milner and templates. My conclusion is that where it really matters, C++'s templates are less flexible than OCaml's genericness. I dare you to try and prove me wrong with production code without being fired… upon.