Les B-trees dans Factorio

 (razberry.substack.com)
4 points par GN⁺ 2023-11-17 | 1 commentaires | Partager sur WhatsApp
  • Après avoir lu le chapitre B-Tree du club de lecture Database Internals, l’auteur a implémenté la structure de données non pas en code, mais sous forme de structures d’usine dans Factorio, afin d’en vérifier visuellement les concepts
  • Un BST ne peut bifurquer à gauche ou à droite que lorsque les clés sont ordonnables ; si les valeurs se concentrent d’un seul côté, l’efficacité de recherche peut tomber au niveau d’une liste linéaire
  • Pour le stockage sur disque, le coût de rééquilibrage d’un BST et la lecture de plusieurs pages deviennent pénalisants ; un B-Tree réduit ce problème en stockant plusieurs clés dans un même nœud
  • L’implémentation dans Factorio représente les nœuds et les opérations de comparaison avec des coffres en bois et des bras filtrants violets, et définit un ordre de tri arbitraire des objets pour créer le chemin de recherche
  • La version B-Tree utilise 3 clés et 4 pointeurs par nœud, ce qui lui permet de contenir bien plus de clés qu’un BST en 2 niveaux, mais il reste des problèmes de représentation des valeurs et de tri manuel

Différences entre BST et B-Tree

  • Un arbre binaire de recherche (BST) stocke une clé par nœud, envoie les clés inférieures vers le nœud de gauche et les clés supérieures vers le nœud de droite
    • L’exemple commence avec la clé racine 8, 3 à gauche et 10 à droite
    • Il ne fonctionne qu’avec des valeurs ordonnables, dont on peut comparer l’ordre
  • Si beaucoup de valeurs sont ajoutées d’un seul côté, l’équilibre du BST se rompt
    • Dans le pire des cas, il devient presque équivalent à une liste triée linéaire, comme 8 -> 10 -> 14
    • On peut corriger le déséquilibre en plaçant 10 comme racine pivot, avec 8 et 14 de part et d’autre
  • Dans le stockage sur disque, un BST est désavantagé
    • Maintenir constamment le rééquilibrage oblige à mettre souvent à jour le disque et les pointeurs
    • Des nœuds voisins pouvant être stockés sur des pages différentes, une seule recherche peut nécessiter la lecture de plusieurs pages
  • Un B-Tree stocke plusieurs clés dans un même nœud et pointe vers ses nœuds enfants avec nombre de clés + 1 pointeurs
    • Dans l’exemple, le nœud [17 | 24] se divise en trois nœuds enfants : ceux dont les clés sont inférieures à 17, ceux dont les clés sont entre 17 et 24, et ceux dont les clés sont supérieures à 24

Arbre de recherche implémenté dans Factorio

  • Factorio est un jeu de construction d’usines, et cette implémentation représente chaque nœud de l’arbre par des structures du jeu
  • L’auteur commence par créer un BST simple
    • Chaque nœud possède un coffre en bois contenant une clé et deux chemins menant vers d’autres nœuds
    • Comme il n’existe pas de méthode de comparaison par défaut entre les matériaux, un critère de tri arbitraire est défini dans l’ordre wood, coal, stone, brick, copper, iron, steel
    • Les bras filtrants violets se chargent des tests de comparaison
      • Dans le premier nœud, un bras vérifie si l’objet est égal à brick
      • Un deuxième bras vérifie s’il est inférieur à brick, comme wood, coal, stone
      • Un troisième bras filtre les valeurs supérieures, comme copper, iron, steel
    • En haut à droite, un garbage collector retire aussi les objets arrivés par erreur sur le convoyeur
  • L’implémentation du B-Tree nécessite davantage de structures par nœud
    • Chaque nœud comporte 3 clés, 3 bras filtrants, 3 coffres en bois et 4 pointeurs vers des enfants
    • Elle peut stocker plus d’informations à profondeur égale
    • Sur 2 niveaux, le BST contient 2 clés, tandis que le B-Tree en contient 12
    • Sur 3 niveaux, le B-Tree monte jusqu’à 48 clés
  • Comme l’auteur ne voulait pas sélectionner et trier manuellement 48 objets dans Factorio, le B-Tree est laissé vide en attendant de trouver une meilleure façon de représenter les valeurs
  • Le BST et le B-Tree sont comparés côte à côte, avec une vidéo YouTube en complément

À lire aussi

1 commentaires

 
GN⁺ 2023-11-17
Commentaires sur Hacker News

  • La conception est inefficace, mais implémenter de la théorie de l’informatique dans Factorio implique aussi, par nature, de jouer d’une manière non optimale.
    Factorio n’est pas un jeu conçu pour frimer avec des B-Tree, et même ses outils sont au fond pensés pour jouer à Factorio.

    1. L’essentiel des arbres auto-équilibrés comme les arbres 2-3, les arbres rouge-noir ou les B-Tree, ce n’est pas la structure d’arbre en elle-même mais le fait qu’ils se rééquilibrent eux-mêmes ; or, dans Factorio, on ne peut pas faire en sorte qu’un arbre se reconfigure tout seul, donc on perd sa caractéristique la plus importante.
    2. Du point de vue de l’optimisation, les bras robotisés sont plus lents que les tapis. Même avec 4 bras par tapis, on ne déplace qu’environ 12 objets par seconde, alors qu’un tapis bleu peut en pousser 45 par seconde. Une conception optimale n’utilisant que des tapis devrait donc employer un répartiteur fonctionnant à 45 objets par seconde.
    3. Du coup, le point de rencontre entre les répartiteurs et l’informatique théorique dans Factorio, c’est le répartiteur de Factorio et le réseau de Benes. Pour étudier les réseaux faits uniquement de crossbars 2 entrées / 2 sorties, on peut commencer par https://en.wikipedia.org/wiki/Clos_network. Un réseau de Benes n’est qu’un réseau de Clos en 2 entrées / 2 sorties, et un réseau de Clos peut aussi avoir une taille arbitraire, comme 5 à 7.
      La méta intéressante à chercher dans Factorio semble être la conception de « tapis mixtes ».
    • Sous une forme plus concrète, il existe le sushi belt, où un même tapis transporte plusieurs matériaux de manière équilibrée tout en bouclant sur lui-même.
      Certaines conceptions se contentent d’accepter de nouveaux objets selon un ratio fixé, tandis que d’autres rétablissent réellement l’équilibre lorsqu’il est perturbé. Personnellement, c’est celle-ci que je préfère : https://www.youtube.com/watch?v=7Gt5Zx0bsOQ
      Cet exemple utilise la logique de circuit du jeu, mais il existe aussi une section sans circuits sur le forum Factorio : https://forums.factorio.com/viewforum.php?f=202
      Ce qui est amusant, c’est que l’objet « fish » de Factorio est une blague inutile ; comme il ne sert à rien, il est parfois utilisé comme valeur nulle, comme indicateur qu’un tapis a bouclé un tour complet, ou comme outil de débogage : https://forums.factorio.com/viewtopic.php?p=544302#p544302
    • Je me demande à quoi ressemblerait une extension Factorio comme « Scriptorio », qui permettrait de mettre du JSON sur des tapis roulants, avec en plus des usines de fonctions JavaScript ou Lua.
      On pourrait alors déplacer non seulement les objets à insérer et à rechercher, mais aussi le B-Tree lui-même au moyen de tapis roulants et de bras robotisés.
      On pourrait écrire une fonction de recherche récursive avec une boucle de tapis traversant l’usine, qui dépilerait l’arbre niveau par niveau jusqu’à atteindre une feuille, puis couperait la boucle pour sortir le résultat.
      C’est un modèle d’exécution intéressant, plus proche du flux de données que du JavaScript standard. Faut-il permettre à plusieurs tapis roulants, bras robotisés et usines différents de pointer vers le même objet JSON de base via plusieurs références, pour autoriser des « tunnels quantiques » ou de « l’action à distance » ? Ce pourrait être utile, mais Factorio traite traditionnellement chaque objet physique comme ayant une identité propre, donc ne pas prendre en charge plusieurs références serait peut-être plus « réaliste ». Ou bien on pourrait étudier la technologie « Quantum Tunneling JSON », puis n’autoriser les références multiples qu’au sein de la « JSON Reference Entangler Factory »
    • En survolant l’article sur les réseaux de Clos, je me suis dit que s’il était possible d’en construire dans Factorio, alors des architectures de réseaux neuronaux simples comme celle visible ici pourraient aussi l’être : [1]
      On pourrait sans doute aussi modifier la sortie en pondérant la densité des ressources arrivant à certains emplacements. D’après le mécanisme montré ici [2], on devrait pouvoir créer une prise de décision pondérée par densité à l’aide de fusions, de séparations et des trois vitesses de tapis
      [1] https://www.asimovinstitute.org/wp-content/uploads/2019/04/N...
      [2] https://wiki.factorio.com/Belt_transport_system#Splitters
    • La prochaine fois, j’aimerais voir s’il est possible d’implémenter aussi l’auto-équilibrage. Je pensais que les bots seraient utiles ici, mais je ne sais pas s’ils peuvent construire des plans dynamiquement.
    • C’est pour ça que je ne joue pas à Factorio. On peut consacrer ce niveau de ressources cérébrales à l’humanité, et en montrer le résultat pour obtenir des réactions sur les réseaux sociaux.
      Les jeux qui demandent du cerveau en échange de chiffres à l’écran sont tout en bas de ma liste. Moi, j’ai envie d’apprendre quelque chose de nouveau.
      Il peut bien y avoir un aspect puzzle, et on peut décider que c’est amusant, mais on peut aussi décider que l’étude est amusante, non ?

  • Beau travail.
    Je lis « Database Internals » dans un club de lecture, et cette semaine correspondait au chapitre 2, consacré aux B-Tree.
    À noter que les inscriptions sont closes, mais si ça vous intéresse, vous pouvez vous procurer Database Internals et suivre ici le programme et les notes en mode « lecture seule » : https://eatonphil.com/2023-database-internals.html

  • Les raisons pour lesquelles « les arbres de recherche binaires ne sont pas adaptés au stockage sur disque » s’appliquent aussi au stockage en mémoire
    Rechercher dans un seul nœud de B-Tree est plus rapide que de suivre la même quantité de pointeurs dans un arbre binaire. Bien sûr, cela augmente la complexité de l’implémentation, mais sauf si on code en C, on n’implémente généralement pas soi-même une map basée sur un arbre
    Il est aussi possible d’avoir une variante où les nœuds internes contiennent davantage d’entrées et où les valeurs ne sont stockées que dans les feuilles. À moins de construire un ensemble plutôt qu’une map. Si on relie aussi les nœuds voisins, on se rapproche en fait d’une skip list

  • Je ne sais pas pourquoi il a fallu qu’un contenu Factorio tombe ici et me donne encore envie d’y reperdre une centaine d’heures. Il y a déjà bien trop de bons jeux à faire cette année

    • Une grosse refonte et l’extension Space Age sont prévues vers la fin de l’année prochaine, donc attendre jusque-là peut aussi être une bonne option

  • On peut tout faire avec des répartiteurs, et il ne devrait pas y avoir besoin de coffres ni de bras d’insertion filtrants. L’explication est bonne

    • Je ne vois pas comment
      Le but n’est pas simplement de répartir la sortie sur plusieurs lignes. Les coffres représentent ici les objets stockés dans le « nœud » correspondant de ce B-Tree disposé en 2D
      Je n’ai pas eu le temps de regarder la vidéo, mais d’après le texte et les captures d’écran, une logique est attachée aux bras d’insertion pour envoyer les objets vers le bon chemin de nœud enfant, de façon à préserver la propriété « triée » de l’arbre
      Vu le choix des valeurs de clé dans le post d’origine, ce serait peut-être possible aussi avec des répartiteurs, mais de mémoire un répartiteur ne peut avoir qu’un seul filtre, donc il en faudrait plusieurs à chaque point de bifurcation. Autrement dit, autant que d’objets à ce point de bifurcation. Les bras d’insertion filtrants acceptent plusieurs filtres, donc ici c’est plutôt mieux, comme on peut aussi le voir sur la première capture d’écran
      Bien sûr, on pourrait abandonner complètement la conception en B-Tree et trier vers n coffres avec n répartiteurs, mais ce serait moins amusant et probablement pas ce que l’auteur du post voulait faire
    • Chaque bras d’insertion se voit attribuer plusieurs objets
      Le filtre d’un répartiteur n’envoie qu’un seul type d’objet d’un côté et tout le reste de l’autre. Mais dans cet exemple, plusieurs types vont d’un côté et plusieurs autres de l’autre, donc ce n’est pas la même chose
    • Il faut trier et filtrer plusieurs objets. Par exemple, dans le premier nœud, le bois, le charbon et la pierre doivent aller à gauche, tandis que le métal doit aller à droite, mais un filtre de répartiteur ne peut filtrer qu’un seul objet

  • Je me demande si Factorio est vraiment si bon que ça. Tout le monde en dit du bien, mais le thème de la construction d’usine a l’air un peu ennuyeux, et j’ai peur que le jeu soit trop répétitif

    • Avant d’essayer, j’étais moi aussi assez sceptique et j’avais les mêmes craintes. Et puis je me suis retrouvé à y passer plus de 100 heures
    • Tous les joueurs de Factorio que je connais y ont consacré plus de 1 000 heures

  • C’est vraiment cool, mais entre gens qui essaient d’écrire, je trouve assez distrayant de ne pas mettre de majuscule au début des phrases

  • Je pensais que ce serait implémenté avec le système de circuits de Factorio