Comment by TeMPOraL | Hacker News Reader

Comment by TeMPOraL | Hacker News Reader

Parent Full thread

Not a fair comparison :P.

The point is that the developers may think O(n^2) is fine because their toy use cases had n=10...100, but then actual users will try to use the software for n=10k, or n=100k, and then either waste their lives working with suddenly slow software, or look for alternatives.

I walked into a case like this the other day. I wanted to do a little semi-collaborative project planning. I found a nice tool, played with it for a moment, figured it has the functionality I need and it's fast enough. Then decided to do the actual plan. Once the number of entries in the system went from 10-20 to 30-40, I started to feel things get a little laggy. 50-60, more laggy. At this point I was committed, so I suffered the tool for couple of months, as its UI kept breaking when handling 100 entries. If I knew this would happen at the start, I'd look for something else. But instead, I walked into a hidden O(n^2) somewhere, that makes me hate the product with a passion now.

It's more than that. The way black box composition is done in modern software, your n=100 code (say, a component) gets reused into a another thing somewhere above, and now you're being iterated through m=100 times. Oops, now n=10k

Generally, Casey seems to preach holistic thinking, finding the right mental model and just write the most straightforward code (which is harder than it looks; people get distracted in the gigantic state space of solutions all the time). However this requires 1. a small team of 2. good engineers. Folks argue that this isn't always feasible, which is true, but the point of these presentations is to spread the coding patterns & knowledge to train the next gen of engineers to be more aware of these issues and work toward said smaller team & better engineers direction, knowing that we might never reach it. Most modern patterns (and org structures) don't incentivize these 2 qualities.

> The way black box composition is done in modern software, your n=100 code (say, a component) gets reused into a another thing somewhere above, and now you're being iterated through m=100 times. Oops, now n=10k

That doesn't seem quite right. as 100 * (100^2) <<<<< 10000^2

Yeah I was only talking about quantities. Equivalently, assume that it's a linear algorithm in the child and a linear one in the parent. Ultimately it ends up as O(nm) being some big number, but when people do runtime analysis in the real world, they don't tend to consider the composition of these blackboxes since there'd be too many combinations. (Composition of two polynomial runtimes would be even worse, yeah.)

Basically, performance doesn't compose well under current paradigms, and you can see Casey's methods as starting from the assumption of wanting to preserve performance (the cycles count is just an example, although it might not appeal to some crowds), and working backward toward a paradigm.

There was a good quote that programming should be more like physics than math.

There was a fun example in the Julia compiler around a year ago.

Part of the compiler was O(N^2) in `let` block nesting depth. That is

  let x = foo(), y = y, z = 2y
    ...
  end

would be a depth of 3. It didn't seem like that should be a problem, N is never going to be 10, let alone 100, right?

Until suddenly, `N` was in the thousands in some critical generated code spit out by some modeling software, so that handling the scoping introduced by `let` suddenly dominated the compilation time...

Reply on news.ycombinator.com