Cheap and greedy generator for common usage pattern

[crisptrutski]

Hey,

Busy looking at improving build performance, specifically heavy use is being made of Traceur and compile times increase dramatically when sourcemap generation is enabled.

The usage pattern of SourceMapGenerator via Traceur is very predicable:

1. Mappings always are always of the "size 4" variety (no name)
2. Sources are all known in advance
3. Mappings are all added in-order

Seems possible one could encode mapping strings greedily, skipping edge cases, intermediate representation, deferred computation etc.

Also imagine this usage pattern to be very common in other compilers. (The assumption of "no names" could relax to "name list known in advance" with only marginal extra overhead)

Perhaps something like the following:

  class OptimizedSourceMapGenerator {
    // Note that `sources` and `names` are now required
    constructor(file, sourceFileRoot, sources, names, [sourcesContents])

    // Assume (or assert) called with (generatedLine, generatedColumn) strictly ascending
    // This is the only retained public method from regular implementation, beyond toString, toJSON
    addMapping(generatedLine, generatedColumn, originalLine, originalColumn, source, name)
  }

Not sure how much this would impact performance, but have a hunch that it could be large!

Would appreciate feedback on whether:

1. There seems to be merit in this approach, or whether you'd anticipate little improvement
2. You have other suggestions
3. PR welcome here for this, or best left as a 3rd party extension.

[fitzgen]

Before diving into specific optimizations, I would suggest doing some profiling, to see specifically what functions you are spending a lot of time in, and how much time is spent in GC.

If a lot of time is spent in GC, then skipping the intermediate "_mappings" might be a big gain. But if GC isn't taking up a lot of time, I wouldn't really expect this to do much.

If sorting is taking a long time, rather than making a whole new type of source map generator, we could add a addMappingSorted method which just does a quick check that the new mapping is in fact ordered after the previous one and then just does an append. We would have to flip a flag if the normal addMapping was ever used and then when we are stringifying we just choose the fast or slow path based on if that flag ever got flipped.

I don't expect knowing the list of sources in advance to have any significant impact.

PRs are welcome here.

[fitzgen]

A bit of low hanging fruit: I think we could remove the toSetString/fromSetString and just use Object.create(null) instead of object literals for objects we use as maps with string keys. This would speed up ArraySet.prototype.has a little.

This is subtly backwards incompatible with old IE, but we can just bump the version number.

[fitzgen]

Another possible optimization is to only generate one mapping per line (if you aren't generating minified JS).

Most debuggers step on each line, and so multiple mappings for a single generated line are usually extraneous.

This sped up pretty-fast's source map generation a ton.

[crisptrutski]

Hey Nick,

Thanks for so much feedback and input!

1. I'm not keen on adding extra addMappingSorted API point. This means updating Traceur also, adding extra test cases here, and it looks like jhttps://github.com/Optimize generator with respect to sorting mappings #149 can get effectively the same speedup (went with a solution involving deoptimizing once out-of-order mapping added, and this overhead adds about 3-4% overhead, from benchmarking up to 1M mappings added)

2. Yes my assumption was that GC was an issue, but my attempts at measuring it have been crude - just calculating the total time spent in garbage collection.

   Perhaps I should port the suite to run in the browser rather than node to get a better view on which allocations are problematic, or you could recommend a Node compatible memory profiler? Stuck to Node at the moment as I'm using a bunch of npm modules, although I guess I could bundle the tests.

   The GC time over the benchmarks rises proportionally as the number of mappings processed is increased, as one would expect. At the 1M mark it accounts for about 5% of the script runtime, which seems quite high (and this is in isolation, not within the full build process)

   Another mention with optimized version is that we could skip building any internal data except an array of VLQ strings - this is where knowing sources and names in advance helps - we can completely skip the array-set and calculate indexes during add operation.

3. Validation is another low hanging fruit - a flag to disable mapping validation gives a speedup almost as large as the sorting invariant. Will send a PR for this.

4. Key transformations on the set are noticeable in profiling, thanks for the idea, I'll PR that too.

5. One-per-output-line is a great idea, and I think workable here for our case. We're composing with input source maps, so there could be an issue if prior compilation has contracted code noticeably, but I think Traceur's own pretty-printing of output should account for this too.

   There's a good spot already in Traceur to skip building the additional mappings, but what do you think about rather adding an option or wrapper to SourceMapGenerator itself?

   For simplicity this option could cause an exception or stop filtering once out-of-order mappings are encountered (using a dictionaries of {line: related mapping's index in _mapping} and {line: related mapping's column} could make it cheap to handle this case properly (ensure that first mapping per line is the one retained), but not interested in this case or sure it's worth adding more code).

Thanks again for the helpful suggestions and feedback

[crisptrutski]

@fitzgen removed the "set string" trick as suggested here crisptrutski@f0bb96b, but it seems to break even outside of ie. Possibly there's another trick to ply on the object?

[fitzgen]

Argh, for some reason I thought that objects with a null prototype didn't get the __proto__ accessor. I don't think there is anything we can do short of implementing our own map or something, which I highly doubt would be a speed up and wouldn't be worth the maintenance cost.

[fitzgen]

One-per-output-line is a great idea, and I think workable here for our case. We're composing with input source maps, so there could be an issue if prior compilation has contracted code noticeably, but I think Traceur's own pretty-printing of output should account for this too.

There's a good spot already in Traceur to skip building the additional mappings, but what do you think about rather adding an option or wrapper to SourceMapGenerator itself?

I don't think it belongs in SourceMapGenerator, but it could groove with the higher-level SourceNode. However, it doesn't sound like you are using that.

[crisptrutski]

Got really dramatic results with a monkey-patch to MappingList#add to support cheap "maybe no-op" strategy in the sorted case, and a "maybe no-op or replace-in-place" approach once it falls into the slow path (with a once off burn in of the supporting data when that branch first hits) - completely shatter the _mappings refactor wins for me (even putting it into the actual class with an if-statement almost halved performance.)

Don't have code to show right now away from laptop, but around 10 lines for massive wins in a nice decoupled way - feel like decorating a generator to "simplify mappings" is pretty natural.

Can put the voodoo upstream without issue if it offends though :)

[fitzgen]

I'm having a hard time parsing all that without being able to look at the code :)

[crisptrutski]

Not my clearest exposition I guess ;)

So the mechanism is actually a bit unsightly, as it pushes down into the MappingList. Almost all the complexity here is for the !this._sorted case too.

WIll rather see about a PR for filtering the mappings earlier in Traceur itself, but here you go for interests sake:

  MappingList.prototype.add = function MappingList_add(aMapping) {
    var mapping, line;
    if (generatedPositionAfter(this._last, aMapping)) {
      if (aMapping.generatedLine > this._last.generatedLine) {
        this._last = aMapping;
        this._array.push(aMapping);
      }
    } else {
      if (!this._unordered) {
        for (var i=0;i<this._array.length;i++) {
          var existing = this._array[i];
          line = existing.generatedLine;
          this._idxPerLine[line] = i;
          this._colPerLine[line] = existing.generatedColumn;
        }
      }
      this._unordered = true;
      line = aMapping.generatedLine;
      if (!(line in this._colPerLine)) {
        this._idxPerLine[line] = this._array.length;
        this._colPerLine[line] = aMapping.generatedColumn;
        this._array.push(aMapping);
      } else if (aMapping.generatedCol < this._colPerLine[line]) {
        this._array[this._idxPerLine[line]] = aMapping;
        this._colPerLine[line] = aMapping.generatedColumn;
      }
    }
  };

where this._idxPerLine and this._colPerLine are initialized to empty objects in the constructor (arrays could work too, but were slightly slower in my tests).