Scopes: memory requirement for translating stack traces

[rakudrama]

There have been discussions about the size of source maps (e.g. #41) but mostly concentrated on the file size. This issue is about the memory requirements for using sourcemaps.

Consider translating stack traces to the source language. The application server might do the translation, e.g. when the in-browser app logs a stack trace by sending back to the server. In practice, application servers see unwelcome spikes in memory usage when translating a burst of stack traces. In the server memory profiles I examined, 10-20% of the steady state memory was related to decoded source maps.

One reason for the high memory load  is that the entire source map must be decoded before any part of it can be used. However, translating a stack trace accesses the source map sparsely.

A stack trace typically has ten or so lines. These correspond to a similar number of functions in the original source. The ~10 stack trace lines reference a few generated files (3 is common in the crash logs I sampled). The generated files are large - I looked at a 9.8MB .js file that has a 15.8MB source map (12MB if proprietary extensions are stripped).

Digging into this sourcemap:

The sources section names ~4.6k files

The mappings section is 3.85MB which encodes 530k mapping records.
If the implementation naively represents the decoded source map using classes for each record type in the specification, you might expect one mapping record with its positions to take about 12 words (= 48 bytes when using, say, Java, with compressed pointers).
That would be about 25MB of heap - a 6.6x expansion over the encoded memory footprint.
Some clever implementations can pack this into arrays and reduce it to ~12MB, or a 3x expansion.

The names section has 180k names in 7.9MB. After parsing the JSON, the list and the individual strings it contains occupy about 10MB of heap.

During the stack frame translation we have resident:

• The .js file, since it is scanned to find the beginning of the JavaScript function enclosing the stack frame positions (9.8MB)
• The list of names (10MB)
• The decoded mappings (12MB)

That is 31.8MB for only one file and there are typically two more in the stack trace.

Scopes

For the scopes proposal, the .js file is no longer needed, as the scopes field of the JSON encodes ranges 'covering' generated functions. Can the ranges, stripped of any bindings, be decoded into a data structure that occupies less memory than the source code?
This is not clear. How dart2js uses V3 mappings, ranges have a lot of overlap with the mappings. Ranges are more complicated, but potentially more sparse.

The original source scopes are also needed, since they are the definition, containing the name of the original source function, for the ranges we care about in order to translate the stack.

Stripping the source map while decoding

For stack trace translation:

• Bindings are not needed.
• Ranges that correspond to non-function scopes are not needed.
• Scopes are of interest only for the name of the source function.

It would help memory if the unneeded parts could be stripped while decoding.

If the bindings are going to be unused, can they be stripped from the ranges without reference to the original scope's variables?
If yes, then decoding the scopes could be deferred until we know the few that are required.
Could there be some way to decouple the parsing of ranges so that it could precede parsing original scopes?
Could the scopes be encoded in a list of strings, like sourceContents

There is currently one 'index' space for scopes. If the definition was a pair (sourceIndex, scopeIndexWithinSource) then it would be unnecessary to decode the OriginalScopeTree for sources that are not named in the translated stack trace.

[szuend]

Yes, the format allows dropping items while decoding that a consumer is not interested in. E.g. a consumer can just ignore any "original scope variables" item and "generated range bindings item without problem. That is, a decoder can just ignore any VLQs it sees after a D, G or H tag and read until the next comma ,. Essentially skipping over that item.

While the current format can't be decoded/parsed partially from the outset, all of the "index information" can be built with a single pass over the "scopes" string looking only at the tag of each item with some VLQ decoding. Concretely: If you have a single pass that just looks at the B, C, E and F tags, which corresponds to the original scope start/end and generated range start/end items, you can record:

• index into the "scopes" string <-> first occurrence of E i.e. where the ranges start
• index into the "scopes" string <-> occurrence of B where the root scope for sourceIndex begins as well as what the "scopeIndex" is of that scope (Edit: plus the current value of name/kind index)

This would be a single pass over the "scopes" string without any VLQ decoding. The only information you'd need to track is the current scope nesting depth and a scope counter. You don't even have to pass over the whole string, as you can stop once you see the first E as no scope information can come after.

Edit: The initial version of this comment was wrong. As you'd have to decode the name/kind index of all scopes to keep track of the incremental index. We could reset the name/kind index for each root scope back to 0, which would allow partial decoding of original scope trees. This we'd have to decide now, before we finalize the initial version.

[hbenl]

Ensuring that the scopes information can be decoded in a more memory-efficient way for stack translation purposes (i.e. when bindings are not needed) sounds like a good idea. I agree with @szuend that this can probably be done already with the current proposal.

We could reset the name/kind index for each root scope back to 0, which would allow partial decoding of original scope trees.

I like that idea.

[rakudrama]

We could reset the name/kind index for each root scope back to 0, which would allow partial decoding of original scope trees.

Lets say we split the scopes into a list of strings parallel to the sources.

To decode scopes for any source on demand, we need to know the start scopeId for the source file.
This could be an initial VLQU in each file's scopes encoding. All other accumulators start at zero.
This extra VLQ would add about 1.6% to the encoding of the scopes.
A verifier would check that no two scopes have the same index.
(It would also allow the scopeIndex to be decoupled from the sourceIndex, but I'm not sure if that is interesting.)

Parsing just the start scopeId for each scope would allow the construction of a compact 'map' from scopeId to sourceIndex via a bsearchable sorted list of <startScopId, sourceIndex> pairs.

Would deferred parsing of the scopes work for the full debug experience where the ranges have bindings?

[szuend]

If we split scopes back into scopes and ranges, where scopes is a list of strings, then I think we should change "definition" to go from a single scopeIndex to a tuple (sourceIndex, scopeIndex). We could do that in any case, even if we keep the current single scopes string.

Would deferred parsing of the scopes work for the full debug experience where the ranges have bindings?

I can't see why not. There is no decoding state for "binding expressions" that depends on the decoding state of scopes. This is in fact true for everything in "generated ranges". You can decode "generated ranges" independently of "original scopes" as they use separate decoder state for the incremental line/column/definition indices.

[rakudrama]

There is no decoding state for "binding expressions" that depends on the decoding state of scopes.

I was wondering if there was any parsing constraint based on

[[Bindings]] are intended for debuggers to retrieve the values of original variables. The length of [[Bindings]] must be equal to [[Variables]] of the corresponding Original Scope Record. Given an index i, [[Binding]][i] describes how to retrieve the value for the original variable [[Variables]][i].

That would be unfortunate, in effect forcing the parsing of scopes ahead of ranges just in case there are some bindings.
I didn't see a constraint that checks the must.

[szuend]

A decoder doesn't need to validate. In "spec speak", many of these checks are behind an "if cond, optionally report an error". Which means a decoder is free to ignore e.g. an invalid scopeIndex or an invalid index into "names".

In the same vein, decoding and actually resolving can happen in separate steps. That is, you decode the range with a definition scope index, but actually resolving it to an "original scope" happens once a consumer needs it.