gestion mémoire rebol
paullys19-Jan-2011/9:40:43+1:00
Je cherche de la doc, des infos sur la gestion de la mémoire par Rebol. Car j'obtiens des résultats assez inattendus: au dela de 80000 string dans un block, rebol rame.Mais gère sans problème plus de 100000 objets liés (objet pointant sur autre objet), une explication?
guest219-Jan-2011/11:47:39+1:00
En soi, un block de strings ne "rame" pas, c'est une structure de données. Ca prend plus ou moins de place en mémoire, c'est tout.

J'imagine que tu fais allusion aux opérations que tu exécutes sur ce bloc.
Là encore il faut être précis.
De quelles opérations parles-tu ?

(Rappel: Des exemples de code passent mieux que des explications approximatives)
paullys19-Jan-2011/13:20:54+1:00
J'ai pas dit que le block rame, mais rebol rame (sous entendu a du mal a digérer les opérations sur ces blocks en particulier mais aussi semble de plus en plus mal gérer la mémoire).
Il s'agit simplement d'opérations d'indexation et de tri.
j'ai testé block de blocks, blocks de string et b-tree.
Pas essayé les hash car l'ordre est important.

Je n'ai pas parlé des opérations car toutes les opérations sont affectées (vu qu'il s'agit visiblement de la gestion de la mémoire par rebol).

Enfin ce n'est pas un problème en soi puisque je contourne le pbm en utilisant des handles sur des fichiers. Mais ce pbm m'a conduit à cette question, une rapide recherche google ne m'a rien remonté d'intéressant, donc je me demandais si on disposait d'infos sur la gestion de la mémoire par Rebol.
Didec19-Jan-2011/13:45:46+1:00
Quand même, faudrait voir un exemple de code pour pouvoir en tirer des conclusions !
guest219-Jan-2011/14:38:56+1:00
Ouais bon ça se complique, tes propos font encore moins sens qu'avant.

Comme Didec l'a insinué, tu as probablement tiré des conclusions trop hâtivement, erreur courante chez des jeunes Padawans, une revue de code s'impose.

J'en appelle à la charte du reboleur écrite par Saint Carl en l'an de grâce 1515.
Elle m'autorise à ne pas argumenter davantage tant que du code n'aura pas été posté.
paullys19-Jan-2011/15:05:47+1:00
Je demande si vous avez des infos sur la gestion mémoire.
le code est un tri-fusion basique:
trifuse: func [a b /local c][
a: sort a   
b: sort b   
c: copy []

while [ all [a <> [] b <> [] ]][;print [a/1/1 b/1/1]
either a/1/1 > b/1/1 [append/only c b/1 remove b][
either a/1/1 = b/1/1 [
append/only c join a/1 copy next b/1
remove a remove b
][append/only c a/1 remove a] ]
]
if all [a = [] b <> []] [append c b]
if all [b = [] a <> []] [append c a]
return c
];
donc aucun intérêt à checker!!
paullys19-Jan-2011/15:13:17+1:00
PS: le sort n'est pas le sort rebol, d'où a: sort a
Didec19-Jan-2011/16:16:21+1:00
Bon on a le code, mais il faudrait un petit exemple de données aussi (pas les 80000 string!, mais un exemple de ce à quoi ça ressemble, qu'on pourra toujours générer en grand nombre par la suite pour les tests) !

De plus tu dis que le 'sort n'est pas celui de Rebol. Alors quel est son code ?

je rappelle, à toutes fins utiles, que le 'sort de Rebol accepte une fonction pour réaliser la comparaison de 2 éléments dans le cas de besoins de tri spécifiques.
DocKimbel19-Jan-2011/16:48:31+1:00
donc aucun intérêt à checker!!
...bien au contraire.

Si la taille des blocks (je suppose) a et/ou b est de 80k entrées, ce n'est pas étonnant que le code de ta fonction ne soit pas performant :

1) c: copy [] => il faut toujours préallouer les series quand on sait à l'avance que la quantité de valeurs à y stocker est importante ! Donc un 
c: make block! 80'000
devrait grandement aider.

2) Tu fais beaucoup d'opérations de suppression sur a et b, l'utilisation d'un type list! permet des ajouts/suppressions à temps contant (0(1)).

3) join a/1 copy next b/1 => si a/1 et b/1 sont des string!, le COPY semble de trop, il crée un string! intermédiaire et consomme de la mémoire inutilement.

4) Si la série résultat c n'est utilisée que pour des recherches, elle peut être converti en hash! (to-hash) afin de bénéficier de recherches en 0(1). Le type hash! préserve l'ordre des valeurs stockées et est navigable comme un block!.

Si tu appliques ces optimisations, ton code devrait, a priori, moins souffrir de problèmes de lenteur.


Attention, REBOL est un langage de script interprété, il n'est pas efficace pour traiter de grandes quantitées de données, sauf s'il est possible d'optimiser son code manuellement pour tirer partie des types natifs (ex: hash!, list!) ou des fonctions natives (ex: parse).


Concernant la gestion mémoire, elle n'est pas documentée, RT n'a jamais révélé les détails du modèle mémoire utilisé, ni les algos du GC. On ne peut faire que des hypothèses (mais qui ont de grandes chances d'être les bonnes):

- les block! et dérivés utilisent des cellules contigues de 16 octets pour stocker directement les valeurs scalaires (integer!, decimal!, char!, tuple!, ...) ou un pointeur pour les series et types complexes (object! et dérivés, function!,...) vers un autre block! stockant les sous-éléments.

- en conséquence, les types scalaires sont toujours passés "par valeur" en argument des fonctions, les types séries et complexes, toujours "par référence" (d'où l'intérêt du COPY).

- la réservation mémoire se ferait suivant le modèle de "binning" qui structure la mémoire disponible en listes de zones de tailles croissantes (listes de zones de 16 octets, de 32, de 64, ...). Le modèle mémoire utilise sans doute une variante du Doug Lea Allocator (décrit entre autres ici: http://www.eecs.harvard.edu/~mdw/course/cs61/mediawiki/images/5/51/Malloc3.pdf).

- le GC serait de type "mark & sweep" classique, "stop the world", sans déplacement de blocs libérés/gardés (contrairement à un GC générationnel par ex.).

REBOL est optimisé pour faire des allocations mémoires rapides et des phases de GC rapides (même si elles sont bloquantes). En revanche, la consommation mémoire globale reste importante (comparée à d'autres langages) et la libération des blocks mémoires vers l'OS n'est pas très efficace. REBOL reste néanmoins très stable dans le temps, niveau usage mémoire (sauf bug interne du GC), j'ai des serveurs Cheyenne qui tournent et sont utilisés en production depuis 1 an sans interruption, avec une consommation mémoire qui n'a quasiment pas bougé.
guest219-Jan-2011/16:53:23+1:00
Ton implémentation de la fonction tri-fusion (communément appelée merge-sort) est une catastrophe.
Ca ne m'étonne pas que tu ais de perfs lamentables.

Tu as raison, inutile de checker la suite...
guest219-Jan-2011/17:02:25+1:00
Doc, les suppressions 'remove ne servent à rien dans cette fonction sauf à ralentir le processus ed tri (donc convertir le type en list! est inutile).
Je crois qu'il a essayé d'adapter un algo récursif en itératif mais s'est complèment planté.
coccinelle19-Jan-2011/17:10:01+1:00
Je ne sais pas comment Rebol gère la mémoire et mon niveau ne me permet pas de faire des hypothèses comme le Dock mais si je devais écrire ta fonction en Rebol, ça donnerais ça :
trifuse: func [a b][unique sort join a b]


Marco.
guest219-Jan-2011/17:23:43+1:00
Bon rien à voir avec le tri-fusion ou merge-sort, le nom m'a perturbé.
Néammoins les remove ne servent à rien, Paully ne s'en sert que pour incrémenter artificiellement la position des blocks a et b.
paullys19-Jan-2011/17:33:10+1:00
Merci pour les commentaires du code, mais il s'agit pour l'instant d'un code de test de différentes hypothèses sur l'implémentation d'une base de données.
A priori je n'ai pas fixé de limite de taille des données a exploiter mais j'ai remarqué qu'au dela de 80000 ca commence a ramer. Donc comme je veux rester dans une "zone" d'aisance de rebol je vais donc surement limiter aux alentours de 20000, la taille de la brique primaire.
Après seulement je pourrais réfléchir à l'optimisation du code et encore si rebol est choisi pour le langage de prog final.
Car j'utilise Rebol comme langage de prototypage.
D'ailleurs je trouve que l'on ne souligne pas assez cet aspect de Rebol.
Niveau prototypage et montage rapide de démos; J'ai rien vu de mieux que Rebol.

Pour cette même raison de tests préliminaires, je garde le copy pour pouvoir travailler sur les différents types de données.

Pour utiliser au mieux les types de données, j'ai besoin d'avoir le max d'infos sur la manière dont rebol gère les données en fonction de leurs types.

Dockimbel, le hash conserve l'ordre des données c'est sûr?
Si c'est vrai, c'est une sacrée bonne nouvelle pour moi, car je préfère les hash et je testais les btree en fonction de leur capacité a garder un ordre.

Ce que tu dis sur la réservation mémoire m'a l'air exact, mais pour éviter que cela se face en dynamique (cela correspond d'ailleurs à ta proposition de déclaration de donnee à la taille désirée), si on sait quelle quantité de mémoire on aura besoin, comment dire à Rebol alloue moi X meg?

La distinction scalaire, block me semble exacte aussi, mais cette règle ne semble pas rigoureusement appliquée: "sort" par exemple affecte directement la série passée en arg.

En résumé, il s'agit de savoir les maxs de rebol en terme de gestion de la mémoire pour organiser la gestion de mes données. L'ambition du projet étant de pouvoir gérer toutes les données importantes de toute une vie...plusieurs gigas.
Didec19-Jan-2011/17:33:45+1:00
Oui Marco, ou bien :
trifuse: func [a b][sort union a b]
DocKimbel19-Jan-2011/17:40:52+1:00
@guest2: bien vu !

@Marco: il est possible que sa fonction puisse se simplifier ainsi, mais difficile à dire sans connaitre précisément les structures de données passées dans a et b (il faudrait peut-être un sort/compare). Pas facile à analyser quand les informations sont données au compte-goutte.
paullys19-Jan-2011/17:45:02+1:00
Les "remove" servent à trois choses ils skippent, réduisent la taille instantanées des données utilisées et facilitent le travail après la sortie de boucle.
ce code n'est pas Rebol optimal, mais loin d'être une plantade. C'et pas non plus un code newbie!
Didec19-Jan-2011/17:51:23+1:00
Rien à voir avec la distinction scalaire, block (tu ne peux pas trier un integer!).

>> help sort
USAGE:
SORT series /case /skip size /compare comparator /part length /all /reverse

DESCRIPTION:
Sorts a series.
SORT is an action value.

[...] (je vous passe le reste)

'sort est une action (comme 'insert) et donc modifie la série elle même pour une raison évidente de gain mémoire. On peut toujours faire :
sort copy maserie

dans le cas où on veut garder la série originale.

Maintenant ce que Guest2 laisse entendre c'est que Rebol étant un langage directement interprété, l'optimisation doit se faire au niveau du script et est directement liée aux performances.
Un langage compilé ou JITé aura un résultat éventuellement optimisé pour un piètre code car le compilateur y mettra son grain de sel.

Avec Rebol c'est comme avec "Carouf" : "C'est moi qui décide ! C'est mooooiii qui décide. ...".
guest219-Jan-2011/17:51:23+1:00
Non justement, le taille des tableaux en mémoire n'est pas réduite par les 'remove, la mémoire reste allouée donc aucun gain de ce côté là.
De plus le remove du premier élément d'un tableau provoque de déplacement de tout les éléments suivants. Si le tableau est gros, ça devient catastrophique niveau perfs.
Ce n'est pas spécifique à Rebol. Tu confonds les tableaux et les listes chaînées.
Les block! rebol sont des TABLEAUX en mémoire.
guest219-Jan-2011/17:59:41+1:00
Juste une précision sur les removes dans les blocs. R3 est un peu plus malin, il gère un offset interne sur le début du block et deplace cette offset quand le remove est appliqué sur le premier élément au lieu de tout déplacer. Possible donc que ce script fonctionne beaucoup plus vite avec R3.
Mais c'est quand même un truc à éviter d'une façon générale parcequ'il se base sur une mauvaise hypothèse de départ. La mémoire n'est pas désalouée.
paullys19-Jan-2011/19:08:58+1:00
Cocinelle merci pour la proposition, mais l'idée c'est de cerner les limites de rebol afin de l'utiliser au mieux, d'une part et de pallier à ses manques d'autre part.
En effet les opérations tri de rebol se font en mémoire vive, normal, et donc on ne peut pas les utiliser à partir d'une certaine taille. Donc je m'efforce de trouver le max de rebol puis de me situer en dessous (a environ 80%). Ensuite je mets en place les palliatifs pour répondre à mon cahier des charges. C'est pour cela que ma demande ne concerne pas du tout le code ou l'optimisation du code ( les optimisations à faire à partir de ce code sur des grandes séries seront de l'ordre de 10 ou 20%) mais les infos sur la gestion de la mémoire. D'après les réponses que vous m'avez faites, il n'y guère que des suppositions car aucune documentation de RT.
Guest2, tu es trop prompt à la controverse, ce faisant tu ne lis pas avec attention ce que je dis: je ne dis pas que l'empreinte mémoire est diminuée par les remove mais le volume des données en cours d'utilisation. Le lien entre le volume des données et l'empreinte mémoire c'est la gestion de la mémoire justement. En limitant le volume de données utilisées, c'est un gros POTENTIEL d'optimisation qui est ouvert, c'est ensuite la souplesse et la qualité d'implémentation du langage qui permettra ou non de convertir ce potentiel en réelle économie.
Ensuite comme je suis à la phase de prototypage, ce code doit être hautement portable (dans le sens traduisible dans d'autre langage) et donc ne pas aller trop loin dans les spécificités du langage rebol si d'aventure il n'était pas le langage définitif. Mais en même temps il doit suffisamment tenir compte des spécificités du langage pour permettre d'évaluer la faisabilité du projet dans le langage rebol.
Je ne confonds pas les tableaux et listes chainées.
Pour les scalaires versus séries, dockimbel dit toujours passés par valeurs vu la lenteur relative de sort, non linéairement corrélée avec la longueur des chaines présentées on peut penser que sort "charge" ou modifie momentanément le mode d'adressage et d'accés aux données le temps de son action. Donc faisant exception à la règle d'utilisation des données. En gros le propos de dockimbel semble cohérent avec l'esprit d'implémentation du langage mais que des exceptions semblaient exister, dans le passage d'arg aux fonctions, et donc pouvait exister dans la gestion des données en fonction de la taille des données. Ce ne sont qu'hypothèses et prolongements hypothtiques...
Au final Je ne voulais pas donner le code pour justement qu'on se focalise pas sur le code, mais sur la gestion de la mémoire par Rebol. L'unique question qui m'intéresse. Je n'ai pas besoin d'optimisation Rebol, il est trop tôt.
Enfin en matière d'optimisation comme je l'ai un peu dit dans cette réponse, la finesse algorithmique précède, la finesse d'implémentation. Ce code est algorithmiquement correct (et même un peu plus), je ne lui en demande pas plus.
paullys19-Jan-2011/19:13:12+1:00
P.S: pour bien fixer les idées, ce n'est pas la lenteur ou pas du code qui m'intéresse c'est son RALENTISSEMENT à 80000, et l'inflation mémorielle l'accompagnant. Il y a toujours et pour tous les langages cette limite, il s'agit de la situer et d'essayer d'en rester éloigné. Que cette limite soit repoussée de 20 ou 20% n'a pas d'intérêt dans le cas d'espèces puisque j'ai les moyens de surpasser cette difficulté.
DocKimbel19-Jan-2011/19:26:21+1:00
@paullys

Car j'utilise Rebol comme langage de prototypage.
D'ailleurs je trouve que l'on ne souligne pas assez cet aspect de Rebol.
Niveau prototypage et montage rapide de démos; J'ai rien vu de mieux que Rebol.

Entièrement d'accord avec toi.

Dockimbel, le hash conserve l'ordre des données c'est sûr?

Oui !
>> list: make hash! [a b c d e]
== make hash! [a b c d e]
>> foreach item list [probe item]
a
b
c
d
e
>> sort/reverse list
== make hash! [e d c b a]
>> foreach item list [probe item]
e
d
c
b
a


Attention: le coût d'insertion d'un élément dans un hash! est supérieur à celui d'un block!. Donc, s'il y a énormément d'opérations d'insertion/suppression, il vaut mieux construire sa liste sous forme de block! d'abord, puis convertir en hash! ensuite. Ne pas oublier de pré-allouer (block! ou hash!), mais pour les list!, ce n'est pas nécessaire, a priori (je ne me souviens pas avoir testé çà, à vérifier).

si on sait quelle quantité de mémoire on aura besoin, comment dire à Rebol alloue moi X meg?

Il faut raisonner en "valeurs" (c.a.d. en cellules de block), plutôt qu'en octets. Si tu as 80k chaines à stocker dans un block, il faut réserver 80k places. Si tu as 80k entiers à stocker, idem. Etait-ce bien le sens de ta question ?

Si la quantité de mémoire disponible pour REBOL est une contrainte, c'est difficile de prévoir précisément, il faut compter le nombre de blocks (et dérivés: path!(s), paren!) et multiplier par 16 octets et ajouter la taille des chaines de caractères (en supposant que le nombre d'autres types de données complexes, est marginal). J'ignore combien hash! et list! prennent d'octets par valeurs stockées, c'est à mesurer...Dans tous les cas, le plus simple est de faire tourner son application et vérifier de visu la conso mémoire. J'avais fait un petit outil en 2001 pour surveiller la conso mémoire en live d'une session REBOL (do http://rebol.softinnov.org/old/mem-watch.r), le problème étant que l'outil lui-même modifie la conso mémoire à chaque analyse, donc difficile d'avoir une visualisation parfaitement précise (un RECYCLE à chaque ligne évaluée dans la console est censé tempérer la conso de l'outil, mais ça reste approximatif). Pour les connaisseurs, l'outil tente de simuler le mode /torture de RECYCLE.

La distinction scalaire, block me semble exacte aussi, mais cette règle ne semble pas rigoureusement appliquée: "sort" par exemple affecte directement la série passée en arg.

Le passage "par référence" ne présuppose pas de l'usage qui sera fait de la référence et du fait que la valeur référencée soit modifiée ou pas. Le fait que les arguments soient modifiées ou pas par une fonction dépend du "paradigme" (quel vilain mot...) dans lequel le langage s'inscrit, pour simplifier: impératif, fonctionnel ou fonctionnel pur. REBOL est un langage fonctionnel, mais il n'est pas pur (comme LISP/Scheme et dérivés) car il permet de modifier les arguments passés (ce qu'on appelle un "effet de bord").

il s'agit de savoir les maxs de rebol en terme de gestion de la mémoire

Les limites réelles sont peu ou pas connues. J'imagine qu'il y a une barrière à 2Go pour les séries (block! ou string!) et près de 4Go pour la quantité de mémoire max gérable par REBOL (max d'un pointeur 32-bit), mais ce sont des hypothèses hautes, je n'ai pas testé, les limites réelles peuvent être plus basses. De toute façon, il n'est pas bon d'en demander trop niveau usage mémoire, plus le nombre de séries en usage est grand, plus le travail du GC devient difficile (surtout si ce sont des blocks imbriqués) et les pauses à l'exécution pour le nettoyage, de moins en moins négligeables. Si l'application ne peut supporter des pauses importantes (par ex: 0,5s dans un jeu d'arcade), REBOL peut rapidement devenir un non-choix.
guest219-Jan-2011/19:29:17+1:00
Bon écoute je vais être clair, au vu du code que tu nous as montré (il manque encore un exemple de données pour être complet) il est évident que ton code n'est pas plus lent de seulement 10% ou 20% par rapport à du code Rebol optimal. la différence est de plusieurs ordres de grandeur. Et ceci te conduit à croire que la lenteur est intrinsèque à Rebol alors que c'est ton code qui est mauvais. Appelons un chat, un chat.
Je ne vais pas argumenter davantage parce que j'ai l'impression tu n'essaies pas de comprendre nos explications concernant les manipulations de mémoire inutiles que ton code réalise.
On est tous passé par là. Si tu veux progresser accepte les critiques et essaie de comprendre ce qu'on te dit mais j'ai pas l'impression que t'en ais vraiment envie.
DocKimbel19-Jan-2011/20:33+1:00
Pour les scalaires versus séries, dockimbel dit toujours passés par valeurs vu la lenteur relative de sort, non linéairement corrélée avec la longueur des chaines présentées on peut penser que sort "charge" ou modifie momentanément le mode d'adressage et d'accés aux données le temps de son action. Donc faisant exception à la règle d'utilisation des données.

Je ne suis pas sûr de bien saisir ton explication. Ce qui est passé "par valeur" ce sont les types "scalaires" et non les séries et types complexes qui sont toujours passés par "référence". Mais ceci décrit le fonctionnement du langage au niveau du programmeur REBOL, il est certain que dans le noyau en C, des raccourcis soient pris. Par exemple, il est probable que SORT en interne fasse des modifications "in-place", c.a.d. fasse du "swap" de cellules sans faire d'allocation supplémentaire (quelque soit le contenu de la cellule, scalaire, série, ou type complexe), comme le fait un qsort() en C sur un tableau.

Enfin en matière d'optimisation comme je l'ai un peu dit dans cette réponse, la finesse algorithmique précède, la finesse d'implémentation. Ce code est algorithmiquement correct (et même un peu plus), je ne lui en demande pas plus.

Tu touches du doigt un des principaux reproches que je peux faire à REBOL: pour faire du code "efficace" et rapide, il est souvent nécessaire de dénaturer un algorithme élégant et/ou mathématiquement pur. Parfois, cela va même à l'encontre de la théorie informatique, en obligeant à utiliser des fonctions natives dont on sait que la complexité n'est pas optimale, au lieu de code "mezzanine" implémentant l'algorithme optimal.

Par exemple, il y a un an, j'avais besoin d'implémenter dans Cheyenne un système de blocage des requêtes web de type scanner ou attaque, non pas que Cheyenne y soit sensible (il ne montre aucune faille au test sous Nikto: http://cirt.net/nikto2), mais ce genre de requêtes parasitent complètement les logs HTTP et surcharge inutilement le serveur. J'avais une liste noire de signatures correspondantes aux attaques les plus courantes (extraite des logs) à chercher dans chaque requête entrante, le plus rapidement possible, cela va de soi, pour ne pas plomber les performances du serveur. Deux approches possibles:

1) implémentation "naive" et non-optimale (O(n^2)): 
foreach pattern list [if find request-line pattern [drop-request]]


2) implémentation optimale en O(log(n)): pré-construction d'un arbre de recherche en mémoire à partir de la liste des motifs (1ère lettre => niveau 1, 2ième lettre => niveau 2, ..., chaque niveau étant un hash! des n-ièmes lettres de chaque motif). L'algorithme global peut alors s'exprimer comme: 
foreach letter request-line [
    if find tree letter [
        tree: go-up tree
        if leaf? tree [drop-request]
    ]
]


J'ai passé 1/2 journée sur ce sujet et soigné l’implémentation #2 (avec tests unitaires). Je lance un test de perfs avec une liste de 20 signatures...catastrophe, la version #1 est beaucoup plus rapide que la version #2 (je crois me souvenir d'un facteur 10!)...les boules! J'ai lancé d'autres tests pour en avoir le coeur net en augmentant progressivement le nombre de signatures, ayant atteint ~600 signatures, les perfs des deux approches sont maintenant identiques...ouf, pas la peine de brûler mes livres d'algos et d'adopter Carl comme nouveau dieu, la théorie est sauve! Mais à quel prix...j'ai utilisé la solution #1 finalement (le nombre de signatures utiles est de 20-30) alors que mes 25 ans d'expérience en info me crient que la bonne solution est la #2 ! :-/

Morale de l'histoire: REBOL est un langage interprété dont le code doit être optimisé manuellement, en privilégiant les fonctions natives, quitte à utiliser un algorithme, en théorie non-optimal. Les algorithmes optimaux en REBOL sont ceux qui exploitent les avantages particuliers de son implémentation. J'ai adopté cette approche depuis des années, mais à contre-coeur, et je me fais encore avoir, comme dans le cas que je viens de décrire.

Ah, si seulement le code REBOL pouvait tourner aussi vite que Java ou C, ce problème ne se poserait plus, les algos notoirement optimaux seraient les bons choix d'office et les vaches seraient bien gardées!
paullys19-Jan-2011/22:19:15+1:00
Guest2, tu pars d'une bonne intention c'est certain, mais écoute avant de répondre!!! ce qui m'intéresse c'est la limite de travail de rebol en termes de mémoire et de capacité à mouliner beaucoup de données dans de bonnes conditions. Et dans ce cadre je dis 10 à 20% en étant généreux <=> je pourrais avec modifs gérer peut-être 10000 strings de plus grand max. Et encore je serais sorti de la plage d'utilisation de mpn application (réponse inférieure à la seconde dans 80% des cas).Et ce mur de performance au dela duquel rebol passe plus de temps a gérer la mémoire qu'a appliquer mes commandes ne peut être que repoussé, aucune optimisation ne peut l'empêcher d'advenir.
fais le test avec une boucle qui ne fait rien d'autre que de faire grossir un block tu verras apparaitre ce mur rapidement et là pas d'optimisation de code à faire puisque le code ne fais rien d'autre que faire grossir un block. C'est cela la question, pas de savoir le nombre de cycles perdu à faire un remove ou quand est réallouée la mémoire inutilisée.
Donc pour finir ca rame, c'est bien comme cela et c'est cela que je voulais!
Et pis mon code n'est pas mauvais je le maintiens, il fait ce pour quoi il est fait et c'est cela un bon code!!
C'est pas par ce que je post jamais technique ici que je suis débutant.
Quand à Dockimbel, un grand merci c'est le seul à comprendre et à m'apporter des éléments nouveaux:
-hash conserve l'ordre.
-limites théoriques Rebol 2 ou 4Go (même si je pense que les limites pratiques de rebol sont largemnt en deçà, car à ces niveaux on swappe depuis longtemps sur disque dur au niveau système)
-ton exemple n' est pas très parlant car se coller du btree pour recherche sur 25 valeurs, c'est prendre un fusil mitrailleur pour tuer une mouche.
C'est typiquement un cas d'utilisation d'une table de hashage. Et là puissance Algo, correspond à efficacité implémentation. on passe même de O(n) à O(1).

En revanche dans le cas ou les solutions algo sont bien dimensionnées par rapport aux données entre algo en n^2 et logn,moi, je ne résiste pas au cri du logn et je lache pas l'affaire jusqu'à que l'implémentation du tree me rende mon dû.

On croit souvent compenser les faiblesses algo par optimisation de l'implémentation et pour moi c'est fondamentalement une erreur. Je travail en priorité l'algo, en limitant tant que faire se peut les appels aux spécificités des langages avant le choix du langage de dev. Le code est plus partageable entres devs de langages différents et plus portables et maintenable.
Même s'il est un peu moins optimisé sur un langage particulier.
exemple le code que j'ai exposé peut être traduit dans tous les langages du monde quasi textuellement, fonctionnera sur toutes les plateformes moyennant quelques précautions sur les types de données utilisables et leurs tailles. Et le choix du remove peut éventuellement dans certaines conditions permettre de faire baisser l'empreinte mémoire.
paullys19-Jan-2011/22:51:43+1:00
En fait pour la question "comment dire à Rebol alloue moi X meg?", c'est justement comment réserver une zone mémoire avant de definir son utilisation, un malloc quoi.
et/ou comment agrandir une la taille d'une série par exemple:
a: make block! 80
finalement en cours de route on a besoin de 160, il n'y a pas d'autre choix que de créer un b: make block! 160 et poke b 1 a?
L'intérêt c'est d'être un peu plus efficace que de laisser rebol ajouter a chaque ajout dans b.
J'utilise les hash, avec key/value comme table de hashage<=> associative array et normalement les associatives array ne garantissent pas l'ordre des donnees...Même si elles ne modifient pas l'ordre des donnees tant qu'elle n'en n'ont pas besoin.
paullys19-Jan-2011/22:54:52+1:00
om peut append b block de 80 et ensuite les poke, plus efficace?
DocKimbel19-Jan-2011/23:53:02+1:00
-ton exemple n' est pas très parlant car se coller du btree pour recherche sur 25 valeurs, c'est prendre un fusil mitrailleur pour tuer une mouche.
C'est typiquement un cas d'utilisation d'une table de hashage. Et là puissance Algo, correspond à efficacité implémentation. on passe même de O(n) à O(1).

Mea culpa, je n'ai pas été suffisamment clair dans ma description: mon besoin était un algorithme de recherche de sous-chaines multiples (les signatures) dans une chaine de caractère donnée (la 1ère ligne d'une requête web contenant l'URL demandée). Une table de hashage n'est pas applicable à ce problème (ou alors c'est un algo qui m'est inconnu). L'arbre binaire de recherche aurait tout à fait convenu, c'est bien un "fusil mitrailleur" dont j'avais besoin, chaque microseconde est importante à ce niveau de traitement dans Cheyenne. D'autre part, la fonctionnalité était prévue pour être utilisable par d'autres, pouvant à volonté ajouter de nouvelles signatures via le fichier de config et donc passer bien au-delà de mes besoins initiaux de 20-30.

On croit souvent compenser les faiblesses algo par optimisation de l'implémentation et pour moi c'est fondamentalement une erreur. Je travail en priorité l'algo, en limitant tant que faire se peut les appels aux spécificités des langages avant le choix du langage de dev. Le code est plus partageable entres devs de langages différents et plus portables et maintenable.

Ok, c'est ton choix et il est tout à fait valable, mais dans ce cas, tu ne pas peux d'un côté clamer que "rebol rame" pour un block de 80k strings tout en refusant de prendre en compte la moindre spécificité de REBOL. C'est comme si j'écrivais une boucle en C avec un realloc() au milieu (au lieu de préallouer correctement avant la boucle) et clamer que le "C rame" et que la mémoire est très mal gérée...

Le REMOVE est symptomatique, il est *très* couteux en REBOL si effectué en début d'une série (surtout si elle contient 80k valeurs), comme évoqué par guest2. Chaque REMOVE provoque une recopie mémoire vers la gauche des valeurs à droite dans la série et ne libère aucun espace mémoire (sauf sur un type list!). REBOL, peut-être plus que d'autres langages, repose sur le bon usage des fonctions natives, c'est vital pour avoir un code utilisable (surtout dans le cas d'une grande quantité de données à traiter).

Je comprend tout à fait ton approche: prototyper un code portable pour une implémentation finale dans un autre langage, ça me parait tout à fait censé, mais sache que si le langage final est REBOL, il te faudra sans doute réécrire le code, voir changer d'algorithme pour avoir des performances acceptables, c.a.d., faire le travail deux fois...(quoique dans certains cas, il est bon d'avoir deux implémentations d'un même algorithme afin de pouvoir tester efficacement la version optimisée, mais cela a un coût).

comment agrandir une la taille d'une série par exemple:
a: make block! 80
finalement en cours de route on a besoin de 160, il n'y a pas d'autre choix que de créer un b: make block! 160 et poke b 1 a?

Les series en REBOL sont auto-extensibles, la réallocation est automatique, si tu pars de 80 sans savoir que tu auras besoin de 160, tu préalloues 80 et REBOL étendra la série à 160 quand ce sera nécessaire (par pas de 16 éléments ou octets, mais c'est une supputation). Attention, la préallocation de n éléments (ou octets pour les string! et dérivés) garantie que la serie aura *au moins* n emplacements disponibles, mais REBOL va souvent en réserver plus. Il semble que ce soit via la suite suivante (ce sont les équivalents des "bins" de dlmalloc): 
>> list: [] foreach pool stats/pools [append list pool/1]
== [16 32 48 64 80 96 112 128 144 160 176 192 208 224 240 256 512 1024 2048 4096 16 16 1]


Donc de 16 (au minimum) à 4096 octets, au-dessus, le gestionnaire mémoire est peut-être différent ? Mystère...

J'utilise les hash, avec key/value comme table de hashage<=> associative array et normalement les associatives array ne garantissent pas l'ordre des donnees...Même si elles ne modifient pas l'ordre des donnees tant qu'elle n'en n'ont pas besoin.

Il n'y a pas d'"associative array" en REBOL2, seul REBOL3 en propose un via le type map!. Le type hash! est dual, tu peux le considérer comme un block! (liste ordonnée navigable) avec une table de hashage associée pour un accès rapide aux éléments contenus. Hash! étant très polyvalent, tu peux stocker des couples clé/valeur sans problème (mais la clé *et* la valeur associée seront hashées), l'ordre sera toujours garanti tant que tu ne le modifieras pas explicitement. Attention simplement à une chose: si la clé et la valeur associée sont du même type, tu risques un clash sauf si elles appartiennent à des ensembles bien séparés. J'utilise hash! aussi bien pour stocker juste des clés, que des couples clé/valeur, voire aussi clé + plusieurs valeurs (avec recherche inversée possible de la clé à partir d'une valeur ), il est vraiment très pratique (dommage qu'il ait disparu dans R3 !).

om peut append b block de 80 et ensuite les poke, plus efficace?

POKE d'un block vers un autre va se comporter comme un INSERT/ONLY, ce que tu souhaites faire nécessite un INSERT/PART ou un CHANGE/PART.
paullys20-Jan-2011/14:33:36+1:00
voila un code plus rebolish tenant compte des observations, il me servira par la suite éventuellement, si cette partie est codée en rebol.
trifuseoptrebol: func [a b /local c][
sort a   
sort b   
c: make block! 80000

while [ all [a <> [] b <> [] ]][;print [a/1/1 b/1/1]
either a/1/1 > b/1/1 [append/only c b/1 b: next b][
either a/1/1 = b/1/1 [
append/only c join a/1 next b/1
a: next a b: next b
][append/only c a/1 a: next a ] ]
]
if all [a = [] b <> []] [append c b]
if all [b = [] a <> []] [append c a]
return c
]

Effectivement ca tourne mieux, ce dont je n'ai jamais douté étant donné que les choix du précédent code sont consécutifs à mes contraintes.
J'aurais du vous passer le code en pseudo langage pour que vous compreniez que ce n'est pas une question d'implémentation. Mais d'ordre de grandeur si la limite c'est 80000 c'est bien, si c'est 100000 c'est bien aussi.
Ce n'est pas une critique envers rebol, quoique...
aparté-
L'exemple du remove est parlant l'implémentation est mauvaise, puisque d'après guest2 une autre implémentation est peut-être à l'oeuvre dans R3.Donc je ne refuse pas une petite adaptation au langage mais il ne faut pas que cela entrave la portabilité ni la pérennité du code (en fonction des évolutions du langage et rebol est particulièrement instable de ce point de vue, cela prouve que le langage évolue).Mais il ne faut pas non plus considérer l'implémentation REbol comme l'évangile et critiquer un code seulement à l'aune de sa compatibilité avec Rebol sans tenir compte de la valeur intrasèque du code
-fin aparté.

Pour l'expression "rebol rame", je ne voulais pas vous vexer, c'était plus pour donner un contexte, car ma recherche concerne la façon qu'a rebol d'agencer les données en mémoire.

-L'exemple du hash disparu de r3 me donne raison sur la notion de pérennité du code qui je pense est un très gros sujet pour un langage en évolution et qui n'est que trop peu évoqué.

Cela touche un autre sujet qui est dommageable pour rebol, de mon point de vue, c'est que soit on s'adapte au fonctionnement peu documenté de la mémoire de Rebol (par tatonnement comme vous semblez avoir fait) soit on est obligé de prendre des chemins de traverse.
Il n'est pas possible d'adapter une partie du foncionnement de la VM ou d'ajouter des fonctionnalités dans de bonnes conditions. Exemple rebol est dev en c, pourquoi ne pas laisser un accés même bridé à l'allocation mémoire par un malloc like.
A propos d'où proviennent les informations précieuses sur le hash que tu viens de me donner, car en dehors d'une doc sur hash on l'utilise en croyant que c'est une table de hachache alors que c'est un bloc doublememnt indexé (si je comprends bien ce que tu viens de me dire). C'est un choix intéressant ne serait-ce que par les exemples que tu donnes, mais sans doc et sans possibilité de customiser en fonction de ses besoins, c'est un peu duraille, non.

Enfin dockimbel tu es l'auteur de R-Sharp? Si oui peut-on un peu discuter de la genèse du projet, de l'état d'avancement et d'une finalisation possible de ce projet?
DocKimbel20-Jan-2011/22:40:53+1:00
Hash!: les informations viennent de la doc officielle (http://www.rebol.com/docs/core23/rebolcore-16.html#section-2.5), de 10 ans de pratique de REBOL, des nombreuses discussions avec les autres développeurs REBOL sur la mailing-list, puis sur les serveurs REBOL/IOS dédiés (notamment le serveur "Developer") et enfin les informations distillées par Carl lors de chats en ligne ou en live. Pour le coup, la doc officielle est assez pauvre sur hash!.

on l'utilise en croyant que c'est une table de hachache alors que c'est un bloc doublememnt indexé (si je comprends bien ce que tu viens de me dire)

Hash! ne contient pas de notion de "valeur", il n'y a que des "clés" en fait, car *tous* les éléments contenus sont indexés (simple indexation a priori, mais c'est une supputation). Le type hash! est totalement navigable, toutes les fonctions natives sur les séries fonctionnent comme pour un block! (même PARSE fonctionne). Au niveau de l'implémentation interne, je suppose qu'il y a bien un block! (ou une structure interne équivalente) contenant les éléments + une table de hashage pour la recherche. La seul réelle différence du point de vue de l'utilisateur est la performance de certains actions: FIND et SELECT sont en O(1) contre au mieux O(n) pour un block!. Les performances des insertions/suppressions entre hash! et block! doivent aussi différer (suivant la taille de la série).

Donc en pratique, tu peux utiliser un hash! comme un block!, c'est ce que je fais souvent en combinant la recherche rapide avec de la navigation interne.

R-Sharp: oui, c'est moi l'auteur, je vais ouvrir un nouveau topic pour en parler.

Login required to Post.


Powered by RebelBB and REBOL 2.7.8.4.2