Closed Bug 1579862 Opened 3 months ago Closed 3 months ago

[BinAST] Make Huffman lookup faster

Categories

(Core :: JavaScript Engine, task, P2)

task

Tracking

()

RESOLVED FIXED
mozilla71
Tracking Status
firefox71 --- fixed

People

(Reporter: Yoric, Assigned: Yoric)

References

(Blocks 1 open bug)

Details

Attachments

(8 files)

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.

Priority: -- → P2

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

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.

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

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

Pushed by dteller@mozilla.com:
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

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

Flags: needinfo?(dteller)
Pushed by dteller@mozilla.com:
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
Pushed by dteller@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/4e6dd979ed23
Documenting HuffmanTableImplementationSaturated::InternalIndex;r=arai
Assignee: nobody → dteller
Depends on: 1585520
No longer depends on: 1585520
You need to log in before you can comment on or make changes to this bug.