Linked Array

Et voilà, la recherche documentaire, c'est souvent comme ça : on recherche une chose, et on finit par en trouver une autre.

A l'issue d'un cheminement dont je n'essaierai même pas de décrire les méandres, je suis tombé sur un objet qui m'a souvent intrigué sur HP48, le Linked Array.
Il s'agit d'un type d'objet relativement rare, produit par certaines librairies "haut de gamme" (entendez par là que le programmeur est d'un bon niveau). D'où la question : à quoi peuvent bien servir ces Linked Array ?

La réponse est tombée 15 ans plus tard. Il s'agit tout simplement d'un type de tableau, qui entrepose les données "en brut" dans des cases de taille fixe, en attaquant directement les bits par quartet (ou "nibbles" comme disent les anglais).
Bref, apparemment rien de bien révolutionnaire.

Apparemment oui. Mais c'était avant de tomber sur les bibliothèques de Gadiel Seroussi (docteur es Mathématiques le m'sieur) qui permettent une utilisation très simple de ces données. Les avantages présentés sont simples : la taille de toutes les données dans la Linked Array est très réduite par rapport à une collection d'objets de même contenu (principalement des chiffres entiers), et surtout la manipulation de ces valeurs est très rapide.

Voilà des arguments qui me parlent. D'autant plus que Phantasie Conquest se prête excessivement bien à ce type de données.

En fait, à l'origine, les mondes étaient découpés en sous-répertoires, contenant chacun une tripotée de données, individuellement stockées et appelées par leur petit nom; c'était nettement plus facile, notamment pour programmer en UserRPL, et bien suivre ce qu'il se passe.
Toutefois, ces données prenaient énormément de place. Un monde "de base", de 24 villes, commençait à 12Ko minimum, pour évoluer vers 15Ko. C'est peu pour un PC d'aujourd'hui, mais à l'époque, cela représentait une grande quantité comparé aux possibilités de la calculatrices.

Pour résoudre ce problème, j'ai donc créé à cette époque un système de registres "custom", fait à la main, avec des données stockées dans des entiers binaires. Chaque registre fait 8 octets, soit 64 bits. C'est pas mal, on peut stocker plusieurs données par registre. Donc on créé des "maps", pour affecter un espace précis à chaque variable du registre. C'est précis au bit prêt, parce qu'il n'y a pas tant d'espace que ça.

Les résultats ont été spectaculaires. La taille des mondes a été divisée par plus de 3 (pour reprendre l'exemple ci-dessus, un monde de 24 villes tombe à moins de 3 Ko pour les villes, toutefois évoluant vers 5Ko pour les autres données), ce qui permettait d'envisager des mondes plus grands, ou encore plus de mondes sur la calculatrice.
Un véritable progrès, de quoi se trouver très fier . Car de plus, grâce à une bonne virtualisation de l'accès aux données, ce changement de structure est resté relativement indolore pour l'essentiel du code, qui commençait déjà à être gros, donc difficile à débugguer (oui, à l'époque, pas de PC, donc pas d'éditeur, donc tout sur la calculatrice, vous pouvez imaginer la galère avec un code de plusieurs milliers de lignes...)

C'était un bon début. Toutefois, on peut aussi noter quelques inconvénients.
Tout d'abord, le mapping est contraignant. L'espace est attribué de façon relativement juste, au bit prêt, et généralement il n'y a pas de rab. Lorsque des données ont besoin de grossir, ce n'est souvent pas possible. Pour contourner le problème, je donne souvent un ou deux bits d'avance, mais ceux-cis sont rapidement avalés, et le jeux s'en trouve mécaniquement limité.
Le mapping a un autre inconvénient, c'est la performance. En effet, comme on est au bit prêt, et que la découpe est différente pour chaque registre, il n'est pas possible d'extraire aisément. Cela prend de nombreuses et coûteuses étapes.
D'une part il faut charger la map. Soit elle est inscrite en dur dans une procédure dédiée pour une variable, soit elle est chargée à partir d'une liste complète, générique, qui par référence permet de ressortir le bon couple Registre/Offset pour chaque variable.
C'est déjà beaucoup moins lisible. Vous pouvez pas imaginer le temps que ça m'a pris, des années plus tard, pour reconstituer la map sans doc.
Ensuite, il faut shifter. Et là pas de bol, pas d'appel simple du style "shift le binaire de n bits". Non, il faut diviser par un nombre réel (la représentation en hexa étant impossible en dessous de 20bits sur mon compilateur). Galère (en décimal, le mapping est plus dur à lire) et perte de performances.
J'en suis arrivé au point que je ne traitais plus que les Delta, et pas les valeurs elle-même, afin de conserver des performances raisonnables.

Enfin, bien que ce mécanisme soit très performant, on peut noter un regret : il y a encore de la marge.
64 bits, exploités ras-la-gueule, à leur maximum, ce n'est jamais que 8 octets. Oui, mais un entier binaire, c'est 13 octets sur HP48. Une fois sauvegardé avec un nom de variable même très court (2 lettres), c'est déjà 20 octets. Soit un rendement de 40%

Voilà donc les problèmes : performance, limitation et complexité en tout premier lieu, efficacité en second lieu.

Pour la complexité, le Linked Array va apporter peu mais ce sera sensible : plus besoin de charger une map cryptique avec une allocation au bit prêt ! Une simple référence sur une case, et ca suffit.

A priori, on y perd en stockage me diriez-vous ? et bien pas vraiment.
L'avantage, c'est que Toutes les variables sont dans la Linked Array, et non pas par paquet de 8 octets qui en font 20 au final.
De fait, sur l'ensemble des données, on y gagne. Ainsi, une ville actuelle coûte 100 octets en registre, elle n'en coûtera plus que 70 en Linked Array.

Et ceci se fait tout en ajoutant de très confortables marges de manoeuvre. Fini l'allocation au bit prêt qui ne permet plus d'évoluer ensuite. Les frontières explosent, les possibilités d'évolution sont retrouvées !

Mais la vrai plus value, se seront sans doute les performances, à priori d'un tout autre ordre de grandeur, ce qui se comprend compte tenu du mécanisme trivial.
De plus, il devient possible, si ce n'est carrément évident, d'agir sur la donnée elle-même
et non plus seulement en delta.
Je ferai un benchmark pour bien comparer.

Reste le problème de la virtualisation. En effet, pour ne pas casser le code, il faudra veiller à conserver au maximum les interfaces actuelles. Et c'est là, en fait que se situeront les pertes de performance.
En effet, une procédure = un nom global = une recherche, dans un répertoire particulièrement chargé.

La bonne nouvelle, c'est que le Linked Array va permettre de bien diminuer le nombre de variables, puisqu'elles seront regroupées dans une seule table. En revanche, les procédures elles même coûteront du temps, voire seront plus nombreuses.

Voilà qui pourra probablement être solutionné par le passage en Librairie, une évolution bien au delà de mes connaissances actuelles. De ce que j'en comprends, lors de la compilation de librairie, les liens entre les appels de procédure sont mappés "en dur", via une table, et non plus soumis à une recherche à chaque appel, ce qui doit sauver un temps monstrueux pour Phantasie Conquest, qui compte plus de 200 programmes.

Au delà de mes compétences, certes, mais qui sait, tout change ...