1577764 - [BinAST] Make Context-0.1 faster

Status: RESOLVED INCOMPLETE

(Core :: JavaScript Engine, task, P2)

Description

[David Teller [:Yoric] - still alive but not very active]

Once we have landed a first implementation of Context 0.1, we'll need to work on the slow bits:

• we have a few uses of strcmp during Huffman prelude reading, which could be resolved mostly statically;
• our Huffmman lookup is in linear time, we could do much better.

Comment 1

[David Teller [:Yoric] - still alive but not very active]

Attachment: Bug 1577764 - Get rid of HuffmanTableXXX::impl;r?arai

Comment 2

[David Teller [:Yoric] - still alive but not very active]

Attachment: Bug 1577764 - New implementation HuffmanTableMap;r?arai

Depends on D45315

Comment 3

[David Teller [:Yoric] - still alive but not very active]

Attachment: Bug 1577764 - Introducing HuffmanTableImplementationGeneric;r?arai

As we intend to have several implementations of Huffman Table depending
on the size of data, we start by introducing a small abstraction
HuffmanTableImplementationGeneric holding a Variant<...> with
possible implementations of Huffman Tables.

In this patch, there is only a single implementation HuffmanTableImplementationMap.
A followup patch will introduce an alternate fast but space-costly optimized for
small tables.

Comment 4

[David Teller [:Yoric] - still alive but not very active]

Attachment: Bug 1577764 - Introducing HuffmanTableImplementationSaturated;r?arai

We introduce a new implementation of Huffman Tables that trades
space for a fast lookup. For the time being, this implementation
is reserved for tables with a max bitlength of 8 or less.

Depends on D45643

Comment 5

[David Teller [:Yoric] - still alive but not very active]

From a recent profile, the dominating costs seem to be

Self Weight	Self Weight	Function
23.68 s	14.2%	js::frontend::HuffmanTableImplementationMap<JSAtom*>::lookup(js::frontend::HuffmanLookup) const
10.83 s	6.5%	mozilla::Result<js::frontend::HuffmanLookup, JS::Error&> js::frontend::BinASTTokenReaderContext::BitBuffer::getHuffmanLookup<(js::frontend::BinASTTokenReaderContext::Compression)0>(js::frontend::BinASTTokenReaderContext&)
8.03 s	4.8%	js::frontend::TagReader::operator()(js::frontend::HuffmanTableIndexedSymbolsSum const&)
6.03 s	3.6%	js::frontend::BinASTTokenReaderContext::enterTaggedTuple(js::frontend::BinASTKind&, js::frontend::BinASTTokenReaderContext::BinASTFields&, mozilla::Variant<js::frontend::BinASTTokenReaderBase::RootContext, js::frontend::BinASTTokenReaderBase::ListContext, js::frontend::BinASTTokenReaderBase::FieldContext> const&, js::frontend::BinASTTokenReaderContext::AutoTaggedTuple&)
4.01 s	2.4%	js::frontend::FunctionBox::FunctionBox(JSContext*, js::frontend::TraceListNode*, JSFunction*, unsigned int, js::frontend::Directives, bool, js::GeneratorKind, js::FunctionAsyncKind)
3.57 s	2.1%	mozilla::Result<js::frontend::HuffmanTableIndexedSymbolsLiteralString::Contents, JS::Error&> js::frontend::BinASTTokenReaderContext::readFieldFromTable<js::frontend::HuffmanTableIndexedSymbolsLiteralString>(mozilla::Variant<js::frontend::BinASTTokenReaderBase::RootContext, js::frontend::BinASTTokenReaderBase::ListContext, js::frontend::BinASTTokenReaderBase::FieldContext> const&)

• percentages are taken from the total time spent in BinASTTokenReaderContext::parse;
• the code is that of bug 1579862;
• I'm parsing 10x an arbitrary subsample of files from real-js-samples

Comment 6

[Phabricator Automation]

Comment on attachment 9091682 [details]
Bug 1577764 - Get rid of HuffmanTableXXX::impl;r?arai

Revision D45315 was moved to bug 1579862. Setting attachment 9091682 [details] to obsolete.

Comment 7

[Phabricator Automation]

Comment on attachment 9091684 [details]
Bug 1577764 - New implementation HuffmanTableMap;r?arai

Revision D45316 was moved to bug 1579862. Setting attachment 9091684 [details] to obsolete.

Comment 8

[Phabricator Automation]

Comment on attachment 9092309 [details]
Bug 1577764 - Introducing HuffmanTableImplementationGeneric;r?arai

Revision D45643 was moved to bug 1579862. Setting attachment 9092309 [details] to obsolete.

Comment 9

[Phabricator Automation]

Comment on attachment 9092310 [details]
Bug 1577764 - Introducing HuffmanTableImplementationSaturated;r?arai

Revision D45644 was moved to bug 1579862. Setting attachment 9092310 [details] to obsolete.

Comment 10

[David Teller [:Yoric] - still alive but not very active]

Attachment: Bug 1577764 - Making single-arg constructors explicit;r?arai

Comment 11

[Phabricator Automation]

Comment on attachment 9092597 [details]
Bug 1577764 - Making single-arg constructors explicit;r?arai

Revision D45813 was moved to bug 1579862. Setting attachment 9092597 [details] to obsolete.

Comment 12

[David Teller [:Yoric] - still alive but not very active]

Latest update

--------------- | ------- | -----------------------------------------
10.67 s 6.0% | 10.67 s | decltype(auto) mozilla::detail::VariantImplementation<unsigned char, 1ul, js::frontend::MultiLookupHuffmanTable<JSAtom*, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, js::frontend::MultiLookupHuffmanTable<JSAtom*, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>, js::frontend::HuffmanTableUnreachable>::matchN<mozilla::Variant<js::frontend::SingleLookupHuffmanTable<JSAtom*>, js::frontend::MultiLookupHuffmanTable<JSAtom*, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, js::frontend::MultiLookupHuffmanTable<JSAtom*, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>, js::frontend::HuffmanTableUnreachable> const, js::frontend::GenericHuffmanTable<JSAtom*>::lookup(js::frontend::HuffmanLookup)
10.27 s 5.8% | 10.27 s | js::frontend::BinASTTokenReaderContext::readTagFromTable(js::frontend::BinASTInterfaceAndField const&)
8.44 s 4.7% | 8.44 s | decltype(auto) mozilla::detail::VariantImplementation<unsigned char, 1ul, js::frontend::MultiLookupHuffmanTable<js::frontend::BinASTKind, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, js::frontend::MultiLookupHuffmanTable<js::frontend::BinASTKind, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>, js::frontend::HuffmanTableUnreachable>::matchN<mozilla::Variant<js::frontend::SingleLookupHuffmanTable<js::frontend::BinASTKind>, js::frontend::MultiLookupHuffmanTable<js::frontend::BinASTKind, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, js::frontend::MultiLookupHuffmanTable<js::frontend::BinASTKind, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>, js::frontend::HuffmanTableUnreachable> const, js::frontend::GenericHuffmanTable<js::frontend::BinASTKind>::lookup(js::frontend::HuffmanLookup) const::'lambda'(js::frontend::MultiLookupHuffmanTable<js::frontend::BinASTKind, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6> const&), js::frontend::GenericHuffmanTable<js::frontend::BinASTKind>::lookup(js::frontend::HuffmanLookup) const::'lambda'(js::frontend::MultiLookupHuffmanTable<js::frontend::BinASTKind, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6> const&), js::frontend::GenericHuffmanTable<js::frontend::BinASTKind>::lookup(js::frontend::HuffmanLookup)
8.40 s 4.7% | 8.40 s | mozilla::Result<js::frontend::HuffmanLookup, JS::Error&> js::frontend::BinASTTokenReaderContext::BitBuffer::getHuffmanLookup<(js::frontend::BinASTTokenReaderContext::Compression)0>(js::frontend::BinASTTokenReaderContext&)
7.41 s 4.2% | 7.41 s | js::frontend::MultiLookupHuffmanTable<JSAtom*, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>::lookup(js::frontend::HuffmanLookup) const
4.56 s 2.5% | 4.56 s | js::frontend::FunctionBox::FunctionBox(JSContext*, js::frontend::TraceListNode*, JSFunction*, unsigned int, js::frontend::Directives, bool, js::GeneratorKind, js::FunctionAsyncKind)
3.98 s 2.2% | 3.98 s | js::frontend::UsedNameTracker::noteUse(JSContext*, JSAtom*, unsigned int, unsigned int)
3.79 s 2.1% | 3.79 s | mozilla::Result<js::frontend::HuffmanTableIndexedSymbolsLiteralString::Contents, JS::Error&> js::frontend::BinASTTokenReaderContext::readFieldFromTable<js::frontend::HuffmanTableIndexedSymbolsLiteralString>(js::frontend::BinASTInterfaceAndField const&)
3.67 s 2.0% | 3.67 s | decltype(auto) mozilla::detail::VariantImplementation<unsigned char, 1ul, js::frontend::MultiLookupHuffmanTable<unsigned int, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, js::frontend::MultiLookupHuffmanTable<unsigned int, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>, js::frontend::HuffmanTableUnreachable>::matchN<mozilla::Variant<js::frontend::SingleLookupHuffmanTable<unsigned int>, js::frontend::MultiLookupHuffmanTable<unsigned int, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, js::frontend::MultiLookupHuffmanTable<unsigned int, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6>, js::frontend::HuffmanTableUnreachable> const, js::frontend::GenericHuffmanTable<unsigned int>::lookup(js::frontend::HuffmanLookup) const::'lambda'(js::frontend::MultiLookupHuffmanTable<unsigned int, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6> const&), js::frontend::GenericHuffmanTable<unsigned int>::lookup(js::frontend::HuffmanLookup) const::'lambda'(js::frontend::MultiLookupHuffmanTable<unsigned int, js::frontend::MultiLookupHuffmanTable<unsigned long, js::frontend::SingleLookupHuffmanTable<unsigned long>, (unsigned char)6>, (unsigned char)6> const&), js::frontend::GenericHuffmanTable<unsigned int>::lookup(js::frontend::HuffmanLookup)
3.62 s 2.0% | 3.62 s | js::frontend::BinASTParser<js::frontend::BinASTTokenReaderContext>::parseInterfaceStaticMemberExpression(unsigned long, js::frontend::BinASTKind, mozilla::Variant<js::frontend::BinASTTokenReaderBase::FieldContext, js::frontend::BinASTTokenReaderBase::ListContext> const&)
3.62 s 2.0% | 3.62 s | bool GetUTF8AtomizationData<JS::WTF8Chars>(JSContext*, JS::WTF8Chars, unsigned long*, JS::SmallestEncoding*, unsigned int*)
3.57 s 2.0% | 3.57 s | js::frontend::BinASTParser<js::frontend::BinASTTokenReaderContext>::parseInterfaceIdentifierExpression(unsigned long, js::frontend::BinASTKind, mozilla::Variant<js::frontend::BinASTTokenReaderBase::FieldContext, js::frontend::BinASTTokenReaderBase::ListContext> const&)

Or, to make it a bit more palatable

1. String Huffman lookups.
2. readTagFromTable
3. BinASTKind Huffman lookups.
4. getHuffmanLookup
5. u32 Huffman lookups.
6. Function allocation.
7. Function allocation (I think).
8. String readFieldFromTable
9. u8 Huffman lookups.
10. ...

Comment 13

[David Teller [:Yoric] - still alive but not very active]

As of bug 1587663 + bug 1587738, we're finally faster than text parsing on real-js-samples \o/

On my machine, we get a ratio of 0.95-0.96 (CPU time and wallclock time seem to agree) in favor of BinAST parsing, or more if we believe the profiler (0.83).

The only downside is that since we de-templatized the code, the profiler now doesn't differentiate anymore between the different types of values, so we lost that information. On the upside, some symbols are now much easier to read.

Total time	%	Total time	Symbol
32.59 s	10.0%	32.59 s	js::frontend::MultiLookupHuffmanTable<js::frontend::SingleLookupHuffmanTable, (unsigned char)6>::lookup(js::frontend::HuffmanLookup) const
17.45 s	5.3%	17.45 s	js::frontend::GenericHuffmanTable::lookup(js::frontend::HuffmanLookup) const
15.86 s	4.8%	15.86 s	mozilla::Result<js::frontend::HuffmanLookup, JS::Error&> js::frontend::BinASTTokenReaderContext::BitBuffer::getHuffmanLookup<(js::frontend::BinASTTokenReaderContext::Compression)0>(js::frontend::BinASTTokenReaderContext&)
12.33 s	3.8%	12.33 s	js::frontend::BinASTTokenReaderContext::readTagFromTable(js::frontend::BinASTInterfaceAndField const&)
9.71 s	2.9%	9.71 s	JSAtom* AtomizeUTF8OrWTF8Chars<JS::WTF8Chars>(JSContext*, char const*, unsigned long)
8.03 s	2.4%	8.03 s	js::frontend::UsedNameTracker::noteUse(JSContext*, JSAtom*, unsigned int, unsigned int)
7.82 s	2.4%	7.82 s	js::frontend::FunctionBox::FunctionBox(JSContext*, js::frontend::TraceListNode*, JSFunction*, unsigned int, js::frontend::Directives, bool, js::GeneratorKind, js::FunctionAsyncKind)
7.68 s	2.3%	7.68 s	bool GetUTF8AtomizationData<JS::WTF8Chars>(JSContext*, JS::WTF8Chars, unsigned long*, JS::SmallestEncoding*, unsigned int*)
6.90 s	2.1%	6.90 s	js::frontend::ParseNodeAllocator::allocNode(unsigned long)
6.69 s	2.0%	6.69 s	js::frontend::BinASTParser<js::frontend::BinASTTokenReaderContext>::parseInterfaceStaticMemberExpression(unsigned long, mozilla::Variant<js::frontend::BinASTTokenReaderBase::FieldContext, js::frontend::BinASTTokenReaderBase::ListContext> const&)
6.55 s	2.0%	6.55 s	mozilla::Result<js::frontend::BinASTSymbol, JS::Error&> js::frontend::BinASTTokenReaderContext::readFieldFromTable<js::frontend::HuffmanTableIndexedSymbolsLiteralString>(js::frontend::BinASTInterfaceAndField const&)

Or, in more readable terms:

1. Lookups in two-level Huffman tables (10%)
   1. of Strings (50% thereof)
   2. of BinASTKind (20% thereof)
   3. of List length (10% thereof)
   4. others
2. Generally speaking, lookup in Huffman tables (5%)
   1. for readTagFromTable (60% thereof)
   2. of List length (20% thereof)
   3. others
3. Reading and maintaining the stream (4.8%)
4. readTagFromTable
5. String processing during initialization.
6. Allocating functions, I believe.
7. Allocating functions.
8. More string processing during initialization.
9. Memory allocation of the AST.
10. parseInterfaceStaticMemberExpression – not sure why
11. readFieldFromTable for literal strings.

Comment 14

[Matthew Gaudet (he/him) [:mgaudet]]

Resolving BinAST bugs as Incomplete.