Реализация простой карты на 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?

(Этот раздел добавлен @petercordes для более подробного описания того, что делает тест. И из обсуждения в комментариях с ОП, чтобы описать, что, по моему мнению, является одной из целей.)
Версия C++ написана так, что ее можно компилировать в машинный код, аналогичный тому, что JVM может JIT-компилятор для версии Java. Как Java удается выполнять те же машинные операции, что и версия C++, но быстрее.
(Примечание редактора (@petercordes): я выполнил машинный код, сгенерированный JVM Hotspot, и основные циклы в одношаговом режиме. представляют собой линейный поиск по связному списку с использованием 32-битных сжатых ссылок вместо clang++ с использованием собственных указателей. При прерывании JVM с помощью GDB обычно RIP указывает на место, где код проводит большую часть своего времени.
clang++ -O3 ... -m32 по-прежнему медленнее, поэтому это не просто 32-битные указатели, а объекты Java по-прежнему имели размер не менее 24 байтов, а не только 12 для 2 ссылок + int. Вероятно, что-то связано с шаблонами распределения и промахами в кэше, поскольку Java выполняет больше машинных инструкций внутри цикла и даже должна заменять на 3, чтобы превратить 32-битное значение в указатель, поэтому в лучшем случае задержка при загрузке будет хуже. .)
В версии C++ широко используются указатели для отражения семантики Java. Сохраняемые и извлекаемые «значения» представляют собой просто указатели (все на один и тот же фиктивный объект). Вероятно, это бесполезно для большинства случаев использования. Например, put принимает объект по константной-ссылке, т. е. указатель в asm, а get возвращает его как не-const указатель. Хэш-таблица никогда не разыменовывает указатель значения и не удаляет объект, на который указывает; в Java об этом позаботится сборщик мусора. В C++ его гипотетически можно использовать для построения карты объектов, принадлежащих чему-то другому, а также для автоматического или статического хранения. Эквивалентно это может принимать uintptr_t по значению. (Ссылка не допускает значения NULL, но мы от этого не зависим.)
Хеш-таблица представляет собой массив связанных списков (указателей в C++ с nullptr, указывающим на ключи в этом ведре). При коэффициенте загрузки 100 это на самом деле тест связанного списка, а не нормальные условия работы хеш-таблицы.
Это было выбрано для того, чтобы время каждой операции было достаточно большим, чтобы измеряйте с помощью Linux clock_gettime, вызываемого из Java System.nanoTime или Glibc Chronic::steady_lock::now. Накладные расходы на измерение должны быть примерно одинаковыми на обоих языках и очень высокими по сравнению с простым поиском по хеш-сегменту, который попадает в кеш, но довольно небольшими по сравнению с обходом связанного списка из 50 элементов (средней длины).

Сам класс Bench также каждый раз добавляется к std::map в C++ или к пользовательской хэш-карте в Java, используя дизайн, аналогичный тестируемой хэш-таблице, используемый с коэффициентом загрузки значительно ниже 1. Это находится за пределами временного региона, но при первом запуске необходимо выполнить некоторое выделение, так что это будет происходить между каждым выделением узла для тестируемой хеш-таблицы.
Чтобы попытаться Чтобы свести к минимуму разницу в производительности между Java GC и C++, не использующим GC, мы используем свободный список неограниченного размера, удаляя его только в деструкторе: если метод Remove() находит совпадение, он перемещает узел из корзины. связанный список с заголовок списка свободных. put берет начало списка свободных и вызывает new только в том случае, если он пуст. Таким образом, new вызывается только внутри первого раунда вызовов put, а второй (после очистки) должен проходить через связанный список узлов. Это должно быть дешево, потому что существует целый поиск по связанному списку между выделениями для выполнения вне очереди, чтобы скрыть задержку загрузки даже при промахе в кэше.
Первоначальный вариант Stage не единственный, который в версии C++ медленнее, чем в версии Java, так что это не просто чистая производительность new. Может быть, что-нибудь о локальности аллокаций?

Весь исходный код, которого немного, со скриптами для компиляции и выполнения вместе с нашими результатами находятся в 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]

GraalVM: (собственный образ)
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]

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