Discussion :

[Lunixinclar]

Discussion intéressante. Ca serait sympa de faire un concours et de comparer
les performances avec certificat ou médaille du meilleur parseur.
Pour ça on pourrait envoyer tous les progs à un admin, qui les compile et les mesure sur la même machine. Puis on les publie quelque part pour que les participants puissent comparer leur code.

But: afficher toutes les URLs vers stdout.
URL à parser : http://www.google.fr/search?q=href
Durée: 7 jours.

Qui est partant?

[David.Schris]

Discussion intéressante. Ca serait sympa de faire un concours et de comparer
les performances avec certificat ou médaille du meilleur parseur.
Pour ça on pourrait envoyer tous les progs à un admin, qui les compile et les mesure sur la même machine. Puis on les publie quelque part pour que les participants puissent comparer leur code.

But: afficher toutes les URLs vers stdout.
URL à parser : http://www.google.fr/search?q=href
Durée: 7 jours.

Qui est partant?

Sauf que prendre une URL comme référence n'est pas forcément la meilleure idée : il y a un risque que le résultat renvoyé par Google change entre l'exécution de deux programmes à comparer et que cela fausse le résultat ; la page renvoyée est trop petite ; elle ne contient peut-être pas assez de cas différents (il y a des chances que Google forme toujours ses balises de la même façon) ; parler d'URL c'est aussi supposer que les programmes récupèreront la page via le net alors que le temps de réponse de Google peut varier ; etc.
Si tu veux comparer, il faut être certain que ce qui est fourni en entrée aux programmes soit fixe, représentatif et d'une taille suffisamment importante pour que les écarts de résultat soient significatifs. Il faut aussi fixer des règles plus strictes, comme par exemple "récupérer la valeur de l'attribut 'href' des balises 'a' et ignorer tous les autres liens", sinon un programme qui gère moins de cas (moins de balises/attributs) pourrait être avantagé à tort par rapport à un autre qui sait en gérer plus.

[pirus]

oui, il faut que l'organisateur du concours eventuel choisisse une page, si possible assez lourde (de l'ordre de plusieurs mega) pour etre capable de mesurer quelque-chose de significatif, puis qu'il la sauvegarde. chaque parser pourrait alors n'etre qu'un filtre qui lirait la page sur stdin et ressortirait les liens sur stdout.

bien sur, tout doit se faire sur la meme machine, et l'organisateur doit preciser la config hardware, l'OS, et le(s) compilateur(s) utilisable(s) (donc les langages); il faut aussi savoir quels seront les criteres d'evaluation.. un vrai contest, quoi.

enfin, et dans l'interet de tous, il faut se mettre d'accord sur les questions de propriete/licence des sources publies.

-pirus.

[David.Schris]

enfin, et dans l'interet de tous, il faut se mettre d'accord sur les questions de propriete/licence des sources publies.

Ou ... ne pas publier les sources ?

[pirus]

Ou ... ne pas publier les sources ?

je ne peux pas dire que ca m'enchante forcement de balancer dans la nature ce qui represente pour moi une des parties les plus importantes d'un projet sur lequel le fonde beaucoup d'espoir.. effectivement, on pourrait choisir de definir une API assez simple, avec par exemple un init() et des callbacks, et chaque participant fournirait un .o precompile, qui implementerait cette API..

en meme temps, cette demarche est un peu contradictoire avec la vocation didactique du site.. si c'est organise serieusement, que ca peut etre vraiment utile a quelqu'un et qu'on est quand meme quelques uns a participer, je suis pret a faire le "sacrifice".

-pirus.

[Gruik]

On verra rien comme difference si il s'agit d'analyser juste une page... il faut analyser plusieurs milliers de page pour voir lequel est le plus efficace

[Lunixinclar]

Le facteur le plus déterminant pour les performances, c'est l' algorithme.

Mesuré à l'ordre de la micro-seconde, tu verras les écarts. On parlera de
millisecondes voire de secondes, sur quelques Mo.
La moyenne sera faite sur plusieurs tests, et en local bien entendu!

Le C est puissant (http://dada.perl.it/shootout/) mais perd sur l' algorithmique.
On a parlé de pointeurs, de tableau de chars, d' expressions régulières, de
strstr()... Ca va être très palpitant pour les participants.

Je peaufine les règles et poste une annonce demain.

[Gruik]

Pour un traitement aussi simple en C, ce n'est pas l'algorithme qui est determinant mais les interactions avec le systeme.
Par exemple, si tu veux afficher des trucs sur la sortie standard, ca va dependre de ce que fait le systeme à ce moment là, le terminal peut être prêt à recevoir immediatement le texte à afficher, ou pas.
Pareil si on doit acceder à des fichiers (ex, lire la page html d'entrée).. Lire le meme fichier peut varier de plusieurs ms..

Je te garantis que cette analyse est peanuts comparé à un fopen/fread du fichier d'entrée

C'est pour ça que je dis que pour y voir quelquechose il faut executer le traitement plein de fois.

[David.Schris]

Je peaufine les règles et poste une annonce demain.

Dans ce cas, pense à préciser, entre autres, sur quelle "norme" les programmes doivent être basés (HTML ? XHTML ? Quelle version ?).
Pour éviter de trop compliquer les choses, il faudrait peut-être aussi spécifier un encodage de caractères ("simple"...genre ASCII , pas UTF-8) à supporter.

[pirus]

Par exemple, si tu veux afficher des trucs sur la sortie standard, ca va dependre de ce que fait le systeme à ce moment là, le terminal peut être prêt à recevoir immediatement le texte à afficher, ou pas.
Pareil si on doit acceder à des fichiers (ex, lire la page html d'entrée).. Lire le meme fichier peut varier de plusieurs ms..

on peut simplement utiliser "time", qui va donner qqchose du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
real    0m0.261s
user    0m0.203s
sys     0m0.044s

et prendre en compte uniquement la partie "user" du temps d'execution, qui correspond au temps que le processus passe en user space, par opposition au kernel space ("sys" avec time), qui correspond entre autres aux appels systeme, dont les I/O (disque et tty).

pour l'histoire de la sortie standard, je serais assez pour faire un test fonctionnel d'abord (en redirigeant la sortie dans un fichier), puis faire les tests de perf en > /dev/null .

pour l'evaluation, soit on fait un moyenne sur N sessions, soit on prend le meilleur temps des N sessions, comme vous voulez. autre possibilite, si N = 5 par exemple, on peut faire la moyenne des 3 meilleurs temps.

Lunixinclar, n'oublie pas de preciser le langage (C ou C++), afin que ce soit clair pour tout le monde.

sinon, quelqu'un nous trouve un sponsor ?

-pirus.

[David.Schris]

on peut simplement utiliser "time"
[...]
et prendre en compte uniquement la partie "user" du temps d'execution
[...]
pour l'histoire de la sortie standard, je serais assez pour faire un test fonctionnel d'abord (en redirigeant la sortie dans un fichier), puis faire les tests de perf en > /dev/null .
[...]

+1

sinon, quelqu'un nous trouve un sponsor ?

Je propose les ventilateurs "Freezer" : les ventilateurs que le chaud il en a peur.

[Gruik]

on peut simplement utiliser "time", qui va donner qqchose du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
real    0m0.261s
user    0m0.203s
sys     0m0.044s

et prendre en compte uniquement la partie "user" du temps d'execution, qui correspond au temps que le processus passe en user space, par opposition au kernel space ("sys" avec time), qui correspond entre autres aux appels systeme, dont les I/O (disque et tty).

Ah ouais, ça tue
Mais la precision de time risque pas d'etre un peu limite?

[David.Schris]

[...]
Mais la precision de time risque pas d'etre un peu limite?

Pas si le fichier en entrée est suffisamment important et représentatif.

[pirus]

[...]
Mais la precision de time risque pas d'etre un peu limite?

Pas si le fichier en entrée est suffisamment important et représentatif.

oui, meme si la constance entre deux evaluations successives avec "time" n'est pas parfaite-parfaite, on reste en gros dans les memes valeurs entre deux evaluations d'un meme programme. ca deviendra d'ailleurs d'autant plus interessant si la difference n'est pas enorme, et s'il doit y avoir "photo" a la fin entre plusieurs participants

(maintenant excusez-moi, mais la F1 je ne loupe sous aucun pretexte , a dans 2h).

-pirus.

[pirus]

bon.. en attendant que ce soit formalise, on pourrait proposer la chose suivante:

• chaque participant fournit le source d'un executable qui prend un flux HTML ASCII en entree (sur stdin) et sort une liste des URL ("a href" et "img src", un URL par ligne) sur stdout, et les instructions pour le compiler,
• etre capable de parser le HTML "courant" (pas forcement limite au XHTML strict W3C, qui correspond malheureusement encore a de la science fiction sur pas mal de sites), disons quelque-chose qui tourne autour du HTML 4.01 ?
• chacun choisit les termes de la "licence" selon lesquels il veut distribuer son code, sachant qu'il s'agit quand meme d'un echange d'idees a vocation didactique, et que de toute facon, une fois que le code est sur le Net..
• si possible, faire en sorte que le code soit raisonnablement portable entre Linux et Windows, il faut qu'un maximum de personnes puissent en profiter,

l'objectif etant de parser correctement le HTML (en ne loupant pas de liens), et le plus vite possible, le tout dans une ambiance bon enfant et conviviale

en attendant de se mettre d'accord sur une methodologie de test (sujet qu'on a deja aborde), est-ce que ca vous convient ? je ne tiens pas forcement a prendre la responsabilite de l'organisation, mais il faut s'y mettre sans tarder si on veut que ca demarre (sinon chacun va repartir a ses petites affaires).

je pense que les quelques points ci-dessus permettent deja a chacun de commencer quelque-chose. pendant ce temps, le forum peut etre mis a contribution pour les questions relatives a l'organisation des tests, par exemple, et si possible a inciter d'autres personnes a participer.

je n'ai pas vraiment d'a priori concernant le langage a utiliser.. C et C++ me semblent etre les deux possibilites les plus vraissemblables, mais il serait peut-etre dommage de s'y limiter arbitrairement.

comme je l'ai deja dit, je suis partant si je ne suis pas tout seul donc manifestons-nous (en precisant le langage et l'OS par exemple ?).

puis c'est un echange d'idees; si ce thread doit rester silencieux pendant plusieurs jours alors que chacun a la tete dans le guidon, c'est moins interessant.

-pirus.

[Lunixinclar]

Pas mal le 'time' c'est une excellente remarque. Mais problèmes de portabilité.
En outre il fait appel à des fonctions que j' appelle directement pour mesurer
un bout de code (comme par exemple une fonction), pas le processus complet: inutile de
mesurer le temps pris pour démarrer l' application. En effet le loader d'exécutable
prend toujours quelques millisecondes pour charger une application
(http://shootout.alioth.debian.org/gp...hello&lang=all)
C'est pourquoi je mesure le temps réel pris par une boucle ou une fonction, pas
par son l'implémentation. Pas besoin de mesurer le main().
De plus, ces fonctions font bien la différence entre le temps pris par le code et
celui pris par le système, en fournissant additionnellement des infos sur la
mémoire, ce qu' hélas le binaire time ne fait pas (mais que ps ux fait approximativement).
Time est effectivement une appli simple et très pratique, mais qui ne répond pas
à la précision requise pour le benchmark en question.


Les différences entre les appels sont tout à fait normaux, c'est également expliqué ici
http://shootout.alioth.debian.org/de...gcc-3#cputable

Cependant, soient 2 programmes A et B. Sur 100 tests,
A obtient la moyenne de 4.1552 millisecondes.
B obtient la moyenne de 5.1457 millisecondes.
Même si la différence est infime, je préfère l' algorithme A.




Concernant les propositions de Pirus, voici mon point de vue.
Il va y avoir deux types de tests: windows OU Linux. Ca écarte les questions
de portabilité.
Pour la licence, le message que je t'ai envoyé ce matin disait:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
III. Propriété intellectuelle

Chaque source est propriété de son auteur. En d' autres termes,
vous en êtes le détenteur et vous avez le droit de la publier.
Par défaut toutes les sources du contest seront publiées avec
la licence GPL (elle garantit les droits de propriété intellectuelle
tout en respectant l' Open-Source)
sauf sur demande expresse de votre part, auquel cas a) Personne
ne la publiera sur le net ou ne la transmettra sans votre accord
et/ou b) Indiquez dans l'en-tête de la source la licence à
laquelle elle est assujettie. Plus d' infos ici:
http://opensource.org/licenses/

J'avais promis de faire une annonce aujourd'hui, mais c'est encore trop tôt.
Beaucoup de choses à faire et elles ne vont pas se faire toutes seules. Si.
Par conséquent comme j' organise le contest je n'aurai pas le droit d'y participer.

Un camarade programmeur a envie de participer lui aussi, ça fait deux!
N'hésitez pas à exprimer vos opinions.

[pirus]

[...]
En outre il fait appel à des fonctions que j' appelle directement pour mesurer
un bout de code (comme par exemple une fonction), pas le processus complet: inutile de
mesurer le temps pris pour démarrer l' application. En effet le loader d'exécutable
prend toujours quelques millisecondes pour charger une application
[...]

oui, c'est precisement ce qui fait qu'il y a un delta, dans les stats de "time", entre "real" et la somme de "user" et "sys" (voir l'exemple que j'avais cite plus haut).

C'est pourquoi je mesure le temps réel pris par une boucle ou une fonction, pas
par son l'implémentation. Pas besoin de mesurer le main().

ah ? l'idee de ne pas mesurer main() est interessante

De plus, ces fonctions font bien la différence entre le temps pris par le code et
celui pris par le système

mais de quelles fonctions parles-tu ?

bon.. revenons sur terre: on ne va certainement pas avoir a comparer les programmes a la milliseconde pres. chacun (je pense) a une idee precise de la facon dont il veut implementer son affaire, et comme tu le faisais remarquer toi-meme hier:

Le facteur le plus déterminant pour les performances, c'est l' algorithme.

je pense que l'interet de cet exercice reside plus dans la confrontation d'idees et de methodes, que dans la course a la milliseconde. par exemple, dans les interventions precedantes, il a ete question de regex, d'analyseur syntaxique et d'automate a etats. si on est 4 ou 5 a jouer le jeu, on va sans doute avoir des rapports de performance entre les programmes de l'ordre de 10 ou 20, peut-etre plus.

je prefererais de loin (et sans vouloir parler en leur nom, je pense que David.Schris et Gruik partagent cet opinion) que tu participes et que tu te fasses plaisir, plutot que nous nous perdions dans les meandres d'une formalisation lourde, dont l'utilite est tout a fait secondaire.

-pirus.

[David.Schris]

[...]
un flux HTML ASCII en entree (sur stdin)
[...]
une liste des URL ("a href" et "img src", un URL par ligne) sur stdout,
[...]
quelque-chose qui tourne autour du HTML 4.01
[...]
raisonnablement portable entre Linux et Windows
[...]
dans une ambiance bon enfant et conviviale
[...]
est-ce que ca vous convient ?

Oui.

[...]
C et C++ me semblent etre les deux possibilites les plus vraissemblables, mais il serait peut-etre dommage de s'y limiter arbitrairement.

Idée : le soutien d'un modérateur et l'annonce par ce dernier dans un forum général ou dans les forums dédiés aux différents langages (une contribution sous Access, ça vous tente ? ).

[...]
comme je l'ai deja dit, je suis partant si je ne suis pas tout seul

Pareil.

donc manifestons-nous (en precisant le langage et l'OS par exemple ?).

C (gcc) Linux+Windows (si on a 7 jours pour le faire, je risque d'être assez pris cette semaine).

J'avais promis de faire une annonce aujourd'hui, mais c'est encore trop tôt.

Pas de soucis, prends ton temps, certains passent probablement leur week-end dans les gorges du Verdon : il faut leur laisser le temps de revenir [1].

Un camarade programmeur a envie de participer lui aussi, ça fait deux!

Trois.

je prefererais de loin [...] que tu participes et que tu te fasses plaisir

Il a la troouuuiiiille, le force pas
Hum...
Ben oui, viendez joué zavec nous m'sieur Lunixinclar : plus on est de...enfin, vous voyez... Du coup, ça fait 4.

Bon, je vais manger. Je ramène un truc à quelqu'un ?

[1] - Avant qu'on me tape dessus : je n'ai RIEN contre les gorges du Verdon.

[pirus]

donc hm.. C++ (gcc) Linux + Windows pour moi.

Bon, je vais manger. Je ramène un truc à quelqu'un ?

t'as pas plutot un ventilateur "Freezer" ?
il n'empeche que le gagnant peut toujours payer sa binouze a l'occasion

Idée : le soutien d'un modérateur et l'annonce par ce dernier dans un forum général ou dans les forums dédiés aux différents langages (une contribution sous Access, ça vous tente ? ) .

c'est une bonne idee, je vais tacher de voir si je peux faire un peu de pub.

-pirus.

[granquet]

bon, je connais strictement rien en html ... donc c'est pas gagné

menfin, je me suis essayé a votre petit concours. je pense pas gagner, j'ai fait ça en 20 minutes sans passer par les phases conception/algo ...

c'est tres sommaire, et ça m'etonnerais que ce soit optimisé ... mais bon ... suis debutant moi

c'est ici: http://82.243.81.8/html-parse.c
c'est donc trés sommaire et pas terrible, je reverrais surement ma copie.

real 0m0.084s
user 0m0.004s
sys 0m0.040s

compilé avec -march=athlon64 -O2 -pipe
avec un athlon 64 3000+ sous linux x86_64 sur la page: http://www.google.fr/search?q=href
(moyenne sur 3 essais)