Discussion :

[gasche]

- sans l'augmentation du tas mineur, l'écart augmente car la taille des continuations est importante et le GC est plus souvent appelé
- avec la 2 est meilleure mais de peu de chose

Tout à fait. Pour donner des chiffres, il y a trois fonctions "représentatives" de l'activité du GC, mark_slice, sweep_slice et caml_oldify_mopup. Pour un lancement sur 2_000_000 :
- mark_slice : 2) 223 appels, 3) 301 appels
- sweep_slice : 2) 144, 3) 188
- olidify : 2) 367, 3) 489

La version avec continuation fait plus travailler le GC.
Avec le tas augmenté, la 2 est meilleure, mais de "peu de choses" parce que les temps d'exécution sont courts. Il y a quand même au moins 20% de différences de performance, ce qui n'est pas négligeable (bien que pas pharaonique).
Cependant, la solution des continuations est tout de même moins bonne car elle utilise nettement plus de mémoire. Si j'augmente encore l'entrée (de 2_000_000 à 5_000_000), elle réclame vraiment trop de mémoire et son comportement devient erratique (freeze, Out_of_memory, tué par l'OS, etc.). Je n'ai pas les détails précis car la mesure de la consommation mémoire est délicate et je ne connais pas trop ce domaine. En gros, à partir d'un certain niveau, la consommation mémoire joue de toute façon sur les performances et la solution avec continuation devient beaucoup moins intéressante.
Ceci dit, la facilité de l'optimisation "tranches de 10" rend la version par continuations tout de même très pertinente.

Par ailleurs, il est possible de "réifier" les continuations en utilisant, au lieu d'une fermeture ocaml directement, un simple type algébrique modélisant cette fermeture (et plus légère en mémoire). C'est une transformation assez classique, et j'ai l'intuition (je n'ai pas vérifié mais si ça t'intéresse je peux toujours regarder (après manger)) qu'elle donnerait, à quelques manipulations équationnelles près, précisément le programme tail-récursif.

[Garulfo]

Tout à fait. Pour donner des chiffres, il y a trois fonctions "représentatives" de l'activité du GC, mark_slice, sweep_slice et caml_oldify_mopup. Pour un lancement sur 2_000_000 :
- mark_slice : 2) 223 appels, 3) 301 appels
- sweep_slice : 2) 144, 3) 188
- olidify : 2) 367, 3) 489

La version avec continuation fait plus travailler le GC.
Avec le tas augmenté, la 2 est meilleure, mais de "peu de choses" parce que les temps d'exécution sont courts. Il y a quand même au moins 20% de différences de performance, ce qui n'est pas négligeable (bien que pas pharaonique).
Cependant, la solution des continuations est tout de même moins bonne car elle utilise nettement plus de mémoire. Si j'augmente encore l'entrée (de 2_000_000 à 5_000_000), elle réclame vraiment trop de mémoire et son comportement devient erratique (freeze, Out_of_memory, tué par l'OS, etc.). Je n'ai pas les détails précis car la mesure de la consommation mémoire est délicate et je ne connais pas trop ce domaine. En gros, à partir d'un certain niveau, la consommation mémoire joue de toute façon sur les performances et la solution avec continuation devient beaucoup moins intéressante.
Ceci dit, la facilité de l'optimisation "tranches de 10" rend la version par continuations tout de même très pertinente.

Par ailleurs, il est possible de "réifier" les continuations en utilisant, au lieu d'une fermeture ocaml directement, un simple type algébrique modélisant cette fermeture (et plus légère en mémoire). C'est une transformation assez classique, et j'ai l'intuition (je n'ai pas vérifié mais si ça t'intéresse je peux toujours regarder (après manger)) qu'elle donnerait, à quelques manipulations équationnelles près, précisément le programme tail-récursif.

Effectivement ça m'intéresse. En fait donc, à partir d'un certain niveau, la méthode par continuation tombe sur les mêmes limitations que la récursivité naïve.

Il serait aussi intéressant de voir quel serait la puissance d'une version paresseuse de l'insert. Il doit bien exister un delay/force sous ocaml non? Je n'ai jamais explorer ça.

Sinon c'est 20% de plus... mais si ça reste 20% ce n'est pas très grave. Ça veut dire que fondamentalement ça se tient.

[gasche]

Pour la réification, voici le code de départ :

Code ocaml :

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

1
2
3
4
5
6
7
8
9
let insert_3 r x ys =
  let rec insert_aux r element liste k =
    if r = 0
    then k (element :: liste)
    else match liste with
    | [] -> failwith "insert"
    | t :: q -> insert_aux (r-1) element q (fun l -> k (t :: l))
  in
  insert_aux r x ys (fun x -> x)

Je remarque que l'on emploie manipule des continuations à deux endroits :
- au moment de l'appel initial on construit une "continuation identité", (fun x -> x)
- au moment de l'appel récursif, on dispose d'une continuation k et d'un élément t, et on construit une nouvelle continuation (fun li -> k (t :: li)) à partir de ces deux éléments

Je déclare donc un type algébrique pour modéliser concrètement ces continuations :

Code :

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

1
2
3
type 'a kont = 
| Id  (* continuation identité *)
| Kont of 'a kont * 'a  (* continuation crée à partir d'une continuation et d'un élément *)

Je découpe maintenant le calcul en deux fonctions. La première, build_kont, construit la continuation réifiée, et la deuxième, apply_kont, "applique" cette continuation (c'est à dire fait le calcul). Dans la version non-réifiée, on n'a pas d'apply-kont puisqu'on utilise directement l'application d'une fonction à son argument. Par analogie, on remplace la ligne

Code :

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

if r = 0 then k (element :: liste)

par :

Code :

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

if r = 0 then apply_kont k (element :: liste)

Voici la fonction build_kont :

Code :

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

1
2
3
4
5
6
  let rec build_kont r element liste k =
    if r = 0
    then apply_kont k (element :: liste)
    else match liste with
    | [] -> failwith "insert"
    | t :: q -> build_kont (r-1) element q (Kont (k, t))

C'est la même, j'ai juste directement remplacé (fun l -> k (t :: l)) par Kont (k, t).

Et voici apply_kont, selon la définition évidente :

Code :

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

1
2
3
and apply_kont k li = match k with
  | Id -> li
  | Kont (k, t) -> apply_kont k (t :: li)

Je transforme "Id" en l'identité, et je rappelle récursivement apply_kont sur (t :: li), de même que ma continuation non-réifiée relançait l'appel k (t :: li).


Dans un deuxième temps, je remarque (vous l'avez peut-être déjà vu avant, mais on ne peut pas révéler tout d'un coup, c'est moins drôle) que mon type de continuations est isomorphe au type des listes OCaml :

Code :

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

1
2
type 'a kont = Id | Kont of 'a kont * 'a
type 'a list = [] | :: of 'a * 'a list

On peut donc remplacer ma réification par des listes, en faisant attention à l'ordre de Kont, inversé par rapport à celui de :: :

Code :

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

1
2
3
4
5
6
7
8
9
let rec build_kont r element liste k =
  if r = 0
  then apply_kont k (element :: liste)
  else match liste with
  | [] -> failwith "insert"
  | t :: q -> build_kont (r-1) element q (t :: k)
and apply_kont k li = match k with
| [] -> li
| t :: k' -> apply_kont k' (t :: li)

On remarque maintenant que build_kont ressemble assez fortement à la version tail-rec :

Code :

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

1
2
3
4
5
6
7
let rec insert_aux r element liste tete =
    if r = 0
    then List.rev_append tete (element :: liste) 
    else match liste with
    | [] -> failwith "insert"
    | t :: q -> insert_aux (r-1) element q (t :: tete)
  in

On peut d'ailleurs jeter un oeil à l'implémentation de List.rev_append :

Code :

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

1
2
3
4
let rec rev_append l1 l2 =
  match l1 with
    [] -> l2
  | a :: l -> rev_append l (a :: l2)

C'est exactement apply_kont.

Donc en réifiant la version par continuations, j'arrive exactement à la version tail-récursive.

[gasche]

Il serait aussi intéressant de voir quel serait la puissance d'une version paresseuse de l'insert. Il doit bien exister un delay/force sous ocaml non? Je n'ai jamais explorer ça.

Il existe un lazy/force, mais je pense que la solution à explorer en premier est celle utilisant les flots (module Stream) :

Code :

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

1
2
3
4
5
6
7
let stream_insert r elem stream =
  Stream.from (fun k ->
                 if k < r then Some (Stream.next stream)
                 else if k = r then Some elem
                 else match Stream.peek stream with
                 | None -> None
                 | Some x -> Stream.junk stream; Some x)

Il n'y a pas de listes paresseuses dans la bibliothèques standard OCaml (mais il y a plusieurs bibliothèques tierces qui le proposent). J'imagine qu'en Haskell (et donc tout pareil avec une bibliothèque de listes paresseuses en OCaml), cela ressemble à ça :

Code :

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

insert r x li = take r li ++ [x] ++ drop r li

[Jedai]

Effectivement ça m'intéresse. En fait donc, à partir d'un certain niveau, la méthode par continuation tombe sur les mêmes limitations que la récursivité naïve.

Pas exactement non plus, la version par continuation est limité par la taille totale de la mémoire vive, alors que la version par récursion naïve est limitée par la taille de la pile. La première limitation est légitime (c'est le prix à payer pour ne pas vivre dans un univers imparfait), la seconde l'est beaucoup moins (surtout si on peut atteindre des limites bien supérieures avec une tail-rec).
Bien sûr la version par continuation est plus limitée que la rev_append, donc on peut considérer que de ce point de vue la rev_append est préférable.

Il serait aussi intéressant de voir quel serait la puissance d'une version paresseuse de l'insert. Il doit bien exister un delay/force sous ocaml non? Je n'ai jamais explorer ça.

Bonne question, je peux comparer avec Haskell : sans la modification du GC, la version naïve en Haskell enterre toutes les version en OCaml (complètement), mais avec la modif, on obtient des résultats un peu plus raisonnables avec Haskell un peu meilleur que la version par continuation, et un peu moins bon que la version par rev_append ou la version naïve en OCaml.

Je suis plutôt content du résultat : au final avec la version naïve en Haskell on obtient des performances tout à fait acceptables par rapport à OCaml (en supposant que le GC d'OCaml ait été tweaké sinon... ) et qui marche dans tous les cas de figure (pas de Stack Overflow), avec une consommation mémoire plus faible qu'aucune des solutions OCaml.

--
Jedaï

[Jedai]

Il n'y a pas de listes paresseuses dans la bibliothèques standard OCaml (mais il y a plusieurs bibliothèques tierces qui le proposent). J'imagine qu'en Haskell (et donc tout pareil avec une bibliothèque de listes paresseuses en OCaml), cela ressemble à ça :

Code :

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

insert r x li = take r li ++ [x] ++ drop r li

En fait je n'avais pas considéré cette version, on va l'appeler la "super-naïve", elle a des performances tout à fait correctes, bien que moins bonne que le naïf :

Code :

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

1
2
3
insert 0 x ys = x : ys
insert r x [] = []
insert r x (y:ys) = y : insert (r-1) x ys

--
Jedaï

[gasche]

Comment tu fais pour tester les performances du programme Haskell ?

[Garulfo]

Bon j'ai des TP de Scheme à produire -_- mais je reviendrais comme dirait le gouverneur de Californie.

(commentaire : 'sti que c'est chiant de faire du paresseux en ocaml...)

[gasche]

(commentaire : 'sti que c'est chiant de faire du paresseux en ocaml...)

Pas du tout. Modulo une légère extension de la syntaxe, tu peux faire du filtrage sur les valeurs paresseuses, et ça passe tout seul :

Code :

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

1
2
3
4
let rec (++) s t =
    lazy (match s with
            | lazy Nil -> force t
            | lazy (Cons (x, s')) -> Cons (x, s' ++ t))

Évidemment, c'est tout explicite, mais je trouve ça pas mal personnellement, dans certain cas c'est même très utile pour bien comprendre ce qu'on fait (j'avais vu un exemple de "circular programming" en Haskell, et c'est vachement plus facile à comprendre quand tu essaies en même temps de coder une version en OCaml qui marche).

[Garulfo]

Pas du tout. Modulo une légère extension de la syntaxe, tu peux faire du filtrage sur les valeurs paresseuses, et ça passe tout seul :

Code :

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

1
2
3
4
let rec (++) s t =
    lazy (match s with
            | lazy Nil -> force t
            | lazy (Cons (x, s')) -> Cons (x, s' ++ t))

Évidemment, c'est tout explicite, mais je trouve ça pas mal personnellement, dans certain cas c'est même très utile pour bien comprendre ce qu'on fait (j'avais vu un exemple de "circular programming" en Haskell, et c'est vachement plus facile à comprendre quand tu essaies en même temps de coder une version en OCaml qui marche).

On peut mettre des lazy dans les filtres ? Humm pas pire ça...
Quand je disais que c'était chiant c'était à cause du typage qui m'emmerde. En Scheme c'est plus simple et straightforward. C'est probablement un manque d'habitude de ma part.

[Garulfo]

Ça marche pas ton truc... ou bien j'ai raté un morceau.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
type 'a liste = Nil | Cons of 'a * 'a liste ;;
 
let consl a l = lazy ( Cons (a,l) ) 
and fstl l = match l with 
             | lazy (Cons (h,t)) -> h
             | else failwith "fstl : argument n'est pas une liste paresseuse"
and sndl l = match l with
             | lazy (Cons (h,t)) -> t 
             | else failwith "sndl : argument n'est pas une liste paresseuse"  
             ;;

Qu'ai-je donc raté ? Parce qu'a priori, je suppose que tu sais ce que tu m'as envoyé... donc je me suis trompé quelque part non ?

En tout cas, pour ça — liste paresseuse — je préfère le Scheme

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
(define (car-l L) (car (force L)))
(define (cdr-l L) (cdr (force L)))
(define (cons-l a L) (delay (cons a L)))
(define null-l (delay '()))
(define (null-l? L) (null? (force L)))
(define list-l 
  (lambda L (if (null? L) null-l (cons-l (car L) (apply list-l (cdr L)))))
  )
 
(define (get n L)
  (cond ((null? (force L)) '())
        ((= n 0) (car-l L))
        (else (get (1- n) (cdr-l L)))
        )
  )
 
(define (insert-l r x L)
  (cond ((= r 0) (cons-l x L))
        ((null-l? L) null-l)
        (else (cons-l (car-l L) (insert-l (1- r) x (cdr-l L))))
        )
  )

Le code de l'insert-l est le même que l'insert avec les versions lazy des opérateurs. Difficile de faire plus simple comme transformation.

[gasche]

On peut mettre des lazy dans les filtres ? Humm pas pire ça...

Désolé de ne pas avoir été plus explicite. La possibilité d'utiliser lazy dans des filtrages (où il a l'effet symétrique, c'est à dire de forcer la valeur filtrée) est apportée par une extension syntaxique utilisant camlp4 (le préprocesseur ocaml top moumoutte), LazyPattern (en fait ça fait partie de l'extension "patterns" qui ajoute un autre truc rigolo, mais c'est du détail)

Quand je disais que c'était chiant c'était à cause du typage qui m'emmerde. En Scheme c'est plus simple et straightforward. C'est probablement un manque d'habitude de ma part.

Ça me semble étrange, puisque le typage ne t'emmerde que s'il est incorrect (ou en tout cas qu'il n'arrive pas à l'inférer, parfois il y arrive, ça t'emmerde pas et ça foire :p ), ce qui est plutôt pratique quand tu manipules des trucs bizarres comme les valeurs paresseuses à mon avis.

Le code de l'insert-l est le même que l'insert avec les versions lazy des opérateurs. Difficile de faire plus simple comme transformation.

Bon déjà, ton code a une petite erreur : il faudrait englober le tout (ou au moins le "else") dans un "delay" supplémentaire : actuellement tu forces la tête de ta liste à l'appel de la fonction "insert", et le comportement n'est donc pas totalement paresseux.

Ensuite, le code est effectivement simple, et absolument reproductible en OCaml (avec l'extension syntaxique, encore) :

Code ocaml :

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

1
2
3
4
5
6
7
let cons_l hd tl = lazy (Cons (hd, tl))
 
let rec insert_l n x ys =
  if n = 0 then cons_l x ys
  else lazy (match Lazy.force ys with
               | Nil -> invalid_arg "insert_l"
               | (Cons (hd, tl)) -> cons_l hd (insert (n - 1) x tl))

(disclaimer : par manque de temps, aucun des codes de ce post n'a été testé. Merci de ne pas jeter de pierres trop grosses)

Par ailleurs, j'utilise ici des types algébriques personnels, ce qui est moins élégant que le sucre syntaxique pour les listes. Les vraies bibliothèques de listes paresseuses viennent parfois avec du sucre syntaxique (encore une fois camlp4 gling gling). De mémoire, cela donne quelque chose comme :

Code ocaml :

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

1
2
3
4
5
let rec insert n x ys =
   if n = 0 then [^ x :: ys ^]
   else lazy (match ys with
                | [^ ^] -> invalid_arg "insert_l"
                | [^  hd :: tl ^] -> [^ hd :: insert (n - 1) x tl ^])

Évidemment, avec les fonctions définies dans la lib en question (LList, issue de ça), tu peux écrire quelque chose d'encore plus proche du scheme :

Code ocaml :

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

1
2
3
4
let rec insert n x ys = lazy (
  if n = 0 then Cons (x, ys)
  else try Cons (hd ys, insert (n-1) x (tl ys))
        with LazyListFailure -> invalid_arg "insert")

Comblé ?

[Garulfo]

[...]
Bon déjà, ton code a une petite erreur : il faudrait englober le tout (ou au moins le "else") dans un "delay" supplémentaire : actuellement tu forces la tête de ta liste à l'appel de la fonction "insert", et le comportement n'est donc pas totalement paresseux.[...]

Je ne suis pas sûr de comprendre... la partie « else » est dans un delay.
L'opérateur est un cons-l et celui-ci est défini comme un (delay (cons ..)). La tête n'est donc pas forcée puisque contenue dans un delay. C'est uniquement quand tu l'évalueras que le force sera appliqué.

Exemple avec mon code

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
> (define liste-l (list-l 1 2 3 4 5 6 7 8 9))
> (define liste-inseree (insert-l 3 10 (list-l 1 2 3 4 5 6 7 8 9)))
> liste-inseree
#<struct:promise>
> (car-l liste-inseree)
1
> (get 3 liste-inseree)
10
> liste-l
#<struct:promise>
> (get 3 liste-l)
4

Peut être n'ai je pas compris ce que tu voulais dire ?
Pour faire ça bien il faudrait de toute façon faire des macros (donc utiliser des define-macro), car sinon les arguments sont évalués dès l'appel de la fonction (évaluation en ordre applicatif). Là aussi, il est plus simple de faire des macros en plt-scheme qu'en ocaml.

En tout cas...

[Garulfo]

[...]
Ça me semble étrange, puisque le typage ne t'emmerde que s'il est incorrect (ou en tout cas qu'il n'arrive pas à l'inférer, parfois il y arrive, ça t'emmerde pas et ça foire :p ), ce qui est plutôt pratique quand tu manipules des trucs bizarres comme les valeurs paresseuses à mon avis.
[...]
Ensuite, le code est effectivement simple, et absolument reproductible en OCaml (avec l'extension syntaxique, encore) :

Code ocaml :

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

1
2
3
4
5
6
7
let cons_l hd tl = lazy (Cons (hd, tl))
 
let rec insert_l n x ys =
  if n = 0 then cons_l x ys
  else lazy (match Lazy.force ys with
               | Nil -> invalid_arg "insert_l"
               | (Cons (hd, tl)) -> cons_l hd (insert (n - 1) x tl))

[...]

Code ocaml :

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

1
2
3
4
let rec insert n x ys = lazy (
  if n = 0 then Cons (x, ys)
  else try Cons (hd ys, insert (n-1) x (tl ys))
        with LazyListFailure -> invalid_arg "insert")

Comblé ?

Quand je dis que le typage m'emmerde c'est parce que j'ai besoin de faire appel à une construction que j'aurais voulu éviter. En Scheme j'utilise toujours des listes et des paires: une liste étant une paire. Si en ocaml tu essayes de mettre des « :: » comme pour la version non paresseuse, tu vas en baver aussi. Les nouveaux opérateurs de la version Scheme sont uniquement les opérateurs précédé de force ou delay selon le cas.


Donc l'emmerdement vient du fait que pour que ce soit correct il faille faire plus de blahblah qu'en Scheme. Certes il y a le gain de la fiabilité ; ce que je ne renie pas du tout et qui en vaut la chandelle.

[InOCamlWeTrust]

Aie ! Aie ! Aie !

Il faut penser ITERATEURS les mecs, vous avez pas compris la leçon !

Quand je vois certains codes, ça me fait sauter au plafond... bon, heureusement que c'est de l'expérimentation !

[Garulfo]

Aie ! Aie ! Aie !

Il faut penser ITERATEURS les mecs, vous avez pas compris la leçon ![...]

Puisque le problème s'insérait dans un cours — très probablement — je suppose qu'au contraire, tu n'as pas compris la leçon

Mais effectivement on expérimente là. Enfin moi je prenais ça ainsi.

Mais proposes quelque chose de magnifique ^_^ et dis ce que tu n'aimes pas. Ça sera intéressant.

[Garulfo]

[...]
Comblé ?

Je vais faire le chieur peut-être... mais t'aurais pas une versions sans l'extension ?

[Garulfo]

Ah bin finalement je l'ai

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
type 'a liste = Nil | Cons of 'a * 'a liste lazy_t;;
 
let consl a l = lazy ( Cons (a,l) ) 
and fstl l = match Lazy.force l with 
             | Cons (h,t) -> h
             | _ -> failwith "fstl : argument n'est pas une liste paresseuse"
and sndl l = match Lazy.force l with
             | Cons (h,t) -> t 
             | _ -> failwith "sndl : argument n'est pas une liste paresseuse"  
             ;;
 
let rec insert_lazy r x liste =
  if r = 0 
  then consl x liste
  else match (Lazy.force liste) with
     | Nil -> lazy Nil 
     | Cons (h,t) -> consl h (insert_lazy (r-1) x t)
;;

Par contre je ne saurais pas comment faire pour que ce soit de la « vrai » évaluation paresseuse. Pour ça il me faudrait des macros et je n'en ai jamais utilisé en ocaml. Pour la version Scheme, il suffit peu ou prou de remplacer les defines des fonctions de bases par des define-macros.