Re: [squeak-dev] compiled squeakjs

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Eliot Miranda-2

Hi Florin,

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

> 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 :)



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
Reply | Threaded
Open this post in threaded view
|

re: compiled squeakjs

ccrraaiigg
 

> Come on folks; someone out there must think this is useful and
> interesting.

     Well, like a lot of things, I think everyone considers the result
useful and interesting, but the work to get there tedious. :)


-C

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

Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Florin Mateoc-4
In reply to this post by Eliot Miranda-2
 
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



Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Florin Mateoc-4
In reply to this post by Eliot Miranda-2
 
Hi Eliot,

Thank you for pointing me to this project (in particular to NS2V8).

I have just read Ryan's post "Update on compilation to Dart and JavaScript" and I have a couple of questions:



Ryan,

Can you please explain what you do for initialization (especially for large arrays, sets, etc)? Assuming that Newspeak also has something like Smalltalk's nil, do you fill them at creation time with nil?
I was thinking of avoiding that and testing the receiver at every invocation for JavaScript's undefined instead. Of course, this just moves the pain point, I am not sure which is better. Also, the test for nil can be avoided when the receiver is "this" or "super" or some literal - one can optimize this even in other cases with some static analysis.

I also don't understand the line:
"NS2JS and NS2V8 both map Newspeak's basic types onto JavaScript's basic types by installing functions on the prototypes of Number, String, etc. We apply strict mode, so these functions do not operate on boxed values."

E.g. the following snippet works:

"use strict"
Number.prototype.test = function() {return 5};
var n = 2;
n.test()

So what does it mean that "these functions do not operate on boxed values"?


Thank you,
Florin
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Ryan Macnak
In reply to this post by Eliot Miranda-2
 
On Sun, Jan 18, 2015 at 10:38 AM, Eliot Miranda <[hidden email]> wrote:
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.

I thought there were already a few projects that attached a Squeak VM to NaCl.
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Ryan Macnak
In reply to this post by Florin Mateoc-4
 
On Sun, Jan 18, 2015 at 12:59 PM, <[hidden email]> wrote:
Ryan,

Can you please explain what you do for initialization (especially for large arrays, sets, etc)? Assuming that Newspeak also has something like Smalltalk's nil, do you fill them at creation time with nil?

We eagerly assign nil to all slots. For regular objects, it is important that slots for a given class are always initialized in the same order, otherwise a JS engine like V8 won't consider all the instances to be of the same Map (hidden class), things will seem more polymorphic than they are, and optimizations won't happen. For arrays, I don't know whether this is more harmful to performance because we pollute type data about the array's elements with UndefinedObject or this is more helpful because we don't need checks for undefined in #at:. Certainly in terms of implementation effort, eager initialization is much better than sprinkling checks in all the places that access slots.
 
I was thinking of avoiding that and testing the receiver at every invocation for JavaScript's undefined instead. Of course, this just moves the pain point, I am not sure which is better. Also, the test for nil can be avoided when the receiver is "this" or "super" or some literal - one can optimize this even in other cases with some static analysis.

We do very little static analysis beyond the standard cheats for #ifTrue: and friends. Generally, it makes implementing reflection much more difficult. dart2js is a good example of a compiler with this problem.

I also don't understand the line:
"NS2JS and NS2V8 both map Newspeak's basic types onto JavaScript's basic types by installing functions on the prototypes of Number, String, etc. We apply strict mode, so these functions do not operate on boxed values."

E.g. the following snippet works:

"use strict"
Number.prototype.test = function() {return 5};
var n = 2;
n.test()

So what does it mean that "these functions do not operate on boxed values"?

When the function test is not in strict mode, every invocation requires the allocation of a number object to use as the receiver. In strict mode, the receiver is the number value directly. (ECMAScript 5.1 10.4.3)

Ryan
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Eliot Miranda-2
In reply to this post by Ryan Macnak
 


On Sun, Jan 18, 2015 at 4:17 PM, Ryan Macnak <[hidden email]> wrote:
On Sun, Jan 18, 2015 at 10:38 AM, Eliot Miranda <[hidden email]> wrote:
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.

I thought there were already a few projects that attached a Squeak VM to NaCl.

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.  I want something that doesn't involve running under a managed run-time (the VM is a managed run-time, layering two on top of each other has always seemed like a poor choice to me).  And if NaCl made it really easy to do why haven't any of these projects delivered yet?

--
best,
Eliot
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Florin Mateoc-4
In reply to this post by Ryan Macnak
 
Hi Ryan,

Thank you for your prompt reply,

On 1/18/2015 7:26 PM, Ryan Macnak wrote:

<snip>

> So what does it mean that "these functions do not operate on boxed values"?
>
> When the function test is not in strict mode, every invocation requires the allocation of a number object to use as
> the receiver. In strict mode, the receiver is the number value directly. (ECMAScript 5.1 10.4.3)
>
> Ryan


Ah, ok, so you meant that by using strict mode, "these functions" operate more efficiently for primitive values, not
that they do not work

Florin
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] compiled squeakjs

Florin Mateoc-4
In reply to this post by Ryan Macnak
 
Sorry, I forgot to mention something:

On 1/18/2015 7:26 PM, Ryan Macnak wrote:
 


On Sun, Jan 18, 2015 at 12:59 PM, <[hidden email]> wrote:
Ryan,

Can you please explain what you do for initialization (especially for large arrays, sets, etc)? Assuming that Newspeak also has something like Smalltalk's nil, do you fill them at creation time with nil?

We eagerly assign nil to all slots. For regular objects, it is important that slots for a given class are always initialized in the same order, otherwise a JS engine like V8 won't consider all the instances to be of the same Map (hidden class), things will seem more polymorphic than they are, and optimizations won't happen. For arrays, I don't know whether this is more harmful to performance because we pollute type data about the array's elements with UndefinedObject or this is more helpful because we don't need checks for undefined in #at:. Certainly in terms of implementation effort, eager initialization is much better than sprinkling checks in all the places that access slots.
 

There is no need to check for undefined in #at:, or in any place that just references slots. Undefined can be assigned and passed around in general. The only checks needed are for receivers at invocation time (and even those can be sometimes avoided), and then (if receiver is undefined) delegate to the UndefinedObject instance

Florin
Reply | Threaded
Open this post in threaded view
|

Re: compiled squeakjs

Bert Freudenberg
In reply to this post by Eliot Miranda-2
 
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:

> 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




smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [squeak-dev] re: compiled squeakjs

Yoshiki Ohshima-3
In reply to this post by Eliot Miranda-2
 
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
Reply | Threaded
Open this post in threaded view
|

Re: compiled squeakjs

Bert Freudenberg
In reply to this post by Bert Freudenberg
 
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.

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 -


smime.p7s (5K) Download Attachment