7 ms·

"it generated quite good machine code, almost as fast as the hand coded one" I'm sorry but this is complete bullshit. What is expected of a compiler these days

by oelang 12y ago

"it generated quite good machine code, almost as fast as the hand coded one" I'm sorry but this is complete bullshit. What is expected of a compiler these days (SSA, advanced instruction scheduling, smart inlining descisions) is not comparable with what the first optimizing compilers did.

kryptiskt 12y ago
The first Fortran competed with handcrafted code on extremely limited machines so it had to be almost as good to gain any traction. It did help that Fortran at that time was a barebones language so the translation was pretty straightforward. http://polaris.cs.uiuc.edu/publications/c1070.pdf http://polaris.cs.uiuc.edu/publications/c1070.pdf
- acqq 12y ago
  Thanks a lot kryptiskt. It's exactly the article I needed as the reference. For those who haven't seen what's behind your link, it's called "The FORTRAN I Compiler" and is written by David Padua in 2000. The must-read.
- cbsmith 12y ago
  It may have also helped that processor designs were also incredibly simple and the typical demands of a modern optimizer bear almost no resemblance to the demands of a compiler back then.
acqq 12y ago
If you want more modern comparison between what the article complains about and what's possible with the language which has GC, then look at this: Fabrice Bellard implemented the whole X86 emulator in JavaScript and with it it boots the Linux (measured on my machine and in my browser) in three seconds. The Linux kernel it boots is approximately 2 MB. http://bellard.org/jslinux/ http://bellard.org/jslinux/ Whereas Maxime Chevalier-Boisvert (the author of the article we all comment) compiles a = 0; a; a; … // (60000 times is a used) a; in four seconds with her D code. The program with no loops and one single variable, and just less than 200 KB of input.
- tachyonbeam 12y ago
  That is not a fair comparison at all. 1. An x86 emulator doesn't need to allocate much. It's probably an interpreter. It can parse x86 instructions straight from a byte vector, and use another byte vector for the RAM. 2. V8 and Firefox have much better garbage collectors than D, because they need their GC to be fast, and so they've made sure it is. 3. Higgs is a much more complex piece of software than this. 4. The 4 seconds time, as I pointed out, is at least 75% GC (but possiby more). That's the whole point of the blog post. It shouldn't be possible for the GC to take most of the execution time.
  - acqq 12y ago
    How many allocations do you actually make to compile a single variable used 60000 times? I still claim you don't have to allocate much too for that particular input, as long as you use vectors/arrays, the ones you also recognize Bellard probably uses and which I've mentioned in my top comment as the right way to make your code faster. It's really as simple as that.
    - bmm6o 12y ago
      Read the article, please. My implementation of a liveness analysis scales poorly with function size. It allocates a huge bit matrix (vector of bit sets) for liveness computation. This grows quadratically with the function size, which means that in some cases, obscene amounts of memory are required, and this data structure doesn’t fit in the cache
      - acqq 12y ago
        The "doesn't fit in the cache" argument has nothing to do with too many small allocations which obviously happen (otherwise GC effects wouldn't be noticeable) and which almost certainly can be replaced with much less allocations of some arrays of things. Which it what I suggest since my top comment.
        tachyonbeam 12y ago

by oelang 12y ago

kryptiskt 12y ago

The first Fortran competed with handcrafted code on extremely limited machines so it had to be almost as good to gain any traction. It did help that Fortran at that time was a barebones language so the translation was pretty straightforward. http://polaris.cs.uiuc.edu/publications/c1070.pdf http://polaris.cs.uiuc.edu/publications/c1070.pdf

acqq 12y ago
Thanks a lot kryptiskt. It's exactly the article I needed as the reference. For those who haven't seen what's behind your link, it's called "The FORTRAN I Compiler" and is written by David Padua in 2000. The must-read.
cbsmith 12y ago
It may have also helped that processor designs were also incredibly simple and the typical demands of a modern optimizer bear almost no resemblance to the demands of a compiler back then.

acqq 12y ago

If you want more modern comparison between what the article complains about and what's possible with the language which has GC, then look at this: Fabrice Bellard implemented the whole X86 emulator in JavaScript and with it it boots the Linux (measured on my machine and in my browser) in three seconds. The Linux kernel it boots is approximately 2 MB. http://bellard.org/jslinux/ http://bellard.org/jslinux/ Whereas Maxime Chevalier-Boisvert (the author of the article we all comment) compiles a = 0; a; a; … // (60000 times is a used) a; in four seconds with her D code. The program with no loops and one single variable, and just less than 200 KB of input.

tachyonbeam 12y ago
That is not a fair comparison at all. 1. An x86 emulator doesn't need to allocate much. It's probably an interpreter. It can parse x86 instructions straight from a byte vector, and use another byte vector for the RAM. 2. V8 and Firefox have much better garbage collectors than D, because they need their GC to be fast, and so they've made sure it is. 3. Higgs is a much more complex piece of software than this. 4. The 4 seconds time, as I pointed out, is at least 75% GC (but possiby more). That's the whole point of the blog post. It shouldn't be possible for the GC to take most of the execution time.
- acqq 12y ago
  How many allocations do you actually make to compile a single variable used 60000 times? I still claim you don't have to allocate much too for that particular input, as long as you use vectors/arrays, the ones you also recognize Bellard probably uses and which I've mentioned in my top comment as the right way to make your code faster. It's really as simple as that.
  - bmm6o 12y ago
    Read the article, please. My implementation of a liveness analysis scales poorly with function size. It allocates a huge bit matrix (vector of bit sets) for liveness computation. This grows quadratically with the function size, which means that in some cases, obscene amounts of memory are required, and this data structure doesn’t fit in the cache
    - acqq 12y ago
      The "doesn't fit in the cache" argument has nothing to do with too many small allocations which obviously happen (otherwise GC effects wouldn't be noticeable) and which almost certainly can be replaced with much less allocations of some arrays of things. Which it what I suggest since my top comment.
      - tachyonbeam 12y ago