Оптимизация итератора, выполненная компилятором Rust
Я пытаюсь понять, как ржавчина осуществляет оптимизацию с помощью итераторов. Рассмотрим следующий код
let v: Vec<T> = vec![...]
let v2: Vec<P> = v.into_iter().map(|x| x.transform()).collect();
где transform() поглощает self и возвращает другую структуру P. То есть сигнатура функции выглядит так
impl T {
fn transform(self) -> P {...}
}
Если T и P имеют одинаковый размер, сможет ли компилятор оптимизировать код, чтобы не выделять еще один вектор в памяти и создавать карту на месте? Во время создания карты половина вектора будет иметь один тип, а другая — другой, но структура кода не позволяет пользователю получить доступ к вектору в сломанном состоянии между ними.
Если эта оптимизация не выполнена, есть ли способ сделать это с помощью небезопасного кода? Я бы iter_mut с transmute работал? например
v.iter_mut().for_each(|x| {
let p: *mut T = x;
unsafe {
let x = ptr::read(p);
let y = x.transform();
ptr::write(p, transmute::<P, T>(y));
}
});
let v = unsafe {transmute::<Vec<T>, Vec<P>>(v)};
Наконец, было бы здорово, если бы вы рассказали мне, какой метод вы использовали для исследования оптимизации. Я новичок в программировании низкого уровня, поэтому буду очень признателен за любые указания в общем направлении.
А что касается вашей ручной реализации, я не знаю, правильно ли трансмутировать Vec<T> в Vec<P>. Я думаю, вам следует пройти через Vec::into_raw_parts, привести указатель, а затем через Vec::from_raw_parts.
Также обратите внимание, что T и P иметь одинаковый размер недостаточно, и для этого преобразования они должны иметь одинаковое выравнивание, чтобы иметь смысл.
Ах, ок, я упустил из виду проблему выравнивания. Спасибо что подметил это.
Ответы 1
Да, так и есть.
Хорошо, технически компилятор этого не сделает. Но в стандартной библиотеке для этого есть специализация.
Документы даже говорят, что Век мог это сделать .
Vec может использовать любую из следующих стратегий или ни одну из них, в зависимости от предоставленного итератора:
...
- выполнить итерацию на месте исходного выделения, поддерживающего итератор
На практике в настоящее время это так.
pub fn foo(data: Vec<u32>) -> Vec<i32> {
data.into_iter().map(|v| v as i32).collect()
}
Это компилируется в следующую сборку:
example::foo::h155d07d1e93916ee:
mov rax, rdi
movabs rcx, 4611686018427387903
and rcx, qword ptr [rsi + 16]
movups xmm0, xmmword ptr [rsi]
movups xmmword ptr [rdi], xmm0
mov qword ptr [rdi + 16], rcx
ret
То есть только перемещать вектор. Даже петли нет.
Итерация на месте работает только если:
- Выравнивание типа источника и назначения одинаковое.
- Используемые адаптеры итераторов взяты из std (поскольку только они реализуют необходимые свойства).
- Исходная коллекция поддерживает итерацию на месте (только
VecиBinaryHeap). - Если у вас есть
flatten(),flat_map()илиarray_chunks()в процессе разработки, значит, происходит какой-то сложный расчет.
Реализация здесь.
Если вам нужна гарантия, не трансмутируйте Vec, это неразумно. Вместо этого используйте Vec::from_raw_parts().
Спасибо за отличный ответ. Могу я спросить, почему трансмутировать Веков нецелесообразно?
@DE0CH Потому что расположение Vec не гарантировано.
Я не думаю, что это возможно. Подумайте, что произойдет, если
transformпаникует. Тогда стек разматывается и в какой-то момент вектор отбрасывается. Это, в свою очередь, приведет к удалению всех его элементов. Но некоторые из них уже будутP, но все равно будут вызываться с помощью реализацииTdrop. Это будет мгновенный UB.