Performance
Physics Optimization Strategies
Sergiy Migdalskiy
Valve

1

My first computer

Do you remember yours?
2

User-friendly computer

ZX Spectrum
3

8-bit CPU

A CPU most fondly remembered
4

Back Then vs Now

5

Golden Oldies
Float24Mul:;BHL*CDE ->AHL
ld a,b \ xor cand 80h
push afsla b \ sra b
sla c \ sra c
ld a,badd a,cpop bcjp m,$+10
cp 64
jr nc,SetInf-2
jp $+7
cp -64
jr c,SetInf-2;B has the rightsignand 7Fhor bpush af
ld b,hld c,lcallBC_Times_DE
bit 7,lld l,hld h,bjr z,$+3inc hl
pop afret
BC_Times_DE:;BHLA is theresult
ld a,bor a
ld hl,0ld b,h;1
add a,ajr nc,$+4
ld h,dld l,e;2
add hl,hlrla

jr nc,$+4add hl,deadc a,b;227+10b-7p
add hl,hlrla
jr nc,$+4add hl,deadc a,b

jr nc,$+4add hl,deadc a,b;1

add hl,hlrla
jr nc,$+4add hl,deadc a,b;2

add hl,hlrla
jr nc,$+4add hl,deadc a,badd hl,hlrla
jr nc,$+4add hl,deadc a,badd hl,hlrla
jr nc,$+4add hl,deadc a,b;===;AHL is the resultof B*DE*256
push hl
ld h,bld l,b
ld b,ald a,cadd hl,hl
rla

6

ld c,hadd a,ajr nc,$+4
ld h,dld l,eadd hl,hlrla
jr nc,$+4add hl,deadc a,cadd hl,hlrla
jr nc,$+4add hl,deadc a,c;227+10b-7p
add hl,hlrla
jr nc,$+4
add hl,deadc a,c

add hl,hlrla
jr nc,$+4add hl,deadc a,cadd hl,hlrla
jr nc,$+4add hl,deadc a,c

add hl,hlrla
jr nc,$+4add hl,deadc a,cadd hl,hlrla
jr nc,$+4add hl,deadc a,cpop de;NowBDE*256+AHL
ld c,ald a,lld l,hld h,cadd hl,de
ret ncinc b;BHLA is the 32bit result
retBrave New World

mulss
mulps
vmulps1 float4 floats
8 floats
7

I’ve got the Power!
virtual void Foo();…
pObject->Foo();•Fetch object pointer•Fetch Vtable pointer•Fetch Vtable entry

8

The cost of a cache miss9

Cache miss opportunity cost10

Main Memory Is Not Slow
4
Core

464 K

464 K

11~2064 K

100+

64 K

2+G/s/core

~20

256 K

L3
2..20 M

RAM

100+

~20

256 K

8-36 G/s

~20

256 K

100+

256 K

100+

4CoreCoreCore

Main Memory Is Latent

12

Think Short

p[0]->x, p[1]->x, p[2]->x, p[3]->x

13

Think Short

p[0]->x, p[1]->x, p[2]->x, p[3]->x

14

Cache lines are indivisible
Pack & Align

15

One Cycle per Byte~2 G/s
Core~2 G/s
CoreRAM~8 G/s~2 GHz~2 G/s
Core~2 G/s
Core16

Measure
Estimate
VerifyRepeat17

Compute-Bound
Predictable
We are trained for thisHard to achieve

18

Opportunity cost: take 219

Cache Misses…

…they’re bad20Cache miss 2x

New Norm: 1.5 IPC

21

Cache Miss: Ticks
Last-gen PowerPC

Modern x86/AMD64

500

375

250

1250Ticks22

3+ IPC and beyond

1 tick{mov %r11,%r10
mov %rsi,%rcx
mov %r13,%r12
mov %r15,%r1423

inc %r11
inc %r10inc %rsi}

1 tickCache miss: RealCost (tm)Last-gen PowerPC

Modern x86/AMD64

500375250

1250Ticks

Instructions Delayed** Not-So-Rigorous Analysis (tm)24

OOO FTW!

25

OOO Limits

26

OOO Limits IRL

27

Latency and Throughput
mulps
mulps
mulps
mulps

Dependency Graph

29

Think Short ChainsMore opportunities to reorder
Many cache misses resolve at once

30

Reorder Buffer
New CPUs*: 192 entries
Finite code window* Intel Haswell, Apple Cyclone

31

Short Chains FTW

32

OOO: The New Old

Real CPU Latency
200150100500Latency

Real Latency** The Real Latency: a technical term (tm)34

PrefetchLinear Streams
Cache Miss Overlap
Fix All or Nothing

35

Maxing RAM out

36

Load Balance

RAMCPU8%9%37

Prefetch Techniques
Use Linear Streams
Rely on Reordering
Manual prefetch

3837 GB/s? Really?
40

30

20

100
1 Stream

2 Streams

2x2 Streams

39

Many Streams

1 byte per op~2 G/s
Core~2 G/s
Core
RAM~8 G/s

~2 GHz~2 G/s
Core~2 G/s
Core

40

Cache Misses…

…beware of ‘em.

41Bandwidth: take 2
1. Load Data
2. …Other Stuff (150+ cycles)…
3. Use Data42

Bandwidth: Hi-End

Lo-End: 1 byte/cycle
Hi-End: 3-4 bytes/cycle

43

Load Hit Store
int32

Don’t Mix
int16

int16

44

Writing is Reading
Stores affect cache(pollution, migration)
Branches are inexpensive

45

Branch (mis)prediction
Predictability=performance
1-4 deep history
random = 50% mispredicted
misprediction is ~10-20 ticks

46

Branch Prediction
predicted branch ~0-1 tick
~100% consistent = ~100% predicted

47

48

Careful: Recursion

Return Stack Buffer
Typically 8-24 deep49

Case study: cloth• 16 verts• 1.6 Instructions per Cycle• 600 cycles• 5 cache lines streamed• 8 cache lines random access• ~1.4 bytes per cycle• ALU bound, RAM: 4.7 G/s
50

Cycles / IterationnStart = __rdtsc();for( int i = 0; i < N; ++i)
OneIteration();Cycles +=__rdtsc() - nStart;
Iterations += N;
51

Derived Metrics
Instructions per cycle
Cycles per byte
Instructions per byte
Bytes per second52

OOO: cost/benefit

53

OOO is good54

SummaryCache• OOO• RAM• 1 byte per op•55

8 bit Rulez!
8-bit64-bit

Small PointersYesNoFixed Addresses

Yes

No56

Relative PointerRPointer< Foo >Foo *Same in 32- and64-bit

Yes

NoMoveable

Yes

No57

Relative Pointer
7FFF01B0…….

01B0……..

0000

58

Limitations+/-0x7FFF

16-bit —> +/-32KB
32-bit —> +/-2GB59

RPointer<T>
template <typename T>class RPointer{unsigned short m_nOffset;
public:T* operator -> (){Assert( m_nOffset != 0 ); // must not be NULL
return ( ( byte* )&m_nOffset ) + m_nOffset;}};void operator = (T*p){m_nOffset = p?((byte*)p)-(byte*)this:0;}60

Recap: sandbox

61

Recap: pointers

62

Cache Misses…

…did I mention ‘em?

63

Recap: moveable64Filling In
VirtualAllocCommit
65Pointer vs Offset
struct Elem
{RPointer<Elem> m_pNext;
int m_nData;};…
Elem *p = new(pAllocator) Elem;p->m_pNext = NULL;
p->m_nData = 123;

struct Elem
{Elem *m_pNext;
int m_nData;};…
Elem *p = new(pAllocator) Elem;p->m_pNext = NULL;
p->m_nData = 123;66

Strengths• Very simple• No runtime overhead• Data is relocatable• Data is more compact

67

Limitations• No Automatic Versioning• Continuous Data Block• More Stuff to Learn

68SummaryCache• OOO• RAM• 1 byte per op• Resource Pointers•69Simpler times

VIdeo: simple sequence of instructions

70

Big O71

Tricks72

O*(?)How useful is O*?

73

“0”
Best optimization everDo nothing

74

O(1)
•Cache it•Do it once per frame•Approximate it•Be creative…

75

≡O(N) O(200*N)

Array

List76

N ≠ 200*N

Array

List77

O* nuances
TraversalCache Misses
in Traversal

Array

O(N)

O(0)

Linked List

O(N)

O(N)

78

Map vs Hashtable
Classic RB-TreeClassic Hash
Table

Worst-Case

O(log N)

O(N)

AmortizedO(log N)

O(1)

79

Priorities
Cache-Friendly Algorithms•Algorithm vs Cache•C1 * N vs C2 * log N•CPU vs Memory

Depends on N, C1 and C2

Where’s the Bottleneck?
80

Simpler times (cont'd)81Cache misses…

…the wildcard of perf82

Next stop: SIMD
Writing Physics?
ALU bound?
SIMD!

83

What to SIMDize
Repetitive
Independent
Computations

84How to SIMDize
Debug Scalar code
Have No Branches
Interleave data
SIMDize code85Gather86

Scatter87

Free Lunch for SIMD
Full

Ports #0,#1,#5
Port #2

Partially Idle

Port #3

Partially Idle

Port #4

Partially Idle
88

Swizzle-Pack Data

89

Gather-Scatter
Pack your data
Gather-Scatter pipeline well
1 op per byte

90

Interleave
Scalar Path
No Branches
template <typename Float>91

template <typename Float>
template <typename Float >inline SinCos< Float> ApproximateGivensRotation( const Float & a11, const Float & a12,
const Float & a22 ){const Float two = Replicate<Float>( 2.0f );Float ch = two * ( a11 - a22 );Float sh = a12;
typename FloatTraits<Float>::Bool b = CmpLt( Replicate<Float>( 5.82842712474619f ) *sh*sh, ch*ch );Float omega = RsqrtEst( ch*ch + sh *sh );SinCos<Float>res;res.s = Select( Replicate<Float>( 0.3826834323650897717284599840304f ), omega * sh, b );res.c = Select( Replicate<Float>( 0.92387953251128675612818318939679f ), omega * ch, b );return res;}92

SIMD data structures
struct SimdRod{
uint16 nNode[ 2 ][ 4 ];float4 f4MaxDist;float4 f4MinDist;float4 f4MassRatio;
float4 f4RelaxationFactor;
void Init( const Rod pScalar[4] );};struct Rod{
uint16 nNode[ 2 ];float flMaxDist;float flMinDist;float flMassRatio;
float flRelaxationFactor;};93

Cloth SIMD order94

SIMD lanes•Homogenous•Independent
Semi-Myth: SIMD is premature optimization

95

SIMD branches (ala GPU)

96

SIMD branches (multipass)
1. Sort into batches
2. Process batches
3. Merge results

97

SIMD
The Good:• Almost 4x perf
• Separable=Easy• AVX: 66% users• Easy to Write

The Bad:• Hard to Retrofit• Hard to Automate• Requires Planning• Hard to Read98

Performance Re-CapCache
• OOO
• RAM
• 1 byte per op• Resource Pointers• O*(…)• SIMD• Multi-Thread•99

Special Thanks
3D Art Support - Anna Bibikova
2D Art Support - Heather Campbell

100LinksAgner Fog Software Optimization Resrouces
http://agner.org
Software optimization guide for AMD processors
http://support.amd.com/TechDocs/25112.PDF
Intel® 64 and IA-32 Architectures Optimization Reference Manual
http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html

Intel® Architecture Code Analyzer
https://software.intel.com/en-us/articles/intel-architecture-code-analyzer

The Art of Multiprocessor ProgrammingIntel VTune
VerySleepy
GlowCode
Luke Stackwalker

101Attribution
Images of Z80: "Z80A-HD" by ZeptoBars - Licensed under CC BY 3.0 via Wikimedia
Commons - http://commons.wikimedia.org/wiki/File:Z80A-HD.jpg#mediaviewer/File:Z80AHD.jpg• Image of Haswell wafer - licensed under the Creative Commons Attribution 2.0 Genericlicense. http://en.wikipedia.org/wiki/Haswell_(microarchitecture)#mediaviewer/
File:Haswell_Chip.jpg• Image of Radio-86RK: created by Audriusa, available under the Creative Commons CC0
1.0 Universal Public Domain Dedication. https://commons.wikimedia.org/wiki/
File:Radio86RK.png• Listing of 24-bit float multiplication for Z80: https://drive.google.com/folderview?
id=0B4HNIXQZLWM8Z3NQMGJTbHVhRm8&usp=sharing, licensed for free use anddistribution• ZX Spectrum picture - http://commons.wikimedia.org/wiki/File:ZXSpectrum48k.jpg - CC2.5•102

Performance Recipe• Better Algorithm!
• 1 byte per op• Stream• Prefetch• SIMDize• Multithread• Profit!
103

Videos, Links and Errata

http://sergiy.space104