4 ms·

I agree with you that algorithm choice is what's most relevant. However: I'd argue that accidentally quadratic algorithms are easier to hide in a concise langu

I agree with you that algorithm choice is what's most relevant. However: I'd argue that accidentally quadratic algorithms are easier to hide in a concise language. Writing out a quadratic loop explicitly takes space, and that space alone might make people pay more attention than some subtle implicit language construct. Either way, the most common source of unintended quadratic (or higher) behavior is helper functions and library calls. The other thing to keep in mind when it comes to algorithms is that cache behavior and therefore memory layout matters a lot for performance on modern hardware. Managed languages really stand in the way of optimizing memory layout, which can be a systematic performance disadvantage compared to C++. I do hope we get some more innovation in the design space occupied by Rust, where you get fairly explicit control over memory layout, but still have statically checked memory safety guarantees.

lmm 6y ago
> I'd argue that accidentally quadratic algorithms are easier to hide in a concise language. Writing out a quadratic loop explicitly takes space, and that space alone might make people pay more attention than some subtle implicit language construct. Either way, the most common source of unintended quadratic (or higher) behavior is helper functions and library calls. I disagree. When every loop is full of cruft around setting up the iterators, it's easy to drift past what's actually happening. In a language where looping over a list takes a single syntactic token, it's a lot more obvious when you've nested several such loops. > The other thing to keep in mind when it comes to algorithms is that cache behavior and therefore memory layout matters a lot for performance on modern hardware. Managed languages really stand in the way of optimizing memory layout, which can be a systematic performance disadvantage compared to C++. C++ doesn't really make cache behaviour clear either though. I agree that we need better tooling for handling those aspects of high-performance code, but they actually need to come from somewhere lower-level than C++.
- atq2119 6y ago
  Nested loops are obvious in most languages, including C++ -- unless you happen to work with people who don't indent their code properly, but then you have bigger problems than the choice of language. The real problems tend to come from where the quadratic behaviour doesn't come from nested loops, but from library calls. The canonical example of this is building up a string with successive string concatenation in C. As for cache behaviour, C++ allows you to control memory layout, which is really what's required there, while most managed languages don't give you that control at all.
  - lmm 6y ago
    > Nested loops are obvious in most languages, including C++ -- unless you happen to work with people who don't indent their code properly, but then you have bigger problems than the choice of language. We live in a fallen world. In a large enterprise codebase there will almost certainly be parts that aren't indented correctly. And even if everything is indented perfectly, the sheer amount of stuff in a C++ codebase makes everything far, far less obvious.

lmm 6y ago

> I'd argue that accidentally quadratic algorithms are easier to hide in a concise language. Writing out a quadratic loop explicitly takes space, and that space alone might make people pay more attention than some subtle implicit language construct. Either way, the most common source of unintended quadratic (or higher) behavior is helper functions and library calls. I disagree. When every loop is full of cruft around setting up the iterators, it's easy to drift past what's actually happening. In a language where looping over a list takes a single syntactic token, it's a lot more obvious when you've nested several such loops. > The other thing to keep in mind when it comes to algorithms is that cache behavior and therefore memory layout matters a lot for performance on modern hardware. Managed languages really stand in the way of optimizing memory layout, which can be a systematic performance disadvantage compared to C++. C++ doesn't really make cache behaviour clear either though. I agree that we need better tooling for handling those aspects of high-performance code, but they actually need to come from somewhere lower-level than C++.

atq2119 6y ago
Nested loops are obvious in most languages, including C++ -- unless you happen to work with people who don't indent their code properly, but then you have bigger problems than the choice of language. The real problems tend to come from where the quadratic behaviour doesn't come from nested loops, but from library calls. The canonical example of this is building up a string with successive string concatenation in C. As for cache behaviour, C++ allows you to control memory layout, which is really what's required there, while most managed languages don't give you that control at all.
- lmm 6y ago
  > Nested loops are obvious in most languages, including C++ -- unless you happen to work with people who don't indent their code properly, but then you have bigger problems than the choice of language. We live in a fallen world. In a large enterprise codebase there will almost certainly be parts that aren't indented correctly. And even if everything is indented perfectly, the sheer amount of stuff in a C++ codebase makes everything far, far less obvious.