Estudo interessante de C++ (AOT) vs Java (JIT) com resultados favoráveis ao JIT

Projeto GitHub com resultados e mais detalhes => https://github.com/coralblocks/CoralBench?tab=readme-ov-file#hotspotvm--xcomp-and-jit-vs-c-llvm-clang-vs-graalvm

Diante dos detalhes abaixo, alguém tem alguma ideia do motivo pelo qual a versão em C++ do benchmark foi mais lenta que a versão em Java? Será que algo passou despercebido ou existe algum aspecto da implementação em C++ que poderia ser otimizado ainda mais? Talvez opções específicas de otimização do Clang que deveríamos explorar?

O objetivo desta pesquisa é explorar as diferenças de desempenho entre as estratégias de compilação JIT (just-in-time) e AOT (ahead-of-time) e entender suas respectivas vantagens e desvantagens. O intuito não é afirmar que uma linguagem é mais lenta ou pior do que a outra.

Em nossos testes, observamos melhores resultados com o HotSpot JVM 23 usando a compilação JIT. Obtivemos resultados mais lentos com C++ (compilado com Clang 18), GraalVM 23 (compilado com native-image) e HotSpot JVM 23 com a flag -Xcomp. Estamos buscando entender por que isso acontece e, se possível, identificar formas de melhorar o desempenho da versão em C++ para igualar os resultados da compilação JIT em Java.

Nosso benchmark envolve a comparação de uma implementação de tabela hash (map) em Java com uma implementação equivalente em C++. Fizemos todo o esforço possível para garantir consistência entre as duas implementações, mas é possível que alguns detalhes tenham sido negligenciados.

A implementação da tabela hash em si é simples, e procuramos tornar o código em Java e C++ o mais equivalente possível, incluindo a forma como a memória é gerenciada. Por exemplo, garantimos que os valores da tabela hash em C++ sejam armazenados por referência, e não por valor, para evitar cópias desnecessárias.

O benchmark cria uma tabela hash com 5.000.000 de buckets e insere 10.000.000 de objetos, minimizando colisões. A busca linear em cada bucket é limitada a um máximo de duas iterações para evitar discrepâncias nas medições devido a comportamentos variados de colisão entre os diferentes elementos.

A classe Bench, que realiza as medições, também foi projetada para ser equivalente nas duas implementações.

To compile and execute:

$ 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

$ ./target/cpp/int_map_benchmark 0 10000000 5000000

bench.hpp:

#ifndef BENCH_HPP
#define BENCH_HPP

#include <chrono>
#include <iostream>
#include <limits>
#include <iomanip>
#include <string>
#include <cmath>
#include <map>
#include <sstream>

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

    void mark();
    void measure();
    void reset();
    void printResults() const;

private:
    int warmupCount;
    int measurementCount;
    long long sum;
    long long minTime;
    long long maxTime;
    int size;
    std::map<long long, long long>* results;
    std::chrono::steady_clock::time_point startTime;
    
    static std::string formatWithCommas(long long value);
    static std::pair<double, std::string> formatTime(double nanos);
    static std::string formatPercentage(double perc);
    static double roundToDecimals(double d, int decimals);
    void printPercentiles() const;
    void addPercentile(double perc) 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<long long>::max()),
      maxTime(numeric_limits<long long>::min()),
      size(0) {

        results = new std::map<long long, long long>();

}

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<chrono::nanoseconds>(endTime - startTime).count();
    measurementCount++;

    if (measurementCount > warmupCount) {
        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++;
    }
}

void Bench::reset() {
    measurementCount = 0;
    sum = 0;
    minTime = numeric_limits<long long>::max();
    maxTime = numeric_limits<long long>::min();
    results->clear();
    size = 0;
}

void Bench::printResults() const {
    int effectiveCount = measurementCount - warmupCount;
    if (effectiveCount <= 0) {
        cout << "Not enough measurements after warmup to report statistics." << endl;
        return;
    }

    double avg = static_cast<double>(sum) / effectiveCount;

    string effCountStr = formatWithCommas(effectiveCount);
    string warmupStr = formatWithCommas(warmupCount);
    string totalStr = formatWithCommas(measurementCount);

    cout << "Measurements: " << effCountStr
         << " | Warm-Up: " << warmupStr
         << " | Iterations: " << totalStr << endl;

    auto [avgVal, avgUnit] = formatTime(avg);
    auto [minVal, minUnit] = formatTime(static_cast<double>(minTime));
    auto [maxVal, maxUnit] = formatTime(static_cast<double>(maxTime));

    cout << fixed << setprecision(3);
    cout << "Avg Time: " << avgVal << " " << avgUnit << " | "
         << "Min Time: " << minVal << " " << minUnit << " | "
         << "Max Time: " << maxVal << " " << maxUnit << endl;

    printPercentiles();
}

string Bench::formatWithCommas(long long value) {
    std::string numStr = std::to_string(value);
    int insertPosition = static_cast<int>(numStr.length()) - 3;
    while (insertPosition > 0) {
        numStr.insert(insertPosition, ",");
        insertPosition -= 3;
    }
    return numStr;
}

pair<double, string> Bench::formatTime(double nanos) {
    if (nanos >= 1'000'000'000.0) {
        double seconds = nanos / 1'000'000'000.0;
        return {roundToDecimals(seconds, 3), seconds > 1 ? "seconds" : "second"};
    } else if (nanos >= 1'000'000.0) {
        double millis = nanos / 1'000'000.0;
        return {roundToDecimals(millis, 3), millis > 1 ? "millis" : "milli"};
    } else if (nanos >= 1000.0) {
        double micros = nanos / 1000.0;
        return {roundToDecimals(micros, 3), micros > 1 ? "micros" : "micro"};
    } else {
        double ns = nanos;
        return {roundToDecimals(ns, 3), ns > 1 ? "nanos" : "nano"};
    }
}

double Bench::roundToDecimals(double d, int decimals) {
    double pow10 = std::pow(10.0, decimals);
    return std::round(d * pow10) / pow10;
}

void Bench::printPercentiles() const {

    if (size == 0) return;

    double percentiles[] = {0.75, 0.90, 0.99, 0.999, 0.9999, 0.99999};

    for (double p : percentiles) {
        addPercentile(p);
    }
}

std::string Bench::formatPercentage(double perc) {
    double p = perc * 100.0;

    std::ostringstream oss;
    oss << std::fixed << std::setprecision(6) << p;

    std::string s = oss.str();
    // remove trailing zeros
    while (s.back() == '0') {
        s.pop_back();
    }

    // if the last character is now a '.', remove it
    if (s.back() == '.') {
        s.pop_back();
    }

    // Append the '%' sign
    s += "%";

    return s;
}

void Bench::addPercentile(double perc) const {

    if (results->empty()) return;

    long long target = static_cast<long long>(std::llround(perc * size));
    if (target == 0) return;
    if (target > size) target = size;

    // Iterate through the map to find the top element at position target
    long long iTop = 0;
    long long sumTop = 0;
    long long maxTop = -1;

    for (auto &entry : *results) {
        long long time = entry.first;
        long long count = entry.second;

        for (int i = 0; i < count; i++) {
            iTop++;
            sumTop += time;
            if (iTop == target) {
                maxTop = time;
                goto FOUND;
            }
        }
    }

FOUND:;

    double avgTop = static_cast<double>(sumTop) / iTop;
    auto [avgVal, avgUnit] = formatTime(avgTop);
    auto [maxVal, maxUnit] = formatTime(static_cast<double>(maxTop));

    cout << fixed << setprecision(3);
    cout << formatPercentage(perc) << " = [avg: " << avgVal << " " << avgUnit
         << ", max: " << maxVal << " " << maxUnit << "]\n";
}

int_map.hpp:

#ifndef INT_MAP_HPP
#define INT_MAP_HPP

#include <optional>
#include <cstddef>

template <typename E>
class IntMap {

private:

    template <typename T>
    struct Entry {
        int key;
        T* value;
        Entry<T>* next;
    };

    Entry<E>** data;
    int count;
    Entry<E>* head;
    const int capacity;

    Entry<E>* newEntry(int key, const E& value, Entry<E>* next) {
        Entry<E>* newEntry = head;

        if (newEntry != nullptr) {
            head = newEntry->next;
        } else {
            newEntry = new Entry<E>();
        }

        newEntry->key = key;
        newEntry->value = const_cast<E*>(&value);
        newEntry->next = next;

        return newEntry;
    }

    void free(Entry<E>* e) {
        e->value = nullptr;
        e->next = head;
        head = e;
    }

    int toArrayIndex(int key) const {
        return (key & 0x7FFFFFFF) % capacity;
    }

public:

    IntMap(int capacity)
        : capacity(capacity), count(0), head(nullptr) {
        data = new Entry<E>*[capacity];
        for (int i = 0; i < capacity; i++) {
            data[i] = nullptr;
        }
    }

    ~IntMap() {
        clear();

        while (head != nullptr) {
            Entry<E>* temp = head;
            head = head->next;
            delete temp;
        }

        delete[] data;
    }

    int size() const {
        return count;
    }

    E* get(int key) const {
        Entry<E>* e = data[toArrayIndex(key)];
        while (e != nullptr) {
            if (e->key == key) {
                return e->value;
            }
            e = e->next;
        }
        return nullptr;
    }

    E* put(int key, const E& value) {
        int index = toArrayIndex(key);
        Entry<E>* e = data[index];

        while (e != nullptr) {
            if (e->key == key) {
                E* old = e->value;
                e->value = const_cast<E*>(&value);
                return old;
            }
            e = e->next;
        }

        data[index] = newEntry(key, value, data[index]);
        count++;
        return nullptr;
    }

    E* remove(int key) {
        int index = toArrayIndex(key);
        Entry<E>* e = data[index];
        Entry<E>* prev = nullptr;

        while (e != nullptr) {
            if (e->key == key) {
                if (prev != nullptr) {
                    prev->next = e->next;
                } else {
                    data[index] = e->next;
                }

                E* oldValue = e->value;
                free(e);
                count--;
                return oldValue;
            }
            prev = e;
            e = e->next;
        }
        return nullptr;
    }

    void clear() {
        for (int index = capacity - 1; index >= 0; index--) {
            while (data[index] != nullptr) {
                Entry<E>* next = data[index]->next;
                free(data[index]);
                data[index] = next;
            }
        }
        count = 0;
    }
};

#endif // INT_MAP_HPP

int_map.cpp:

#include "int_map.hpp"

// NOOP

int_map_benchmark.cpp:

#include "int_map.hpp"
#include "bench.hpp"
#include <iostream>

using namespace std;

struct Dummy {};

int main(int argc, char* argv[]) {

    int warmupCount = 1000000;
    int measureCount = 1000000;
    int capacity = 100000;

    if (argc > 1) {
        warmupCount = atoi(argv[1]);
    }
    if (argc > 2) {
        measureCount = atoi(argv[2]);
    }
    if (argc > 3) {
        capacity = atoi(argv[3]);
    }

    cout << "\nArguments: warmup=" << warmupCount << " measurements=" << measureCount << " mapCapacity=" << capacity << endl << endl;

    int iterations = warmupCount + measureCount;

    IntMap<Dummy>* map = new IntMap<Dummy>(capacity);
    Bench bench(warmupCount);
    Dummy dummy;

    cout << "Benchmarking put..." << endl;
    bench.reset();
    for (int i = 0; i < iterations; i++) {
        bench.mark();
        map->put(i, dummy);
        bench.measure();
    }
    bench.printResults();
    cout << endl;

    cout << "Benchmarking get..." << endl;
    bench.reset();
    for (int i = 0; i < iterations; i++) {
        bench.mark();
        volatile auto val = map->get(i); // volatile to prevent optimization out
        bench.measure();
    }
    bench.printResults();
    cout << endl;

    cout << "Benchmarking remove..." << endl;
    bench.reset();
    for (int i = 0; i < iterations; i++) {
        bench.mark();
        map->remove(i);
        bench.measure();
    }
    bench.printResults();
    cout << endl;

    delete map; 
    return 0;
}

Results:

Benchmarking put...
Measurements: 10,000,000 | Warm-Up: 0 | Iterations: 10,000,000
Avg Time: 38.597 nanos | Min Time: 30.000 nanos | Max Time: 31.107 micros
75% = [avg: 32.235 nanos, max: 33.000 nanos]
90% = [avg: 32.501 nanos, max: 35.000 nanos]
99% = [avg: 33.093 nanos, max: 106.000 nanos]
99.9% = [avg: 37.288 nanos, max: 884.000 nanos]
99.99% = [avg: 38.177 nanos, max: 1.316 micros]
99.999% = [avg: 38.438 nanos, max: 15.270 micros]

Benchmarking get...
Measurements: 10,000,000 | Warm-Up: 0 | Iterations: 10,000,000
Avg Time: 24.109 nanos | Min Time: 19.000 nanos | Max Time: 15.886 micros
75% = [avg: 21.578 nanos, max: 25.000 nanos]
90% = [avg: 22.200 nanos, max: 26.000 nanos]
99% = [avg: 22.978 nanos, max: 91.000 nanos]
99.9% = [avg: 23.639 nanos, max: 160.000 nanos]
99.99% = [avg: 23.884 nanos, max: 432.000 nanos]
99.999% = [avg: 23.963 nanos, max: 13.451 micros]

Benchmarking remove...
Measurements: 10,000,000 | Warm-Up: 0 | Iterations: 10,000,000
Avg Time: 24.279 nanos | Min Time: 19.000 nanos | Max Time: 29.132 micros
75% = [avg: 21.899 nanos, max: 24.000 nanos]
90% = [avg: 22.426 nanos, max: 26.000 nanos]
99% = [avg: 23.140 nanos, max: 91.000 nanos]
99.9% = [avg: 23.798 nanos, max: 153.000 nanos]
99.99% = [avg: 24.017 nanos, max: 426.000 nanos]
99.999% = [avg: 24.125 nanos, max: 13.548 micros]