int sumElements(LinkedList<int> * list) {
int total = 0;
for ( Node * node = list->head; node != nullptr; node = node->next )
total += node->value;
return total;
}Which snippet is faster when summing 100,000 integers?
int sumElements(LinkedList<int> * list) {
int total = 0;
for ( Node * node = list->head; node != nullptr; node = node->next )
total += node->value;
return total;
}int sumElements(Array<int> * array) {
int total = 0;
int size = array->size;
for ( int i = 0; i < size; ++i )
total += array->items[i];
return total;
}Which snippet is faster when summing only the x coordinate? Assume there is 1,000,000 particles.
struct Particle {
float x, y, z;
int unused[5]; // Pad so sizeof(Particle) is 32 bytes
};
float sumX(const vector<Particle>& particles) {
float total = 0.0f;
for (const Particle& particle : particles)
total += particle.x;
return total;
}struct ParticlesSoA {
vector<float> x, y, z;
};
float sumX(const ParticlesSoA& particles) {
float total = 0.0f;
for (float value : particles.x)
total += value;
return total;
}| Budget | AoS: 32 B item | SoA: 4 B item |
|---|---|---|
| Fit in one cache line (64 B) | 2 items | 16 items |
| Fit in L1 cache (32 KiB) | 1,024 items | 8,192 items |
| Fit in L2 cache (1 MiB) | 32,768 items | 262,144 items |
| RAM in 1 µs (50 GB/s) | 1,562 items | 12,500 items |
Which snippet is faster when writing 100,000 samples into a circular buffer whose capacity is guaranteed to be a power of two?
void writeSamples(const vector<int>& samples,
vector<int>& ring, int& writeIndex) {
const int mask = ring.size() - 1;
for (int sample : samples) {
ring[writeIndex & mask] = sample;
++writeIndex;
}
}void writeSamples(const vector<int>& samples,
vector<int>& ring, int& writeIndex) {
const int capacity = ring.size();
for (int sample : samples) {
ring[writeIndex % capacity] = sample;
++writeIndex;
}
}Which snippet is faster on random input when there are 100,000 items and a 50% chance of being above the threshold?
int filterAbove(const vector<int>& data,
vector<int>& output, int threshold) {
int count = 0;
for (int value : data) {
if (value >= threshold)
output[count++] = value;
}
return count;
}int filterAbove(const vector<int>& data,
vector<int>& output, int threshold) {
int count = 0;
for (int value : data) {
output[count] = value;
count += (value >= threshold);
}
return count;
}The CPU starts down one path, then must recover when the guess is wrong
if (sqrt( a ) < 10)
funcA();
else
funcB();Which snippet is faster for mostly ASCII input?
int countCodePoints(const string& text) {
const int sizes[16] = {
1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 2, 2, 3, 4
};
int index = 0;
int count = 0;
while (index < text.size()) {
const unsigned char byte = text[index];
index += sizes[byte >> 4];
++count;
}
return count;
}int countCodePoints(const string& text) {
int index = 0;
int count = 0;
while (index < text.size()) {
const unsigned char byte = text[index];
if (byte < 0x80) index += 1;
else if (byte < 0xE0) index += 2;
else if (byte < 0xF0) index += 3;
else index += 4;
++count;
}
return count;
}Removing a branch can replace misprediction risk with a dependency chain
byte = buffer[index];
index += sizes[byte << 4];byte = buffer[index]; byte << 4 sizes[...] index += ... byte = buffer[index]; byte << 4 sizes[...] byte = buffer[index];
if (byte < 0x80)
++index;byte = buffer[index] if byte < 0x80; jump ++index // (predicted) byte = buffer[index] if byte < 0x80; jump ++index Which snippet is faster for summing a large array of floating-point values?
double sumArray(const vector<double>& data) {
double sum = 0.0;
for (double value : data)
sum += value;
return sum;
}double sumArray(const vector<double>& data) {
double sum0 = 0.0, sum1 = 0.0;
double sum2 = 0.0, sum3 = 0.0;
int index = 0;
for (; index + 3 < data.size(); index += 4) {
sum0 += data[index];
sum1 += data[index + 1];
sum2 += data[index + 2];
sum3 += data[index + 3];
}
for (; index < data.size(); ++index)
sum0 += data[index];
return sum0 + sum1 + sum2 + sum3;
}Multiple accumulators shorten dependency chains and can expose vectorization
Which counter layout is faster when two threads update separate counters?
struct Counters {
atomic<int> counterA{0};
atomic<int> counterB{0};
};
++counterA; // Thread A
++counterB; // Thread Bstruct PaddedCounter {
atomic<int> value{0};
char padding[60];
};
struct Counters {
PaddedCounter counterA;
PaddedCounter counterB;
};
++counterA; // Thread A
++counterB; // Thread BWhich implementation is faster?
double harmonicSeries(int n) {
if (n <= 0) return 0.0;
return (1.0 / n) + harmonicSeries(n - 1);
}double harmonicSeries(int n, double total = 0.0) {
if (n <= 0) return total;
return harmonicSeries(n - 1, total + (1.0 / n));
}The highlighted expression must remain available while the recursive call returns
double harmonicSeries(int n) {
if (n <= 0) return 0.0;
return (1.0 / n) + harmonicSeries(n - 1);
}sub rsp, 40 ; frame and shadow space
mov [rsp+32], ecx ; preserve n
dec ecx
call harmonicSeries
movsd xmm1, [one]
cvtsi2sd xmm2, [rsp+32]
divsd xmm1, xmm2
addsd xmm0, xmm1 ; finish the return expression
add rsp, 40
retpush rbx ; save callee's rbx
sub rsp, 32 ; shadow space
mov ebx, ecx ; preserve n
dec ecx
call harmonicSeries
movsd xmm1, [one]
cvtsi2sd xmm2, ebx
divsd xmm1, xmm2
addsd xmm0, xmm1 ; finish the return expression
add rsp, 32
pop rbx
retThe updated argument is ready before the recursive call
double harmonicSeries(int n, double total = 0.0) {
if (n <= 0) return total;
return harmonicSeries(n - 1, total + (1.0 / n));
}sub rsp, 40 ; frame and shadow space
cvtsi2sd xmm2, ecx
movsd xmm3, [one]
divsd xmm3, xmm2
addsd xmm1, xmm3 ; update total
dec ecx
call harmonicSeries
add rsp, 40
retcvtsi2sd xmm2, ecx
movsd xmm3, [one]
divsd xmm3, xmm2
addsd xmm1, xmm3 ; update total
dec ecx
jmp harmonicSeries ; no work remainsa = b / c d = sqrt(c)