Вопросы по небезопасному rustу

Тех.вопросы
1

День добрый, господа.
Смотрю вот код linked-hash-map и возникло пару вопросов.

В кратце - там двусвязный список элементы которого имеют структуру:

struct Node<K, V> {
    next: *mut Node<K, V>,
    prev: *mut Node<K, V>,
    key: K,
    value: V,
}

И автор библиотеки переиспользует эти структуры. То есть при удалении он освобождает память key, возвращает value, а сам узел сохраняет в списке free чтобы потом его переиспользовать.

// add to free list
(*node).next = self.free;
self.free = node;
// drop the key and return the value
drop(ptr::read(&(*node).key));
ptr::read(&(*node).value)

Вот так он переиспользует узлы.

let free = self.free;
ptr::write(free, Node::new(k, v));
free

  1. Вопрос номер один больше риторический, знаю такую технику переиспользования практикуют в языках с GC, что бы снизить нагрузку на него и на перераспределение памяти, насколько это актуально для rust и языков без GC? (вообще мне такой подход немного претил и в языках с GC всегда возникала мысль - а на кой тогда вообще этот GC, если, фактически, часть работ приходится делать за него ибо если это не делать за него всё будет в 2 раза медленнее)

  2. Второй вопрос технический, насколько корректно автор библиотеки это делает:
    drop я так понимаю полностью освобождает память;
    ptr::write делает mov перемещает управление памятью во вновь созданную переменную типа T;
    далее он переиспользует узел, фактически он создаёт новый узел в куче и перезаписывает его в адрес старого узла.

Разве это вообще повышает производительность, ведь он фактически, всё одно, создаёт новый узел а не переиспользует старый, мало того он после его создания перезаписывает его в адреc старого узла?

Корректно ли это по памяти, когда он перезаписывает всю структуру ноды значение поля value, которое он вычитал и вернул из функции, может же ещё использоваться в программе и не быть освобождено к моменту перезаписи всей структуры?

2

… насколько это актуально для rust и языков без GC?

Разве это вообще повышает производительность, ведь он фактически, всё одно, создаёт новый узел а не переиспользует старый, мало того он после его создания перезаписывает его в адреc старого узла?

Вполне себе актуально, насколько я представляю: выделение нового блока памяти это очень дорогая операция в среднем.

3 
ptr::write(free, Node::new(k, v));

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

Вроде бы тут все в порядке. Он вернул копию поля value, а при перезаписи через ptr::write не вызывается drop для старого значения. Даже если value содержит какие-то указатели на объекты, которые должны быть освобождены, для них drop будет вызван когда копия value которую мы вернули выйдет из области видимости.

4

Выделение памяти в языках с GC дешевле, чем без него, потому что в языках с GC аллокация памяти это просто инкремент указателя, потому что память всегда выровнена и дефрагментирована. Поиск по списку блока блока подходящего размера намного тяжелее.

MaybeUninit ?

5

Действительно Node::new(k, v) создается на стеке.

Но с чего вы взяли что он вернул копию поля value?
вот небольшой пример

6

В вашем примере ptr::read вызывается после того как вы изменили значение x. Так все работает:

    let mut x = 12;
    let y = &x as *const i32;

    let ret = unsafe {std::ptr::read(y)};

    x = 13;
    assert_eq!(ret, 12);

@Pzixel Да. MaybeUninit как раз то что нужно. Но это совсем новая фишка, только найтли.

Хотя непонятно как его тут использовать. Все равно от копирования избавиться не удасться, просто оно будет происходить в другом месте - при вызове MaybeUninit::set(Node).

7

Выходит ptr::read создаёт value копию когда он возвращает value?
Но тогда что он освобождает drop(ptr::read(&(*node).key)); делает копию и удаляет копию ?

8

Тут дело в том, что если key не Copy то просто так его не удалить:

drop((*node).key);

Rust будет ругаться что не может переместить значение. В таких случаях обычно mem::replace() используют:

drop(mem::replace(&mut (*node).key, mem::uninitialized()));

По факту там результат тот же получается, только без затирания старого значения. Использовать “оставшийся” key после этого конечно нельзя.

Пример для конкретики - если тип ключа будет Box<usize>:

let tmp = ptr::read(&(*node).key);
drop(tmp);

После выполнения первой строчки у нас будет два бокса которые указывают на одно место в куче. После второй - это место в куче будет освобождено и первый бокс, который остался в (*node).key превратится в висячий указатель.

1 лайк