Structures de données inconsistantes et langages dynamiques - efficace?

Question

J'ai lu récemment sur les structures de données inconsistantes du cache comme les tas de tampon auxiliaires. Ces structures de données fonctionnent en conservant leurs éléments les plus récemment accédés dans la mémoire cache afin que tout accès ultérieur soit également plus rapide.

La plupart de ces structures de données sont implémentées avec un langage de bas niveau comme C/C++. Cela vaut-il la peine d'essayer de porter ces structures de données sur un langage dynamique tel que Python, ou est-ce que le temps de fonctionnement sur une machine virtuelle ruine tous les avantages de performance de ces structures de données? Il semble que ce soit le dernier, mais j'ai pensé que je demanderais de voir si quelqu'un a réellement une certaine expérience avec cela.

Answer 1

En C (ou C++), vous disposez d'un contrôle précis de la taille exacte de chaque structure de données. Vous avez également la possibilité d'un contrôle précis de l'allocation de stockage. Vous pouvez, après tout, étendre la méthode new, utiliser malloc directement et sinon structurer la mémoire pour créer une localité spatiale.

Dans la plupart des langages dynamiques (comme Python), vous n'avez aucun contrôle sur la taille exacte de quoi que ce soit, et encore moins sur son emplacement.

En Python, vous pouvez avoir une certaine localité temporelle, mais vous avez peu ou pas de localité spatiale.

La localisation temporelle pourrait être améliorée par la simple mémorisation des résultats. C'est une accélération si courante que les gens incluent souvent un décorateur de mémoisation pour découpler la mémoisation (localité temporelle) de l'algorithme de base.

Je ne pense pas que les implémentations inconscientes en cache C ou C++ traduisent en langages dynamiques car je ne pense pas que vous ayez assez de contrôle. Au lieu de cela, il suffit d'exploiter la mémo pour les accélérations.

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

Answer 2

L'un des principaux points d'algorithmes inconscients du cache est que la taille de l'objet ne compte pas vraiment (parce que vous ne connaissez pas la taille du prochain niveau de pagination de la mémoire de toute façon), de sorte que le l'incapacité de connaître la taille exacte n'est pas importante. À un certain point, la taille de plus d'un objet «correspond» à la taille du bloc de mémoire suivant. (Remarque: ne pas connaître la taille de l'objet est un problème important pour les implémentations prenant en charge le cache).

De plus, la plupart des allocateurs de mémoire VM seront alloués à la fin d'un espace de génération, aussi longtemps que vous allouez tous vos objets en même temps, vous pouvez commencer par OK. Malheureusement, certains algorithmes inconsistants du cache supposent que vous pouvez modifier la disposition de la mémoire, ce qui est généralement impossible avec une machine virtuelle.

Un autre gros problème est que la plupart des implémentations basées sur VM utilisent des références pour les objets. Donc, un objet avec trois chaînes est en réalité 4 objets (l'objet lui-même, et 3 objets string). À moins que ces quatre objets ne soient alloués les uns à côté des autres, l'analyse de l'algorithme se décompose. Ajouter dans le compactage garbage collector et d'autres "optimisations" que les machines virtuelles sont libres de faire et vous avez un écart important entre le contrôle dont vous avez besoin et l'état actuel de la recherche sur ces algorithmes.