0% found this document useful (0 votes)

10 views24 pages

Codedive CPUCachesHandouts

Uploaded by

billzheng888

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

10 views24 pages

Codedive CPUCachesHandouts

Uploaded by

billzheng888

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 24

CPU Caches and Why You Care

Scott Meyers, Ph.D.

Software Development Consultant
http://aristeia.com
[email protected]
Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Last Revised: 10/28/14

A Tale of Two Traversals

Two ways to traverse a matrix:
 Each touches exactly the same memory.

Row Major Column Major

Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Slide 2

A Tale of Two Traversals

Code very similar:
void sumMatrix( const Matrix<int>& m,
long long& sum, TraversalOrder order)
{
sum = 0;
if (order == RowMajor) {
for (unsigned r = 0; r < m.rows(); ++r) {
for (unsigned c = 0; c < m.columns(); ++c) {
sum += m[r][c];
}
}
} else {
for (unsigned c = 0; c < m.columns(); ++c) {
for (unsigned r = 0; r < m.rows(); ++r) {
sum += m[r][c];
}
}
}
}
Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Slide 3

A Tale of Two Traversals

Performance isn’t:

A Tale of Two Traversals

Traversal order matters.
Why?

A Scalability Story
Herb Sutter’s scalability issue in counting odd matrix elements.
 Square matrix of side DIM matrix
with memory in array matrix.
DIM
 Sequential pseudocode:
int odds = 0; DIM
for( int i = 0; i < DIM; ++i )
for( int j = 0; j < DIM; ++j )
if( matrix[i*DIM + j] % 2 != 0 )
++odds;

A Scalability Story
 Parallel pseudocode, take 1:
int result[P];
// Each of P parallel workers processes 1/P-th of the data;
// the p-th worker records its partial count in result[p]
for (int p = 0; p < P; ++p )
matrix
pool.run( [&,p] {
result[p] = 0; DIM
int chunkSize = DIM/P + 1;
int myStart = p * chunkSize;
int myEnd = min( myStart+chunkSize, DIM ); DIM
for( int i = myStart; i < myEnd; ++i )
for( int j = 0; j < DIM; ++j )
if( matrix[i*DIM + j] % 2 != 0 )
++result[p]; } );
pool.join(); // Wait for all tasks to complete
odds = 0; // combine the results
for( int p = 0; p < P; ++p )
odds += result[p];
Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Slide 7

A Scalability Story
Scalability unimpressive:

Faster than
1 core

Slower than
1 core

A Scalability Story
 Parallel pseudocode, take 2:
int result[P];
for (int p = 0; p < P; ++p )
pool.run( [&,p] {
int count = 0; // instead of result[p]
int chunkSize = DIM/P + 1;
int myStart = p * chunkSize;
int myEnd = min( myStart+chunkSize, DIM );
for( int i = myStart; i < myEnd; ++i )
for( int j = 0; j < DIM; ++j )
if( matrix[i*DIM + j] % 2 != 0 )
++count; // instead of result[p]
result[p] = count; } ); // new statement
... // nothing else changes

A Scalability Story
Scalability now perfect!

A Scalability Story
Thread memory access matters.
Why?

CPU Caches
Small amounts of unusually fast memory.
 Generally hold contents of recently accessed memory locations.
 Access latency much smaller than for main memory.

CPU Caches
Three common types:
 Data (D-cache, D$)
 Instruction (I-cache, I$)
 Translation lookaside buffer (TLB)
 Caches virtual→real address translations

Voices of Experience
Sergey Solyanik (from Microsoft):
Linux was routing packets at ~30Mbps [wired], and wireless at
~20. Windows CE was crawling at barely 12Mbps wired and
6Mbps wireless. ...
We found out Windows CE had a LOT more instruction cache
misses than Linux. ...
After we changed the routing algorithm to be more cache-local, we
started doing 35MBps [wired], and 25MBps wireless - 20% better
than Linux.

Voices of Experience
Jan Gray (from the MS CLR Performance Team):
If you are passionate about the speed of your code, it is imperative
that you consider ... the cache/memory hierarchy as you design
and implement your algorithms and data structures.
Dmitriy Vyukov (developer of Relacy Race Detector):
Cache-lines are the key! Undoubtedly! If you will make even single
error in data layout, you will get 100x slower solution! No jokes!

Cache Hierarchies
Cache hierarchies (multi-level caches) are common.
E.g., Intel Core i7-9xx processor:
 32KB L1 I-cache, 32KB L1 D-cache per core
 Shared by 2 HW threads
 256 KB L2 cache per core
 Holds both instructions and data
 Shared by 2 HW threads

 8MB L3 cache
 Holds both instructions and data
 Shared by 4 cores (8 HW threads)

Core i7-9xx Cache Hierarchy

Core 0
T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache
Core 1

T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache
Main
L3 Cache
Memory
Core 2

T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache
Core 3

T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache

CPU Cache Characteristics

Caches are small.
 Assume 100MB program at runtime (code + data).
 8% fits in core-i79xx’s L3 cache.
 L3 cache shared by every running process (incl. OS).
 0.25% fits in each L2 cache.
 0.03% fits in each L1 cache.
Caches much faster than main memory.
 For Core i7-9xx:
 L1 latency is 4 cycles.
 L2 latency is 11 cycles.
 L3 latency is 39 cycles.
 Main memory latency is 107 cycles.
 27 times slower than L1!
 100% CPU utilization ⇒ >99% CPU idle time!

Effective Memory = CPU Cache Memory

From speed perspective, total memory = total cache.
 Core i7-9xx has 8MB fast memory for everything.
 Everything in L1 and L2 caches also in L3 cache.
 Non-cache access can slow things by orders of magnitude.
Small ≡ fast.
 No time/space tradeoff at hardware level.
 Compact, well-localized code that fits in cache is fastest.
 Compact data structures that fit in cache are fastest.
 Data structure traversals touching only cached data are fastest.

Cache Lines
Caches consist of lines, each holding multiple adjacent words.
 On Core i7, cache lines hold 64 bytes.
 64-byte lines common for Intel/AMD processors.
 64 bytes = 16 32-bit values, 8 64-bit values, etc.
 E.g., 16 32-bit array elements.
Main memory read/written in terms of cache lines.
 Read byte not in cache ⇒ read full cache line from main memory.
 Write byte ⇒ write full cache line to main memory (eventually).
Cache
Line
byte

Cache Lines
Explains why row-major matrix traversal better than column-major:

Cache Line Prefetching

Hardware speculatively prefetches cache lines:
 Forward traversal through cache line n ⇒ prefetch line n+1
 Reverse traversal through cache line n ⇒ prefetch line n-1

Implications
 Locality counts.
 Reads/writes at address A ⇒ contents near A already cached.
 E.g., on the same cache line.
 E.g., on nearby cache line that was prefetched.
 Predictable access patterns count.
 “Predictable” ≅ forward or backwards traversals.
 Linear array traversals very cache-friendly.
 Excellent locality, predictable traversal pattern.
 Linear array search can beat log2 n searches of heap-based BSTs.
 log2 n binary search of sorted array can beat O(1) searches of
heap-based hash tables.
 Big-Oh wins for large n, but hardware caching takes early lead.

Cache Coherency
From core i7’s architecture:
Core 0

T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache
Main
L3 Cache
Memory
Core 1

T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache

Assume both cores have cached the value at (virtual) address A.

 Whether in L1 or L2 makes no difference.
Consider:
 Core 0 writes to A.
 Core 1 reads A.
What value does Core 1 read?
Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Slide 24

Cache Coherency
Caches a latency-reducing optimization:
 There’s only one virtual memory location with address A.
 It has only one value.
Hardware invalidates Core 1’s cached value when Core 0 writes to A.
 It then puts the new value in Core 1’s cache(s).
Happens automatically.
 You need not worry about it.
 Provided you synchronize access to shared data...
 But it takes time.

False Sharing
Suppose Core 0 accesses A and Core 1 accesses A+1.
 Independent pieces of memory; concurrent access is safe.
 But A and A+1 probably map to the same cache line.
 If so, Core 0’s writes to A invalidates A+1’s cache line in Core 1.
 And vice versa.
 This is false sharing.
Core 0

T0 L1 I-Cache
L2 Cache
T1 L1 D-Cache
Main
... A-1 A A+1 ... L3 Cache
Memory
Core 1

T0 L1 I-Cache
Line from Core 0’s cache L2 Cache
T1 L1 D-Cache

... A-1 A A+1 ...

Line from Core 1’s cache

False Sharing
It explains Herb Sutter’s issue:
int result[P]; // many elements on 1 cache line
for (int p = 0; p < P; ++p )
pool.run( [&,p] { // run P threads concurrently
result[p] = 0;
int chunkSize = DIM/P + 1;
int myStart = p * chunkSize;
int myEnd = min( myStart+chunkSize, DIM );
for( int i = myStart; i < myEnd; ++i )
for( int j = 0; j < DIM; ++j )
if( matrix[i*DIM + j] % 2 != 0 )
++result[p]; } ); // each repeatedly accesses the
// same array (albeit different
// elements)

False Sharing
And his solution:
int result[P]; // still multiple elements per
// cache line
for (int p = 0; p < P; ++p )
pool.run( [&,p] {
int count = 0; // use local var for counting
int chunkSize = DIM/P + 1;
int myStart = p * chunkSize;
int myEnd = min( myStart+chunkSize, DIM );
for( int i = myStart; i < myEnd; ++i )
for( int j = 0; j < DIM; ++j )
if( matrix[i*DIM + j] % 2 != 0 )
++count; // update local var
result[p] = count; } ); // access shared cache line
// only once

False Sharing
His scalability results are worth repeating:

With False Sharing Without False Sharing

False Sharing
Problems arise only when all are true:
 Independent values/variables fall on one cache line.
 Different cores concurrently access that line.
 Frequently.
 At least one is a writer.
All types of data are susceptible:
 Statically allocated (e.g., globals, statics).
 Heap allocated.
 Automatics and thread-locals (if pointers/references handed out).

Voice of Experience
Joe Duffy at Microsoft:
During our Beta1 performance milestone in Parallel Extensions,
most of our performance problems came down to stamping out
false sharing in numerous places.

Summary
 Small ≡ fast.
 No time/space tradeoff in the hardware.
 Locality counts.
 Stay in the cache.
 Predictable access patterns count.
 Be prefetch-friendly.

Guidance
For data:
 Where practical, employ linear array traversals.
 “I don’t know [data structure], but I know an array will beat it.”
 Use as much of a cache line as possible.
 Bruce Dawson’s antipattern (from reviews of video games):
struct Object { // assume sizeof(Object) ≥ 64
bool isLive; // possibly a bit field
...
};
std::vector<Object> objects; // or an array
for (std::size_t i = 0; i < objects.size(); ++i) { // pathological if
if (objects[i].isLive) // most objects
doSomething(); // not alive
}
 Be alert for false sharing in MT systems.
Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Slide 33

Guidance
For code:
 Fit working set in cache.
 Avoid iteration over heterogeneous sequences with virtual calls.
 E.g., sort sequences by type.
 Make “fast paths” branch-free sequences.
 Use up-front conditionals to screen out “slow” cases.
 Inline cautiously:
 The good:
 Reduces branching.
 Facilitates code-reducing optimizations.
 The bad:
 Code duplication reduces effective cache size.
 Take advantage of PGO and WPO.
 Can automate some of above.

Beyond Surface-Scratching
Cache-related topics not really addressed:
 Other cache technology issues:
 Memory banks.
 Associativity (but wait...).
 Inclusive vs. exclusive content.

 Latency-hiding techniques.
 Hyperthreading.

 Cache performance evaluation:

 Why it’s critical.
 Why it’s hard.
 Tools that can help.

 Cache-oblivious algorithm design.

Beyond Surface-Scratching
Overall cache behavior can be counterintuitive.
Matrix traversal redux:
 Matrix size can vary.

 For given size, shape can vary:

Beyond Surface-Scratching
Row major traversal performance unsurprising:

Beyond Surface-Scratching
Column major a different story:

Beyond Surface-Scratching
A slice through the data:

Beyond Surface-Scratching
Igor Ostrovsky’s demonstration of cache-associativity effects.
 White ⇒ fast.
 Blue ⇒ slow.

Further Information
CPU caches:
 What Every Programmer Should Know About Memory, Ulrich
Drepper, 21 November 2007,
http://people.redhat.com/drepper/cpumemory.pdf.
 “CPU cache,” Wikipedia.
 “Gallery of Processor Cache Effects,” Igor Ostrovsky, Igor
Ostrovsky Blogging (Blog), 19 January 2010.
 “Writing Faster Managed Code: Know What Things Cost,” Jan
Gray, MSDN, June 2003.
 Relevant section title is “Of Cache Misses, Page Faults, and
Computer Architecture”
 “Optimizing for instruction caches,” Amir Kleen et al., EE Times,
29 Oct. 2007 (part 1), 5 Nov. 2007 (part 2), 12 Nov. 2007 (part 3).
 “Memory is not free (more on Vista performance),” Sergey
Solyanik, 1-800-Magic (Blog), 9 December 2007.
 Experience report about optimizing use of I-cache.
Scott Meyers, Software Development Consultant © 2013 Scott Meyers, all rights reserved.
http://www.aristeia.com/ Slide 41

Further Information
CPU caches:
 “Martin Thompson on Mechanical Sympathy,” Software
Engineering Radio, 19 February 2014.
 “Eliminate False Sharing,” Herb Sutter, DrDobbs.com, 14 May
2009.
 “False Sharing is no fun,” Joe Duffy, Generalities & Details:
Adventures in the High-tech Underbelly (Blog), 19 October 2009.
 “Real-World Concurrency,” Bryan Cantrill and Jeff Bonwick,
ACM Queue, September 2008.
 Discusses false sharing.

 “Native Code Performance and Memory: The Elephant in the

CPU,” Eric Brumer, Channel 9, 28 June 2013.
 Video of a Build 2013 presentation.

 “07-26-10 – Virtual Functions,” Charles Bloom, cbloom rants

(Blog), 26 July 2010.
 Note ryg’s comment about per-type operation batching.

Further Information
Data-oriented design:
 “Data-Oriented Design and C++,” Mike Acton, CppCon 2014,.
 Conference keynote presentation.
 Video available at YouTube.
 “Pitfalls of Object Oriented Programming,” Tony Albrecht,
Game Connect: Asia Pacific 2009.

Further Information
Profile-guided optimization (PGO):
 “Profile-Guided Optimizations,” Gary Carleton, Knud
Kirkegaard, and David Sehr, Dr. Dobb’s Journal, May 1998.
 Still a very nice overview.

 “The Future of Code Coverage Tools,” Mohammad Haghighat

and David Sehr, StickyMinds.com.
 “Build faster and high performing native applications using
PGO,” Ankit Asthana, Visual C++ Team Blog, 4 April 2013.
 “/GL and PGO,”Lin Xu, Visual C++ Team Blog, 1 December 2009.
 “POGO,” Lawrence Joel, Visual C++ Team Blog, 12 November
2008.
 “Profile Guided Optimizations,” Shachar Shemesh, Scribd,
Uploaded 3 June 2009, http://tinyurl.com/2u6lvln.
 Much code optimization info, including PGO for gcc.

Further Information
More on PGO:
 “Cache Aware Data Layout Reorganization Optimization in
GCC,” Mostafa Hagog and Caroline Tice, Proceedings of the GCC
Developers’ Summit, June 2005.
 Using PGO to change DS layouts to improve D$ performance.

 “Profile driven optimisations in GCC,” Jan Hubička, Proceedings

of the GCC Developers’ Summit, June 2005.
 “GoingNative 12: C++ at Build 2012, Inside Profile Guided
Optimization,” Channel 9, 28 November 2012.
 Video interview about PGO support in MS Visual C++.

 “Profile Guided Optimization (PGO)—Under the Hood,” Ankit

Asthana, Visual C++ Team Blog, 27 May 2013.
 “The *New Performance Optimization Tool* for Visual C++
applications,” Ankit Asthana, Visual C++ Team Blog, 22 October
2013.

Further Information
Whole-program optimization (WPO):
 “Optimizing real-world applications with GCC Link Time
Optimization,” Taras Glek and Jan Hubička, Proceedings of the
GCC Developers’ Summit, October 2010.
 “Whole Program Optimization with Visual C++ .NET,” Brandon
Bray, The Code Project, 10 December 2001 .
 “Link-Time Code Generation,” Matt Pietrek, MSDN Magazine,
May 2002.
 “Quick Tips On Using Whole Program Optimization,” Jerry
Goodwin, Visual C++ Team Blog, 24 February 2009.
 “Introducing ‘/Gw’ Compiler Switch,” Ankit Asthana, Visual C++
Team Blog, 11 September 2013.
 Enables elimination of unused global data.

Licensing Information
Scott Meyers licenses materials for this and other training courses
for commercial or personal use. Details:
 Commercial use: http://aristeia.com/Licensing/licensing.html
 Personal use: http://aristeia.com/Licensing/personalUse.html
Courses currently available for personal use include:

About Scott Meyers

Scott is a trainer and consultant on the design and
implementation of C++ software systems. His web
site,
http://www.aristeia.com/
provides information on:
 Training and consulting services
 Books, articles, other publications
 Upcoming presentations
 Professional activities blog

Understanding Cache Memory Operations
No ratings yet
Understanding Cache Memory Operations
49 pages
08 Caches
No ratings yet
08 Caches
78 pages
4 Memory Models
No ratings yet
4 Memory Models
19 pages
GDC2003 Memory Optimization 18mar03
No ratings yet
GDC2003 Memory Optimization 18mar03
60 pages
Cache Memory: How Caching Works
No ratings yet
Cache Memory: How Caching Works
15 pages
4.chap6 Lookahead Vs Look Through Cache
No ratings yet
4.chap6 Lookahead Vs Look Through Cache
23 pages
L15 Cache Introduction
No ratings yet
L15 Cache Introduction
35 pages
Data Oriented Design for Efficient CPU Processing
No ratings yet
Data Oriented Design for Efficient CPU Processing
17 pages
Lecture Slides 07 071-Caches-Basics
No ratings yet
Lecture Slides 07 071-Caches-Basics
11 pages
Memory 2
No ratings yet
Memory 2
31 pages
Advanced Computer Architecture
No ratings yet
Advanced Computer Architecture
21 pages
CPSC 312 Cache Memories: Topics
No ratings yet
CPSC 312 Cache Memories: Topics
39 pages
Computer Architecture and Organization: Lecture15: Cache Performance
No ratings yet
Computer Architecture and Organization: Lecture15: Cache Performance
17 pages
Unit II
No ratings yet
Unit II
9 pages
Introduction to Cache Memory Systems
No ratings yet
Introduction to Cache Memory Systems
14 pages
Presentation 1
No ratings yet
Presentation 1
33 pages
Memory & Cache Fundamentals
No ratings yet
Memory & Cache Fundamentals
38 pages
Lecture Slides 07 071-Caches-Basics
No ratings yet
Lecture Slides 07 071-Caches-Basics
11 pages
10 Caches
No ratings yet
10 Caches
34 pages
Why Caches Matter
No ratings yet
Why Caches Matter
14 pages
CH04 COA9e
No ratings yet
CH04 COA9e
58 pages
Ddca 2024 Lecture24 Memory Hierarchy and Caches Beforelecture
No ratings yet
Ddca 2024 Lecture24 Memory Hierarchy and Caches Beforelecture
304 pages
Cache
No ratings yet
Cache
36 pages
Computer Engineering Students
No ratings yet
Computer Engineering Students
17 pages
Memory System Overview and Technologies
No ratings yet
Memory System Overview and Technologies
44 pages
Locality Principles in Caching Systems
No ratings yet
Locality Principles in Caching Systems
18 pages
Cache Performance and Write Strategies
No ratings yet
Cache Performance and Write Strategies
30 pages
Chapter 3 P1
No ratings yet
Chapter 3 P1
57 pages
Lec2 PDF
No ratings yet
Lec2 PDF
21 pages
Week 11
No ratings yet
Week 11
45 pages
Parallel & Distributed Computing
No ratings yet
Parallel & Distributed Computing
58 pages
CS 3853 Computer Architecture - Memory Hierarchy
No ratings yet
CS 3853 Computer Architecture - Memory Hierarchy
37 pages
Cache Memory Organization Guide
No ratings yet
Cache Memory Organization Guide
18 pages
Computer Architecture: Cache Memory
No ratings yet
Computer Architecture: Cache Memory
51 pages
Cache Memory Organization Guide
No ratings yet
Cache Memory Organization Guide
19 pages
CS 61C: Great Ideas in Computer Architecture: Lecture 12 - Memory Hierarchy/Direct-Mapped Caches
No ratings yet
CS 61C: Great Ideas in Computer Architecture: Lecture 12 - Memory Hierarchy/Direct-Mapped Caches
27 pages
Memory Cache
No ratings yet
Memory Cache
18 pages
High-Performance Managed Languages Guide
No ratings yet
High-Performance Managed Languages Guide
107 pages
Week 10
No ratings yet
Week 10
59 pages
Cache Simulation Overview
No ratings yet
Cache Simulation Overview
144 pages
CMP3010L09 MemoryII
No ratings yet
CMP3010L09 MemoryII
39 pages
Core Performance
No ratings yet
Core Performance
13 pages
Lecture 16
No ratings yet
Lecture 16
22 pages
Cache Memory Design in Computer Architecture
No ratings yet
Cache Memory Design in Computer Architecture
32 pages
Understanding CPU Caching
No ratings yet
Understanding CPU Caching
7 pages
03-Chap4-Cache Memory Mapping
No ratings yet
03-Chap4-Cache Memory Mapping
24 pages
10 Multi-Level Strategies: Assignments
No ratings yet
10 Multi-Level Strategies: Assignments
20 pages
Welcome To Part 3: Memory Systems and I/O
No ratings yet
Welcome To Part 3: Memory Systems and I/O
31 pages
Address Fields in Cache Memory System
No ratings yet
Address Fields in Cache Memory System
56 pages
Cache Memory Optimization Techniques
No ratings yet
Cache Memory Optimization Techniques
100 pages
Cache Memory & Design Principles
No ratings yet
Cache Memory & Design Principles
47 pages
Cache Memory
No ratings yet
Cache Memory
89 pages
CS33 S25 L14 OpenMP Intro Annotated
No ratings yet
CS33 S25 L14 OpenMP Intro Annotated
73 pages
IT3030E CA Chap6 Memory
No ratings yet
IT3030E CA Chap6 Memory
69 pages
Advanced Memory Systems Lecture
No ratings yet
Advanced Memory Systems Lecture
88 pages
Caches and Memory Hierarchy Explained
No ratings yet
Caches and Memory Hierarchy Explained
144 pages
High Performance Computing WS2022 Slides 5 Caches
No ratings yet
High Performance Computing WS2022 Slides 5 Caches
36 pages
ADO.NET Overview and Key Components
No ratings yet
ADO.NET Overview and Key Components
24 pages
CD 1
No ratings yet
CD 1
15 pages
Syntax Analysis: CD: Compiler Design
No ratings yet
Syntax Analysis: CD: Compiler Design
36 pages
5 Complexity: 5.1 The O Notation
No ratings yet
5 Complexity: 5.1 The O Notation
5 pages
Problem Solving and Algorithms PDF
No ratings yet
Problem Solving and Algorithms PDF
12 pages
Dynamic Memory Allocation in C++
No ratings yet
Dynamic Memory Allocation in C++
18 pages
PyCUDA AH PDF
No ratings yet
PyCUDA AH PDF
16 pages
Key-Value Databases Explained
No ratings yet
Key-Value Databases Explained
75 pages
A Calculator in Pharo Smalltalk Using Spec
100% (1)
A Calculator in Pharo Smalltalk Using Spec
15 pages
Substitution Rule (User Exit) in FI - FB60 or Manage Supplier Invoices Apps For Partner Bank Type in SAP S4HANA
100% (1)
Substitution Rule (User Exit) in FI - FB60 or Manage Supplier Invoices Apps For Partner Bank Type in SAP S4HANA
47 pages
Batch Processing with Spark Guide
No ratings yet
Batch Processing with Spark Guide
41 pages
Experiment - 2: Q. Write A Shell Script To Swap Two Numbers Without Using 3rd Variable
No ratings yet
Experiment - 2: Q. Write A Shell Script To Swap Two Numbers Without Using 3rd Variable
14 pages
ARM Cortex-M Instruction Guide
No ratings yet
ARM Cortex-M Instruction Guide
31 pages
Exam 120
No ratings yet
Exam 120
6 pages
DMS Model-Answer-Paper-Summer-2023
50% (2)
DMS Model-Answer-Paper-Summer-2023
18 pages
Creating An Ability
No ratings yet
Creating An Ability
9 pages
B.Tech - Information Technology Curriculum and Syllabus
No ratings yet
B.Tech - Information Technology Curriculum and Syllabus
184 pages
CSC126 Tutorial 11 Sample Answer
No ratings yet
CSC126 Tutorial 11 Sample Answer
7 pages
Emotion Recognition
No ratings yet
Emotion Recognition
31 pages
Chapter 2 - File Structures - Attempt Review
No ratings yet
Chapter 2 - File Structures - Attempt Review
15 pages
Bca Sem-3 (2019) (Suply) May-2023 Cs-15 Rdbms Using Oracle
No ratings yet
Bca Sem-3 (2019) (Suply) May-2023 Cs-15 Rdbms Using Oracle
3 pages
Segment Trees: Java Implementation Guide
No ratings yet
Segment Trees: Java Implementation Guide
17 pages
Unit1 - Java Control Statements
No ratings yet
Unit1 - Java Control Statements
15 pages
Guide To Cloudsimexample1.Java Simulation Workflow: Cloudsim Setup Using Eclipse Ide
No ratings yet
Guide To Cloudsimexample1.Java Simulation Workflow: Cloudsim Setup Using Eclipse Ide
15 pages
ITCS 321 Test ONE NOV 2018 KEY AAA
No ratings yet
ITCS 321 Test ONE NOV 2018 KEY AAA
5 pages
Pintos User Programs Guide
No ratings yet
Pintos User Programs Guide
17 pages
Entering Measures Into A Table Using Script
No ratings yet
Entering Measures Into A Table Using Script
6 pages
Question Paper and Solutions
No ratings yet
Question Paper and Solutions
3 pages
Daa Question Bank
No ratings yet
Daa Question Bank
5 pages
Armed Bear Common Lisp Guide
No ratings yet
Armed Bear Common Lisp Guide
52 pages

Codedive CPUCachesHandouts

Uploaded by

Codedive CPUCachesHandouts

Uploaded by

CPU Caches and Why You Care

CPU Caches and Why You Care

Scott Meyers, Ph.D.

A Tale of Two Traversals

Row Major Column Major

A Tale of Two Traversals

A Tale of Two Traversals

A Tale of Two Traversals

Core i7-9xx Cache Hierarchy

CPU Cache Characteristics

Effective Memory = CPU Cache Memory

Cache Line Prefetching

Assume both cores have cached the value at (virtual) address A.

... A-1 A A+1 ...

With False Sharing Without False Sharing

 Cache performance evaluation:

 Cache-oblivious algorithm design.

 For given size, shape can vary:

 “Native Code Performance and Memory: The Elephant in the

 “07-26-10 – Virtual Functions,” Charles Bloom, cbloom rants

 “The Future of Code Coverage Tools,” Mohammad Haghighat

 “Profile driven optimisations in GCC,” Jan Hubička, Proceedings

 “Profile Guided Optimization (PGO)—Under the Hood,” Ankit

About Scott Meyers

You might also like