27
questions
17
votes
4
answers
42k
views
Confused between Temporal and Spatial locality in real life code
I was reading this question, I wanted to ask more about the code that he showed i.e
for(i = 0; i < 20; i++)
for(j = 0; j < 10; j++)
a[i] = a[i]*j;
The questions are,
I understand ...
user379888
6
votes
2
answers
5k
views
Does _mm_clflush really flush the cache?
I'm trying to understand how the hardware cache works by writing and running a test program:
#include <stdio.h>
#include <stdint.h>
#include <x86intrin.h>
#define LINE_SIZE 64
#...
- 715
5
votes
2
answers
1k
views
CPU spatial cache locality in array iteration
My understanding of the L1 cache was that a memory fetch loads a cache line. Assuming the cache line size is 64 bytes, if I access memory at address p, it will load the entire block from p to p + 64 ...
- 9,317
3
votes
1
answer
84
views
Why is inserting sorted keys into std::set so much faster than inserting shuffled keys?
I was accidentally surprised to found that inserting sorted keys into std::set is much much faster than inserting shuffled keys. This is somewhat counterintuitive since a red-black tree (I verified ...
- 374
3
votes
2
answers
1k
views
Understanding spatial and temporal locality
I was studying for my architecture final and came across the following lines of code:
for(i = 0; i <= N ;i++){
a[i] = b[i] + c[i];
}
The question is: "How does this code snippet demonstrate ...
- 181
2
votes
2
answers
1k
views
Cache misses when accessing an array in nested loop
So I have this question from my professor, and I can not figure out why vector2 is faster and has less cache misses than vector1.
Assume that the code below is a valid compilable C code.
Vector2:
void ...
- 373
2
votes
2
answers
1k
views
Importance of padding in Dynamic Memory Allocation
I am trying to implement a heap (implicit free list with header/footer) and deciding on whether I should add padding to it. What are the tangible benefits of adding pads? I read that it somehow ...
- 1,051
2
votes
1
answer
154
views
Why can't modern compilers optimize row-major order accesses in loops?
In the textbook Computer Systems: a Programmer's Perspective there are some impressive benchmarks for optimizing row-major order access.
I created a small program to test for myself if a simple ...
- 3,488
2
votes
0
answers
67
views
In Apache Spark, how to make a task to always execute on the same machine?
In its simplest form, RDD is merely a placeholder of chained computations that can be arbitrarily scheduled to be executed on any machine:
val src = sc.parallelize(0 to 1000)
val rdd = src....
- 4,130
2
votes
0
answers
224
views
How to benchmark random access with JMH?
I was trying to observe the effects of CPU cache spatial locality by benchmarking sequential/random reads to an array with JMH. Interestingly, the results are almost the same.
So I wonder, is this ...
- 1,880
1
vote
5
answers
2k
views
data locality for implementing 2d array in c/c++
Long time ago, inspired by "Numerical recipes in C", I started to use the following construct for storing matrices (2D-arrays).
double **allocate_matrix(int NumRows, int NumCol)
{
double **x;
int ...
- 1,059
1
vote
0
answers
350
views
Improving cache locality of binary search by doing local linear search?
Binary search of a sorted array may have poor cache locality, due to random access of memory, but linear search is slow for a large array. Is it possible to design a hybrid algorithm? For example, you ...
- 647
1
vote
0
answers
38
views
Detect whether a cache line is reused due to spatial or temporal locality
Is there a practical tool to detect whether a cache line is reused (a cache miss is avoided) due to either spatial or temporal locality?
I could not find a related discussion in cachegrind.
I was able ...
- 1,515
1
vote
0
answers
80
views
java mechanical sympathy trough thread pinning
Given we have an application that is heavily polluted with concurrency constructs
multiple techniques are used (different people worked without clear architecture in mind),
multiple questionable ...
- 11.2k
0
votes
2
answers
179
views
Can a custom allocator improve cache locality for lists?
This is a rather hypothetical question.
I only have limited knowledge about how the cpu cache works.
I know a cpu loads subsequent bytes into the cache.
Since a list uses pointers/indirection into ...
- 4,537