Производительность C ++ std :: unordered_map против Kotlin / Java HashMap

Question

Я создал проект Andorid для измерения некоторых эквивалентных частей кода, и этот заставил меня задуматься, почему?Почему C ++ в 3 раза медленнее?

Я уже внес некоторые изменения в C ++, как немедленную попытку внедрения, а затем push_back был медленнее, чем текущий подход, но все же.Сложности здесь должны быть одинаковыми, верно?

Kotlin: 139945691ns

C ++: 347100764ns

Kotlin:

data class Record(
    val year: Int,
    val month: Int, 
    val day: Int, 
    var temperature: Double
)

val records = ArrayList<Record>()
val map = HashMap<String, ArrayList<Record>>()

records.forEach { map.getOrPut("${it.year}-${it.month}") { ArrayList() }.add(it) }

C ++

typedef struct record {
    int year;
    int month;
    int day;
    double temperature;
} Record;

std::vector<Record> records;
std::unordered_map<std::string, std::vector<Record>> map;

for (const auto &record : records) {
    const std::string & key = std::to_string(record.year) + " " + std::to_string(record.month);
    const auto & it = map.find(key);

    if (it == map.end()) {
        map.emplace_hint(it, key, std::vector<Record>())->second.push_back(record);
    } else {
        it->second.push_back(record);
    }
}

// Редактировать

Код C ++: https://pastebin.com/KqD02pSD

КодексКод Котлина: https://pastebin.com/iG7hCqHT

---

Важное редактирование

Я изменил ключ карт на Int - [year * 100 + month].И результаты все еще похожи;В 3 раза медленнее.

Answer 1

Всегда трудно сказать, почему именно определенный фрагмент кода работает так, как он работает без надлежащего профилирования.Особенно когда речь идет о C ++, где нет стандартной реализации, и, следовательно, качество реализации компилятора и библиотеки может значительно различаться в зависимости от того, какой набор инструментов вы используете (примеры: 1 , 2 ).Кроме того, интерфейс, который стандарт требует для unordered_map, к сожалению, серьезно ограничивает то, что может сделать реализация под ним (см. этот доклад для получения дополнительной информации).Общеизвестно, что std::unordered_map, к сожалению, не обязательно является лучшей хеш-таблицей, на которую можно надеяться ( немного больше на , что ).

Помимо проблем производительности самого std::unordered_map, есть несколько незначительных (скорее всего, незначительных) вещей, которые могут поставить ваш код C ++ в дополнительный недостаток.Прежде всего, вы строите строку ключа, а затем копируете ее в карту.Скорее всего, было бы более эффективно переместить строку.Кроме того, std::to_string потенциально более дорогостоящий, чем преобразование, выполняемое интерполяцией строки Kotlin, потому что std::to_string вынужден наблюдать текущую локаль, в то время как интерполяция строки Kotlin конвертирует в фиксированный формат.Как правило, здесь довольно расточительно использовать строки в качестве ключей, как уже указывалось в комментариях к вашему вопросу.

Я бы предложил использовать map.try_emplace() вместо map.emplace_hint() иstd::to_chars() вместо std::to_string().Кроме того, я не удивлюсь, если Kotlin HashTable является просто более эффективным контейнером, чем std::unordered_map, возможно, из-за ограничений, установленных его интерфейсом…

Все это, я сказал,Я не уверен, что именно вы пытаетесь достичь с помощью этого теста.В конце концов, здесь вы сравниваете производительность двух случайно выбранных реализаций хеш-таблиц.Вы никогда не сможете выбрать одно из другого, поскольку они существуют в двух совершенно разных экосистемах, поэтому, какими бы ни были результаты этого теста, они не кажутся очень… полезными!?