Как вы, наверно, знаете, из-за наличия в компьютере различных кэшей (L1, L2, L3...) и того, что операции с памятью выполняются с линиями кэша размером примерно 64 байт каждая, для обеспечения максимальной производительности мы должны писать программы, обеспечивающие локальность.
Но насколько хорошо вы это осознаёте? Допустим, у нас есть массив чисел с плавающей запятой и массив индексов первого массива. Есть программа, складывающая числа из первого массива в порядке, определяемом вторым массивом. То есть в этом примере мы будем складывать ε + α + δ + ζ + β + γ в таком порядке:
Давайте рассмотрим всего два случая: индексы идут в порядке от первого до последнего или в произвольном порядке. До того, как я начал писать этот пост, я не мог ответить ни на один из следующих вопросов:
Насколько большим должен быть массив, чтобы разница производительности вычисления в двух порядках стала заметной?
Сколько в среднем тратится на каждый элемент в порядке от первого до последнего?
Насколько медленнее произвольный порядок последовательного в случае массивов, умещающихся в RAM?
Насколько медленнее произвольный порядок последовательного в случае массивов, не умещающихся в RAM?
Достаточно ли стандартного тасования Фишера-Йейтса для массивов перемешанных индексов для получения произвольного порядка?
Насколько медленнее порядок от первого до последнего в случае массивов, не умещающихся в RAM, при использовании файлов с отображением в память?
Максимально ли быстры файлы с отображением в память?
Если вы уже знаете ответы на эти вопросы, то это замечательно! Если же нет, то делайте ваши предположения и проверьте их, прочитав пост.
Подготовка
Весь код, необходимый, чтобы воссоздать измерения из этого поста, можно найти в репозитории GitHub.
Так как индексы просто хранятся в массиве, они должны использовать один и тот же машинный код для порядка с первого до последнего и произвольного порядка с выбранной точностью типов данных чисел с плавающей запятой и целых чисел. Это значит, что производительность полностью должна определяться динамическим поведением CPU на основании используемых нами данных, а также от другого динамического поведения операционной системы, например, от работы со страницами памяти и областью подкачки.
Код на Rust
use std::ops::{AddAssign, Index};
use num::{Float, Num, traits::ToBytes};
trait Number: Sized + Copy + Into<f64> + AddAssign + Num + Float + ToBytes {}
impl Number for f32 {}
impl Number for f64 {}
fn sum<T: Number, I: Copy>(floats: &[T], indices: &[I]) -> T
where
[T]: Index<I, Output = T>,
{
let mut total = T::zero();
for &i in indices {
total += floats[i];
}
total
}
#[test]
fn test_sum_f64_usize_not_associative() {
let floats: &[f64] = &[0.1, 0.2, 0.3];
let forward: &[usize] = &[0, 1, 2];
let backward: &[usize] = &[2, 1, 0];
assert_eq!(sum(floats, forward), 0.6000000000000001);
assert_eq!(sum(floats, backward), 0.6);
}Теперь нам нужно сгенерировать случайные данные. Для чисел с плавающей запятой мы можем использовать нормальное распределение, а для целочисленных индексов можно просто взять список целых чисел до длины массива и перемешать их, чтобы получить произвольную перестановку тасованием Фишера-Йейтса — стандартным алгоритмом, который перемешивает данные за один проход.
По крайней мере, так я считал поначалу. Небольшой спойлер: ниже мы проведём эксперименты с слишком большими для памяти массивами, и для них алгоритм Фишера-Йейтса оказывается слишком медленным. Поэтому вместо него я реализовал двухпроходное тасование, которое сначала разбивает массив на блоки размером примерно в гигабайт.
Код генерации случайных данных
use std::{
fmt, fs,
io::{self, Read, Seek, Write},
};
use rand::Rng;
use rand_distr::{Distribution, Normal, StandardNormal};
use tempfile::tempfile;
trait Int: TryFrom<usize, Error: fmt::Debug> + ToBytes {}
impl Int for u32 {}
impl Int for u64 {}
trait Progress {
fn new(len: usize) -> Self;
fn step(&mut self);
}
fn random_floats<T: Number, P: Progress>(rng: &mut impl Rng, mut writer: impl Write, n: usize)
where
StandardNormal: Distribution<T>,
{
let mut progress = P::new(n);
let normal = Normal::<T>::new(T::zero(), T::one()).unwrap();
for _ in 0..n {
let x = normal.sample(rng);
writer.write_all(x.to_ne_bytes().as_ref()).unwrap();
progress.step();
}
}
fn first_to_last<I: Int, P: Progress>(mut writer: impl Write, n: usize) {
let mut progress = P::new(n);
for i in 0..n {
writer
.write_all(I::try_from(i).unwrap().to_ne_bytes().as_ref())
.unwrap();
progress.step();
}
}
fn permutation<I: Int, P: Progress>(rng: &mut impl Rng, mut writer: impl Write, n: usize) {
let m = (n * size_of::<I>()).div_ceil(1 << 30);
let mut progress = P::new(2 * n);
let mut files: Vec<fs::File> = (0..m).map(|_| tempfile().unwrap()).collect();
{
let mut writers: Vec<io::BufWriter<_>> = files.iter_mut().map(io::BufWriter::new).collect();
for i in 0..n {
let j = rng.random_range(0..m);
writers[j]
.write_all(I::try_from(i).unwrap().to_ne_bytes().as_ref())
.unwrap();
progress.step();
}
}
for mut file in files {
let mut bytes = Vec::new();
file.seek(io::SeekFrom::Start(0)).unwrap();
file.read_to_end(&mut bytes).unwrap();
let (prefix, values, suffix) = unsafe { bytes.align_to_mut::<I>() };
assert!(prefix.is_empty());
assert!(suffix.is_empty());
for i in 0..values.len() {
let j = rng.random_range(..=i);
values.swap(i, j);
progress.step();
}
writer.write_all(&bytes).unwrap();
}
}Дальше нам нужно просто нужно сохранить их в файлы данных разных размеров. Мы выберем степени двойки, чтобы они удобно хранились на SSD.
Код генерации массовых данных в файлы
use std::{ops::RangeInclusive, path::Path};
use indicatif::ProgressBar;
use rand::SeedableRng;
impl Progress for ProgressBar {
fn new(len: usize) -> Self {
let bar = ProgressBar::new(len as u64);
bar.set_position(0);
bar
}
fn step(&mut self) {
self.inc(1);
}
}
fn make_rng(seed: u64) -> impl Rng {
rand_pcg::Pcg64Mcg::seed_from_u64(seed)
}
fn generate_file(dir_name: &str, file_name: &str, f: impl FnOnce(io::BufWriter<fs::File>)) {
let dir = Path::new(dir_name);
let path = dir.join(file_name);
println!("generating {}", path.display());
fs::create_dir_all(dir).unwrap();
f(io::BufWriter::new(fs::File::create(path).unwrap()));
}
struct Options {
f32: bool,
f64: bool,
u32: bool,
u64: bool,
}
const FLOAT32: &str = "float32";
const FLOAT64: &str = "float64";
const UNSHUFFLED32: &str = "unshuffled32";
const SHUFFLED32: &str = "shuffled32";
const UNSHUFFLED64: &str = "unshuffled64";
const SHUFFLED64: &str = "shuffled64";
fn generate(exponents: RangeInclusive<usize>, options: Options) {
for exponent in exponents {
let n = 1 << exponent;
let name = format!("{exponent}.dat");
if options.f32 {
generate_file(FLOAT32, &name, |writer| {
random_floats::<f32, ProgressBar>(&mut make_rng(0), writer, n);
});
}
if options.f64 {
generate_file(FLOAT64, &name, |writer| {
random_floats::<f64, ProgressBar>(&mut make_rng(1), writer, n);
});
}
if options.u32 {
generate_file(UNSHUFFLED32, &name, |writer| {
first_to_last::<u32, ProgressBar>(writer, n);
});
generate_file(SHUFFLED32, &name, |writer| {
permutation::<u32, ProgressBar>(&mut make_rng(2), writer, n);
});
}
if options.u64 {
generate_file(UNSHUFFLED64, &name, |writer| {
first_to_last::<u64, ProgressBar>(writer, n);
});
generate_file(SHUFFLED64, &name, |writer| {
permutation::<u64, ProgressBar>(&mut make_rng(3), writer, n);
});
}
}
}Результаты
Отлично, теперь, когда у нас есть все эти файлы, можно выполнить для них наш код!
Код вычисления сумм сгенерированных данных
use std::time::Instant;
use serde::Serialize;
trait Reader: AsRef<[u8]> {
fn new(path: &Path) -> Self;
}
impl Reader for Vec<u8> {
fn new(path: &Path) -> Self {
fs::read(path).unwrap()
}
}
#[derive(Serialize)]
struct Measurement<'a> {
floats: &'a str,
indices: &'a str,
exponent: usize,
iteration: usize,
output: f64,
seconds: f64,
}
#[derive(Clone, Copy)]
struct Index32(u32);
#[derive(Clone, Copy)]
struct Index64(u64);
impl<T> Index<Index32> for [T] {
type Output = T;
fn index(&self, index: Index32) -> &Self::Output {
unsafe { self.get_unchecked(index.0 as usize) }
}
}
impl<T> Index<Index64> for [T] {
type Output = T;
fn index(&self, index: Index64) -> &Self::Output {
unsafe { self.get_unchecked(index.0 as usize) }
}
}
unsafe fn reinterpret<T>(bytes: &[u8]) -> &[T] {
let (prefix, values, suffix) = unsafe { bytes.align_to::<T>() };
assert!(prefix.is_empty());
assert!(suffix.is_empty());
values
}
fn measure_files<R: Reader, T: Number, I: Copy>(
dir_floats: &str,
dir_indices: &str,
exponent: usize,
repeat: usize,
) where
[T]: Index<I, Output = T>,
{
let name = format!("{exponent}.dat");
let bytes_floats = R::new(&Path::new(dir_floats).join(&name));
let bytes_indices = R::new(&Path::new(dir_indices).join(&name));
let floats = unsafe { reinterpret::<T>(bytes_floats.as_ref()) };
let indices = unsafe { reinterpret::<I>(bytes_indices.as_ref()) };
for iteration in 0..repeat {
let start = Instant::now();
let total = sum(floats, indices);
let duration = start.elapsed();
let measurement = Measurement {
floats: dir_floats,
indices: dir_indices,
exponent,
iteration,
output: total.into(),
seconds: duration.as_secs_f64(),
};
println!("{}", serde_json::to_string(&measurement).unwrap());
}
}
fn measure<R: Reader>(exponents: RangeInclusive<usize>, options: Options, repeat: usize) {
for exponent in exponents {
if options.f32 {
if options.u32 {
measure_files::<R, f32, Index32>(FLOAT32, UNSHUFFLED32, exponent, repeat);
measure_files::<R, f32, Index32>(FLOAT32, SHUFFLED32, exponent, repeat);
}
if options.u64 {
measure_files::<R, f32, Index64>(FLOAT32, UNSHUFFLED64, exponent, repeat);
measure_files::<R, f32, Index64>(FLOAT32, SHUFFLED64, exponent, repeat);
}
}
if options.f64 {
if options.u32 {
measure_files::<R, f64, Index32>(FLOAT64, UNSHUFFLED32, exponent, repeat);
measure_files::<R, f64, Index32>(FLOAT64, SHUFFLED32, exponent, repeat);
}
if options.u64 {
measure_files::<R, f64, Index64>(FLOAT64, UNSHUFFLED64, exponent, repeat);
measure_files::<R, f64, Index64>(FLOAT64, SHUFFLED64, exponent, repeat);
}
}
}
}Я провёл эти эксперименты на двух машинах:
MacBook Pro 2020 года с чипом M1, 16 ГиБ RAM и SSD на 1 ТБ.
Десктоп с Linux на AMD Ryzen 5 3600X, 24 ГиБ DRAM Corsair Vengeance LPX DDR4 3000 МГц и 3D NAND SATA SSD Western Digital на 1 ТБ.
Для каждого примера данных (с выбранным типом чисел с плавающей запятой и целых чисел, а также размером массива) я выполнял суммирование не меньше десятка раз (в случае маленьких массивов — до сотни раз), отбрасывал первые два результата (пока прогревались кэши) и вычислял среднее оставшихся результатов в секундах.
MacBook
Вот результаты без тасования (синий график) и с ним (жёлтый график) для чисел с плавающей запятой одинарной/двойной точности точности и 32-/64-битных целочисленных индексов:
Стоит отметить, что оси X и Y имеют логарифмический масштаб. Как видите, графики выравниваются примерно на наносекунде на элемент, пока массив чисел с плавающей запятой не становится слишком большим, чтобы уместиться в кэш системного уровня (system-level cache, SLC), имеющий размер 8 МиБ. Далее показатели для порядка от первого до последнего остаются такими же, а для произвольного порядка увеличиваются до четырёх наносекунд. Когда же массив перестаёт помещаться в RAM, резко возрастает время для обоих порядков; подробнее об этом мы поговорим ниже.
Десктоп с Linux
Для маленьких массивов данные оказались чуть более шумными! Похоже, на этом CPU порядок от первого до последнего занимает всего половину наносекунды на элемент. Но даже несмотря на то, что его кэш L3 имеет размер 32 МиБ, произвольный порядок становится медленнее, когда массив чисел с плавающей запятой становится больше 4 МиБ; не совсем понимаю, с чем это связано. Соотношение здесь меняется резче, ранжируясь от четырёх до примерно восьми наносекунд на элемент после расхождения с кривой порядка от первого до последнего.
Как и на MacBook, большой скачок возникает, когда данные перестают помещаться RAM, но здесь интересное отличие заключается в том, что производительность для произвольного порядка начинает резко деградировать ещё до достижения этой точки, хотя порядок от первого до последнего остаётся относительно стабильным. Хоть в машине установлено 24 ГиБ RAM, массивы чисел с плавающей запятой размером больше гигабайта начинают достигать двадцати-тридцати наносекунд на элемент.
Отображение в память
После выполнения этих экспериментов я не знал точно, вызван ли скачок в правой части графика просто тем, что перед выполнением любых операций я пытался считать весь файл в память. Ниже представлены некоторые результаты с использованием файлов с отображением в память. Впрочем, к моему разочарованию, результаты выглядят более-менее похожими (но компьютер хотя бы не тормозил при работе с очень большими массивами).
Код для файлов с отображением в память
use memmap2::Mmap;
impl Reader for Mmap {
fn new(path: &Path) -> Self {
unsafe { Mmap::map(&fs::File::open(path).unwrap()) }.unwrap()
}
}MacBook
Выглядит почти так же, как и предыдущие результаты, но на этот раз мы смогли провести испытания с бóльшим объёмом данных. Как видите, в случае достаточно больших массивов перемешивание индексов практически не влияет на производительность; в обоих методиках в среднем на элемент приходится более двадцати наносекунд. Любопытно, связано ли это явление с особенностями macOS?
Десктоп с Linux
Почти ничего нового, но всё равно интересно, что производительность для произвольного порядка деградирует плавнее, чем производительность порядка от первого до последнего; после достижения миллиарда элементов последняя выглядит почти как ступенчатая функция.
«Прямое» сложение
Это будет последний эксперимент, обещаю! Мне было любопытно, какая часть падения производительности была вызвана просто разницей в полосе пропускания памяти и SSD, а какая — тем, как операционная система обрабатывает файлы с отображением в память. Поэтому я попробовал отдельную реализацию, которая просто считывает файл чисел с плавающей запятой по одному блоку за раз, суммирует этот блок, а затем переходит к следующему блоку.
Код более прямого суммирования из файла
use std::io::BufRead;
fn sum_buffered<T: Number>(dir_floats: &str, exponent: usize, repeat: usize) {
let name = format!("{exponent}.dat");
for iteration in 0..repeat {
let mut reader =
io::BufReader::new(fs::File::open(Path::new(dir_floats).join(&name)).unwrap());
let start = Instant::now();
let mut total = T::zero();
loop {
let buffer = reader.fill_buf().unwrap();
if buffer.is_empty() {
break;
}
let floats = unsafe { reinterpret::<T>(buffer) };
for &float in floats {
total += float;
}
let bytes = buffer.len();
reader.consume(bytes);
}
let duration = start.elapsed();
let measurement = Measurement {
floats: dir_floats,
indices: "unshuffled64",
exponent,
iteration,
output: total.into(),
seconds: duration.as_secs_f64(),
};
println!("{}", serde_json::to_string(&measurement).unwrap());
}
}
fn measure_buffered(exponents: RangeInclusive<usize>, options: Options, repeat: usize) {
for exponent in exponents {
if options.f32 {
sum_buffered::<f32>(FLOAT32, exponent, repeat);
}
if options.f64 {
sum_buffered::<f64>(FLOAT64, exponent, repeat);
}
}
}Стоит отметить, что это не сравнение сопоставимых показателей, как в предыдущих экспериментах, потому что для вычисления суммы используется совершенно другая реализация. Именно поэтому я выделил это в отдельный раздел.
MacBook
Это более-менее подтверждает мои подозрения: похоже, отображение в память не особо умное. Даже если удвоить это время, то в среднем мы получим всего несколько наносекунд на элемент, что гораздо быстрее, чем двадцать с лишним секунд на элемент, которые мы наблюдали для больших массивов.
Десктоп с Linux
В Linux совершенно другая история! Эти значения вполне сравнимы с тем, что мы видели раньше, особенно если удвоить их, чтобы учесть тот факт, что нам нужно считывать один файл вместо одного. Могу только предположить, что у SSD на машине с Linux полоса пропускания меньше, чем у SSD на MacBook, но операционная система Linux обрабатывает файлы с отображением в память умнее, чем macOS. Однако сложно судить с уверенностью, не попробовав провести этот эксперимент с разными операционными системами на одном железе.
Заключение
Вот и всё! Вот ответы на вопросы из начала поста:
Суммирование чисел достаточно сильно зависит от памяти, поэтому для массивов меньше миллиона элементов (размер типичного кэша L3) разница почти незаметна. Однако на моей машине с Linux, похоже, нет прямой взаимосвязи между этой точкой отсечки и самим размером кэша L3.
При порядке от первого до последнего на MacBook среднее время на элемент выравнивается в районе одной наносекунды, а на десктопе с Linux — примерно на половине наносекунды.
Для массивов, превышающих размер кэша L3, но меньше примерно гигабайта, произвольный порядок на MacBook примерно в четыре раза медленнее, а на десктопе с Linux — примерно в 8-16 раз медленнее.
В Linux произвольный порядок начинает становиться ещё более медленным в случае массивов больше гигабайта, в 50 с лишним раз медленнее, чем порядок от первого до последнего; на MacBook же, произвольный порядок просто выравнивается, если все данные помещаются в RAM.
Тасование Фишера-Йейтса слишком медленное для больших данных, которые не помещаются в память! Следует использовать вместо него двухпроходное тасование.
Файлы с отображением в память — это не какая-то магия: если данные слишком велики и не помещаются в RAM, то порядок от первого до последнего наконец-то становится медленнее примерно в 20 раз. После этой точки произвольный порядок в Linux по-прежнему более медленный, но на MacBook имеет примерно ту же скорость, что и порядок от первого до последнего.
Любопытно, что это свойство сохраняется даже при использовании более прямой методики в Linux, но волшебным образом пропадает в macOS; возможно, это вызвано различиями в обработке файлов с отображением в память в этих операционных системах?
Комментарии (3)
Jijiki
28.06.2025 09:47а почему 32 и 64 в расте слышал есть и 128
на фрибсд еще было бы интересно так как он мульти юзер спейс не сингл. и вкусная организация процессов )
(SIMD) gather effect можно обойти устанавливая конкретно порядок отправки и выравнивая данные тогда плавающая точка будет ускореннее вроде, тоесть образно отправляя последовательности прям в том порядке как нужно
примерно 2000 000 должно быть, там будет вроде ощутимо, но я давно тестил
kovserg
У вас какие-то странные тесты и графики: 32bit/1ns=3.7Gb/s 64bit/0.5ns=15Gb/s. Да и методика тоже.
Если хотите истощить кэш, то надо создать массив указателей которые указывает на следуюй элемент, перемешать и щемиться по нему:
Такой тест не даст расслабиться ни кэшу ни банкам в dram. И покажет поряда 0.1Gb/s при пропускной способности в ~70Gb/s при последовательном доступе.
ps: еще заниматнльный момент если память последовательно заполнять нолями и не нулями то можно добиться разных резултатов, т.к. процессор для нулей использует агресивные оптимизации. То есть если сначала заполнить участок нулями, а потом данными и так идти пачками, то получиться быстрее чем если просто заполнять данными.
eimrine
А насколько большая задержка от конвертации данных в код? Я слышал что архитектура современного компьютера не является на 100% фон-Нейманновской, особенно если в предмете исследования имеет место быть многоядерность. Тот же L1 до сих пор разделён как принято в Гарвардской архитектуре.
И ещё интересно, будет ли дополнительное проседание производительности если в массив p перед прогоном теста положить не просто адреса следующих ячеек (возможно, процессор может в какой-то мере это предсказать), а чтобы эти ячейки ещё и рандомизировать для полного исключения последовательного доступа.