Почему пересечение набора Python быстрее, чем пересечение Rust HashSet?

Ответ 1

Когда я перемещаю построение набора из цикла и повторяю только пересечение, для обоих случаев, конечно, Rust быстрее, чем Python 2.7.

Я только читал Python 3 (setobject.c), но для реализации Python некоторые вещи идут на это.

Он использует тот факт, что оба объекта Python set используют одну и ту же функцию хеширования, поэтому он не перепродает хэш. Rust HashSet имеют уникальные ключи для своих хэш-функций, поэтому во время пересечения они должны перефразировать ключи из одного набора с помощью другой хэш-функции набора.

С другой стороны, Python должен обратиться к функции сравнения динамического ключа, например PyObject_RichCompareBool для каждого совпадающего хеша, в то время как код Rust использует дженерики и специализируется на хэш-функции и сравнительном коде для i32. Код для хэширования i32 в Rust выглядит относительно дешевым, и большая часть алгоритма хэширования (обработка более длинного ввода, чем 4 байта) удаляется.

Похоже, что это конструкция множеств, которые разделяют Python и Rust. И на самом деле не просто конструкция, там какой-то значительный код работает, чтобы разрушить Rust HashSet. (Это можно улучшить, подал ошибку здесь: # 31711)

Ответ 2

Проблема производительности сводится к реализации по умолчанию хэширования HashMap и HashSet. Алгоритм хеширования Rust по умолчанию является хорошим универсальным алгоритмом, который также защищает от некоторых типов атак DOS. Тем не менее, он не работает отлично для очень маленьких или очень больших объемов данных.

Некоторые профилирования показали, что make_hash<i32, std::collections::hash::map::RandomState> занимал около 41% общего времени выполнения. Начиная с Rust 1.7, вы можете выбрать, какой алгоритм хеширования использовать. Переход на алгоритм хеширования FNV значительно ускоряет программу:

extern crate fnv;

use std::collections::HashSet;
use std::hash::BuildHasherDefault;
use fnv::FnvHasher;

fn main() {
    let mut len_sums = 0;
    for _ in 0..100000 {
        let set_1: HashSet<i32, BuildHasherDefault<FnvHasher>> = (0..1000).collect();
        let set_2: HashSet<i32, BuildHasherDefault<FnvHasher>> = (500..1500).collect();
        let intersection_len = set_1.intersection(&set_2).count();
        len_sums += intersection_len;
    }
    println!("{}", len_sums);
}

На моей машине это занимает 2,714 секунды по сравнению с Python 9,203.

Если вы сделаете те же изменения, чтобы вывести сборку из цикла, код Rust займет 0,829 с по сравнению с кодом Python 3,093.

Ответ 3

Оставаясь в стороне, Python проносится мимо предыдущих версий Rust, когда вы пересекаете крошечный и огромный набор в неправильном направлении. Например, этот код на детской площадке:

use std::collections::HashSet;
fn main() {
    let tiny: HashSet<i32> = HashSet::new();
    let huge: HashSet<i32> = (0..1_000).collect();
    for (left, right) in &[(&tiny, &huge), (&huge, &tiny)] {
        let sys_time = std::time::SystemTime::now();
        assert_eq!(left.intersection(right).count(), 0);
        let elapsed = sys_time.elapsed().unwrap();
        println!(
            "{:9}ns starting from {:4} element set",
            elapsed.subsec_nanos(),
            left.len(),
        );
    }
}

при запуске с 1.32 или более ранними версиями Rust, а не с текущей версией, обнаруживается, что вы действительно хотите вызвать метод пересечения для меньшего из двух наборов (даже в пограничном случае, когда один набор пуст). Я получил хороший прирост производительности, вызвав эту функцию вместо метода пересечения:

fn smart_intersect<'a, T, S>(
    s1: &'a HashSet<T, S>,
    s2: &'a HashSet<T, S>,
) -> std::collections::hash_set::Intersection<'a, T, S>
where
    T: Eq + std::hash::Hash,
    S: std::hash::BuildHasher,
{
    if s1.len() < s2.len() {
        s1.intersection(s2)
    } else {
        s2.intersection(s1)
    }
}

Метод в Python обрабатывает два набора одинаково (по крайней мере, в версии 3.7).

PS Почему это? Скажем, в небольшом наборе Sa есть элементы A, в большом наборе Sb - B, требуется время Th для хеширования одного ключа, время Tl (X) для поиска хешированного ключа в наборе с X элементами. Затем:

• Sa.intersection(&Sb) стоит A * (Th + Tl (B))
• Sb.intersection(&Sa) стоит B * (Th + Tl (A))

Предполагая, что хеш-функция хороша, а блоков много (потому что, если мы беспокоимся о производительности пересечения, мы должны были убедиться, что множества эффективны с самого начала), тогда Tl (B) должен быть на уровне Tl (A ) или, по крайней мере, Tl (X) должен масштабироваться намного меньше, чем линейно с заданным размером. Поэтому это A против B, который определяет стоимость операции.

PS Та же проблема и обходной путь существовали для is_disjoint а также для union (дешевле скопировать большой набор и добавить несколько элементов, чем копировать небольшой набор и добавить много, но не очень). Запрос на объединение был объединен, поэтому это несоответствие исчезло со времен Rust 1.35.