Mark unneeded elements for serialization/execution

[enebo]

There are various fields that or of interest for parsing use cases and ones which are of interest for execution. For execution, CallNode
will include a token for opening and closing which are unused and also for message (while I think we only care about name). I used call because it is a common thing and you can see that will expand time and memory of making/processing a serialized blob.

I propose possibly annotating elements with a profile or something to indicate what we want. This could be as simple as an extra field in config.yml:

  - name: CallNode
    child_nodes:
      - name: receiver
        type: node?
      - name: call_operator
        type: token?
        exclude: execute
      - name: message
        type: token?
      - name: opening
        type: token?
        exclude: execute
      - name: arguments
        type: node?
      - name: closing
        type: token?
        exclude: execute
      - name: block
        type: node?
      - name: name
        type: string
    comment: |
      Represents a method call, in all of the various forms that can take.

This would mean some writes in serialize would exclude for the profile specified. There are many ways we could specify this but just excluding these three tokens would reduce each call between 7 (foo 1) and 27 bytes. From a simple analysis of loading a single scaffolded Rails app the serialized to source ratio averages 2.44x. Using a very simple numeric compression scheme I can get that down to 1.44 but I imagine trimming out unneeded elements will be a pretty decent win.

[enebo]

I implemented this (only generated serialize.c) and did a modest pass of excludes (if exclude is present on the node it will just not emit -- rough WIP). From those changes the average ratio to source for a simple Rails app drops from 2.44x to 2.21x. Somewhat modest but it lead to another size issue with how we serialize.

The node needs a {start, end} but this is generally only derivable from first and last tokens. we need the range to underline or to currently calculate line number but this potentially is storing 16 bytes if there is a clean start/end but potentially more if there are other optional endings.

[kddnewton]

I'm going to respond to this in a couple of parts.

• In general I'm fine with tagging certain attributes as not being part of the serialization.
• A lot of tokens on the tree are going to go away in favor of locations. Right now we store an extra byte to indicate the type of node, but in most cases it's not really necessary. For example with call nodes we're just going to track opening_loc and closing_loc.
• I think you're going to want the call operator, because it could be &..
• For the locations, you shouldn't have to derive anything, as in addition to all of the attributes, each node stores it range.

[enebo]

"A lot of tokens on the tree are going to go away in favor of locations. Right now we store an extra byte to indicate the type of node, but in most cases it's not really necessary. For example with call nodes we're just going to track opening_loc and closing_loc."

If some tokens are equiv of an enum (e.g. keywords) you may want to just store a byte and mark it some new type keywords.

Note: this next paragraph does mean locations just not as specific as I think you are referring to them.

For tokens like Strings or things which are variable and larger in length it makes sense (after all we have the source in hand and need it for error reporting). I definitely think there is some value in considering a constant pool. Most files are littered with the same identifiers/symbols/etc and many could be representable as a single byte to a pool entry. If you need full loc you can then add a special byte followed by the loc to source. For JRuby, we did this for IR serialization and it reduces needing to make n instances of ByteList/String since that is shareable in many cases so it reduces object churn too. It is also smaller.

"I think you're going to want the call operator, because it could be &.."

yeah I didn't exclude that one. parens and also message since name seems to be what we would use (e.g. call for foo, bar = 1, 2 foo= is name but not message).

"For the locations, you shouldn't have to derive anything, as in addition to all of the attributes, each node stores it range."

OMG! :) I totally forgot this. So I will update once I exclude more tokens.

[eregon]

Re the constant pool we mentioned it a few times and it seems a big win. It'd be good to open an issue or discussion about it for the specifics. Not quite sure how to format it in the serialized form and have fast access to it. Maybe use an index per constant string in the pool + table of offsets relative to start of table to index into and then at those start+offsets the length followed by the bytes.

[enebo]

Nice removing those other tokens now drops the ratio of source to blob to 2.04. I will try and make a PR on this to at least see what I am thinking.

[kddnewton]

@enebo I think we could also have separate serializers/deserializers. If you want, you could have exclude: jruby and then write your own template that serializes/deserializes using that information. I was thinking this might be what you want anyway because I figure when you hit a def node you're going to stop deserializing and instead store the serialized AST?

[enebo]

@kddnewton Lazy parsing is definitely a longer term goal and I can see not all parties may want that so I think that makes sense that we could see multiple {de,}serializers.

I do think though, thus far, most of the serialization ideas will benefit all parties involved. I doubt anyone who consumes the serialized format who wants to just do execution wants extra tokens to skip over. For any changes we make other than exclusion I would hope it would not complicate other users at all. I may be assuming too much perhaps?

With using short + marker for int on serialize u32 along with this exclude feature the ratio of source to blob is 1.21x from 2.44x. With a little more work I think we can make a serialization format more dense than Ruby. I have been wanting to chat with you but I think the notion of us pre-compiling all shipped source with blobs would end up being a pretty neat idea. It would eliminate some startup overhead for JRuby but it may be an interesting win for MRI and even more so with TR based on amount of Ruby they load.

In working through JRuby's AOT IR Serialization it is doing lots of small reads from a byte buffer (sounds familiar right). The lessons learned were:

1. Smaller is faster. A protobuffer design or something which was designed to iterate over fixed struct sizes could probably be faster but if you are reading bytes at a times and making decisions with those bytes the time to process is linear with the amount you read.
2. Object construction is expensive for startup time. GC obviously really helps but you cannot escape the cost of initialization.

So my other long term goal is to not create a tree at all which likely will require a design which is more oriented towards that. That is pretty blue sky though. I looked at it and making this work means no generation at all (unless we radically changed the design to be much more typed).

So yeah multiple deserializers is fine but I do think there are some generic merits to reducing number of elements and overall size of the blob for implementations which plan on executing ruby from it.

[enebo]

I should add I am ok with incubating ideas on a JRuby-specific serializer. This is an off-line sort of thing for us (I think) so I can add things to JRuby-specific one and if they work out well I can pitch them to the other serializer(s).

[eregon]

I think for now it's best to use the same Java Loader for both JRuby and TruffleRuby. And that loader can simply hardcore the semantics/execution-only mode (and error otherwise) since there is currently no use for it besides for execution.
Regarding lazy parsing I would think the only places it makes sense are method definitions and potentially block definitions.
Method definition is an obvious win and probably what everyone doing lazy parsing does currently.
Block definition is much less useful l, it needs to remember more state from the surrounding scope so it's far more complicated and much less useful, it's rather rare that a block is not used but the surrounding method is.

I think that also means we don't need to have "serialized length to next node" for any node except method declaration node, which should be a decent saving.