Tableau d'octets mutables efficace en Lua natif

J'essaie de réaliser une implémentation efficace d'un décodeur LZ77 en langage Lua natif (c'est-à-dire sans bibliothèque C et sans dépendance aux bibliothèques Lua non-core) - voir liblzg.Tableau d'octets mutables efficace en Lua natif

Pour charger et analyser le fichier binaire, une chaîne Lua fonctionne parfaitement et avec de bonnes performances (par exemple, en utilisant la méthode s: byte (k)). Cependant, pour créer les données de sortie décodées, les chaînes ne sont pas très optimales, puisqu'elles sont immuables, et la concaténation de chaînes prend beaucoup de temps lorsque la sortie devient grande.

Le décodeur doit être capable de:

Append un octet à la sortie à la fois (jusqu'à des millions de fois)
Lire (plus ou moins accès aléatoire) de la mémoire tampon de sortie

Quelles sont les meilleures options? La taille des données de sortie est connue avant la main, de sorte qu'il peut être pré-alloué.

Source

2010-11-24 marcus256

Par curiosité, pourquoi ne peut-on utiliser la bibliothèque C? Est-ce un exercice éducatif ou nécessaire dans un environnement Lua sandboxed? –

C'est plus un exercice éducatif (je veux voir la performance, et comment les techniques diffèrent entre un langage compilé de bas niveau et un environnement de script géré). En outre, j'imagine que la mise en œuvre pure de Lua rendrait le déploiement plus facile. – marcus256

Question parfaite. Btw je ne suis pas l'unique qui a eu la même idée – Hydro

Sons comme un travail parfait pour table.concat votre sortie est juste une table d'octets.

Lorsque vous avez besoin de copier, vous le faites comme vous le feriez normalement pour une table. par exemple:

for i=#output-5,9 do output[#output+1]=output[i] end

Quand vous avez finalement terminé avec le flux de sortie, le convertir en une chaîne avec str=table.concat(output)

Source

2010-11-24 18:52:55 daurnimator

Quelle est la pénalité de performance d'une grande table? Je suppose que c'est en fait une table de nombres (c'est-à-dire double), donc juste la valeur serait de 8: 1 en taille, et puis il y a l'overhead d'index de table. - Je vais le tester. Aussi, aurais-je quelque chose à gagner de pré-allouer la table de sortie (puisque la taille est connue)? – marcus256

Par curiosité: Quelle est l'utilité de table.concat? Dis, j'ai 1 000 000 éléments de table - serait-il utile de faire une sorte de concaténation récursive (1 + 1, 1 + 1, 1 + 1, ....100 + 100, 100 + 100, etc) de sorte que vous ne finissez pas en faisant 999,997 + 1, 999,998 + 1 etc? – marcus256

ŒUVRES! (vitesse: 3 Mo/s, par rapport à 300 Mo/s pour la version C, OK) J'ai également obtenu une augmentation de la vitesse en gardant la trace de la longueur de sortie dans une variable séparée au lieu de #output (opération coûteuse pour les tables). Je ne suis pas sûr de la consommation de la mémoire, mais je le considère: problème résolu. – marcus256

Évitez la concaténation de chaînes: enregistrez les chaînes de sortie dans une table et enregistrez toutes les chaînes à la fin. Si vous craignez que la table devienne trop grande, rincez-la périodiquement. Voir http://www.lua.org/pil/11.6.html

Source

2010-11-24 10:58:37 lhf

Hé, tu m'as battu dessus. Upvoted vous à la place. – Zecc

Malheureusement, cela ne résout pas le problème de l'accès aléatoire au tampon. Une opération qui doit être supportée est (par exemple): "ramener 9 octets à partir de 5 octets dans le tampon de sortie et l'ajouter au tampon de sortie" (oui, la copie peut se chevaucher!). – marcus256

@ marcus256 L'approche proposée par @lhf fonctionnerait toujours dans ce cas. Vous avez juste besoin de corriger certaines fonctions pour faire abstraction de ces opérations sur une table de chaînes. Peut-être devriez-vous «vider» la table en une seule chaîne à chaque fois qu'une lecture/écriture superposée doit se produire, ou est-ce que cela tue encore votre performance? –

Tableau d'octets mutables efficace en Lua natif

Répondre

Questions connexes