C++-Implementierung einer einfachen Karte langsamer als die entsprechende Implementierung in Java: Code-/Benchmark-Probl ⇐ Java

[Guest]

Ziel dieser Forschung ist es, die Leistungsunterschiede zwischen JIT- (Just-in-Time-Kompilierung) und AOT-Strategien (Ahead-of-Time-Kompilierung) zu untersuchen und ihre jeweiligen Vor- und Nachteile zu verstehen. Die Absicht besteht nicht darin, zu behaupten, dass eine Sprache langsamer oder schlechter als die andere ist.

In unseren Tests haben wir bessere Ergebnisse mit der HotSpot JVM 23 unter Verwendung der JIT-Kompilierung (JVMCI und C2) beobachtet. Mit C++ (kompiliert mit Clang 18), GraalVM 23 (kompiliert mit Native-Image) und HotSpot JVM 23 mit dem Flag -Xcomp (JVMCI und C2) erzielten wir langsamere Ergebnisse. Wir möchten verstehen, warum dies geschieht, und wenn möglich Wege finden, die Leistung der C++-Version zu verbessern, um sie an die Ergebnisse der JIT-Kompilierung von Java anzupassen.
Unser Benchmark beinhaltet den Vergleich eines einfachen und Implementierung einer kleinen Hash-Tabelle (Map) in Java zu einer äquivalenten Implementierung (zeilenweise) in C++. Wir haben alle Anstrengungen unternommen, um die Konsistenz zwischen den beiden Implementierungen sicherzustellen. Das Ziel besteht nicht darin, die Standardbibliotheksimplementierungen von Hash-Tabellen zu vergleichen (

Code: Select all

java.util.HashMap

und std::unordered_map), da sie natürlich mit nicht äquivalentem Quellcode implementiert sind.
Der Benchmark erstellt eine Hash-Tabelle mit 20.000 Buckets und fügt 2.000.000 ein Objekte. Wir fügen einmal ein, löschen die Karte und fügen dann erneut ein, um den internen Objektpool des Entry-Objekts der Hash-Tabelle zu nutzen. Mit anderen Worten: Beim ersten Einfügen werden Objekte im Heap zugewiesen. Beim zweiten Einfügen werden Objekte aus dem internen Objektpool wiederverwendet.
Die Bench-Klasse, die die Messungen verarbeitet, sollte ebenfalls in beiden Sprachen gleichwertig sein .
Hat jemand angesichts dieser Details einen Einblick, warum die C++-Kartenimplementierung langsamer war als die Java-Kartenimplementierung? Gibt es etwas, das wir übersehen haben, oder einen Aspekt der C++-Implementierung, der weiter optimiert werden könnte? Vielleicht sollten wir spezifische Optionen zur Clang-Optimierung untersuchen?

(Dieser Abschnitt wurde von @petercordes hinzugefügt, um detaillierter zu beschreiben, was der Benchmark macht. Und aus der Diskussion in Kommentaren mit dem OP, um zu beschreiben, was meiner Meinung nach eines der Ziele ist.)
Die C++-Version ist so geschrieben, dass sie zu ähnlichem Maschinencode kompiliert werden kann Eine JVM könnte JIT für die Java-Version sein. Wie schafft Java das? Dieselben Maschinenoperationen wie die C++-Version, aber schneller.
(Anmerkung des Herausgebers (@petercordes): Ich habe den von der Hotspot-JVM generierten Maschinencode in Einzelschritten ausgeführt, und tatsächlich sind die Hauptschleifen verknüpft -list lineare Suchen mit 32-Bit-komprimierten Referenzen im Vergleich zu clang++ mit nativen Zeigern. Beim Unterbrechen der JVM mit GDB zeigt RIP normalerweise auf eine Stelle, an der der Code die meiste Zeit verbringt.

Code: Select all

clang++ -O3 ... -m32

ist immer noch langsamer, es handelt sich also nicht nur um 32-Bit-Zeiger, und die Java-Objekte waren immer noch mindestens 24 Bytes groß, nicht nur 12 für 2 Referenzen + ein int. Wahrscheinlich etwas mit Zuordnungsmustern und Cache-Fehlern, da Java mehr Maschinenanweisungen innerhalb der Schleife ausführt und sogar shl um 3 umwandeln muss, um einen 32-Bit-Wert in einen Zeiger umzuwandeln, sodass die Latenz bei der Lastnutzung im besten Fall schlechter ist .)
Die C++-Version verwendet in großem Umfang Zeiger, um die Semantik von Java widerzuspiegeln. Die gespeicherten und abgerufenen „Werte“ sind lediglich Zeiger (alle auf dasselbe Dummy-Objekt). Für die meisten Anwendungsfälle ist es wahrscheinlich nicht nützlich. Beispielsweise nimmt put ein Objekt als const-Referenz, also einen Zeiger in asm, während get es als Nicht-Referenz zurückgibt.

Code: Select all

const

Zeiger. Die Hash-Tabelle dereferenziert niemals den Wertzeiger oder löscht das Objekt, auf das verwiesen wird; In Java kümmert sich der GC darum. In C++ könnte es hypothetisch zum Erstellen einer Karte von Objekten verwendet werden, die etwas anderem gehören, oder in der automatischen oder statischen Speicherung. Es könnte äquivalent ein uintptr_t als Wert annehmen. (Eine Referenz ist nicht nullbar, aber wir sind nicht darauf angewiesen.)
Die Hash-Tabelle ist ein Array verknüpfter Listen (Zeiger in C++, wobei nullptr „on“ angibt Schlüssel in diesem Eimer). Bei einem Lastfaktor von 100 handelt es sich tatsächlich um einen Linked-List-Benchmark und nicht um normale Betriebsbedingungen für eine Hash-Tabelle.
Dies wurde gewählt, um die Zeit für jeden Vorgang lang genug zu machen Messen Sie mit Linux clock_gettime, wie es von Javas System.nanoTime oder Glibcs ​​chrono::steady_clock::now aufgerufen wird. Der Messaufwand sollte in beiden Sprachen ziemlich gleich sein und sehr hoch im Vergleich zu nur einer Hash-Bucket-Suche, die im Cache landet, aber ziemlich gering im Vergleich zum Durchlaufen einer verknüpften Liste mit 50 Elementen (durchschnittliche Länge).

Die Bench-Klasse selbst fügt außerdem jedes Mal eine std::map in C++ oder eine benutzerdefinierte Hashmap in Java hinzu, die ein ähnliches Design wie die zu vergleichende Hash-Tabelle verwendet und mit einem Auslastungsfaktor deutlich darunter verwendet wird 1. Dies liegt außerhalb des zeitgesteuerten Bereichs, erfordert jedoch beim ersten Durchlauf eine gewisse Zuweisung, sodass dies zwischen jeder Zuweisung eines Knotens für die zu vergleichende Hash-Tabelle geschieht.
Zum Versuch Um Leistungsunterschiede zwischen Javas GC und Nicht-GC-C++ zu minimieren, verwenden wir eine freie Liste mit unbegrenzter Größe und löschen immer nur im Destruktor: Wenn „remove()“ eine Übereinstimmung findet, wird der Knoten aus dem Bucket verschoben verknüpfte Liste mit der head der freien Liste. put übernimmt den Kopf der freien Liste und ruft new nur auf, wenn es leer ist. new wird also nur innerhalb der ersten Runde von put-Aufrufen aufgerufen, während die zweite (nach clear) durch die verknüpfte Liste der Knoten vorrücken muss. Das sollte günstig sein, weil es eine vollständige Linked-List-Suche zwischen Zuordnungen für die Ausführung außerhalb der Reihenfolge gibt, um die Ladelatenz selbst bei einem Cache-Fehler zu verbergen.
Der anfängliche Put stage ist nicht der einzige, der für die C++-Version langsamer ist als die Java-Version, es handelt sich also nicht nur um die Rohleistung von new. Vielleicht etwas über die Lokalität der Zuordnungen?

Der gesamte Quellcode, der nicht viel ist, mit Skripten zum Kompilieren und Ausführen zusammen mit unseren Ergebnissen ist offen. Quell-Github-Projekt CoralBench.
Aus den Kommentaren unten geht hervor, dass eine wichtige Verbesserungsquelle für den C++-Code benutzerdefinierte Allokatoren für die Hash-Tabellen-internen Entry-Objekte. Es wurde erwähnt, dass Java mithilfe des Schlüsselworts new Objekte einfacher/schneller im Heap zuordnen kann als C++, dieser Mangel kann jedoch in C++ durch die Verwendung von benutzerdefinierten Allokatoren behoben werden. Leider sind meine C++-Kenntnisse begrenzt und ich muss einige Nachforschungen anstellen, um zu verstehen, wie das geht. Eine Antwort hier mit einer solchen Änderung/Verbesserung im C++-Code wäre großartig.
Es ist wichtig zu beachten, dass beim zweiten Put-Benchmark Der C++-Code weist keinen Eintrag im Heap zu, da alle Objekte im internen Objektpool verfügbar sind (vom ersten Put an). Daher bin ich mir nicht sicher, warum C++ beim zweiten Put-Benchmark immer noch langsamer ist.
FTR, unten sind unsere aktuellen Ergebnisse für Java und C++:
HotSpotVM JIT: (mit Graal JVMCI JIT)

Code: Select all

PUT => Avg: 371 ns | Min: 28 ns | 99.9% = [avg: 367 ns, max: 1.743 micros]
PUT => Avg: 613 ns | Min: 27 ns | 99.9% = [avg: 606 ns, max: 2.184 micros]
GET => Avg: 615 ns | Min: 14 ns | 99.9% = [avg: 607 ns, max: 2.549 micros]
DEL => Avg: 662 ns | Min: 18 ns | 99.9% = [avg: 658 ns, max: 2.538 micros]

HotSpotVM JIT: (mit C2 JIT)

Code: Select all

PUT => Avg: 342 ns | Min: 29 ns | 99.9% = [avg: 338 ns, max: 1.661 micros]
PUT => Avg: 596 ns | Min: 28 ns | 99.9% = [avg: 589 ns, max: 2.161 micros]
GET => Avg: 599 ns | Min: 20 ns | 99.9% = [avg: 592 ns, max: 2.275 micros]
DEL => Avg: 826 ns | Min: 23 ns | 99.9% = [avg: 817 ns, max: 3.420 micros]

C++ LLVM: (clang)

Code: Select all

PUT => Avg: 726 ns | Min: 30 ns | 99.9% = [avg: 720 ns, max: 4.097 micros]
PUT => Avg: 857 ns | Min: 18 ns | 99.9% = [avg: 848 ns, max: 2.933 micros]
GET => Avg: 874 ns | Min: 18 ns | 99.9% = [avg: 865 ns, max: 3.010 micros]
DEL => Avg: 875 ns | Min: 19 ns | 99.9% = [avg: 871 ns, max: 2.810 micros]

GraalVM: (native-image)

Code: Select all

PUT => Avg: 190 ns | Min: 21 ns | 99.9% = [avg: 183 ns, max: 814 ns]
PUT => Avg: 659 ns | Min: 23 ns | 99.9% = [avg: 656 ns, max: 2.762 micros]
GET => Avg: 399 ns | Min: 21 ns | 99.9% = [avg: 396 ns, max: 2.124 micros]
DEL => Avg: 323 ns | Min: 27 ns | 99.9% = [avg: 321 ns, max: 1.850 micros]

Benchmark-Umgebung:

Code: Select all

$ uname -a
Linux hivelocity 4.15.0-20-generic #21-Ubuntu SMP Tue Apr 24 06:16:15 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

$ cat /etc/issue | head -n 1
Ubuntu 18.04.6 LTS \n \l

$ cat /proc/cpuinfo | grep "model name" | head -n 1 | awk -F ": " '{print $NF}'
Intel(R) Xeon(R) E-2288G CPU @ 3.70GHz

$ arch
x86_64

$ clang++ --version
Ubuntu clang version 18.1.0 (++20240220094926+390dcd4cbbf5-1~exp1~20240220214944.50)
Target: x86_64-pc-linux-gnu
Thread model: posix
InstalledDir: /usr/bin

$ java -version
java version "23.0.1" 2024-10-15
Java(TM) SE Runtime Environment Oracle GraalVM 23.0.1+11.1 (build 23.0.1+11-jvmci-b01)
Java HotSpot(TM) 64-Bit Server VM Oracle GraalVM 23.0.1+11.1 (build 23.0.1+11-jvmci-b01, mixed mode, sharing)

$ native-image --version
native-image 23.0.1 2024-10-15
GraalVM Runtime Environment Oracle GraalVM 23.0.1+11.1 (build 23.0.1+11-jvmci-b01)
Substrate VM Oracle GraalVM 23.0.1+11.1 (build 23.0.1+11, serial gc, compressed references)

So kompilieren Sie den C++-Code:

Code: Select all

rm -f target/cpp/int_map_benchmark target/cpp/int_map.o target/cpp/bench.o target/cpp/int_map_benchmark.o

mkdir -p target/cpp

clang++ -Ofast -march=native -flto -std=c++17 -I./src/main/c -c ./src/main/c/int_map.cpp -o ./target/cpp/int_map.o
clang++ -Ofast -march=native -flto -std=c++17 -I./src/main/c -c ./src/main/c/bench.cpp -o ./target/cpp/bench.o
clang++ -Ofast -march=native -flto -std=c++17 -I./src/main/c -c ./src/main/c/int_map_benchmark.cpp -o ./target/cpp/int_map_benchmark.o

clang++ -Ofast -march=native -flto -std=c++17 -o ./target/cpp/int_map_benchmark ./target/cpp/int_map.o ./target/cpp/bench.o ./target/cpp/int_map_benchmark.o

So führen Sie den C++-Code aus:

Code: Select all

#!/bin/bash

WARMUP=${1:-0}
MEASUREMENTS=${2:-2000000}
CAPACITY=${3:-20000}

./target/cpp/int_map_benchmark $WARMUP $MEASUREMENTS $CAPACITY

Unter dem C++-Code:

Code: Select all

// =====>  bench.hpp
#ifndef BENCH_HPP
#define BENCH_HPP

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

class Bench {
public:
Bench(int warmupCount = 0);
~Bench();

void mark();
void measure();
bool measure(long long);
void reset();
void reset(bool);
void printResults() const;
void printResults(bool) const;
bool isWarmingUp() const;
int getIterations() const;
int getMeasurements() const;
double getAverage() const;

private:
int warmupCount;
int measurementCount;
long long sum;
long long minTime;
long long maxTime;
int size;
std::map* results;
std::chrono::steady_clock::time_point startTime;

static std::string formatWithCommas(long long value);
static std::pair formatTime(double nanos);
static std::string formatPercentage(double perc);
static double roundToDecimals(double d, int decimals);
void printPercentiles() const;
void addPercentile(double perc) const;
double avg() const;
};

#endif // BENCH_HPP

// =====> bench.cpp
#include "bench.hpp"
using namespace std;

Bench::Bench(int warmupCount)
: warmupCount(warmupCount),
measurementCount(0),
sum(0),
minTime(numeric_limits::max()),
maxTime(numeric_limits::min()),
size(0) {

results = new map();

}

Bench::~Bench() {
delete results;
}

void Bench::mark() {
startTime = chrono::steady_clock::now();
}

void Bench::measure() {
auto endTime = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast(endTime - startTime).count();
measure(elapsed);
}

bool Bench::measure(long long elapsed) {

bool isToMeasure = ++measurementCount > warmupCount;

if (isToMeasure) {
sum += elapsed;
if (elapsed < minTime) minTime = elapsed;
if (elapsed > maxTime) maxTime = elapsed;

// Increment the frequency of this elapsed time
auto it = results->find(elapsed);
if (it == results->end()) {
results->insert({elapsed, 1});
} else {
it->second++;
}
size++;
}

return isToMeasure;
}

int Bench::getIterations() const {
return measurementCount;
}

int Bench::getMeasurements() const {
return size;
}

void Bench::reset() {
reset(false);
}

void Bench::reset(bool repeatWarmup) {
measurementCount = 0;
sum = 0;
if (!repeatWarmup) warmupCount = 0;
minTime = numeric_limits::max();
maxTime = numeric_limits::min();
results->clear();
size = 0;
}

bool Bench::isWarmingUp() const {
return warmupCount