1424934 - Investigate using one byte per cell for marking information

Status: RESOLVED WONTFIX

(Core :: JavaScript: GC, enhancement, P5)

Description

[Jon Coppeard (:jonco)]

Currently we store marki

Comment 1

[Jon Coppeard (:jonco)]

Currently we store mark bits in a per-chunk sparse bitmap with two bits allocated for every possible start position.

To support parallel marking we'd like to move to having a single byte per cell.  Probably this would be stored in the arena rather than at the end of the chunk.  We could store them after the arena header before the first cell, for example.

The current arrangement was chosen because it has good cache behaviour, so there may be perf implications to moving to a different arrangement.  We should try this and see what difference it makes.  It may be worth taking a small hit in throughput if it unlocks larger gains later on.

Comment 2

[Jon Coppeard (:jonco)]

I just realised that this will complicate the implementation of atom marking: this copies the mark bits for arenas containing atoms and uses them to maintain per-zone bitmaps which represent an over-approximation of the atoms held live by that zone.  This is done using bitwise operations, memcpy, etc.  

Using one byte per atom could increase the memory usage substantially.  We may have to map atom marking information to a one-bit-per-atom bitmap to avoid this penalty.

Comment 3

[Randell Jesup [:jesup] (needinfo me)]

It's possible that moving mark bits away from the allocations would be a security win (reducing ease of leveraging bounds-overwrites: see https://bugs.chromium.org/p/chromium/issues/detail?id=633030)

Comment 5

[Jon Coppeard (:jonco)]

Attachment: Bug 1424934 - Replace the chunk's mark bitmap with one byte per cell in the arena r?sfink

Try is looking good and performance results don't show any major regressions. There's still room for improvement though.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/d389e3aa4522
Replace the chunk's mark bitmap with one byte per cell in the arena r=sfink,jandem

Comment 7

[Arthur Iakab [arthur_iakab]]

https://hg.mozilla.org/mozilla-central/rev/d389e3aa4522

Comment 8

[Arthur Iakab [arthur_iakab]]

https://hg.mozilla.org/mozilla-central/rev/d389e3aa4522

Comment 9

[Jon Coppeard (:jonco)]

Telemetry for 74 is now working and shows no discernable change from this so far.

Comment 10

[Jon Coppeard (:jonco)]

Sadly it seems this is has caused a performance regression on android. Mark time telemetry is showing a sizeable increase on aarch64 for version 74 (this change landed two days after branching).

Mark time telemetry on aarch64:

                73       74, to 15th
5th Percentile  10.29    10.4  
25th Percentile 55.07    51.62 
Median          89.11    99.39 
75th Percentile 151.8    215.07
95th Percentile 492.97   712.5 

Total GC time:

                73       74    
5th Percentile  25.6     25.9  
25th Percentile 93.98    87.69 
Median          148.45   165.7     +10%
75th Percentile 240.1    317.62    +32%
95th Percentile 723.69   965.18    +33%

Testing locally with a benchmark that constantly allocates shows a 10% time increase for long running GCs with this change.

I think this approach has been proved to work and can still be a stepping stone to further improvements (like concurrent marking) but until we have these other improvements ready to land we should back it out.

Comment 11

[Jon Coppeard (:jonco)]

Attachment: backout-1424934

Comment 12

[Pulsebot]

Backout by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/5fda66dee91f
Backed out changeset d389e3aa4522 as requested by jonco:

Comment 13

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

Backout merged: https://hg.mozilla.org/mozilla-central/rev/5fda66dee91f

Comment 14

[Alexandru Ionescu (needinfo me) [:alexandrui]]

== Change summary for alert #24772 (as of Thu, 23 Jan 2020 06:11:02 GMT) ==

Improvements:

1% Base Content JS windows7-32 opt 2,944,152.67 -> 2,929,577.33
1% Base Content JS windows7-32-shippable opt 2,944,152.67 -> 2,929,577.33
0.43% Base Content JS windows7-32-shippable opt 2,944,155.33 -> 2,931,488.00

For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=24772

Comment 15

[Jon Coppeard (:jonco)]

We're not planning to do this at the current time.