Optimize LOS for better parallelization. (mono/mono#17173)
authorJohan Lorensson <lateralusx.github@gmail.com>
Wed, 23 Oct 2019 18:58:04 +0000 (20:58 +0200)
committerAleksey Kliger (λgeek) <alklig@microsoft.com>
Wed, 23 Oct 2019 18:58:04 +0000 (14:58 -0400)
commitf3fce827bd5a43a6ba35c9a93deb6abe335ebdae
treeeeaae942ac9b2476c37b9014c82598ee2f360c02
parentca40ea5f7a0430422c9a3940fc939fc528f8bc86
Optimize LOS for better parallelization. (mono/mono#17173)

Scanning LOS list as part of minor GC didn't parallelize well since
all scan jobs needed to walk the complete LOS list. This led to touching
a lot of memory walking the list, increasing minor GC pause times
when the number of items in the LOS list increased. As an example,
stressing LOS data structure using ~600 MB's of random sized byte arrays
caused minor GC pause times between ~20ms without parallelization and ~19ms
with parallelization. NOTE, the more work each job gets (more memory to scan)
we will get a better parallelization, but still a lot of room for improvement.

Changing from a normal linked list to a SgenArrayList makes it more effective
to parallelize the scan jobs and since the list is using sequential
memory, this will also reduce cache misses for each thread iterating LOS
objects. Tagging objects in SgenArrayList with reference information reduce
cache misses dramatically in cases where objects not including references
exists on the list, since scanning jobs can skip these items without any
need to touch object memory causing cache misses.

Same scenario running with fix gives us minor GC pause times, without
parallelization in ~7ms (down from 20~ms) and with parallelization,
< 5ms (down from 19ms). NOTE, the more work each job gets (more memory to scan)
we will get a better result using parallelization, so the delta will increase
between using and not using parallelization, this scenario primarily stress
the extreme case where most LOS objects doesn't have references.

In total, this optimization reduce minor GC pause time 4x, from ~19ms when
using parallelization down to < 5ms.

Commit migrated from https://github.com/mono/mono/commit/df30c7228c4061573601ea9a71772cc6f00e4b85
src/mono/mono/metadata/sgen-mono.c
src/mono/mono/sgen/sgen-array-list.h
src/mono/mono/sgen/sgen-debug.c
src/mono/mono/sgen/sgen-gc.c
src/mono/mono/sgen/sgen-gc.h
src/mono/mono/sgen/sgen-los.c