1449220 - ModuleBuilder import/export lookup uses linear search

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P2)

Description

[Jon Coppeard (:jonco)]

When creating module metadata we maintain vectors of import and export entry objects which we search using linear search in a couple of places.  This happens to check whether an export is re-exporting an import and when we hit a new export statement the parser to check for duplicate exported names.  This leads to N^2 behaviour and is bound to cause problems for large modules.

Comment 1

[Jon Coppeard (:jonco)]

Attachment: bug1449220-module-hash-tables

Patch to use hash tables for import / entry lookup in ModuleBuilder.  importEntries_ uses a map as we have to lookup an object by name.  For exports there is not always a name (in the case of |export *|) so I added a separate set for exported names.  I removed importedBoundNames_ which was unused.

I also had to update a test that assumed importEntries would be present in a certain order.

Comment 2

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/627599ba1f3b
Use hash tables for looking up imports and exports when building module metadata r=jorendorff

Comment 3

[Arthur Iakab [arthur_iakab]]

https://hg.mozilla.org/mozilla-central/rev/627599ba1f3b