1579862 - [BinAST] Make Huffman lookup faster

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P2)

Description

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

Huffman lookup is currently O(entries). We can make it O(bit length), possibly even better. Let's do so.

See https://gist.github.com/Yoric/a9267822dee8776186624800169b217c for more details.

Comment 1

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

Attachment: Bug 1579862 - Tweaking HuffmanTableImplementationSaturated;r?arai

A few changes to HuffmanTableImplementationSaturated:

• we can now create instances of HuffmanTableImplementationSaturated with max bit lengths up to 10;
• we reject cases in which we have more than 256 elements;
• internal indices in HuffmanTableImplementationSaturated are now represented with uint8_t instead of usize_t,
  which divides the size of this array by 4 and should improve memory locality.

According to my benchmarking, this decreases duration by ~7%.

Depends on D45644

Comment 2

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

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

Comment 3

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

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

Depends on D45315

Comment 4

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

Attachment: Bug 1579862 - 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 5

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

Attachment: Bug 1579862 - 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 6

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

Ok, there's more to do with faster lookup, but according to my benchmarks, this already increases speed by ~14%.

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/04c6be2f7cfa
Get rid of HuffmanTableXXX::impl;r=arai
https://hg.mozilla.org/integration/autoland/rev/6ce3c1949f8b
New implementation HuffmanTableMap;r=arai
https://hg.mozilla.org/integration/autoland/rev/e288a597f967
Introducing HuffmanTableImplementationGeneric;r=arai
https://hg.mozilla.org/integration/autoland/rev/bbddaf060c98
Introducing HuffmanTableImplementationSaturated;r=arai
https://hg.mozilla.org/integration/autoland/rev/ebb8ad9cd82e
Tweaking HuffmanTableImplementationSaturated;r=arai

Comment 8

[Andreea Pavel [:apavel]]

backed out for build bustages on BinASTTokenReaderContext.h

Push with failures: https://treeherder.mozilla.org/#/jobs?repo=autoland&resultStatus=testfailed%2Cbusted%2Cexception&revision=ebb8ad9cd82eae549eb6e96395fdde61f48fb78a&selectedJob=266480147

Failure log: https://treeherder.mozilla.org/logviewer.html#/jobs?job_id=266480147&repo=autoland&lineNumber=6145

Backout: https://hg.mozilla.org/integration/autoland/rev/e5065ace97fd1e76ff0f5779a5a83d1fad43b523

Comment 9

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

Ah, right, forgot to make the constructors explicit. I'm on it.

Comment 10

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

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

Comment 11

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

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

Comment 12

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/ea90070799fb
Get rid of HuffmanTableXXX::impl;r=arai
https://hg.mozilla.org/integration/autoland/rev/8191ba5b58da
New implementation HuffmanTableMap;r=arai
https://hg.mozilla.org/integration/autoland/rev/0723ca2ce2bb
Introducing HuffmanTableImplementationGeneric;r=arai
https://hg.mozilla.org/integration/autoland/rev/9e0541d8cea7
Introducing HuffmanTableImplementationSaturated;r=arai
https://hg.mozilla.org/integration/autoland/rev/2f3c022f9315
Tweaking HuffmanTableImplementationSaturated;r=arai
https://hg.mozilla.org/integration/autoland/rev/97d38d633c8e
Making single-arg constructors explicit;r=arai

Comment 13

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

Attachment: Bug 1579862 - Documenting HuffmanTableImplementationSaturated::InternalIndex;r?arai

Comment 14

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/4e6dd979ed23
Documenting HuffmanTableImplementationSaturated::InternalIndex;r=arai

Comment 15

[Bogdan Tara[:bogdan_tara | bogdant]]

https://hg.mozilla.org/mozilla-central/rev/ea90070799fb
https://hg.mozilla.org/mozilla-central/rev/8191ba5b58da
https://hg.mozilla.org/mozilla-central/rev/0723ca2ce2bb
https://hg.mozilla.org/mozilla-central/rev/9e0541d8cea7
https://hg.mozilla.org/mozilla-central/rev/2f3c022f9315
https://hg.mozilla.org/mozilla-central/rev/97d38d633c8e
https://hg.mozilla.org/mozilla-central/rev/4e6dd979ed23