Branch prediction (C++ och Java)

// ConsoleApplication4.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <algorithm>
#include <ctime>
#include <iostream>

const int ITERATIONS = 100000;

void test(const char *desc, int *data, unsigned arraySize) {
	// Test
	clock_t start = clock();
	long long sum = 0;

	for (unsigned i = 0; i < ITERATIONS; ++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 << desc << ": " << elapsedTime << std::endl;
	std::cout << "sum = " << sum << std::endl;
}

int main()
{
	// Generate data (f = filtered)
	const unsigned arraySize = 32768;
	unsigned fArraySize = 0;
	int data[arraySize];
	int fData[arraySize];

	for (unsigned c = 0; c < arraySize; ++c)
		data[c] = std::rand() % 256;

	for (int i = 0; i < arraySize; i++)
		if (data[i] >= 128)
			fData[fArraySize++] = data[i];

	test("filtered", fData, fArraySize);
	test("unsorted", data, arraySize);
	std::sort(data, data + arraySize);
	test("sorted", data, arraySize);
	return 0;
}

filtered: 4.726
sum = 312275400000
unsorted: 24.831
sum = 312275400000
sorted: 8.992
sum = 312275400000

filtered: 0.826
sum = 312275400000
unsorted: 1.027
sum = 312275400000
sorted: 1.021
sum = 312275400000

Kan man stänga av processorns branch prediction med instruktioner i kompilatorn verkligen?

Nej, det har jag inte påstått heller.

Poängen med detta test är väl att om data är sorterat kommer BP gissa rätt oftare än när det är osorterat.

Då förstår jag inte vad kompilatoroptimeringar har med saken att göra.

Nej, jag ser inte heller att optimeringarna påverkar BP, men de påverkar körtiden. Att de synliga "effekterna" av BP blir tydligare när man slår på optimering handlar sannolikt om att kompilatorn genererar mindre korkad kod. Med färre instruktioner som exekveras kommer skillnaden mellan sorted och unsorted mätt i sekunder (som är ungefär lika stor oavsett om det är ooptimerad och optimerad kod) att bli större relativt den totala körtiden.

Det beror på vad du gör i din nästan tomma loop. Ge några exempel på nästan tomma loopar så kan jag tala om vilka man kan optimera och varför.

Min poäng är att slå på kompilatoroptimeringar i det här fallet gjorde koden upp till 24 gånger snabbare. Och om man ska kolla på att optimera ett program så är det lätt att dra helt fel slutsatser om man sitter och tittar på hur kod fungerar utan optimering på. Finns en massa saker man kan göra i ett program som ser väldigt ineffektiva ut men som en vettig kompilator optimerar, vilket gör att det som ser ut som en 3x speedup i praktiken faktiskt är noll.

Nej, det har inte med varandra att göra. Att du på en 64-bits-CPU har möjlighet att köra ett 32-bits-instruktionsset innebär att man i den moden "bara" jobbar med den lägre halvan av registren. (Ja, detta är vansinnigt förenklat.)

Vi kan jämföra med att kompilatorn kan generera binärer för X86 och för ARM (två olika arkitekturer). Du förväntar dig att programmet skall bete sig likadant oavsett om kör det på din PC eller på din RPi. Om en 64-bits-CPU (i olika moder) kan köra både ett 64-bits- och ett 32-bits-instruktionsset så kan du kompilera samma program till 32-bits och 64-bits-instruktioner. Precis som att X86- och ARM-varianterna av programmet skall bete sig likadant och producera samma resultat så skall även 32- och 64-bits-varianterna bete likadant och producera samma resultat. I fallet vi diskuterar här kommer data att vara 32-bitar i båda fallen och hanteras likadant i cachen oavsett om du kör programmet i 32-bits- eller 64-bits-smak. På samma sätt som 32-bits-binären har instruktioner som laddar 32-bitar från minnet kommer 64-bits-binären använda instruktioner som laddar 32-bitar i taget från minnet. Det är dessa operationer som cachen ser.

Vad som däremot kommer skilja är att i 64-bits-binären kommer pekare vara 64 bitar och att datastrukturer kan innehålla en del padding för att pekare, long och doubles skall ha 8-bytes-alignment. Detta gör att en del saker tar större plats i minnet (och i cachen) och att färre saker ryms i cachen. (Men å andra sidan har CPU ofta fler register i 64-bits-mode så det är en fråga om gungor och karuseller. I bland vinner man på att bygga 32-bits-binärer, ibland är det bättre med 64-bits-binärer.)

TL;DR: även 32-bitsbinärer använder cachen till 100%.

Jo, X86 instruktionskoding är lite speciell. För att göra 64-bits-versioner av instruktioner så lägger man typiskt på ett prefix (en eller flera bytes före instruktionen) som gör att 64-bitsprogrammen blir lite större.

Beträffande storleken på L1 så är det en balansgång. Ju större cachen blir desto längre tid tar en access. Så det är inte säkert att det blir snabbare bara för att den görs större.