js/src/vm

[Luke Wagner]

In bug 644074 (just landed) I added a dir 'vm' in js/src that is
currently only inhabited by a Stack{.cpp,.h,-inl.h} triplet. In comment
0 of the bug I mentioned why I added a dir vs. just adding the files to
js/src. I also discussed this with random people and got positive
feedback, so I'm emboldened to mention it here for broader feedback and
perhaps agreement.

What I'm hoping is that js/src/vm can be a place to collect
{.cpp,.h,-inl.h} triplets where each triplet describes a cohesive
VM-wide (independent of execution mode) data-structure and its primitive
types/operations. Other examples that come to mind:
- the string hierarchy and the 3 or so non-inline operations in jsstr.cpp
- values
- property tree + shape + low-level JSObject operations (which Brendan
already wanted to reflow)
- high-level generic JSObject operations (thereby perhaps cleaving
JSObject)
- each one of these typed object specializations that Nick/Waldo have
been extruding (e.g. GlobalObject)

By "cohesive", the hope would be that each triplet's header would act
like a (very poor man's) module interface that all external C++ code
went through. JIT code tends/needs to break every such C++ abstraction,
but at least the JIT can nominally claim to "simulate" or "open code"
specific operations in vm and refer to greppable named constants in the
C++ interface (as has been the precedent with StackFrame::offsetOfX()).

With this perspective, code that would not be in vm would be:
- compilation/execution modes (which seem to be getting their own dirs
anyway)
- library natives (which perhaps deserve their own 'stdlib' dir?)

One last minor comment on the grouping/division of types by file:
David and Waldo raised the very reasonable question of whether
js::StackFrame should be in its own file rather than in vm/Stack.h (its
big). My reasoning for not wanting to is that FrameRegs + StackFrame +
StackSegment + StackSpace + *FrameGuard altogether form a single logical
data structure which I'd like to present as a whole (hence the new
unified stack layout comment at the top of Stack.h). (This perspective
was stolen from John Lakos' "Large Scale C++ Design". The same
perspective shows up in math as many-sorted algebra so its not just C++
crazy-talk :) I mention this since the question may come up again (I
can see at least one example in the list above).

[Brendan Eich]

Nice. We should have a strawman we agree with on other subdirs:

- vm
- parser (includes lexer, bulids ASTs)
- bytecode (emitter, decompiler, utilities)
- tracejit
- methodjit

Or something like this. Any such strawman already mooted?

/be

> _______________________________________________
> dev-tech-js-engine-internals mailing list
> dev-tech-js-en...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-tech-js-engine-internals

[Bill McCloskey]

I think it makes sense to have a gc directory as well.

[Luke Wagner]

These all sound great to me.

[Brendan Eich]

Ok, how about a metabug to track doing this? Can't wait to lose the js8.3 names!

/be

[Brendan Eich]

On Apr 26, 2011, at 3:27 PM, Bill McCloskey wrote:

> I think it makes sense to have a gc directory as well.

Definitely -- my list was not exhaustive -- bhackett may have an addition, not sure.

/be

[Steve Fink]

I'd like to propose a slightly different setup. At a top level:

- crazy_stuff/
- really_crazy_stuff/
- dragons/

Each toplevel directory would have subdirectories:

- TOPLEVEL/undocumented/
- TOPLEVEL/documented_properly/
- TOPLEVEL/documented_improperly/
- TOPLEVEL/documented_properly_but_unintelligibly/

We can make a toplevel documentation_status/ with the same subdirs
populated with symlinks to all the relevant files if people would like.
Finally, there'd be one more tree rooted at the toplevel:

- org/mozilla/www/.org.mozilla.www/

containing READMEs, test cases, specs, and tutorial videos (in a flat
directory; no subdirectories here to keep things simple.)

I think that covers all the bases. Who's with me?

On 04/26/2011 03:27 PM, Bill McCloskey wrote:
> I think it makes sense to have a gc directory as well.
>

> ----- Original Message -----
>> Nice. We should have a strawman we agree with on other subdirs:
>>
>> - vm
>> - parser (includes lexer, bulids ASTs)
>> - bytecode (emitter, decompiler, utilities)
>> - tracejit
>> - methodjit
>>
>> Or something like this. Any such strawman already mooted?
>>
>> /be

[Brendan Eich]

LOL -- but srsly, this is a bikeshed we need to paint. Our current lumpy, overgrown structure is like some medieval church with a skyscraper and two power plants grafted on. There's no reason we shouldn't incrementally reform filenames and directory structure (according to an agreed-upon plan) just as we do code within files.

One thing you may be poking fun at, where I agree completely: deep (esp. Java's reverse-DNS) naming hierarchies are losers. Remember the Zen of Python (the Good Parts):

Explicit is better than implicit.
...
Flat is better than nested.
Sparse is better than dense.
Readability counts.
...
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
...
Now is better than never.
Although never is often better than *right* now.
...

/be

[Steve Fink]

Sorry, I didn't actually mean to poke fun. I'm totally in favor of the
new organization.

(I've just spent too long today trying to get this test case to work,
and my brain spontaneously popped out that post in an effort to save
itself. I'll try to tighten down the latches before it strikes again.)

[Brian William Hackett]

I think the inference and analysis stuff would work OK split between vm/ and bytecode/ --- vm/ for core data structures describing types of variables/objects/properties (this is where js::Object etc. would live, right?), bytecode/ for the actual bytecode analysis being performed.

Brian

----- Original Message -----

> On Apr 26, 2011, at 3:27 PM, Bill McCloskey wrote:
>
> > I think it makes sense to have a gc directory as well.
>

> Definitely -- my list was not exhaustive -- bhackett may have an
> addition, not sure.
>
> /be
>
> >

[Luke Wagner]

At the risk of sounding like a wimp, I'd kindof like to proceed
incrementally, hoisting some initial triples that have recently been
worked-over (values, strings, these new object classes if Waldo likes
the idea) and hoisting additional triples as they get attention.

Having an official Plan of Record (perhaps a wiki page) sounds good
though to guide this incremental transition.

> Ok, how about a metabug to track doing this? Can't wait to lose the js8.3 names!
>
> /be
>
> On Apr 26, 2011, at 4:00 PM, Luke Wagner wrote:
>
>> These all sound great to me.
>>

>>> I think it makes sense to have a gc directory as well.
>>>

[Brendan Eich]

On Apr 26, 2011, at 4:40 PM, Luke Wagner wrote:

> At the risk of sounding like a wimp, I'd kindof like to proceed incrementally, hoisting some initial triples that have recently been worked-over (values, strings, these new object classes if Waldo likes the idea) and hoisting additional triples as they get attention.

Yeah, I wasn't saying we fix everything all at once and urgently. Incremental is the watchword. But the plan of record needs recordation.

> Having an official Plan of Record (perhaps a wiki page) sounds good though to guide this incremental transition.

Is wiki better than bug? Dunno, not sure.

/be

[Brendan Eich]

The standard library implementations, beyond Object and Function and Proxy, could go in vm, or they could go in a separate subdir (stdlib? yech). Not sure about this one, can play it by ear.

/be

On Apr 26, 2011, at 4:35 PM, Brian William Hackett wrote:

> I think the inference and analysis stuff would work OK split between vm/ and bytecode/ --- vm/ for core data structures describing types of variables/objects/properties (this is where js::Object etc. would live, right?), bytecode/ for the actual bytecode analysis being performed.
>
> Brian
>
> ----- Original Message -----
>> On Apr 26, 2011, at 3:27 PM, Bill McCloskey wrote:
>>

>>> I think it makes sense to have a gc directory as well.
>>

>> Definitely -- my list was not exhaustive -- bhackett may have an
>> addition, not sure.
>>
>> /be
>>
>>>

>>> ----- Original Message -----
>>>> Nice. We should have a strawman we agree with on other subdirs:
>>>>
>>>> - vm
>>>> - parser (includes lexer, bulids ASTs)
>>>> - bytecode (emitter, decompiler, utilities)
>>>> - tracejit
>>>> - methodjit
>>>>
>>>> Or something like this. Any such strawman already mooted?
>>>>
>>>> /be
>>

[Luke Wagner]

On 04/26/2011 04:41 PM, Brendan Eich wrote:
> On Apr 26, 2011, at 4:40 PM, Luke Wagner wrote:
>
>> At the risk of sounding like a wimp, I'd kindof like to proceed incrementally, hoisting some initial triples that have recently been worked-over (values, strings, these new object classes if Waldo likes the idea) and hoisting additional triples as they get attention.
>
> Yeah, I wasn't saying we fix everything all at once and urgently. Incremental is the watchword. But the plan of record needs recordation.

Oops, sorry, didn't mean to put words in your mouth. Recordation agreed.

>> Having an official Plan of Record (perhaps a wiki page) sounds good though to guide this incremental transition.
>
> Is wiki better than bug? Dunno, not sure.

I'm about to be out for a week, but I'll take a first stab if no one
does first. This sounds like overkill as I type it but... since I want
properties of a wiki and bugzilla, I was thinking of making a wiki page
to host the official Plan of Record and filing a meta bug to track the
incremental-hoisting bugs as they pop up.

[Jeff Walden]

On 04/26/2011 07:42 PM, Brendan Eich wrote:
> The standard library implementations, beyond Object and Function and Proxy, could go in vm, or they could go in a separate subdir (stdlib? yech). Not sure about this one, can play it by ear.

Yeah, we should do this, in a separate subdirectory; I've wanted to do it for awhile, separate nitty-gritty implementation details of strings and stuff from String and its methods and all. stdlib works but is kinda meh, builtins might perhaps work as well.

Jeff

[Luke Wagner]

Filed bug 653057
Started wiki page (still pretty incomplete): http://wiki.mozilla.org/JS_engine_modularization

On Apr 26, 2011, at 4:40 PM, Luke Wagner wrote:

> At the risk of sounding like a wimp, I'd kindof like to proceed incrementally, hoisting some initial triples that have recently been worked-over (values, strings, these new object classes if Waldo likes the idea) and hoisting additional triples as they get attention.
>

> Having an official Plan of Record (perhaps a wiki page) sounds good though to guide this incremental transition.
>

>> Ok, how about a metabug to track doing this? Can't wait to lose the js8.3 names!
>>
>> /be
>>
>> On Apr 26, 2011, at 4:00 PM, Luke Wagner wrote:
>>
>>> These all sound great to me.
>>>

>>>> I think it makes sense to have a gc directory as well.
>>>>

[David Herman]

Pardon the pedantry, but it seems un-JavaScript-y to call it a "method JIT" -- there's nothing special about methods in JS. Isn't the method JIT really just a function JIT? I'm not trying to police anyone's speaking habits or anything, but putting a top-level directory called "methodjit" in a JS engine seems kinda gauche. funjit? basejit?

Dave, paintbrush in hand

[David Mandelin]

On 4/27/2011 9:25 AM, David Herman wrote:
> Pardon the pedantry, but it seems un-JavaScript-y to call it a "method JIT" -- there's nothing special about methods in JS. Isn't the method JIT really just a function JIT? I'm not trying to police anyone's speaking habits or anything, but putting a top-level directory called "methodjit" in a JS engine seems kinda gauche. funjit? basejit?

As a compiler implementer, I don't even know what the difference between
a method and a function is. :-) But I get your point.

For new names, keep in mind that we will be getting more function JITs,
and we don't know exactly what the baseline JIT will be, or what that
even means. IonMonkey is going to add an optimizing function JIT and
probably a profiling JIT as well. I guess those might be optjit and
profjit, so both funjit and basejit seem still open.
> Dave, paintbrush in hand
I was going to bikeshed a bit on "builtins" vs. "runtime", but the spec
has a chapter called "ECMAScript Standard Built-in Objects", so builtins
seems good after all.

Dave

[Boris Zbarsky]

On 4/27/11 12:25 PM, David Herman wrote:
> funjit? basejit?

basejit seems more accurate in terms of what it's trying to do.

superhappyfunjit would be nice to have on general principle, though!

-Boris

[Nicholas Nethercote]

On Wed, Apr 27, 2011 at 8:18 AM, Luke Wagner <l...@mozilla.com> wrote:
>
> One last minor comment on the grouping/division of types by file:
> David and Waldo raised the very reasonable question of whether
> js::StackFrame should be in its own file rather than in vm/Stack.h (its
> big).  My reasoning for not wanting to is that FrameRegs + StackFrame +
> StackSegment + StackSpace + *FrameGuard altogether form a single logical
> data structure which I'd like to present as a whole (hence the new unified
> stack layout comment at the top of Stack.h).  (This perspective was stolen
> from John Lakos' "Large Scale C++ Design".  The same perspective shows up in
> math as many-sorted algebra so its not just C++ crazy-talk :)

That bit in parentheses sounds impressive but I have no idea what it
means. Can you elaborate just a little bit? :)

Nick

[Luke Wagner]

I assume you mean "many-sorted algebra" and not any of the other bits in parens? I'll hazard an answer, knowing full well that there are at least three PhDs on the list who know a lot more about this than I do and may smite my answer with truth. (I'm at a layover in Hong Kong -- be gentle :)

A single-sorted algebraic "structure" is something like a monoid, group, ring, field, etc: an abstract domain with a collection of operations (over this domain) and axioms that the operations must satisfy (e.g., distributivity, associativity, commutativity, etc). A single-sorted "algebra" implements a structure by picking a particular domain and set of operations that satisfy the axioms of the structure. (For example, the ring structure specifies an abstract + and * with a couple of axioms (associativity of +, distributivity, inverse for + and *, etc); the integers with arithmetic + and * are an algebra).

An important idea about all this is that, when you prove things about an algebraic structure, the proof is expressed only in terms of the declared operations/axioms of the structure, and not the particular details of any one algebra, so your theorem holds for all algebras of that structure. Now this starts to sound like abstract data types in computer science (s/structure/public interface/, s/axioms/specification/, s/algebra/concrete class/) and we can see that abstract algebraists are kinda like programmers who really really like reusable code.

A many-sorted structure/algebra is just the extension of the concept that can have more than one domain (thus, the operations can include more than one domain in their signature). An example is a vector space (which has a domain of scalars and a domain of vectors).

So then what's the correspondence of these multi-sorted structures/algebras in programming? Classes/interfaces (of mainstream OOP languages) associate all operations with a single domain of values. I have little doubt there exist languages which solve the problem directly. We can hack multi-sorted-ness in C++ while maintaining some semblance of interface/implementation separation by just having multiple classes (one per domain) and making them all friends of each other. Then there is the question as to how to distribute the operations between the classes (or perhaps as non-member functions), but unless you want runtime polymorphism (which requires something like multi-methods), it's a question of aesthetics.

I mentioned this originally because recognizing many-sorted algebras as a peer concept to single-sorted algebras helps to avoid a design mindset of "every class must be its own encapsulated island" which I feel can be detrimental when trying to modularize complex data structures like we have in SpiderMonkey. The Stack was one example; I think low-level objects + property tree will be another.

I hope that somewhat explains my admittedly-terse parenthetical :)

-Luke

[Jason Orendorff]

On 4/27/11 7:44 PM, Luke Wagner wrote:
> I hope that somewhat explains my admittedly-terse parenthetical :)

This was quite a nice explanation, and a lovely thing to read over my
morning coffee.

Mind if I blit it into my blog?

-j

[Paul Biggar]

I'm loving these tidy-ups, but can I request a tiny comment at the top
of new files, explaining what the file does in a sentence or two (even
if it's obvious)?

I'd love to request a README saying what each directory does, but the
names are thus-far self-explanatory.

On Tue, Apr 26, 2011 at 16:00, Luke Wagner <l...@mozilla.com> wrote:
> These all sound great to me.
>
>> I think it makes sense to have a gc directory as well.
>>
>> ----- Original Message -----
>>>
>>> Nice. We should have a strawman we agree with on other subdirs:
>>>
>>> - vm
>>> - parser (includes lexer, bulids ASTs)
>>> - bytecode (emitter, decompiler, utilities)
>>> - tracejit
>>> - methodjit
>>>
>>> Or something like this. Any such strawman already mooted?
>>>
>>> /be
>>
>> _______________________________________________
>> dev-tech-js-engine-internals mailing list
>> dev-tech-js-en...@lists.mozilla.org
>> https://lists.mozilla.org/listinfo/dev-tech-js-engine-internals
>
> _______________________________________________
> dev-tech-js-engine-internals mailing list
> dev-tech-js-en...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-tech-js-engine-internals
>

--
Paul Biggar
Compiler Geek
pbi...@mozilla.com

[Boris Zbarsky]

On 4/28/11 7:02 PM, Paul Biggar wrote:
> I'm loving these tidy-ups, but can I request a tiny comment at the top
> of new files, explaining what the file does in a sentence or two (even
> if it's obvious)?

Note that mxr will show the first C-style comment after the license
header as long as ther is no other code before it (so it needs to be
before the include guard in headers) in the Description column in its
directory listing. See
http://mxr.mozilla.org/mozilla-central/source/layout/base/ (the
"Description" column) for some example.

> I'd love to request a README saying what each directory does, but the
> names are thus-far self-explanatory.

Fwiw, if there's a README in a directory, the first sentence or so of
the README is also shown in mxr. See the description for "editline" in
http://mxr.mozilla.org/mozilla-central/source/js/src/

-Boris

[Luke Wagner]

How about a big honkin' one: http://hg.mozilla.org/tracemonkey/file/3dd6ec45084c/js/src/vm/Stack.h#l64 :)
Actually, though, the comment gets into implementation details before giving a high-level description of the module, so, "yes".

This should go on the modularization wiki as well.

On Apr 28, 2011, at 4:02 PM, Paul Biggar wrote:

> I'm loving these tidy-ups, but can I request a tiny comment at the top
> of new files, explaining what the file does in a sentence or two (even
> if it's obvious)?
>

> I'd love to request a README saying what each directory does, but the
> names are thus-far self-explanatory.
>
>
>

[Jim Blandy]

On 04/27/2011 05:44 PM, Luke Wagner wrote:
> I have little doubt there exist languages which solve the problem directly.

Test of my comprehension: in the Common Lisp Object System, rather than
having methods each of which belongs to a particular class, you define
"generic functions" (a name) that hold a collection of "methods" (actual
definitions) each of which is specific to a particular combination of
argument classes. This differs from C++ overloaded functions in that the
arguments' run-time types select the method to call, not their
compile-time types.

Generic functions sound like operations in a multi-sorted structure.

(I have never used CLOS.)

[Brendan Eich]

This is what Luke referred to as "mutli-methods" in "Then there is the question as to how to distribute the operations between the classes (or perhaps as non-member functions), but unless you want runtime polymorphism (which requires something like multi-methods), it's a question of aesthetics."

From CLOS's not quite sound generic functions came multi-methods in Dylan and Cecil, which IIRC begat the class-precedence-list or C3 linearization for method resolution.

http://www.webcom.com/haahr/dylan/linearization-oopsla96.html

We wanted multi-methods in ES4 as a better way forward than AS3's Java 1-style classes with interfaces; another ES4 over-reach, but the roots are good.

/be

[Wes Garland]

> We wanted multi-methods in ES4

I would love to see them in ES someday. I have most recently been working
on a medium-scale wholly JS project, where we have library code doing fairly
mundane things, like accessing customer records, etc.

We like to pass around IDs or whole records, depending on what the call site
already knows, doing lazy database lookups. We also like to pass "unknown"
when the call site doesn't know a particular piece of information, but it is
possible to infer it (sometimes via the database) from the other arguments.

If I had multi-methods, I could get rid of horrible function-intro blocks
that start like this:

if (typeof interaction === "string")
iid = interaction;
else if (typeof interaction === "object")
{
iid = interaction.id;
if (interaction && !customer)
cid = interaction.customerId;
}

if (typeof customer === "string")
cid = customer;
else if (typeof customer === "object")
cid = customer.id;

..and refactor into several functions, each eventually calling the same
"guts" function.

Wes

--
Wesley W. Garland
Director, Product Development
PageMail, Inc.
+1 613 542 2787 x 102

[Luke Wagner]

They have even been investigated for C++: http://www.research.att.com/~bs/multimethods.pdf
Spoiler: way faster than simulating it in the language, but you can have precedence ambiguities that only show up at dynamic library load time.