Oto fragment kodu C ++, który pokazuje niektóre bardzo dziwne zachowania. Z jakiegoś dziwnego powodu sortowanie danych w cudowny sposób przyspiesza prawie sześciokrotnie:
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.
std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}- Bez
std::sort(data, data + arraySize);tego kod działa w 11,54 sekundy. - Po posortowaniu danych kod działa w 1,93 sekundy.
Początkowo myślałem, że może to być anomalia dotycząca języka lub kompilatora, więc wypróbowałem Javę:
import java.util.Arrays;
import java.util.Random;
public class Main
{
public static void main(String[] args)
{
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c)
data[c] = rnd.nextInt() % 256;
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i)
{
// Primary loop
for (int c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}Z podobnym, ale mniej ekstremalnym rezultatem.
Najpierw pomyślałem, że sortowanie przenosi dane do pamięci podręcznej, ale potem pomyślałem, że to głupie, ponieważ tablica właśnie została wygenerowana.
- Co się dzieje?
- Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie nieposortowanej tablicy?
Kod sumuje niektóre niezależne warunki, więc kolejność nie powinna mieć znaczenia.
168
Woops ... dotyczy: Meltdown and Spectre
—
KyleMit
@SachinVerma Z czubka głowy: 1) JVM może być w końcu wystarczająco inteligentny, aby używać ruchów warunkowych. 2) Kod jest związany z pamięcią. 200 M jest zdecydowanie za duże, aby zmieścić się w pamięci podręcznej procesora. Tak więc wydajność będzie ograniczana przepustowością pamięci zamiast rozgałęziania.
—
Tajemniczy
@ Mysticial, około 2). Pomyślałem, że tabela predykcji śledzi wzorce (niezależnie od faktycznych zmiennych, które zostały sprawdzone dla tego wzorca) i zmienia wyniki prognozy na podstawie historii. Czy mógłbyś podać mi powód, dla którego super duża tablica nie skorzystałaby z przewidywania gałęzi?
—
Sachin Verma
@SachinVerma Tak, ale kiedy tablica jest tak duża, prawdopodobnie odgrywa to jeszcze większą rolę - przepustowość pamięci. Pamięć nie jest płaska . Dostęp do pamięci jest bardzo wolny, a przepustowość jest ograniczona. Aby nadmiernie uprościć, istnieje tylko tyle bajtów, które można przenieść między procesorem a pamięcią w ustalonym czasie. Prosty kod, taki jak ten w tym pytaniu, prawdopodobnie przekroczy ten limit, nawet jeśli zostanie spowolniony przez nieprzewidziane zdarzenia. Nie dzieje się tak w przypadku tablicy 32768 (128 KB), ponieważ pasuje ona do pamięci podręcznej L2 procesora.
—
Mysticial
Pojawiła się nowa luka w zabezpieczeniach o nazwie BranchScope: cs.ucr.edu/~nael/pubs/asplos18.pdf
—
Veve
