compiled squeakjs

Hi,

Inspired by Bert's project, I started thinking about how to get Smalltalk compiled to Javascript instead of interpreted.
I do have previous experience in compiling Smalltalk to Java (after type inference, which we thankfully don't need
here). But, the requirements are a bit tighter here: we have to take an unknown image, get it translated on the fly,
completely automatically, and even allow the translated image to self-modify. Plus we cannot just decree that become:
cannot be used

Given that the input is an image, not sources, we'd better rely on the decompiler, so I started there. I think I fixed
it, so that it can now decompile everything correctly.
I also implemented a few AST transformations (similar to the ones that were necessary for Java, like normalizing the
various boolean constructs and making them statements).
I then started to write a Javascript pretty-printer, but I stopped when I realized that there were a few things missing:
while non-local returns and resumable exceptions can be implemented using exceptions and an explicit stack of handlers,
preemption (and Smalltalk's processes in general) were harder. After some research I came to the conclusion that this
was doable if, instead of doing a direct pretty-printing of the Smalltalk nodes to Javascript, we also used the
translation process to transform the code in continuation passing style. Then non-local returns become trivial and
preemption can be implemented with closures, without needing access to the underlying execution stack.
An interrupted context would have a no-arg closure representing the continuation instead of a pc. In general, only
preemption points (which all have a corresponding continuation closure) would have to be mapped, and this would happen
at image read time as well. The exception would be the debugger - I am not sure about that one yet.
The primitive code would be inlined in the primitive methods, followed by a preemption point and the failure code.
Unfortunately invocation would still not be direct, but looked up (and invoking DNU if needed), but I would store all
the translated methods directly in the class prototype, so there would be no need for explicit superclass chain lookup.
The instvars would also be stored directly in the class prototype (but with a prefix, to not conflict with the methods
or with reserved keywords), and they would be accessed directly (with dot notation), except for assignments, which would
record the owner (and the index in the owner), for all non-primitive types (not sure what to do about strings).
Every method (and formerly Smalltalk block closure) would have a single temp called "thisContext", which would be an
owner for the actual temps. The owners info would be used for implementing become: and allReferences.

The ProtoObject and Object methods coming from Smalltalk would be stored in Object.prototype. Proxy classes would have
their prototypes cleared and only contain the ProtoObject methods.
Primitive type classes would have to be massaged a little: Number would have a union of methods from the Smalltalk
Number subclasses, as well as the methods inherited from Magnitude.
String would also have the methods inherited from Collection and SequenceableCollection, as well as from Character (and
Magnitude) and Symbol - this one could be a little nastier, but I think it could be made to work.
I would also map Array to Array, IdentitySet to Set and IdentityDictionary to Map. Weak collections are harder, because
Javascript decided to make them not enumerable. Because of this, allInstances would also be a challenge.

I am not sure yet about the bootstrap process. I just have a fuzzy feeling that Craig's Context running under SqueakJS
might make it easier.

I hope this gives a general idea about the approach. Please do point out weaknesses that I may have missed. For me this
is fun and I will proceed slowly, as time permits, since I cannot do it at work.
Of course, I am very interested to hear Bert's opinion :)

Florin

Hi Florin,

On Jan 18, 2015, at 9:32 AM, Florin Mateoc <[hidden email]> wrote:



I like your approach, that if making everything work, not taking the simpe approach of translating what will work directly and disallowing the rest (as does Amber and Clamato etc).  You might want to talk to Ryan Macnak and Gilad Bracha about their Newspeak implementation above JavaScript (they're also doing one above Dart).

I do think Bert's approach is fun, too.  But I do feel extremely frustrated that no one is taking the obvious route of making a plugin to allow the Cog VM to be used directly, gaining much higher performance and reducing the number of execution platforms we have to support.

A plugin would use JavaScript to collect events, to render and to access the DOM (all of this code can be stolen from Bert's VM). The JavaScript component would connect to the VM via a socket.  The VM itself would be quite small (it's already only around a megabyte of executable).  For me arguments about the inconvenience and slowness of downloading and installing are not compelling given the ubiquity of Flash.  

And then there really is /no/ difference in the execution semantics, and /no/ performance degradation, and the code is as portable as Bert's VM provided Cig runs on the platform.

I'd be doing this myself if I weren't working on getting Spur released, getting 64-but Spur working, working with Clément on Sista and looking at hosting Cog over Xen.  Come on folks; someone out there must think this is useful and interesting.

> Florin

Hi Eliot,

On 1/18/2015 1:38 PM, Eliot Miranda wrote:

<snip>

> I like your approach, that if making everything work, not taking the simpe approach of translating what will work
> directly and disallowing the rest (as does Amber and Clamato etc). You might want to talk to Ryan Macnak and Gilad
> Bracha about their Newspeak implementation above JavaScript (they're also doing one above Dart).

Thank you for the reference to the Newspeak compilation to JavaScript, I might steal some ideas.

> I do think Bert's approach is fun, too.  But I do feel extremely frustrated that no one is taking the obvious route of making a plugin to allow the Cog VM to be used directly, gaining much higher performance and reducing the number of execution platforms we have to support.
>
> A plugin would use JavaScript to collect events, to render and to access the DOM (all of this code can be stolen from Bert's VM). The JavaScript component would connect to the VM via a socket.  The VM itself would be quite small (it's already only around a megabyte of executable).  For me arguments about the inconvenience and slowness of downloading and installing are not compelling given the ubiquity of Flash.  
>
> And then there really is /no/ difference in the execution semantics, and /no/ performance degradation, and the code is as portable as Bert's VM provided Cig runs on the platform.
>
> I'd be doing this myself if I weren't working on getting Spur released, getting 64-but Spur working, working with Clément on Sista and looking at hosting Cog over Xen.  Come on folks; someone out there must think this is useful and interesting.

Let's hope this gets accepted as a GSOC project

Florin

> As I understand it, running under NaCl requires reworking the JIT and
> has real problems doing the self-modifying code involved in inline
> caches, etc.

     Yep, you rebuild your app to use the NaCl instruction set, and it
translates to physical instructions on demand. The "safety" constraints
it places on the code you generate are substantial. If you were even
allowed to run the code you want, the performance goal would be demolished.

     But worse, you've also demolished the "run anywhere" goal from the
outset, by limiting yourself to browsers that support NaCl. And I don't
see how to meet this goal with any browser-plugin approach. There just
isn't a widely-supported mechanism anymore, after the death of the
Netscape-style plugin.


-C

--
Craig Latta
netjam.org
+31   6 2757 7177 (SMS ok)
+ 1 415  287 3547 (no SMS)

Hi Florin,

this sounds extremely interesting. In particular the part about using continuations to model execution flow, that thought had not occurred to me yet. Indeed, non-local returns and interruptability are the hardest to map to JS. I will have to think about this idea a while :)

SqueakJS does compilation, too, by now. It has a (very simple) JIT compiler that compiles bytecodes into equivalent JavaScript, on a method-by-method basis. Read the initial comment at
        https://github.com/bertfreudenberg/SqueakJS/blob/master/jit.js

To see it in action, open your browser's JS console and evaluate "SqueakJS.vm.method.compiled" which is the compiled version of the currently executing method. Or, if you're running a JS profiler, the generated methods will show up in that profile, too, and you can see their source.

This is not a high-performance JIT yet, but it helps a lot compared to the simple interpreter. Here's the numbers on Chrome's V8:
with JIT: 82315112 bytecodes/sec; 902155 sends/sec
no JIT:    2775850 bytecodes/sec; 137439 sends/sec

Also interesting - no JIT, before V8 deoptimization kicks in:
          11494252 bytecodes/sec; 523121 sends/sec
With the JIT, the code is more distributed, less polymorphic, so V8 can optimize better.

Beware microbenchmarks etc, but it pays hugely to make your code "friendly" for the JS VM. Amber for example, on the same machine in the same browser, reports '2214839.4241417497 bytecodes/sec; 229042.45283018867 sends/sec' even though it directly compiles to JavaScript and does not have full Smalltalk semantics (e.g. no real thisContext, no become). I suspect deoptimization in V8. Indeed, on FireFox it reports '3007518.796992481 bytecodes/sec; 408234.4251766217 sends/sec', which is roughly the same as SqueakJS (40327662 bytecodes/sec; 516034 sends/sec).

So since you're after the highest performance, it may pay off to do some experiments first.

Btw, here is a very interesting talk about how to make Smalltalk-style method invocation be fast on V8.
video: http://2014.jsconf.eu/speakers/vyacheslav-egorov-invokedynamic-js.html
slides: http://mrale.ph/talks/jsconfeu2014/

I did not fully understand your proposal about the object memory layout, and how become would work. Also, allInstances/weak refs and finalization isn't accounted for.

Do you intend this to be a fully compatible VM for Squeak? That was my goal with SqueakJS, performance being secondary (although not unimportant). SqueakJS does fully implement Squeak's execution semantics, including thisContext, non-local return, stack unwinding, DNU, process switching etc. and the object memory semantics too, including allObjects/allInstances, weak refs and finalization.

Your proposed mapping to JS Arrays/Maps etc. seems to imply that it would not be fully compatible, right? Rather a Smalltalk-for-the-web with fewer compromises than Amber? Or is this even only meant as a deployment step, not as a fully self-hosted development environment?

- Bert -

On 18.01.2015, at 18:32, Florin Mateoc <[hidden email]> wrote:

On 1/19/2015 10:37 AM, Bert Freudenberg wrote:
Hi Bert,

Thank you for the pointers, I will now have to go do some reading.

The idea for become: goes something like this (I know that standard WeakMaps are not enumerable, but given that
Google/Caja were apparently able to write a WeakMap shim without native support, I hope that code can be used as
inspiration to give us enumerable ones - this would also address the more general requirement for weak
collections/allInstances):
 
assignments, as well as the at:put: and instvarAt:put: primitives, add (if not already there) to the right-hand side
object a WeakMap property "owners". This happens only for non-primitive types. The keys are the owners and the values
are the indexes within the owner where the owned object lives. If there is already a previous object within the owner at
that index, the owner/index pair is removed from the previous object's owners.
At become: time, we iterate the owners and do the replacement


But to address the last part about compatibility:

Having gone through the experience of successfully migrating a huge Smalltalk application to Java (more than 2000
screens, many thousands of classes and millions of lines of code), I think of it as representative enough to be
confident in the general feasibility of the approach, even though we still do not have out of the box a fully automated
translation solution for every particular aspect (anyway, that was not the goal). Furthermore, one aspect of the
migration seemed pretty challenging: since this was an application already deployed in production at many (and vocal)
customers, we wanted to ensure a smooth transition and we did not just want the general functionality to be there but
essentially pixel-identical behavior for the Java incarnation. The original application also had proxies, a way of
applying patching in production, it included the compiler for runtime evaluation (both for patching, debugging and for
evaluating customer-specific scripts).
Now, we did not implement a Smalltalk vm on top of Java, so of course we did not fully implement Smalltalk (VA)
execution semantics. It turns out we did not need to. We achieved through automatic translation over 90% of the
functionality, including the (99%) pixel-identical presentation (we chose SWT as a target UI framework, since it mapped
closely to the original VA UI framework). For the rest we came up with ad-hoc solutions: we implemented something for
the proxies (taking advantage of the specific way they were used in the original application (so no general solution)),
we included the compiler and wrote a Java classloader for patching, we also wrote an inspector with Java runtime
evaluation capabilities. These last ones were just functionally equivalent (the evaluated snippets are Java, not
evaluating/translating on the fly Smalltalk scripts to Java - although that would have been fun). We reimplemented the
db communications layer to use JDBC.
All in all, this was a pragmatic approach and the application behaves the same and runs at the same speed as the
original, so from the point of view of the users, it is essentially the same.

This was a long-winded way of saying that I don't think exact execution semantics are that important. If you think the
pc in a context is part of Smalltalk's semantics, obviously the proposed approach does not address that. Even for a more
ambitious goal (we want to run (almost) any image, not just a specific one, even if huge and complex), I think this is a
place where one can cheat without being caught. Even allObjects/allInstances might not be required, especially that my
understanding is that the main purpose (other than debugging) for allInstances was to allow mutation. I don't think
mutation presents the same challenges in JavaScript.

Regarding mappings, of course one could write Smalltalk code that would catch us, but I think most "normal" usage
patterns could be covered. My goal would be a Smalltalk-for-the-web that could read and run almost any Squeak image (I
would not consider code purposely written to catch us cheating as a unveiling a bug, but I would consider any normal
usage pattern that would not work a bug), allowing self-hosted further development (with hooks for the Smalltalk
compiler to perform the same steps as the ones performed at image read time).


Florin

On Mon, Jan 19, 2015 at 6:21 AM, Craig Latta <[hidden email]> wrote:
>
>> As I understand it, running under NaCl requires reworking the JIT and
>> has real problems doing the self-modifying code involved in inline
>> caches, etc.
>
>      Yep, you rebuild your app to use the NaCl instruction set, and it
> translates to physical instructions on demand. The "safety" constraints
> it places on the code you generate are substantial. If you were even
> allowed to run the code you want, the performance goal would be demolished.

"Demolished" is probably a too strong word; The Mono JIT they ported
to NaCl only slowed down something like 7%.  (Not going through the
PNaCl layer but just x86 nacl code.)  So that is not that bad...
However,

>      But worse, you've also demolished the "run anywhere" goal from the
> outset, by limiting yourself to browsers that support NaCl. And I don't
> see how to meet this goal with any browser-plugin approach. There just
> isn't a widely-supported mechanism anymore, after the death of the
> Netscape-style plugin.

Yes, this is a real issue.  In that regard, asm.js has a better
chance, but still trying to stay on the JavaScript level, and taking
the advantage of JavaScript's JIT is a practical solution, even though
it may not give us the real Cog performance.

--
-- Yoshiki

> The Mono JIT they ported to NaCl only slowed down something like 7%.

     Well, it seems to me that Cog has higher performance aspirations
than Mono, and is probably doing even more interesting instruction abuse. :)

> ...asm.js has a better chance, but still trying to stay on the
> JavaScript level, and taking the advantage of JavaScript's JIT is a
> practical solution, even though it may not give us the real Cog
> performance.

     Yeah, I think I could live with what Florin and Bert are discussing
now.


-C

--
Craig Latta
netjam.org
+31   6 2757 7177 (SMS ok)
+ 1 415  287 3547 (no SMS)

On 1/19/2015 1:03 PM, Florin Mateoc wrote:
> The idea for become: goes something like this (I know that standard WeakMaps are not enumerable, but given that
> Google/Caja were apparently able to write a WeakMap shim without native support, I hope that code can be used as
> inspiration to give us enumerable ones - this would also address the more general requirement for weak
> collections/allInstances): assignments, as well as the at:put: and instvarAt:put: primitives, add (if not already
> there) to the right-hand side object a WeakMap property "owners". This happens only for non-primitive types. The keys
> are the owners and the values are the indexes within the owner where the owned object lives. If there is already a
> previous object within the owner at that index, the owner/index pair is removed from the previous object's owners. At
> become: time, we iterate the owners and do the replacement

And of course, if we did have enumerable WeakMaps, cleaning up of the previous owned object's owners does not need to
happen, we can just check if what the owner has at the index is still valid at the time of executing become: or
allReferences - this would move some pain to the right/less frequent place.

Unfortunately, the shim that I mentioned is a dead end - they just store, as a hidden property, each weakMap value in
the corresponding object used as its weakMap key, there is nothing stored in the weakMap itself to be iterated over.
I think it's a pity that, for some obscure security scenario, they (ECMAScript) cripple an otherwise very useful
feature. They could have offered a secure, non-enumerable version of weak collections in addition to an enumerable one
for situations where it does not matter. Oh well, back to the drawing board (or to Bert's object layout :) )

Florin

On 20.01.2015, at 08:25, Florin Mateoc <[hidden email]> wrote: Yep. Working around the lack of weak collections in JavaScript was why I had to come up with my own memory model. I couldn't simply adopt Dan's, who used a Java weak array in JSqueak/Potato.

I briefly got excited about the new WeakMap support in ES6, but as you discovered, without enumeration they are much weaker (pun intended) than what we have in Smalltalk. At first I thought they were completely useless, since the same could be achieved by adding a property to each object. But beyond that you can bulk-empty the WeakMap, being equivalent to removing that property from all those objects. So essentially WeakMaps are useful as caches that can easily be invalidated. I cannot think of another application.

The *reason* for designing WeakMaps in such a limited way is that the ECMAScript committee thinks garbage collection should be unobservable. No expression in the language should depend on the state of the GC. This gives implementers of the language a lot more freedom in designing their VM.

SqueakJS's "become" is pretty expensive, as is "allObjects". For "allInstances" it depends on whether there are instances in New Space, if not, it's much cheaper. My rationale for that is that these operations are expensive traditionally, so the class library has been designed to avoid them where possible (e.g. OrderedCollection delegating to an array instead of being an array). With Spur making "become" cheap, we may see this stuff sneak back in, and would have to re-evaluate the trade-offs.

For your case, since you're mainly interested in porting a specific application, I think reference counting might work. This would make write-operations more expensive (but you already said that you're willing to pay that), but the cost would be spread over time. In contrast, SqueakJS does no checks at all on writing, making the general case be fast, but paying for that with a pause of a couple hundred milliseconds when it needs to walk the full object memory (e.g. for become).

- Bert -

On 20.01.2015, at 08:25, Florin Mateoc [hidden email] wrote:

On 1/19/2015 1:03 PM, Florin Mateoc wrote:

The idea for become: goes something like this (I know that standard WeakMaps are not enumerable, but given that
Google/Caja were apparently able to write a WeakMap shim without native support, I hope that code can be used as
inspiration to give us enumerable ones - this would also address the more general requirement for weak
collections/allInstances): assignments, as well as the at:put: and instvarAt:put: primitives, add (if not already
there) to the right-hand side object a WeakMap property "owners". This happens only for non-primitive types. The keys
are the owners and the values are the indexes within the owner where the owned object lives. If there is already a
previous object within the owner at that index, the owner/index pair is removed from the previous object's owners. At
become: time, we iterate the owners and do the replacement

And of course, if we did have enumerable WeakMaps, cleaning up of the previous owned object's owners does not need to
happen, we can just check if what the owner has at the index is still valid at the time of executing become: or
allReferences - this would move some pain to the right/less frequent place.

Unfortunately, the shim that I mentioned is a dead end - they just store, as a hidden property, each weakMap value in
the corresponding object used as its weakMap key, there is nothing stored in the weakMap itself to be iterated over.
I think it's a pity that, for some obscure security scenario, they (ECMAScript) cripple an otherwise very useful
feature. They could have offered a secure, non-enumerable version of weak collections in addition to an enumerable one
for situations where it does not matter. Oh well, back to the drawing board (or to Bert's object layout :) )

Yep. Working around the lack of weak collections in JavaScript was why I had to come up with my own memory model. I couldn't simply adopt Dan's, who used a Java weak array in JSqueak/Potato.

I briefly got excited about the new WeakMap support in ES6, but as you discovered, without enumeration they are much weaker (pun intended) than what we have in Smalltalk. At first I thought they were completely useless, since the same could be achieved by adding a property to each object. But beyond that you can bulk-empty the WeakMap, being equivalent to removing that property from all those objects. So essentially WeakMaps are useful as caches that can easily be invalidated. I cannot think of another application.

Well, they also work as an "alreadySeen" collection for recursive operations.

The *reason* for designing WeakMaps in such a limited way is that the ECMAScript committee thinks garbage collection should be unobservable. No expression in the language should depend on the state of the GC. This gives implementers of the language a lot more freedom in designing their VM.

I am not sure I understand this argument. Indeed, as they say, enumerating weak collections introduce some indeterminism. So what? Does that make Smalltalk or Java programs in general less deterministic than JavaScript ones? Obviously one has to take care and work around the possibility that something might or might not be there, but this is not such a unique situation in programming. As for the vm implementors, I wouldn't know, but did actually implementing weak references make the vms (various Smalltalk, Java, ActionScript...) take a hit in general performance or complexity?

I think they only thing they "really" cared about was something about security (this is Mark Miller we are talking about :) ):
"This is necessary to prevent attackers observing the internal behavior of other systems in the environment which share weakly-mapped objects. Should the number or names of items in the collection be discoverable from the API, even if the values aren't, WeakMap instances might create a side channel where one was previously not available."

And I don't think this argument holds water, especially since, as I said, they could have offered both secure and unsecure versions.

Florin