News for hackers. Stuff that matters.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by iovrthoughtthis on Monday April 12, 2021 @07:47AM (#26778296)
great post, this part

> For reference, a Python version of this same loop runs in 1 minute and 38 seconds … a dynamically-typed bytecode interpreter is not a good choice for heavy integer arithmetic.

made me wonder about other dynamic langs.

ruby (3.0.0) and lua (5.4.2) ran it in 1:30 and 1:03 respectively but node (12.22.0) ran it in 0:01. how is node so quick?

Re:Mugo, a toy compiler for a subset of Go that can compile ... by inbx0 on Monday April 12, 2021 @09:50AM (#26779407)
Well, for one thing, if you copied the numbers from the example as they are defined, then JS will be dealing with simple floating point numbers and actually gets the answer wrong (but gets there fast!). The answer is beyond 5E+17 but JS's Number.MAX_SAFE_INTEGER is only 9E+15. The results start getting weird after that.

To get the correct answer, we need to convert some of the numbers to BigInts

  var result = 0n

  function main() {
    var sum = 0n
    var i = 1
    while (i <= 1000000000) {
        sum = sum + BigInt(i)
        i = i + 1
    }
    result = sum
  }

  main()
but after that the result is not quite so impressive anymore

  Now using node v15.6.0 (npm v7.4.0)
   time node index.js
  node index.js  51.50s user 0.40s system 103% cpu 50.072 total
Re:Mugo, a toy compiler for a subset of Go that can compile ... by zeugmasyllepsis on Monday April 12, 2021 @09:55AM (#26779477)
Thank you for providing details and not just assuming the JIT was the cause of the difference.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by elcomet on Monday April 12, 2021 @07:57AM (#26778369)
Node uses a JIT compiler (V8) and is not interpreted. This is why it's so fast.

You could compare it with PyPy, a just-in-time compiler for python.

For example, on my machine, the same program runs in 2:12 min with the regular python interpreter, and in 1.57 seconds with pypy.

Re:Mugo, a toy compiler for a subset of Go that can compile ... by Joker_vD on Monday April 12, 2021 @08:11AM (#26778481)
Erlang/OTP 22 (on my machine™, of course) runs it in 9.3 seconds when invoked from the compiled module, and in at least in 5 minutes when invoked as a fun defined in the shell: "at least" because I did not have enough patience to wait until it actually completes.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by josefx on Monday April 12, 2021 @10:41AM (#26779943)
Ruby has its jit disabled by default as far as I can tell^1 . Lua exists in both jit compiled and interpreted forms. Python definitely is interpreted unless you run it through pypy. JavaScript is basically the only language in that lineup that enables just in time compilation with most of the "default" runtimes.

^1 Most likely because it generates C code and has to call an external C compiler to get things done.

Re:Mugo, a toy compiler for a subset of Go that can compile ... by thysultan on Monday April 12, 2021 @08:07AM (#26778445)
NodeJs and Go can and probably are optimizing the loop away, the authors attempt to assign the sum to result does not prevent this from happening.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by benhoyt on Monday April 12, 2021 @03:00PM (#26783606)
> can and probably are optimizing the loop away

Why do you think that, and how would it do that and still do the calculation? My timing tests showed that Go didn't optimize the loop away (if I counted to 10 billion it took about 10 times as long), and godbolt.org also shows the loop in Go's assembly output: https://www.godbolt.org/z/d38xfGYr6

Re:Mugo, a toy compiler for a subset of Go that can compile ... by makapuf on Monday April 12, 2021 @03:54PM (#26784318)
Fun fact: in C, gcc and clang can(and will) replace the sum of n first integers with a loop (and slight variations) with Euler formula n(n+1)/2. Impressive.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by benhoyt on Monday April 12, 2021 @04:24PM (#26784676)
Wow, that is impressive, thanks. I confirmed this with godbolt.org at -O2.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by nonameiguess on Tuesday April 13, 2021 @07:59AM (#26791018)
Note that Python tends to get around this by providing a wide variety of fast builtin functions to do stuff that would otherwise be slow.

    $ time python -c 'sum = 0
    > for i in range(1000000000): sum += 1'

    real 0m56.655s
    user 0m56.646s
    sys  0m0.008s
Compare to:

    time python -c 'sum(range(1000000000))'

    real 0m8.693s
    user 0m8.684s
    sys  0m0.008s
In reality, anyone is going to do heavy arithmetic using Numpy anyway:

    $ time python -c 'import numpy as np; np.sum(np.arange(1000000000))'

    real 0m2.022s
    user 0m1.661s
    sys  0m2.061s
As a nice bonus, you get hardware speed but it still gives you the right answer, unlike Node trying to use limited precision primitive types.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by jerf on Monday April 12, 2021 @04:28PM (#26784730)
If you think about what something like CPython is doing, you are maximally pessimizing the way the implementation works by adding integers together. You get all the dynamic type manipulation and management that is occurring all the time, but then when it comes time to do the 'payload' of the operation it is doing, it's a simple ADD operation that can complete in (amortized) less than one cycle. It's the worst case for something like CPython. All that work a dynamic language is doing has much better performance characteristics when you get to a "payload" that is like running C code to find a substring match in a string, or something else non-trivial that helps to amortize all the bookkeeping with more real work.

As for why Node runs quickly, adding integers (or floats or whatever) is easy mode for a JIT. This is basically why you see JIT numbers like speeding up the original implementation by factors of literally over 100x, yet you can't expect that multiplier against "real code", for essentially the same reason only now on the other end; the JIT can very successfully cut out all that work CPython or similar implementatiors are doing if you have completely stable types that it can infer (especially something as simple as a single int or float), but now the "payload" is preventing the JIT from posting big numbers in improvement when you have more complicated operations because the JIT isn't going to be able to improve something like a substring search. If you get something like NumPy where you can feasibly write a program that will spend 99+% of its time in highly optimized matrix code, a JIT can't help much with that, because even if it reduced the bookkeeping to zero, you've still got to do all that matrix work.

Statically-typed compiled languages basically bypass the whole "do lots of expensive bookkeeping to permit very flexble coding styles, then write a JIT that figures out how to bypass that expensive bookkeeping as often as possible" to simply constrain you to write in the fast subset in the first place.

Re:Mugo, a toy compiler for a subset of Go that can compile ... by deweller on Monday April 12, 2021 @09:07AM (#26778952)
For reference, this runs in 13s in PHP 8 on my ARM Mac. PHP 8 uses a JIT compiler.
Re:Mugo, a toy compiler for a subset of Go that can compile ... by sfifs on Monday April 12, 2021 @07:55AM (#26778346)
Years of Google engineers squeezing performance for JavaScript heavy web pages maybe?
Re:Mugo, a toy compiler for a subset of Go that can compile ... by iovrthoughtthis on Monday April 12, 2021 @07:56AM (#26778353)
That is certainly how, but why? What have they done that enables it to do that?
Re:Mugo, a toy compiler for a subset of Go that can compile ... by pjmlp on Monday April 12, 2021 @08:36AM (#26778667)
Here, have some fun,

"V8 Internals For JavaScript Developers"

https://vimeo.com/312113316

https://v8.dev/blog

Re:Mugo, a toy compiler for a subset of Go that can compile ... by cdogl on Monday April 12, 2021 @08:10AM (#26778476)
Chrome's V8 engine made quite a stir around the turn of the last decade because it it compiled JavaScript down to native code. It would even watch how code was called (if it couldn't statically figure out a safe way to compile it) and generate native code for the happy paths in hot code paths. I simply assume that all browsers do this now because we take it for granted now that JS is reasonably fast, but I could be wrong.

I credit much of Chrome's success to V8. It's a marvel of engineering. Shame that the rest of Chrome hasn't been held to such a high standard.

Re:Mugo, a toy compiler for a subset of Go that can compile ... by josefx on Monday April 12, 2021 @10:31AM (#26779850)
> I simply assume that all browsers do this now because we take it for granted now that JS is reasonably fast, but I could be wrong.

Chrome came out a month after Mozilla published its TraceMonkey JIT. So JITing JavaScript has been the standard thing to do since the end of 2008.

Re:Mugo, a toy compiler for a subset of Go that can compile ... by KMag on Monday April 12, 2021 @01:33PM (#26782397)
... and TraceMonkey was based on open-sourced Macromedia/Adobe code from the ActionScript 3 VM. AS3 was loosely based on a draft of the ill-fated ES 4, but I'm not sure if it was a strict superset of an earlier ECMAScript standard. It's possible that the Flash AS3 VM had been JITing all of ES2 or ES3 earlier than TraceMonkey came out.