[austincheney]

The simple rule I have found for achieving superior performance in high level languages, particularly JavaScript is to simply do less. It isn't that simple though.

Doing less really means less code totally at the current compilation target, essentially feeding fewer total instructions to the compiler. This means no frameworks and minimal abstractions. It means having a clear appreciation for the APIs you are writing to. It means minimizing use of nested loops, which exponentially increase statement count.

Sometimes caching groups of instructions in functions can allow for cleaner code with a positive performance impact.

V8 cannot compile arithmetic assignment operators, which it calls left-side expressions, so you can see a rapid speed boost in V8 when you replace something like a += 1 with a = a + 1.

The side benefit of less code is generally clearer and cleaner code to read. There isn't any wizardry or black magic. No tricks or super weapon utilities.

As an example I wrote a new diff algorithm last year that I thought was really fast. https://news.ycombinator.com/item?id=13983085 This algorithm is only fast because it does substantially less than other algorithms. I only wrote it because I could not wrap my head around the more famous Myers' O(ND) algorithm. A side benefit, in this case, of doing less is an algorithm that produces substantially more accurate results.

[Narishma]

> V8 cannot compile arithmetic assignment operators, which it calls left-side expressions, so you can see a rapid speed boost in V8 when you replace something like a += 1 with a = a + 1.

Is there a reason it can't? I'm not familiar with Javascript, but aren't the two expressions equivalent?

[austincheney]

The two expressions are equivalent. V8 cannot compile that logic into optimized bytecode due to a violation in its code engine that conflicts with other optimization logic. So instead of fast compiled code the code in the local scope of that expression is slow string interpreted code.

https://github.com/vhf/v8-bailout-reasons

[titzer]

That list is for CrankShaft which has been replaced by TurboFan > 6 months ago. If you continue to experience slowdowns please file a bug and it can be investigated.

[maaark]

There's an automotive engineer somewhere reading this, irrationally upset at the idea of replacing a crankshaft with a turbofan.

[chillee]

Do you have a source that cites the += example? I can't seem to find it on the page you linked.

[austincheney]

I remember seeing the cause of this specific case mentioned in a slide deck by one of the V8 engineers. I don't remember where online it is. I was to validate this performance limitation more than a year ago through self-testing in my personal code.

As titzer mentioned this issue may no longer exist. I would have to run additional tests to independently make an assessment with the current V8.

[whatyoucantsay]

> "It means minimizing use of nested loops, which exponentially increase statement count."

Nesting two loops has an n^2 cost and nesting 3 levels deep costs n^3. At no point does it ever cost 2^n or any x^n.

It's polynomial, not exponential.

[austincheney]

Before I begin just let me say I am not a mathematician. I program so that I don't have to do complex math.

I know in reality the frequency of iterations varies considerably but for simplicity of discussion let's remove variability.

Say we have a loop with 1000 iterations. That is at minimum 1000 statements in the loop body plus expression overhead from the loop itself. If this loop is nested once with a same sized loop there are now 1,000,000 iterations plus some expression overhead per iteration. If it is nested twice deep there are now 1 billion iterations.

That example is exponential of 1000. Given that there is overhead associated with operation of a loop it is actually greater than exponential. It may not be quite so dramatic as a logarithmic growth curve though.

I completely concede that in reality loops vary in iteration count and so nested loops aren't likely perfectly exponential unless their iteration counts are identical. The increase of iterations from nesting loops does increase more dramatically than a simple multiplicative operation as the depth of loop nesting increases, such that the growth of total iterations is a curve on a graph. A polynomial growth operation when graphed should present a straight diagonal line without the presence of a third variable.

[tachyoff]

I wouldn’t call time complexity particularly complex math. Imagine a loop. It does something n times. Within that loop, you do something n times. For each outer looo through n,you do an inner loop through n. Trivially, this is n*n, or n^2, also known as quadratic time. If you nest another loop, it becomes n^3, or cubic time.

Anyway, there might be some confusion of terms, perhaps. Exponential time in the algorithmic complexity sense is any algorithm that takes 2^n operations to complete. If you’re talking about the number of iterations after you loop through n things n times, then that increase itself would not be exponential. But that delta in iterations is unrelated to exponential and polynomial time complexity.

[austincheney]

I am sooo not a math person.

Let's not forget there is overhead to loops. At a minimum let's assume there is a single statement in the loop body, an increment statement and a terminal condition. In a single loop of 1000 iterations there are 3000 things to evaluate. The math becomes:

(n * 3)^x

If a simple loop is nested twice (3 depths) there would be 1 billion iterations but about 27 billion evaluations. Would it be correct to say that is just slightly faster polynomial growth?

[mlevental]

>that example is exponential of 1000.

no it's not. you simply have the definitions mixed up. exponential slow down or speed up means a^x where x=1000. you are describing polynomial growth, i.e. x^a (where x=1000 and a=3)

[yorwba]

It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad.

[whatyoucantsay]

> "It is exponential in the number of nested loops, which is what's important for the realization that adding more nested loops is bad."

Adding more nested loops is bad, but it's not exponential. It's polynomial.

As you nest more and more loops, the big O complexity goes from N to N^2 (quadratic) to N^3 (cubic) to N^4, etc... N^(any number) is polynomial. Exponential would be 2^N or 3^N or any number raised to the N.

See: https://en.wikipedia.org/wiki/Exponential_growth

[nickloewen]

OK I had to write things down to try and make sense of this. If anyone is like me, consider this loop that loops 5 times... maybe it will help?

  defines = 0
  tests = 0
  increments = 0

  defines++
  for (let i = 0; i < 5; i++) {
    tests++
    increments++
  }

  console.log(`defines: ${defines}, tests: ${tests}, increments: ${increments}`)

For the sake of space I'm not going too copy nested versions of that, but imagine nesting it two and then three levels deep.

  1 level will increment 5 (5^1) times    
  2 levels will increment 25 (5^2) times    
  3 levels will increment 125 (5^3) times

More interesting are the number of definitions and tests:

  levels    tests    defines
  1         15       1 
  2         30       6
  3         155      31

But I don't know is how the interpreter works and whether it has tricks to shrink those numbers; those just reflect my naive mental model of how things work.

[kazagistar]

If N is the number of nested loops, and M is the number of times through the loop, then it is indeed a O(M^N). So indeed, complexity scales exponentially with the level of nesting. The wording was just off amd confusing due to it being a nontraditonal formulation of the problem, but what he was saying does actually make sense.

[yorwba]

Something can be exponential in one context and polynomial in another. Asymptotic analysis is about the growth rate of a function in terms of some input variable. The results you get depend on which values you assume to be fixed while others vary. It is usually applied to analyze the runtime of a program in terms of the input size, which is the basis of classifying the runtime complexity, but that's not the only way you can do it.

If you have a sequence of programs with polynomial runtime, but which grows as N, N^2, N^3, N^4, ..., that's a textbook example of exponential growth. It is not generated by running a program on increasingly larger inputs, so there's nothing to be put in the exponential runtime complexity class, but it's exponential nonetheless.

[dbaupp]

In this case, the number of iterations (1000) of each loop is being held fixed, and the depth of nesting is varying, i.e. the body of the inner loop executes O(1000^depth) times.

[Ar-Curunir]

You won't have random extra nested loops appear out of nowhere in your code

[simonbw]

> At no point does it ever cost 2^n or any x^n.

That's only true if your n is referring to the number of iterations of each loop. If your n instead refers to the number of nested loops, you will indeed get a runtime of O(2^n).

Seeing as in this context we were talking about varying the number of nested loops, it makes sense that we would define our variable n = number of nested loops.

[oldandtired]

One would have expected that the arithmetic assignments operators would have been faster as

a += 1 would only compute the address of "a" only once and then duplicate it, whereas

a = a + 1 would compute the address of "a" twice. For more complicated examples the first should see an even faster speedup.

So, from my perspective, there is a serious problem here in the optimiser.