1586971 - [BinAST] Add single-entry variant for `HuffmanTable`

Status: RESOLVED FIXED

(Core :: JavaScript Engine, task, P3)

Description

[Tooru Fujisawa [:arai]]

single-entry table can appear frequently, and allocating 1 entry Vector is inefficient in term of Mutex and also space-efficiency.
we can add another variant with fixed-size inline array.
(maybe this applies also to non-single entry, maybe up to 2 or 3)

locally, this improves the performance by 12% with parsing 200 small files.

Comment 1

[Tooru Fujisawa [:arai]]

running try with new SingleEntryHuffmanTable<T> type.
https://treeherder.mozilla.org/#/jobs?repo=try&revision=84b556e99f771c45daca57f51de30ef8a7b26080

then, here's the size of tables:

table	size in bytes
GenericHuffmanTable<T>	88
SingleEntryHuffmanTable<T>	8 + sizeof(T)
SingleLookupHuffmanTable<T>	72
TwoLookupsHuffmanTable<T>	80
ThreeLookupsHuffmanTable<T>	80

the maximum of sizeof(T) is 8, so single HuffmanEntry can consume 16 bytes.
and we can use up to 5 entries (80 / 16) without consuming extra space in
GenericHuffmanTable<T>, if we add dedicated variant for each number of entries.
(I haven't checked if adding another variants improves the speed tho)

Comment 2

[Tooru Fujisawa [:arai]]

Attachment: Bug 1586971 - Add SingleEntryHuffmanTable. r?Yoric

Comment 3

[Tooru Fujisawa [:arai]]

just noticed that we don't need HuffmanEntry<T> field but just T
will post fixed one.
this reduces the size by 8.
(might apply for 2 or more entires case)

Comment 4

[Nicolas B. Pierron [:nbp]]

(In reply to Tooru Fujisawa [:arai] from comment #0)

single-entry table can appear frequently, and allocating 1 entry Vector is inefficient in term of Mutex and also space-efficiency.

Based on this comment, I would have expected the patch to look like:

- using Table = Vector<Foo, 0, systemAllocPolicy>;
+ using Table = Vector<Foo, 1, systemAllocPolicy>;

Comment 5

[Tooru Fujisawa [:arai]]

(In reply to Nicolas B. Pierron [:nbp] from comment #4)

(In reply to Tooru Fujisawa [:arai] from comment #0)

single-entry table can appear frequently, and allocating 1 entry Vector is inefficient in term of Mutex and also space-efficiency.

Based on this comment, I would have expected the patch to look like:

- using Table = Vector<Foo, 0, systemAllocPolicy>;
+ using Table = Vector<Foo, 1, systemAllocPolicy>;

Yeah, that also works in term of reducing allocation in SingleLookupHuffmanTable.
but adding pre-allocated elements in Vector increases the size of SingleLookupHuffmanTable (because of bigger Vector.mTail),
and that results in increasing the size of GenericHuffmanTable (because SingleLookupHuffmanTable becomes the biggest type),
while adding another non-Vector variant doesn't,
so I chose this way for space-efficiency.

Comment 6

[Tooru Fujisawa [:arai]]

another solution would be making SingleLookupHuffmanTable's implementation a Variant internally, and use static array variant for smaller case.
this would also solve the case that SingleLookupHuffmanTable is used inside MultiLookupHuffmanTable and the SingleLookupHuffmanTable gets only 1 item.

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/0c243363fa85
Add SingleEntryHuffmanTable. r=Yoric

Comment 8

[Dorel Luca [:dluca]]

https://hg.mozilla.org/mozilla-central/rev/0c243363fa85