Stalin: a global optimizing compiler for Scheme

One aggressive optimization that differentiates Stalin (no pun intended, ref StalinGrad) somewhat, is its inlining of callbacks. For example a generic numeric multidimensional integral library would take a callback that implements the function that needs to be integrated. This function is typically computed several hundreds of thousands of times in a very tight hot loop incurring a call overhead on each one. In a C library such callbacks cannot be inlined as it is compiled ahead of time. The whole program analysis paradigm helps a lot in determining the callback function and inlining it in place, this triggers more opportunities for more conventional optimizations.

I think a lot of this can be done now with C++'s template metaprogramming, or in fact using D's CTFE which is quite a pleasure to use. Had Java been not so broken for numeric stuff, its late inlining facilities would have helped too. I have played with this a long time ago and at that time nothing I tried, (not even Fortran) could match it for the same algorithm. Although my fortran would have left a lot to be desired. I had very little idea about what I was doing with the piece of Fortran code.

There is a Fortran name for what I was using, it eludes me now, but the integrator was essentially a coroutine which would yield control to the function computer and resume integrating once it was computed. Its quite amazing that Fortran has coroutine facilities, they call it something else.

EDIT:

Java is not smart about using SSE and such SIMD instructions, this is really a pity. C#, F# are better about this unfortunately its a Microsoft only thing, yes I am aware of Mono. The other problem is that JAVA is over specified. Java compilers have very little room to maneuver. For example arguments of a function are supposed to be evaluated left to right, there goes an opportunity for low level parallelization. C compilers makes no such guarantees and can in principle parallelize such instances. The other problem is that unless one uses low level loops, Java produces just way too many temporaries which on one hand stresses the garbage collector and on the other wastes time instantiating and filling the temporaries only to be garbage collected away. In Java the only form of polymorphism is runtime polymorphism via virtual functions. Compile time polymorphism can be a lot more efficient. For example if accessing (i,j)th entry of matrix is a virtual function that all but ensures that your FLOPS will sink like a stone. Have it as a CRTP in C++ all that will get inlined, and if you are lucky unrolled and then SIMD'ized. That said Java numerics has improved quite a bit lately.

Regarding C's whole program analysis, my comment was about the state of the affairs then, but even now owing to the semantics of the language whole program analysis in C is orders of magnitude more difficult than in Functional languages. The latter has much more semantic information to play with. This was supposed to be mitigated some with the introduction of __restrict__ but it did not quite deliver on the promise. But cat'ing the entire code to one file and compiling it does definitely speed up the runtime, poor man's whole program analysis ! Now you do have support for whole program analysis and link time optimization that this is no longer such a necessity.

You could have a look at Siskind's paper, Flow-Directed Lightweight Closure Conversion. Warning, it's not exactly light reading:

  ftp://ftp.ecn.purdue.edu/qobi/fdlcc.pdf

Although the subject is nominally closure conversion, he describes how flow analysis is used to propagate information about values around the compiler's model of the program. Because the analysis is on a whole program basis it need not be very conservative - in a whole program compiler you never have to give up and do something the slow way because a value might be used in a place you can't see.

This aggressive flow analysis gives the compiler enough information to pick nice flat C-like representations, inline objects inside other objects, use more specialised calling conventions, etc.

For example, a whole program compiler might determine that the elements of an array are never compared with eq or have their mutable parts assigned to, which could allow the elements to be inlined into the array. Doing this is tough or impossible in a traditional compiler because the contents of files that have yet to be compiled is unknown, forcing the compiler to assume the worst.

Pretty neat stuff.

The closest is probably MLton, a compiler for Standard ML.

According to this blog post from 2009[0], it was slightly faster than C compiled with the GCC and almost 15x faster than Chicken Scheme. I have tried looking for more rigorous benchmarks but have been unable to find any.

[0] http://justindomke.wordpress.com/2009/02/23/the-stalin-compi...

Is there anyway you, or some other moderator, could repost this in an environment that allows a proper discussion? Something like enabling the "pending comments" system.

Excuse me a moment. You can say that "indignation about the name is off topic", that doesn't make it so. You are twisting language to suit your whims.

If you had the guts you could say that indignation about the name is not welcome, or will be censored, or is a distraction and an uninteresting subject here on HN. But the project has a name, and the connotations of that name are relevant, as with every project. If the project were named "the impeach obama compiler" or "darren wilson" or "gas the jews" the idea that issues related to the name were "off topic" would be even less tenable than it is now.

I enjoy the maturity of the commenters on HN, and of the mods as well. But please have the intellectual honesty and backbone to be upfront about what you're doing.

Downvoted for this? Thankless job indeed.

Thank you.

(I will say, substantive discussion for a topic like this seems hard. The people really interested in this are those who haven't heard of it, which means they will have little input. From what I've seen, topics like this usually grow slowly as experienced people post interesting anecdotes or general PL tangents, and others hop on).

That's transliterated Hebrew. The first one means "The world and everything in it belongs to God", the second "The end, praise God, creator of the world."

No idea why they are there.

One person's political correctness is another's "that man murdered my wife's great grandfather."

Yes, really. "And you lynch negroes" notwithstanding. (And, yes, I'm also that guy who is more than happy to puncture American propagandistic historiography.)

Yeah, that's the Homo-Iconic Templating Language for ERlang.

It's geek sociopathy at its finest. Or maybe that's the "Oh, come on, stop talking about the deliberately chosen name that could have been anything else and talk about the technical details!" attitude.

It's especially farcical given that without the name and the resulting offended people, butthurt Russians, and random assholes yammering about "political correctness", this post would have probably never made the front page.

The name is a joke, from wikipedia, "Stalin brutally optimizes". Very much true. You know, it would be quite an undertaking to find russian tech guys offended by this name.

And I've also found https://github.com/n4kz/stalin.js by a russian guy - Joseph Stalin => stalin.js - Badass mustache compiler

In the "name" of millions and millions and millions of dead and those brainwashed through terror, I gotta say no, don't relax. It's not funny in the least.

Naming something, even in jest, after one of the most vicious mass murderers in human history is just shameful. Most historians agree that Stalin is responsible for 20 to 60 million non-wartime deaths.

Making jokes about any mass murderer trivializes their victims.

just wait until I unveil my Caliphate static analysis tool next week

SBCL doesn't currently have whole-program optimization. Its focus has been on standard Common Lisp, which is quite dynamic and can't make the kind of closed-world assumption used by whole-program optimization (i.e. we know the entire program at compile-time). It has quite a lot of optimizations, but they operate function-at-a-time.

Its predecessor, CMUCL, did have a mode called "block compilation" that has some similarities: http://common-lisp.net/project/cmucl/doc/cmu-user/compiler-h.... It isn't currently present in SBCL; it was axed as part of the CMUCL->SBCL cleanup. I've occasionally heard suggestions of adding similar functionality to SBCL, but I'm not sure there's any active work on it.

> The man committed genocide and numerous other crimes against humanity.

the amerikan founding fathers have committed acts of genocide (and numerous other crimes) against Native Americans and Africans and yet someone decided it would be a good idea to print them on dollar bills

It is even less appropriate in the light of the fact that Stalin was one of the most brutally incompetent tyrants ever.

There's plenty of bad taste wandering around Purdue's campus. Most recently, multiple professors were criticized for joking about the Cousins shooting as it was happening.

This is 8 years old.