Exploring Garbage Collection
withHaswell Transactional Memory Hardware
Basic elements
1.01
Logo

MASTER VERTICALAND HORIZONTAL
LOGOS
The master logo is supplied in two formats:vertical and horizontal. The vertical format
shown here is the preferred version. Use of
the horizontal version is limited to specificapplications (see below).
A University logo or appropriate sub-brand must
appear on all communications.

Note• Always use themaster artwork
provided. The logo
should always beclear and visible.
Do not try andrecreate the logo.
• It should neverbe placed onto abackground thatmakes it difficult toread. (See page 1.06
Do not…)• See page 1.02 for aCarl Ritson
Tomoharu Ugawa
Richard Jones
2014/06/12

Intel’s Haswell
Transactional Memory Extensions (TSX-NI)

2

Transactional Synchronisation Extensions(Restricted) Transactional Memory... with limited processor support

3

XBEGIN ... XEND
Up to ~16KiB of read and writes

4Complexities
Setup of transaction is expensive (3x CAS)
Fallback required if transaction fails
Aborted transactions expensive

5

Uses for TSX-NI
Simplify parallel collector activities
Facilitate concurrent bitmap marking
Accelerating concurrent copying collection

6

Concurrent Copying Collection
Sapphire on-the-fly concurrent copying collector[Hudson and Moss, 2001 & 2003]

7

Startfrom-space
Object 1

Object 2

Object 38

MarkPhase

from-spaceto-space

Object 1

Object 1'

Object 2

Object 2'

Object 3

Object 3'

9

Copy
Phase

from-space

to-space

Object 1

Object 1'

Object 2

Object 2'

Object 3

Object 3'

10

Copy
Phase

from-space

to-space

Object 1

Object 1'

Object 2

Object 2'

Object 3

Object 3'

Mutator
11

Copy
Phase

from-space

to-space

Object 1

Object 1'

Object 2

Object 2'

Object 3

Object 3'

Mutator
12

Copy
Phasefrom-space

to-space

Object 1

Object 1'

Object 2

Object 2'

Object 3

Object 3'

Mutator13

FlipPhase

from-space

to-space

Object 1

Object 1'

Object 2

Object 2'

Object 3

Object 3'

Mutator14

Finishto-space
Object 1'

Object 2'

Object 3'

Mutator15

Synchronised Replication (Copying Phase)
Mutator updates from-space and to-space
Collector copies data to to-space16

casu = load (to-space)v = load (from-space)
if (u != v)
compare-and-swap (to-space, u, v)
restartelse
break

17

unsafev = load (from-space)store (to-space, v)18

htm
XBEGIN
v1 = load (from-space)store (to-space, v1)
v2 = load (from-space)store (to-space, v2)
...
XEND

19

mhtm
XBEGINcopy object 1
copy object 2...
copy object n
XEND

20

mhtm
scan and record object 1 .. n
XBEGINcopy object 1
copy object 2...
copy object n
XEND

21

stm
v1 = load (from-space)store (to-space, v1)
v2 = load (from-space)store (to-space, v2)...
MFENCE
verify to-space with from-space

22

Test Setup
Intel Core i7-4770 3.4Ghz, 16GiB RAM
Ubuntu 12.04.3 LTS
DaCapo 2006 (sunflow from 2009)
Fixed 350m heap and GC trigger

23

Copy speed
bytes copied / time in copy phase

24

25

mutators running

26

Transactional Penalty
Normal reads= 11 bytes/ns

Normal writes= 6 bytes/ns

Transactional reads = 9 bytes/ns (~80%)
Transactional writes = 6 bytes/ns (100%)27

Peak Performance
Unsafe = 440 bytes/us
440 * 0.8 = 352 bytes/us (exactly as observed)

28

Scaling

29

gc threads

30

Conclusions (Specific)
Speed up of 48-101% for concurrent copying collection
Weak consistency requirements make STM possible
No improvement for bitmap marking and parallel copying

31

Conclusions (General)
Transactional work must be sufficient and concise
Engineering this can add overheads which outweigh benefits

32

Future WorkNew collector designs which exploit strong consistency
Ground up batching of work for transactions... mostly barrier free on-the-fly collection?

33

Questions?
Code: http://github.com/perlfu/sapphire34