tl; dr
- bitvecs могут работать, но для повышения производительности требуется много оптимизации в особых случаях
- Наиболее важны чистые реализации достойных алгоритмов.
Длинная версия
Следует отметить, что производительность различных методов может меняться в зависимости от размера ввода. Это также может быть не так, дело в том, что использование только одного входного размера при тестировании может дать результаты, которые не распространяются на все размеры.
Вот исходный код в вопросе:
pub fn primes(n: u64) -> Vec<usize> {
if n < 4 {
vec![2]
} else {
base(primes((n as f64).sqrt().ceil() as u64), n)
}
}
fn base(r: Vec<usize>, p: u64) -> Vec<usize> {
let fvec = (0..p).map(|_| false).collect::<Vec<bool>>();
let z = r
.iter()
.map(|&x| (0..x).map(|y| y > 0).collect::<Vec<bool>>())
.map(|x| {
(0..p)
.map(|n| !x[(n % (x.len() as u64)) as usize])
.collect::<Vec<bool>>()
})
.fold(fvec, |acc, x| {
acc.iter().zip(x).map(|(a, b)| *a || b).collect()
});
let yy: Vec<usize> = z
.iter()
.enumerate()
.filter_map(|(i, x)| if !*x { Some(i) } else { None })
.skip(1)
.collect();
r.iter().chain(yy.iter()).map(|x| *x).collect()
}
Мне показалось, что приведенный выше код довольно сложно читать. Понять. Вроде бы много лишнего шума, вроде ненужных собирает. Кроме того, имена переменных могут быть более наглядными.
Ниже представлена моя наивная реализация сита (calc_primes_mine_naive, на тестах ниже). У него нет изменчивости, хотя, по общему признанию, есть ненужный сбор. Это в 2–3 раза быстрее, чем указано выше.
pub fn primes_less_than(n: u64) -> Vec<usize> {
let is_not_prime: Vec<bool> = (0..n).map(|num| {
let sieve_upper_bound = (num as f64).sqrt().ceil() as u64 + 1;
(2..sieve_upper_bound).any(|divisor| {
(num % divisor) == 0
})
}).collect();
is_not_prime.iter().enumerate().filter(|(_, this_one_not_prime)| {
!**this_one_not_prime
}).map(|(definitely_prime, _)| { definitely_prime }).collect()
}
Ниже первая попытка оптимизации. Как правило, sqrts медленные, поэтому избавление от повторяющихся sqrts, как указано выше, должно быть абсолютной победой (похоже, не имело большого значения).
pub fn primes_less_than_naive(n: u64) -> Vec<usize> {
let mut sqrt = 1;
let is_not_prime: Vec<bool> = (0..n).map(|num| {
if sqrt * sqrt <= num {
sqrt += 1;
}
let sieve_upper_bound = sqrt + 1;
(2..sieve_upper_bound).any(|divisor| {
(num % divisor) == 0
})
}).collect();
is_not_prime.iter().enumerate().filter(|(_, this_one_not_prime)| {
!**this_one_not_prime
}).map(|(definitely_prime, _)| { definitely_prime }).collect()
}
Посмотрел сборку и профилировал в vtune. Vtune жаловался на накладные расходы на "высокое переключение MS". Я изначально предполагаю, что это было вызвано приведением типов к поплавкам и обратно, но оно продолжалось после удаления всех операций с плавающими точками. Взгляд на сборку, казалось, подразумевал, что могут быть некоторые накладные расходы из-за collect, поэтому я избавился от лишнего сбора.
pub fn primes_less_than_naive2(n: u64) -> Vec<usize> {
let mut sqrt = 1;
(0..n).map(|num| {
if sqrt * sqrt <= num {
sqrt += 1;
}
let sieve_upper_bound = sqrt + 1;
(2..sieve_upper_bound).any(|divisor| {
(num % divisor) == 0
})
}).enumerate().filter(|(_, this_one_not_prime)| {
!*this_one_not_prime
}).map(|(definitely_prime, _)| { definitely_prime }).collect()
}
Отсутствие изменчивости, похоже, немного ухудшило производительность. Возможно, есть способ express без использования mut, но, вероятно, это будет довольно громоздкий код.
pub fn primes_less_than_naive_with_mut(n: usize) -> Vec<usize> {
let mut is_not_prime = vec![false; n as usize];
let sieve_upper_bound = (n as f64).sqrt().ceil() as usize + 1;
(1..sieve_upper_bound).for_each(|step_size| {
(0..n).step_by(step_size).for_each(|i| {
is_not_prime[i] = true;
})
});
is_not_prime.iter().enumerate().filter(|(_, this_one_not_prime)| {
!**this_one_not_prime
}).map(|(definitely_prime, _)| { definitely_prime }).collect()
}
В этот момент vtune жалуется, что некоторые части вышеперечисленного связаны с ядром, и некоторые части привязаны к памяти. Это раздражает, b / c способ решить проблему с привязкой к памяти - использовать битвек, а способ исправить привязку к ядру - не использовать битвек. Пытаясь облегчить ограничение памяти, я попытался изменить направление l oop, идея заключалась в том, что это позволит лучше использовать кеш. Когда я впервые написал это, я обнаружил, что это работает, но с тех пор я этого не сделал.
pub fn primes_less_than_naive_alternating(n: usize) -> Vec<usize> {
let mut is_not_prime = vec![false; n as usize];
let sieve_upper_bound = (n as f64).sqrt().ceil() as usize + 1;
let mut forward = true;
(1..sieve_upper_bound).for_each(|step_size| {
if forward {
(0..n).step_by(step_size).for_each(|i| {
is_not_prime[i] = true;
})
} else {
(0..n).step_by(step_size).rev().for_each(|i| {
is_not_prime[i] = true;
})
};
forward = !forward;
});
is_not_prime.iter().enumerate().filter(|(_, this_one_not_prime)| {
!**this_one_not_prime
}).map(|(definitely_prime, _)| { definitely_prime }).collect()
}
Bitve c версия. Это медленнее (неудивительно). Возможно, удастся сделать это быстро, имея какую-то таблицу поиска по маске для небольшого step_size, но я не optimisti c. Vtune не может сказать ничего интересного, кроме того, что это может быть связано с множеством зависимостей данных. (Иначе говоря, он не может выйти из строя) b / c следующий байт зависит от предыдущего байта [b / c позади сцены, загрузка и сохранение имеют размер слова?])
pub unsafe fn primes_less_than_naive_bitvec(n: usize) -> Vec<usize> {
let num_bytes = n / 8 + 1;
let mut is_not_prime = libc::calloc(size_of::<u8>(), num_bytes) as *mut u8;
let sieve_upper_bound = (n as f64).sqrt().ceil() as usize + 1;
(1..sieve_upper_bound).for_each(|step_size| {
(0..n).step_by(step_size).for_each(|i| {
let address = i >> 3;
let bit_within_the_byte = i & 0b111;
let cur = is_not_prime.offset(address as isize);
*cur |= ((0x1 as u8) << bit_within_the_byte);
});
});
(0..n).filter(|i|{
let address = i / 8;
let bit_within_the_byte = i % 8;
let cur = is_not_prime.offset(address as isize).read();
let is_not_prime = (cur | ((0x1 as u8) << bit_within_the_byte)) > 0;
!is_not_prime
}).collect::<Vec<usize>>()
}
При n = 10:
test calc_primes ... bench: 752 ns/iter (+/- 61)
test calc_primes_mine ... bench: 314 ns/iter (+/- 20)
test calc_primes_mine_alternating_loop_direction ... bench: 110 ns/iter (+/- 6)
test calc_primes_mine_bitvec ... bench: 165 ns/iter (+/- 888)
test calc_primes_mine_naive ... bench: 304 ns/iter (+/- 29)
test calc_primes_mine_naive2 ... bench: 250 ns/iter (+/- 16)
test calc_primes_mine_naive_with_mut ... bench: 70 ns/iter (+/- 4)
При n = 100:
test calc_primes ... bench: 5,924 ns/iter (+/- 2,210)
test calc_primes_mine ... bench: 3,384 ns/iter (+/- 88)
test calc_primes_mine_alternating_loop_direction ... bench: 673 ns/iter (+/- 23)
test calc_primes_mine_bitvec ... bench: 1,194 ns/iter (+/- 36)
test calc_primes_mine_naive ... bench: 3,141 ns/iter (+/- 195)
test calc_primes_mine_naive2 ... bench: 2,919 ns/iter (+/- 107)
test calc_primes_mine_naive_with_mut ... bench: 521 ns/iter (+/- 31)
При n = 1000:
test calc_primes ... bench: 120,828 ns/iter (+/- 18,018)
test calc_primes_mine ... bench: 59,269 ns/iter (+/- 6,993)
test calc_primes_mine_alternating_loop_direction ... bench: 7,080 ns/iter (+/- 2,795)
test calc_primes_mine_bitvec ... bench: 16,186 ns/iter (+/- 470)
test calc_primes_mine_naive ... bench: 56,572 ns/iter (+/- 1,849)
test calc_primes_mine_naive2 ... bench: 54,526 ns/iter (+/- 9,773)
test calc_primes_mine_naive_with_mut ... bench: 5,873 ns/iter (+/- 531)
При n = 10 000
test calc_primes ... bench: 2,672,089 ns/iter (+/- 117,553)
test calc_primes_mine ... bench: 1,222,262 ns/iter (+/- 24,242)
test calc_primes_mine_alternating_loop_direction ... bench: 77,348 ns/iter (+/- 4,845)
test calc_primes_mine_bitvec ... bench: 201,894 ns/iter (+/- 4,446)
test calc_primes_mine_naive ... bench: 1,213,264 ns/iter (+/- 160,097)
test calc_primes_mine_naive2 ... bench: 1,174,753 ns/iter (+/- 88,116)
test calc_primes_mine_naive_with_mut ... bench: 66,283 ns/iter (+/- 6,358)
При = 100 000:
test calc_primes ... bench: 71,953,394 ns/iter (+/- 11,795,923)
test calc_primes_mine ... bench: 27,542,006 ns/iter (+/- 5,158,828)
test calc_primes_mine_alternating_loop_direction ... bench: 1,103,863 ns/iter (+/- 135,770)
test calc_primes_mine_bitvec ... bench: 2,547,044 ns/iter (+/- 180,308)
test calc_primes_mine_naive ... bench: 27,399,779 ns/iter (+/- 3,121,742)
test calc_primes_mine_naive2 ... bench: 26,430,825 ns/iter (+/- 1,818,277)
test calc_primes_mine_naive_with_mut ... bench: 1,045,803 ns/iter (+/- 103,090)
При n = 1000000:
test calc_primes ... bench: 1,827,068,877 ns/iter (+/- 131,368,352)
test calc_primes_mine ... bench: 658,940,900 ns/iter (+/- 45,559,627)
test calc_primes_mine_alternating_loop_direction ... bench: 18,112,057 ns/iter (+/- 1,839,472)
test calc_primes_mine_bitvec ... bench: 30,189,983 ns/iter (+/- 2,649,749)
test calc_primes_mine_naive ... bench: 658,018,301 ns/iter (+/- 39,323,294)
test calc_primes_mine_naive2 ... bench: 651,249,390 ns/iter (+/- 22,800,036)
test calc_primes_mine_naive_with_mut ... bench: 18,212,183 ns/iter (+/- 2,936,353)