Les languages de haut niveau plus rapide que ceux de bas niveau - Page 2

./29> je n'ai jamais vu que le design pattern "iterator" parle de ce que tu fais des items que tu accèdes. Il définit une manière d'itérer, rien de plus.
Par ailleurs il ne s'agit pas dans ce cas d'itérateur mais d'une boucle sur un ensemble, ce qui est conceptuellement différent.

spectras a écrit :

ce que je voulait dire dans mon pavé mal foutu, c'est que ce que tu peut faire avec le "haut niveau", tu peut le faire aussi bien en "bas niveau" voir meme peut etre mieux car tu n'est pas bridé par le fonctionnement dudit haut niveau

Bien entendu. C'est toujours le même équilibre, aussi vieux que le premier assembleur : temps de développement / temps d'exécution.

Ça, c'est sûr, d'où l'existence de tous ces langages de programmation plus ou moins adaptés à ce que l'on veut faire.
Ainsi, mes 2 langages de prédilections sont l'Asm X86 et le PHP :[ul][li]quand les entrées se limitent à quelques touches sur le clavier, la sortie à quelques lignes à l'écran, mais avec vraiment beaucoup beaucoup de calculs à faire entre les deux Asm (les interfaces d'entrée/sortie en Asm, c'est la mort )
[li]quand les entrées sont compliquées (tableaux de taille variable) et de même pour la sortie (tableaux ou graphiques avec de la couleur pour mettre en évidence les points cherchés), mais avec un traitement pas trop long entre les deux PHP (les formulaires pour les entrées et les tableaux HTML pour la sortie, c'est le bonheur )[/ul]

GoldenCrystal a écrit :
Dans la façon dont je vois les choses, un algorithme exprimé en C, est l'expression de l'algorithme en lui même (souvent déjà optimisé par le cerveau humain... tiens donc le compilo C sait pas le faire à notre place ? ^^), et le même algorithme en un langage bien plus évolé, sera plus la représentation conceptuelle de l'algorithme que l'algorithme lui-même.

[...]

Et si je défends les hauts niveau sur le fait qu'ils simplifient la vie aux programmeurs, je les défends pas sur le fait de les rendre cons hein... Si tu vois une [vraie] optimisation à faire (simple qui plus est), alors fais là... Le compilateur l'aurait peut-être fait ou peut-être pas, mais là au moins tu sais que c'est fait. Parce que bon, avec des "le compilateur devrait" tu finis par faire des codeurs fainéants qui ne cherchent même pas l'optimisation, et le compilateur derrière ne doît jamais être une excuse pour ça.

J'ajouterai cependant une nuance dont je n'entends jamais parler : la différence entre algorithmie théorique et algorithmie pratique.
Prenons un cas simple déjà abordé, l'itération :[ul][li]en Java et autres langages de haut niveau (HLL), on va utiliser comme le dit si bien GC une représentation conceptuelle de l'algorithme d'itération en utilisant par exemple un Iterator si on travaille sur une Collection c'est de l'algorithmie conceptuelle
[li]en C (ce que j'appelerai un langage de niveau intermédiaire (MLL)) mais aussi en Java quand on travaille sur les types primitifs (int[] par exemple), on utilise une expression directe de l'algorithme avec une boucle for du genre for ( i = 0 ; i < N ; i ++ ) {...} sans effet de bord sur i ça reste selon moi de l'algorithmie théorique, puisque la théorie dit de parcourir les éléments du tableau, donc on parcourt les éléments du tableau
[li]en Asm == langage de bas niveau (LLL), on sait ce que donne la boucle for précédente (genre, en admettant que N est une constante strictement positive connue à l'assemblage (== compilation) : xor eax,eax | Boucle: | ... | inc eax | cmp eax, N | jl Boucle), et on connaît les flags lus et/ou mis à jour par les instructions : donc si, de manière pratique, l'algorithme peut être adapté à une lecture décroissante du tableau (ce qui est assez généralement le cas), alors il est plus efficace d'écrire mov eax, N | Boucle: | ... | dec eax | jge Boucle (quelques milliards de cmp eax, N en moins sur chaque boucle du programme, croyez-moi, on sens la différence) j'appelle ça de l'algorithmie pratique, on ne reste pas à l'algo théorique qui dit qu'il faut itérer sans préciser si le sens de parcours importe (auquel cas, très bêtement, tout le monde va parcourir dans le sens croissant )[/ul]
Et je trouve qu'il est important d'adapter pratiquement au langage cible l'algorithme théorique de base.
Ainsi, concrètement, j'ai pris il y a 2–3 ans l'algorithme de cryptage DES tel qu'il est donné dans le document descriptif officiel, et je l'ai retravaillé dans l'optique 'Asm pur', en réfléchissant à la représentation des données et aux instructions que j'allais utiliser, pour en faire un nouvel algo décrivant ce que j'allais faire en Asm. Voici textuellement le SMS que m'a envoyé squalyl le 27/07/2004 :

Cryptage DES d'un bloc avec 65536 clés, programme en C. version internet: Sans optimisation: 2273 ms, optimisé 631 ms. Version Ethaniel: Non opti: 1172 ms, opti: 611 ms... Je peux vous appeler maître?

Note : ce qu'il appelle 'optimisation' (je lui ai demandé après), c'est l'option -O de GCC.
D'ailleurs, il faudrait vraiment que je me remette à ce programme, surtout que j'ai trouvé à la même époque comment remplacer 2 instructions à 4µops (sur P4) par 4 instructions à 1µop deux fois moins de temps, et comme en plus il y a plus d'instructions, on peut mieux faire du pipe-lining \o/ !
Et il faudrait aussi que je passe en MMX, paske là tous mes registres normaux sont utilisés et ça me bloque parfois un peu...

Ethaniel :
(quelques milliards de cmp eax, N en moins sur chaque boucle du programme, croyez-moi, on sens la différence)

C'est toujours vrai sur les processeurs modernes ? Ca m'étonne énormément...

Voici textuellement le SMS que m'a envoyé squalyl le 27/07/2004 :

Cryptage DES d'un bloc avec 65536 clés, programme en C. version internet: Sans optimisation: 2273 ms, optimisé 631 ms. Version Ethaniel: Non opti: 1172 ms, opti: 611 ms... Je peux vous appeler maître?

Note : ce qu'il appelle 'optimisation' (je lui ai demandé après), c'est l'option -O de GCC.

Ben à part que tu as écrit du code qui utilise moins de variables intermédiaires, ton code n'est pas du tout plus efficace que le sien Mesurer l'optimisation sans -O c'est un peu idiot, parce que GCC n'essaye même pas de mettre les variables dans des registres et va rechercher chaque variable dans la pile à chaque accès Du coup des détails syntaxiques prennent une importance considérable alors qu'en pratique ils n'ont aucune influence sur le code généré en -O...

Moi je dit il faut tout optimiser en -O9 comme ça plus de problème de code

euh en java tu ne fais pas de l'algorithmie théorique, tu fais du java, même si le langage te permet d'implanter l'algorithme de façon assez proche du niveau conceptuel ça reste de la programmation... (et, euh, tu entends quoi par « algorithme d'itération » ?)

de l'algorithmique théorique c'est ça pour moi : l'algorithme de tri-fusion consiste à diviser une liste en deux sous-listes de taille égale (à 1 près évidemment), à trier chacune de ces deux sous-listes en appliquant l'algorithme récursivement, puis à les fusionner, sachant qu'elles sont triées, en une unique liste triée (la liste fusionnée est donc construite en prenant de façon répétée le plus petit des premiers éléments de chacune des deux listes pour l'ajouter à la fin de la liste en construction, jusqu'à ce que les deux listes de départ soient vides). Bon maintenant code-moi ça en java en moins de 3 secondes puisque java est directement au niveau conceptuel

edit : tiens juste pour information, voici ce que ça donne en caml (transcription directe sans optimisation) (enfin la fonction split j'ai pas spécifié comment on la faisait dans l'algorithme, là je prends toujours le premier élément de la liste de départ et je l'ajoute alternativement à l'une ou à l'autre des deux sous-listes en construction, jusqu'à ce que la liste soit vide). Mais en fait le code suivant fait partout des récursions non terminales qui vont complètement foirer sur des grosses listes, donc en pratique on ne fera *pas* comme ça :

let rec split = function
    [] -> ([], [])
  | x::suite -> let (l1, l2) = split suite in (l2, x::l1)

let rec merge l1 l2 = match (l1, l2) with
    [], l | l, [] -> l
  | x1::s1, x2::s2 -> if x1 < x2 then x1::merge s1 l2 else x2::merge s2 l1

let rec sort l = match l with
    [] | [_] -> l
  | _ -> let (l1, l2) = split l in merge (sort l1) (sort l2)

ba ya pas (encore) des editeurs de design pattern ou autres truc graphiques du genre ou tu dessine ton algo et il te fait ton prog a ta place ?

ben ça j'en sais rien, mais là il parlait du java ^^

Ethaniel > et en pratique en caml (qui est pourtant un langage de haut niveau, c'est pas pour ça qu'il n'y a pas de "pratique" ^^) la bonne façon d'implémenter l'algorithme consiste à trier la liste à l'envers une fois sur deux, ce qui s'écarte de l'algorithme tel que décrit en théorie mais optimise son exécution, bref l'opposition théorie/pratique n'est pas exactement la même que l'opposition haut niveau/bas niveau

Godzil :
ba ya pas (encore) des editeurs de design pattern ou autres truc graphiques du genre ou tu dessine ton algo et il te fait ton prog a ta place ?

(enfin n'empeche a pars ceux qui programment ce genre d'éditeur, sii ça marchais bien ça serais la mort du programmeur traditionnel...)

Sally :
Ethaniel > et en pratique en caml (qui est pourtant un langage de haut niveau, c'est pas pour ça qu'il n'y a pas de "pratique" ^^) la bonne façon d'implémenter l'algorithme consiste à trier la liste à l'envers une fois sur deux, ce qui s'écarte de l'algorithme tel que décrit en théorie mais optimise son exécution, bref l'opposition théorie/pratique n'est pas exactement la même que l'opposition haut niveau/bas niveau

non, si on voulait le faire en haut niveau de façon propre, on s'amuserait pas à (mal) réinventer la roue et on ferait :
list.to_lazy_binary_tree.bottom_up_traversal (fun leaf -> [leaf]) (fun [son1;son2] -> merge son1 son2)

Ce ne sont pas des primitives compliquées, par exemple en ruby on implémenterait les primitives bas niveau comme ça :

class Interval
  def left_half,right_half,singleton... # facile
end

class Array
  def to_lazy_binary_tree
    LazyTree.new(0...size) do |interval|
      interval.singleton ? [self[interval.singleton], nil] : [nil,[interval.left_half,interval.right_half]]
    end
  end
end

class LazyTree
  def initialize(root,&traversal)
    @traversal=traversal; @label,@children=traversal.call(root)
  end
  def bottom_up_traversal(leaf_fun,node_fun)
    if @children
      node_fun.call(@children.map{|value| LazyTree.new(value,&@traversal).bottom_up_traversal(leaf_fun,node_fun)})
    else
      leaf_fun.call(@label)
    end
  end
end

(d'ailleurs, on peut voir que c'est une implémentation qui est[*] très clairement plus efficace que la version classique Caml avec des listes chaînées... à bon entendeur )
(([*] : plus exactement, "serait" si ruby n'était pas interprété et typé dynamiquement ))


Et en plus ça se parallélise très facilement (en fait c'est déjà parallélisé : il suffirait que l'implémentation standard de "Array.map" soit capable de paralléliser toute seule pour que mon implémentation en profite automatiquement)

oui, enfin après, tout dépend ce que tu appelles le haut niveau évidemment... et puis ça n'infirme pas ce que j'ai dit sur l'opposition théorie/pratique : dans la description théorique de l'algorithme il n'y a pas d'arbre, donc en pratique tu ne transcris pas directement l'algorithme tel que décrit. Après je n'ai pas dit que l'implémentation dont je parle était la meilleure (bon ok, j'ai dit la « bonne », j'aurais dû dire « une meilleure » (que la transcription directe), mea culpa)

(par contre j'arrive pas à voir pourquoi ton implémentation est plus efficace, mais ça doit être parce que je ne comprends pas le ruby)

Ben si, il y a implicitement un arbre des récursions...

(c'est plus efficace parce que tes splits s'amusent à lire tout le tableau, le couper en deux, le reconstruire en recopiant tout, etc... ; ma version travaille juste sur des sous-intervalles de l'ensemble des indices du tableau, et ne touche au contenu du tableau que quand on a atteint une feuille)

Oui c'est ce que j'ai dit (enfin non je l'ai effacé en fait apparemment ), mais bon tu fais quand même une traduction assez poussée en remplaçant « on rappelle l'algorithme récursivement » par « on parcourt un arbre » ; en fait tu décides de te placer à un niveau supérieur à celui de l'algorithme que j'ai décrit, d'une certaine façon... enfin je sais pas.

(sinon, ben j'ai pas un tableau, j'ai une liste, donc je peux pas accéder comme ça paf à l'élément d'indice i, je suis bien obligé de parcourir. Mais dans l'implémentation standard ils font pas vraiment le split en fait, ils passent en paramètre le nombre d'éléments à considérer et c'est seulement pour la partie droite qu'ils sont obligés de parcourir la moitié de la liste avant de faire l'appel récursif, par contre la liste n'est jamais coupée en morceaux en fait (il y a juste des pointeurs à des endroits différents de la liste). Ça me semble optimal étant donnée la structure de données, même si je peux me tromper. Bon là je parle de List.sort, après il y a aussi Array.stable_sort sinon mais j'ai la flemme de comprendre comment c'est foutu )

Sally
: en fait tu décides de te placer à un niveau supérieur à celui de l'algorithme que j'ai décrit, d'une certaine façon... enfin je sais pas.

Ben oui exactement, c'est ce que j'ai dit

(sinon, ben j'ai pas un tableau, j'ai une liste, donc je peux pas accéder comme ça paf à l'élément d'indice i, je suis bien obligé de parcourir. Mais dans l'implémentation standard ils font pas vraiment le split en fait, ils passent en paramètre le nombre d'éléments à considérer et c'est seulement pour la partie droite qu'ils sont obligés de parcourir la moitié de la liste avant de faire l'appel récursif, par contre la liste n'est jamais coupée en morceaux en fait (il y a juste des pointeurs à des endroits différents de la liste). Ça me semble optimal étant donnée la structure de données, même si je peux me tromper. Bon là je parle de List.sort, après il y a aussi Array.stable_sort sinon mais j'ai la flemme de comprendre comment c'est foutu )

Oui, évidemment avec une structure pourrie comme une liste on peut pas faire de miracle (et encore j'ai pas parlé des problèmes de localité mémoire ou d'overhead lié au fait que chaque élément est muni d'un pointeur ), mais si Caml choisit la liste comme structure de donnée principale c'est bien parce que c'est facile d'y accéder récursivement en bas niveau... Alors que si on se place à plus haut niveau ce besoin disparaît

Sally a écrit :
de l'algorithmique théorique c'est ça pour moi : l'algorithme de tri-fusion consiste à diviser une liste en deux sous-listes de taille égale (à 1 près évidemment), à trier chacune de ces deux sous-listes en appliquant l'algorithme récursivement, puis à les fusionner, sachant qu'elles sont triées, en une unique liste triée (la liste fusionnée est donc construite en prenant de façon répétée le plus petit des premiers éléments de chacune des deux listes pour l'ajouter à la fin de la liste en construction, jusqu'à ce que les deux listes de départ soient vides). Bon maintenant code-moi ça en java en moins de 3 secondes puisque java est directement au niveau conceptuel

Oui, moi aussi je classe le tri fusion en 'théorique'.
Et je n'ai pas dis que Java était au niveau conceptuel, mais permettait le niveau conceptuel.
Sinon, en 3 secondes : Arrays.sort( tab ) ;

Demander à faire du tri-fusion, c'est de l'algorithmie théorique (selon mes termes ), demander à faire du tri (sans plus de précision), c'est de l'algorithmie conceptuelle, l'implémentation spécifique du tri ayant déjà été faite dans les librairies du langage considéré.
Et si tu m'imposes de faire vraiment du tri-fusion et pas un autre tri en Java, c'est-à-dire de passer du niveau conceptuel au niveau théorique, alors tu conviendras avec moi que j'utiliserai au maximum les types primitifs de Java... ce que je classe justement au point 2, celui des MLL et de l'algorithmie théorique !
Huhu, bien tenté, mais quand même, çay Loupay !

Pollux
:

Ethaniel :
(quelques milliards de cmp eax, N en moins sur chaque boucle du programme, croyez-moi, on sens la différence)

C'est toujours vrai sur les processeurs modernes ? Ca m'étonne énormément...

This algorithm offers guaranteed n*log(n) performance.

Je me demande bien comment ils font leur compte ?

http://www.clubic.com/article-36354-3-le-pentium-laisse-la-place-intel-core-2-duo.html ?

./46> Hmmm en fait ils se permettent de faire le tri dans un espace temporaire. ^^

Ouch, j'espère que tu trie pas une base de quelques millions de lignes

./44 > euh si tu dis juste "je trie" sans dire comment tu le fais c'est pas de l'algorithmie du tout ... à mon avis ton terme d'algorithmie conceptuelle est complètement erroné, m'enfin moi je parlais effectivement de ce que tu appelles l'algorithmie théorique, et je disais que pour moi la théorie c'est l'expression de l'algorithme indépendamment du langage : si tu implantes ton algo en java, ce n'est plus de l'algorithmie théorique, c'est de la programmation ; et que tu utilises un langage de bas ou de haut niveau n'empêche pas que tu puisses t'écarter plus ou moins de l'algorithme théorique dans son implantation, c'est-à-dire que pour moi l'opposition théorie/pratique n'est pas la même que l'opposition haut niveau/bas niveau...

sinon je ne vois pas pourquoi tu devrais utiliser les types primitifs de java pour faire le tri-fusion , au contraire tu peux l'implanter de façon complètement générique avec des interfaces, t'as une interface Liste avec des méthodes d'accès/de construction, une interface Comparable qui te permet de comparer les éléments entre eux (avec une méthode compare donc) et tu peux coder le tri-fusion avec ça, où est-ce que tu as besoin de types primitifs (cc) ??

Ethaniel :
j'appelle ça de l'algorithmie pratique, on ne reste pas à l'algo théorique qui dit qu'il faut itérer sans préciser si le sens de parcours importe (auquel cas, très bêtement, tout le monde va parcourir dans le sens croissant )

Oui sauf que c'est débile d'imposer un sens de parcours quand y en a pas besoin, parce que le jour où tu veux paralléliser ton prog bah t'es baisé.

enfin c'est quand même un peu plus compliqué que ça, si y a pas de dépendance entre deux itérations de la boucle peu importe que tu imposes le sens de parcours, et si y a des dépendances entre tes données il faut de toute façon préciser explicitement que cette dépendance ne change pas la correction de ton résultat... je pense que c'est ce que tu voulais dire, mais disons que le point important n'est pas d'imposer le sens de parcours ou pas, mais plutôt d'avoir une structure qui permette de changer facilement vers un parcours parallèle (c'est ce que font les itérateurs, par exemple : typiquement ils parcourent dans le sens croissant, mais tu peux trivialement remplacer cet itérateur par un autre qui fait un parcours parallèle)

Pollux
: enfin c'est quand même un peu plus compliqué que ça, si y a pas de dépendance entre deux itérations de la boucle peu importe que tu imposes le sens de parcours, et si y a des dépendances entre tes données il faut de toute façon préciser explicitement que cette dépendance ne change pas la correction de ton résultat...

Ah non, pas forcément. Enfin ça doit dépendre des langages mais en scheme par exemple dans la doc de référence il est spécifié que map ne garantit pas l'ordre d'éxécution, et si tu veux avoir le bon ordre tu dois faire un map-in-order ou un truc du genre. C'est donc quand tu veux un parcours ordonné qu'il faut le spécifier.

ah, marrant ^^ mais concrètement, sur une machine mono-processeur, il l'exécute de manière séquentielle ?

petite note: Je vous rappelle qu'en OCaml, actuellement, les threads sont des faux threads (avec un mutex global, les threads caml ne s'exécutent donc pas en même temps) et que donc, actuellement, paralléliser du code OCaml est illusoire

il faut utiliser JoCaml de toute façon

Pollux :
ah, marrant ^^ mais concrètement, sur une machine mono-processeur, il l'exécute de manière séquentielle ?

probablement. en fait c'est pas vraiment la doc de référence, c'est plutôt la spec, donc après chacun l'implémente comme il veut.

library procedure: (map proc list1 list2 ...)

The lists must be lists, and proc must be a procedure taking as many arguments as there are lists and returning a single value. If more than one list is given, then they must all be the same length. Map applies proc element-wise to the elements of the lists and returns a list of the results, in order. The dynamic order in which proc is applied to the elements of the lists is unspecified.

(map cadr '((a b) (d e) (g h)))   
                ===>  (b e h)
(map (lambda (n) (expt n n))
     '(1 2 3 4 5))                
                ===>  (1 4 27 256 3125)
(map + '(1 2 3) '(4 5 6))                 ===>  (5 7 9)
(let ((count 0))
  (map (lambda (ignored)
         (set! count (+ count 1))
         count)
       '(a b)))                         ===>  (1 2) or (2 1)

(Source : Revised⁵ Report on the Algorithmic Language Scheme)

euh, si leur exemple est pas buggé je trouve ça carrément tordu comme truc : il a le droit d'appliquer les fonctions dans l'ordre qu'il veut, mais il a pas le droit de paralléliser l'exécution des fonctions
(parce que sinon c'est tout à fait possible si les fonctions sont exécutées en parallèle que le dernier exemple renvoie (1 1))

Je pense qu'ils ne l'ont pas mis pour ne pas confuser le lecteur peu au courant des histoires de concurrence et de race conditions mais que c'est effectivement un résultat possible. (enfin seulement si l'ordre d'évaluation des multiple values n'est pas spécifié non plus (je ne sais pas si c'est le cas ou pas), sinon (1 1) n'est pas possible mais (2 2) si)