Почему Rust HashMap медленнее, чем Python dict?
Я написал скрипты, выполняющие одни и те же вычисления с dict и hashmap на Rust и Python. Почему-то версия Python более чем в 10 раз быстрее. Как это происходит?
Скрипт ржавчины: `
use std::collections::HashMap;
use std::time::Instant;
fn main() {
let now = Instant::now();
let mut h = HashMap::new();
for i in 0..1000000 {
h.insert(i, i);
}
let elapsed = now.elapsed();
println!("Elapsed: {:.2?}", elapsed);
}
Выход: Elapsed: 828.73ms
Скрипт Python:
import time
start = time.time()
d = dict()
for i in range(1000000):
d[i] = i
print(f"Elapsed: {(time.time() - start) * 1000:.2f}ms")
Выход: Elapsed: 64.93ms
То же самое для строковых ключей. Я искал разные обходные пути для разных хэшеров для HashMap, но ни один из них не дает более чем 10-кратного ускорения.
Например, я только что запустил ваш скрипт Python в онлайн-IDE и получил 2500+ мс. Неудивительно, что это будет медленнее, но это показывает влияние капризов системы и среды. Дело не только в том, что некоторые системы работают быстрее или медленнее во всех случаях.
@EdwardPeters сказал, что большинство проблем вашего бенчмаркинга, за исключением, может быть, одного: схема хеширования, используемая вашей хэш-таблицей, а также сам алгоритм хэш-таблицы, оказывают большое, большое влияние на производительность, и поскольку нет такой, которая лучше любого другого в любой ситуации, вполне возможно, что тот, который использует Python, отличается от того, который использует Rust, и просто быстрее в этом надуманном примере.
Вы, наверное, забыли --release в команде cargo run.
Говоря больше, одной из самых важных вещей в производительности является управление памятью. Любой, кто работал с языком с ручным управлением памятью — C, C++ или Rust, знает, что это боль. Сборка мусора — это гораздо более сложный процесс, но он может иметь серьезные и непредсказуемые последствия для производительности. Одна из причин, по которой вы считаете Rust «быстрым» языком, заключается в том, что он не является сборщиком мусора, но это не преимущество, которое станет очевидным в таком простом случае, как этот, когда сборка мусора Python не имеет никакого отношения.
Более того, Rust — это язык низкого уровня, что не обязательно означает более быструю работу — это означает, что он дает программисту большие возможности для оптимизации. Если программист не использует эту мощь - как в этом случае - вы не ожидаете от этого преимущества в производительности. Точно так же компилятор может выполнять оптимизацию, которую не может выполнять интерпретируемый язык, но если выполняемый процесс настолько прост, то может и не быть ничего подобного, или код может быть настолько простым, что даже JIT интерпретируемого языка оптимизации могут быть эквивалентны.
Из краткого взгляда на strace я соглашусь, что это управление памятью. Похоже, что Python занимает примерно вдвое больше памяти на основе вызовов mmap. И если хэш в rust создается с помощью_capacity, он намного быстрее, чем раньше (и быстрее, чем Python, если скомпилирован с оптимизацией) — похоже, ему приходилось копировать полные данные всякий раз, когда они росли, Python, вероятно, имеет только меньшие ссылки на данные (но поэтому требуется больше памяти).
Однако в гораздо более широком смысле, и это должно быть выводом - объективно сравнивать производительность языков сложно. Даже профессионально выполненные тесты могут не отражать реальную производительность кода, особенно потому, что не существует «единого числа» скорости языка. Чтобы начать делать попытку, вам нужно контролировать начальное состояние вашей системы, включая одновременно запущенные процессы и состояние иерархии памяти.
@Finomnis Я попробовал это локально, и действительно, Rust, созданный с помощью --release, намного быстрее, чем Python. Это может быть интересно, но OCaml немного медленнее, чем Python.
@Finomnis Я имею в виду, что это, безусловно, может иметь место, но это не то и не другое - есть миллион вещей, которые могут повлиять на производительность. Без гораздо более контролируемого эксперимента я не думаю, что в диагностике есть смысл.
@SteffenUllrich «Похоже, что Python занимает примерно в два раза больше памяти на основе вызовов mmap» Возможно, потому, что Python не хранит необработанные целые числа в своих потенциально гетерогенных dict; он хранит динамически размещаемые объекты (которые в конце концов содержат целое число в этом примере), которые намного больше.
@EdwardPeters В целом да, но никогда не должно быть случая, когда такой простой код на Rust в 10 раз медленнее, чем его эквивалент на Python. Это было бы серьезным недостатком в реализации Rust HashMap, учитывая, что Rust специально написан с учетом производительности. Мы не говорим здесь о процентах, мы говорим о порядках.
@Finomnis Это имеет смысл, за исключением крайностей. На самом деле, глядя на это больше, я удивлен, что компилятор Rust не просто оптимизирует это. Разве он не может сказать, что инициализация хэш-карты не имеет побочных эффектов или не создает где-то других ссылок?
@Finomnis, хотя есть абсолютно такие случаи, например, выделение чрезвычайно дорого для ржавчины, гораздо дороже, чем для python, у python также больше возможностей для уловок (например, объединение пустой строки не является операцией, все это обходится и вы просто получаете исходный код обратно), поэтому регулярно люди берут код Python с большим объемом памяти, переводят его в ржавчину с таким же большим объемом памяти (чего вы обычно избегаете), и производительность снижается.
@EdwardPeters Хэш-карта имеет 1 миллион записей, я думаю, что вычисление ее значения во время компиляции - плохая идея. Это сильно раздуло бы исполняемый файл.
Другой распространенной ошибкой является ввод-вывод: rust всегда буферизует строки через стандартный вывод, в то время как python позволяет libc делать свое дело, что означает полную буферизацию, которая намного эффективнее, особенно при записи большого количества очень маленьких строк. Это усугубляется тем, что механизм форматирования ржавчины, как известно,… довольно медленный.
@Finomnis Я не говорю «Делайте это во время компиляции», я говорю «Не делайте этого» - никакое значение никогда не считывается, ничто из того, что я вижу, не может вызвать ошибку ... это мертвая переменная. Я бы ожидал, что компилятор просто обработает это как отсутствие операции.
@EdwardPeters А, теперь я тебя понял. Ага, думаю, может. Я подозреваю, что это слишком сложно для понимания компилятором.
Ответы 1
В Rust по умолчанию не включена оптимизация, потому что это раздражает при отладке. Это делает его в режиме отладки медленнее, чем Python. Включение оптимизации должно решить эту проблему.
Это поведение не специфично для Rust, оно используется по умолчанию для большинства компиляторов (например, gcc/g++ или clang для C/C++, оба требуют флага -O3 для максимальной производительности).
Вы можете включить оптимизацию в Rust, добавив флаг --release к соответствующим командам cargo, например:
cargo run --release
Python не делает различий между оптимизацией и без нее, потому что Python является интерпретируемым языком и не имеет (явного) шага компиляции.
Это поведение вашего кода на моей машине:
- Python: ~180 мс
- Ржавчина: ~1750 мс
- Ржавчина (с
--release): ~160 мс
Реализация Python dict, скорее всего, написана на C и сильно оптимизирована, поэтому по производительности она должна быть похожа на Rust HashMap, что я и вижу на своей машине.
Другим компонентом этой повторяющейся «проблемы» является то, что Rust по умолчанию использует очень безопасную, но относительно дорогую хеш-функцию (SipHash 1-3). Между тем, хеш-функция для целых чисел в Python — это буквально функция тождества, поэтому ее можно вычислить практически бесплатно.
@Masklinn Имеет смысл. Думаю, это объясняет, почему Rust не работает быстрее, как я изначально ожидал. Накладные расходы на динамически выделяемые типы со сборкой мусора (Python) примерно выравнивают накладные расходы на более сложную хеш-функцию (Rust).
FWIW, когда хэш-карта критична для производительности и не подвергается потенциально злонамеренному пользовательскому вводу, обычно предлагается посмотреть что-то вроде fnv, ahash, city, ... (хотя необходимо провести сравнительный анализ, поскольку они могут иметь разные шаблоны конфликтов). Целые числа очень малы, поэтому хэш практически не требует затрат на установку. Можно даже сократить общий хэш, чтобы поддерживать только конкретный случай, например. 32-битные значения.
(для сравнения, "xxhash" имеет много настроек, но очень быстр, когда он шагает, поэтому он хорош для больших ключей)
Во-первых, структуры Python поддерживаются высокооптимизированным кодом C — в простых случаях, когда «клей» минимален, разумно ожидать, что Python будет достаточно быстрым.
range()в частности, это функция с поддержкой C, которая может быть быстрее, чем итерация и ручное добавление значений в Rust. Во-вторых, очень сложно производить такие расчеты производительности — в игру вступают всевозможные вещи, такие как время прогрева и кэширование памяти. Отдельные тесты, подобные этому, часто бессмысленны.