Rust - Pourquoi une telle différence dans l'utilisation de la mémoire entre malloc/alloc et des approches plus "idiomatiques" ?

Question

J'ai utilisé et modifié cette bibliothèque https://github.com/sile/patricia_tree

Une chose qui m'a un peu dérangé est la quantité d'insécurité utilisée dans node.rs, en particulier, il est défini comme un simple pointeur vers un emplacement du tas. En faisant le premier benchmark listé sur la page readme (entrées wikipedia), le PatriciaSet utilise ~700mb (le PatriciaSet contient juste un Node à sa racine).

pub struct Node<V> {
    // layout:
    // all these fields accessed with ptr.offset
    //   - flags: u8
    //   - label_len: u8
    //   - label: [u8; label_len]
    //   - value: Option<V>
    //   - child: Option<Node<V>>
    //   - sibling: Option<Node<V>>
    ptr: *mut u8,
    _value: PhantomData<V>,
}

et utilise malloc pour l'attribution :

        let ptr = unsafe { libc::malloc(block_size) } as *mut u8;

On m'a dit que cette mémoire n'est pas alignée correctement, alors j'ai essayé d'ajouter la nouvelle api d'allocation et d'utiliser Layout/alloc, ce qui n'est toujours pas aligné correctement, mais semble juste "fonctionner". full pr

       let layout = Layout::array::<u8>(block_size).expect("Failed to get layout");
       let ptr = unsafe { alloc::alloc(layout) as *mut u8 };

Ce changement unique, qui détient également le layout dans le bloc de mémoire pointé par ptr a fait augmenter la consommation de mémoire de 40 % lors des tests de performance pour les très grands arbres. Le type de mise en page n'a que 2 mots de large, c'était donc inattendu. Pour les mêmes tests, la consommation est plus proche de ~1000mb (par rapport aux 700 précédents).

Dans une autre tentative, j'ai essayé d'enlever la plupart de l'insécurité et d'aller avec quelque chose d'un peu plus rouillé. pr complet ici

pub struct Node<V> {
    value: Option<V>,
    child: Option<*mut Node<V>>,
    sibling: Option<*mut Node<V>>,
    label: SmallVec<[u8; 10]>,
    _value: PhantomData<V>,
}

créer le nœud d'une manière que l'on peut attendre de rust

        let child = child.map(|c| Box::into_raw(Box::new(c)));
        let sibling = sibling.map(|c| Box::into_raw(Box::new(c)));
        Node {
            value,
            child,
            sibling,
            label: SmallVec::from_slice(label),
            _value: PhantomData,
        }

En termes de performances, elle est à peu près équivalente à la bibliothèque originale non modifiée, mais sa consommation de mémoire ne semble pas être beaucoup plus élevée que l'insertion de chaque élément dans un HashSet, utilisant environ ~1700mb pour le premier benchmark.

La structure de données finale qui utilise le nœud est un trie compressé ou un "arbre de Patricia". Aucun autre code n'a été modifié, à l'exception de la structure de l'objet Node et les implémentations de certaines de ses méthodes qui découlent idiomatiquement de ces changements.

J'espérais que quelqu'un pourrait m'indiquer ce qui cause exactement une différence aussi radicale dans la consommation de mémoire entre ces implémentations. Dans mon esprit, elles devraient être à peu près équivalentes. Elles allouent toutes environ le même nombre de champs avec à peu près les mêmes largeurs. La première, non sécurisée, est capable de stocker une longueur d'étiquette dynamique en ligne, ce qui pourrait être une raison. Mais smallvec devrait être capable de faire quelque chose de similaire avec des tailles d'étiquettes plus petites (utiliser uniquement Vec était encore pire).

Je cherche des suggestions ou de l'aide pour expliquer pourquoi les résultats finaux sont si différents. Si vous êtes curieux, le code pour exécuter ces tests est aquí bien qu'il soit réparti entre les auteurs originaux et mon propre dépôt.

Les outils permettant d'étudier les différences entre les deux sont également les bienvenus !

Answer 1

Vous constatez une utilisation accrue de la mémoire pour plusieurs raisons. Je vais supposer un système Unix 64 bits standard.

Tout d'abord, un pointeur fait 8 octets. Une adresse Option<*mut Node<V>> est de 16 octets car les pointeurs ne sont pas soumis à l'optimisation de la nullité qui se produit avec les références. Les références ne peuvent jamais être nulles, donc le compilateur peut convertir une référence Option<&'a V> en un pointeur nul si la valeur est None et un pointeur ordinaire si c'est Some mais les pointeurs peuvent être nuls, donc cela ne peut pas arriver ici. Rust fait en sorte que la taille du champ de l'enum soit la même que la taille du type de données, donc vous utilisez 16 octets par pointeur ici.

La manière la plus simple et la plus sûre de traiter ce problème est d'utiliser Option<NonNull<Node<V>>> . En faisant cela, votre structure est réduite de 16 octets au total.

Deuxièmement, votre SmallVec a une taille de 32 octets. Ils évitent d'avoir besoin d'une allocation au tas dans certains cas, mais ils ne sont pas, malgré leur nom, nécessairement petits. Vous pouvez utiliser un Vec ou une tranche en boîte, qui probablement permettent de réduire l'utilisation de la mémoire au prix d'une allocation supplémentaire.

Avec ces changements et en utilisant un Vec votre structure aura une taille de 48 octets. Avec une tranche encadrée, elle sera de 40. L'original en utilisait 72. L'économie réalisée dépendra de la taille de vos étiquettes, car vous devrez leur allouer de l'espace.

L'alignement requis pour cette structure est de 8 octets car le plus grand alignement de tout type (le pointeur) est de 8 octets. Même sur des architectures comme x86-64 où l'alignement n'est pas requis pour tous les types, il est toujours plus rapide, et parfois de manière significative, de sorte que le compilateur le fait toujours.

Le code original n'était pas du tout aligné correctement et soit échouera (sur SPARC), soit aura de mauvaises performances (sur PowerPC), soit nécessitera un piège d'alignement dans le noyau s'il est activé (sur MIPS) ou échouera s'il ne l'est pas. Un piège d'alignement dans le noyau pour un accès non aligné a des performances terribles parce que vous devez faire un changement de contexte complet juste pour charger et décaler deux mots, donc la plupart des gens les désactivent.

La raison pour laquelle ce n'est pas correctement aligné est que Node contient un pointeur et il apparaît dans la structure à un décalage dont il n'est pas garanti qu'il soit un multiple de 8. S'il était réécrit de manière à ce que la valeur child y sibling en premier lieu, il serait alors correctement aligné à condition que la mémoire soit correctement alignée (ce qui n'est pas toujours le cas). malloc mais pas votre allocation Rust). Vous pourriez créer un Layout avec Layout::from_size_align(block_size, std::mem::align_of::<*mut Node>()) .

Ainsi, si le code original fonctionnait sur x86-64 et permettait d'économiser beaucoup de mémoire, ses performances étaient mauvaises et il n'était pas portable.

Le code que j'ai utilisé pour cet exemple est simplement le suivant, plus quelques connaissances sur la façon dont Rust gère les types nullables et des connaissances sur le C et l'allocation de mémoire :

extern crate smallvec;
use smallvec::SmallVec;
use std::marker::PhantomData;
use std::ptr::NonNull;

pub struct Node<V> {
    value: Option<V>,
    child: Option<NonNull<Node<V>>>,
    sibling: Option<NonNull<Node<V>>>,
    label: Vec<u8>,
    _value: PhantomData<V>,
}

fn main() {
    println!("size: {}", std::mem::size_of::<Node<()>>());
}