Реализация простой карты на C++ медленнее, чем эквивалентная реализация на Java: проблема с кодом/тестом? ⇐ JAVA

[Anonymous]

Цель этого исследования — изучить различия в производительности между стратегиями JIT (компиляция точно в срок) и AOT (компиляция с опережением времени), а также понять их соответствующие преимущества и недостатки. Цель не состоит в том, чтобы утверждать, что один язык медленнее или хуже другого.
В наших тестах мы наблюдали лучшие результаты с HotSpot JVM 23 с использованием JIT-компиляции (JVMCI и C2). Мы получили более медленные результаты с C++ (скомпилированным с помощью Clang 18), GraalVM 23 (скомпилированным с использованием собственного образа) и HotSpot JVM 23 с флагом -Xcomp (JVMCI и C2). Мы пытаемся понять, почему это происходит, и, если возможно, определить способы повышения производительности версии C++, чтобы она соответствовала результатам JIT-компиляции Java.
Наш тест включает в себя сравнение простого и реализацию небольшой хэш-таблицы (карты) на Java к эквивалентной (построчной) реализации на C++. Мы приложили все усилия, чтобы обеспечить согласованность между двумя реализациями. Цель состоит в том, чтобы не сравнивать реализации стандартной библиотеки хеш-таблицы (java.util.HashMap и std::unordered_map), поскольку они, конечно, реализованы с использованием неэквивалентного исходного кода.
Бенчмарк создает хеш-таблицу с 20 000 сегментами и вставляет 2 000 000 объекты. Мы вставляем один раз, очищаем карту и затем вставляем снова, чтобы воспользоваться преимуществами внутреннего пула объектов объекта Entry хеш-таблицы. Другими словами, при первой вставке объекты будут размещены в куче. При второй вставке объектов они будут повторно использованы из внутреннего пула объектов.
Класс Bench, который обрабатывает измерения, также должен быть эквивалентен на обоих языках. .
Учитывая эти подробности, есть ли у кого-нибудь понимание того, почему реализация карты C++ была медленнее, чем реализация карты Java? Может ли быть что-то, что мы упустили из виду, или какой-то аспект реализации C++, который можно оптимизировать дальше? Возможно, нам следует изучить конкретные варианты оптимизации Clang?
Весь исходный код, которого немного, со скриптами для компиляции и выполнения вместе с нашими результатами, находится на Github проекта. .
Из комментариев ниже видно, что основным источником улучшения кода C++ могут быть настраиваемые распределители для хеша внутренние объекты таблицы Entry. Было упомянуто, что в Java легче/быстрее распределять объекты в куче, чем в C++, с помощью ключевого слова new, но этот недостаток можно устранить в C++ с помощью пользовательских распределителей. К сожалению, мои знания C++ ограничены, и мне придется провести некоторое исследование, чтобы понять, как это сделать. Ответ с таким изменением/улучшением кода C++ был бы отличным.
Важно отметить, что во втором тесте, поставленном, код C++ не будет выделять какие-либо записи в куче, поскольку все объекты будут доступны во внутреннем пуле объектов (с самого начала). Поэтому я не уверен, почему C++ все еще медленнее во втором тесте put.
FTR, ниже приведены наши текущие результаты для Java и C++:
JIT HotSpotVM: (с JIT Graal JVMCI)
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]

JIT HotSpotVM: (с JIT C2)
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: (лязг)
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]

Среда тестирования:
$ 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)

Чтобы скомпилировать код C++:
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

Чтобы запустить код C++:
#!/bin/bash

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

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

Под кодом C++:
// =====> 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

Подробнее здесь: https://stackoverflow.com/questions/792 ... on-in-java