Discussion :

[hortensiass]

Bonjour,
J'ai un probleme en caml light.
Pour un programme je dois insérer un élément dans un tableau pour cela je le coupe en deux avec la fonction sub_vect avec deux fonctions auxilliaires

Code :

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

1
2
3
4
5
6
let aux1 (t:int vect) (i:int)=
sub_vect t 0 i;;
cette fonction ne pose pas de problème, par contre, pour la deuxieme
let aux2 (t:int vect) (i:int)=
let p=vect_length t in
sub_vect t i+1 p-2-i;;

il semble y avoir un probleme de type car il me renvoit à propos de sub_vect... cette expression est de type int->int vect mais est utilisée avec le type int.
merci d'avance

[gorgonite]

et comme cela ?

Code :

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

sub_vect t (i+1) (p-2-i)

[hortensiass]

merci beaucoup et désolée pour cette question!

[InOCamlWeTrust]

Petite remarque : on ne coupe JAMAIS un tableau pour y insérer un élément. C'est une habitude de bonne programmation/algorithmie : si tu dois faire ainsi, ça veut dire que tu n'utilises pas le tableau comme il faut. C'est justement l'une des principales caractéristiques des tableaux : pouvoir accéder à un élément quelconque, à la différence des listes.

[phryte]

merci beaucoup et désolée pour cette question!

Où insérer l'élément ? à un rang ?
voici une réponse possible avec une liste v, (insérer x au rang r) :

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
let v=1::2::3::4::5::[];;
let r=1;;
let rec insert x = fun 
   [] -> [] 
  | (a::q) -> (
      if list_length q = (list_length v)-r 
      then x::a::q 
      else a :: (insert x q)
    )
;;
insert 9 v;;
 
let rec insert1 x = function
[] -> [x]
| t::q when list_length q = list_length v -r -> x::t::q
| t::q -> t :: (insert1 x q);;
insert1 9 v;;

[Jedai]

Où insérer l'élément ? à un rang ?
voici une réponse possible avec une liste v, (insérer x au rang r) :

Sauf que : ta liste v est fixe, ton rang aussi, tu utilises 2 list_length à chaque itération... En bref ton algo est en O(r*n) et ton implémentation n'est pas pratique à réutiliser.

Une solution en O(r) et réutilisable :

Code :

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

1
2
3
4
5
6
let rec insert r x ys = 
  if r = 0 
  then x :: ys 
  else match ys with
    | [] -> []
    | t :: q -> t :: insert (r-1) x q

--
Jedaï

[Garulfo]

Allez hop.. deux autres versions.

Une tail-recursive

Code :

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

1
2
3
4
5
6
7
8
9
10
11
let insert_2 r x ys = 
    let rec insert_aux r element liste tete =
        if r = 0
        then List.rev_append tete (element :: liste) 
        else match liste with
            | [] -> ys
            | t :: q -> insert_aux (r-1) element q (t :: tete)
    in
        insert_aux r x ys []
    ;;

et une par continuation

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
            | [] -> ys
            | t :: q -> let k0 = fun l -> (k (t::l))
                        in
                            insert_aux (r-1) element q k0
    in
        insert_aux r x ys (fun x -> x)
    ;;

[Jedai]

Sympa
La meilleure en OCaml serait la deuxième solution, sans doute la plus efficace (bien que la première puisse être plus efficace pour des r raisonnables). En Haskell la première solution serait parfaitement efficace et ne ferait jamais de stack overflow (petite conséquence de l'évaluation paresseuse, tout comme le map en Haskell n'échoue jamais).

--
Jedaï

[gasche]

En cas de besoin de performances maladif sur cette fonction précise, on peut sans doute faire encore mieux (je parie sur 4 à 8 fois plus vite tant que les paramètres du GC ne changent pas) en utilisant des manipulations localement impures sur les listes, à la manière de Extlib (qui code par exemple map en récursif terminal en une seule passe).

[Garulfo]

Sympa
La meilleure en OCaml serait la deuxième solution, sans doute la plus efficace (bien que la première puisse être plus efficace pour des r raisonnables). En Haskell la première solution serait parfaitement efficace et ne ferait jamais de stack overflow (petite conséquence de l'évaluation paresseuse, tout comme le map en Haskell n'échoue jamais).

--
Jedaï

Il y a une erreur dans ma troisième... pour le cas où r dépasse la taille de la liste.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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
            | [] -> ys
            | t :: q -> let k0 = fun l -> (k (t::l))
                        in
                            insert_aux (r-1) element q k0
    in
        insert_aux r x ys (fun x -> x)
    ;;

Par curiosité, plus qu'autre chose, comment sais-tu que la troisième est moins efficace que la première ? Elle est tail-recursive et évites de faire le rev_append supplémentaire de la deuxième. La perte en mémoire correspond à celle qu'on aurait sur la pile. A priori donc la troisième est plus intéressante que la deuxième je dirais, car si on aboutit au cas d'erreur, la fonction s'arrête directement après avoir dépassé la liste vide et boycott tous les autres appels. C'est la force de la continuation de pouvoir faire des raccourcis qui interrompt directement un calcul (à la goto). Ça serait mieux avec un call/cc mais j'ai lu que celui d'ocaml n'était pas implémenté pour être efficace et était déconseillé... peut être que ça a changé cependant.

[Jedai]

En cas de besoin de performances maladif sur cette fonction précise, on peut sans doute faire encore mieux (je parie sur 4 à 8 fois plus vite tant que les paramètres du GC ne changent pas) en utilisant des manipulations localement impures sur les listes, à la manière de Extlib (qui code par exemple map en récursif terminal en une seule passe).

Tu es certain que c'est plus performant ? C'est plus sûr en cela que tu ne risques pas de Stack Overflow mais plus performant (c'est vrai que c'est de la tail-rec...) ? Il y a des benchs ?

--
Jedaï

[Jedai]

Par curiosité, plus qu'autre chose, comment sais-tu que la troisième est moins efficace que la première ? Elle est tail-recursive et évites de faire le rev_append supplémentaire de la deuxième. La perte en mémoire correspond à celle qu'on aurait sur la pile. A priori donc la troisième est plus intéressante que la deuxième je dirais, car si on aboutit au cas d'erreur, la fonction s'arrête directement après avoir dépassé la liste vide et boycott tous les autres appels. C'est la force de la continuation de pouvoir faire des raccourcis qui interrompt directement un calcul (à la goto).

Tu peux faire exactement la même chose sur la deuxième (d'ailleurs il y a la même erreur), par ailleurs tu fais le rev_append dans la troisième, c'est juste qu'il est exprimé autrement (par une pile de fonctions à appliquer) et de façon moins économe à mon avis (dans la première tu empiles des appels dans la pile, dans la deuxième tu empiles des éléments dans le tas, dans la troisième tu empiles des closures dans le tas).

Mais bien sûr, il faudrait faire des benchs de ces trois solutions pour réellement savoir, là nous ne faisons qu'agiter de l'air.

(Je ne savais même pas que OCaml avait un call/cc, c'est une extension ?)

--
Jedaï

[Garulfo]

Tu peux faire exactement la même chose sur la deuxième (d'ailleurs il y a la même erreur)

Pour la deuxième oui... c'est pour la première que je disais que c'était moins performant. En fait je ne remet pas en cause que 2 est mieux ; mais je dirais plutôt que 3 est mieux que 1. Dans mon message je ne voulais pas comparer 3 et 2, c'est une erreur de ma part. Le 3 est tail-rec et a la possibilité d'abandonner les calculs en cours de route. En général c'est même plus puissant que la version 2 puisqu'on contrôle encore mieux le flot... mais ici ça ne change rien. En tout cas, si on ne gagne pas en mémoire vis-à-vis de 1, on gagne en efficacité je pense. Une simple trace devrait nous le montrer.

J'ai corrigé l'erreur dans le message d'origine. Merci.

(Je ne savais même pas que OCaml avait un call/cc, c'est une extension ?)

C'est sur la page de Xavier Leroy.
http://pauillac.inria.fr/~xleroy/software.html#callcc
mais comme il le dit

This is a very naive implementation: it works only in bytecode, and performance is terrible (call/cc copies the whole stack). It is intended for educational and experimental purposes. Use in production code is not advised.

[Jedai]

En tout cas, si on ne gagne pas en mémoire vis-à-vis de 1, on gagne en efficacité je pense.

Je ne suis pas sûr... Bien évidemment si on insère après la fin de la liste, la troisième est plus efficace, néanmoins la plupart du temps on cherche à insérer dans la liste, pas au-delà de sa fin. Dans un usage normal de la fonction, ce facteur ne compte peut-être pas autant qu'on pourrait le penser.
D'un autre côté, l'allocation et la désallocation dans la pile sont essentiellement gratuite, et dans les deux cas, si on insère vraiment, il y a à peu près autant de fonctions empilées et à exécuter (et désallouer) à la fin, donc je ne vois pas pourquoi la troisième solution serait plus efficace.

La troisième fonction est tail-rec, ce qui signifie qu'au moins elle est plus robuste que la première, mais je pense que c'est son seul avantage.

--
Jedaï

[Jedai]

Par curiosité, j'ai fait un petit bench très imprécis, il en ressort tout de même que "insert" est la plus rapide dans tous les cas où elle s'applique, "insert_2" et "insert_3" sont jusqu'à deux fois plus lent pour des r assez petits (20000 par exemple), insert_2 s'améliore par rapport à insert quand r grandit (sans en rejoindre les performances), mais insert_3 continue à être 2 fois plus lent.

Comme je m'y attendais la fonction naïve insert est la plus performante (dans le cas courant où on insère dans la liste, sinon il est moins performant) et le surcoût des continuations rend insert_3 la plus lente.

La fonction suivante est un peu meilleure que insert, et elle doit moins vite remplir la pile :

Code :

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

1
2
3
4
5
6
7
8
let insert_4 r x ys =
  let rec insert_aux r ys = 
    if r = 0 
    then x :: ys 
    else match ys with
      | [] -> []
      | t :: q -> t :: insert_aux (r-1) q
  in insert_aux r ys

--
Jedaï

[Garulfo]

[...]
Comme je m'y attendais la fonction naïve insert est la plus performante (dans le cas courant où on insère dans la liste, sinon il est moins performant) et le surcoût des continuations rend insert_3 la plus lente.

Ok... donc la création des fermetures couterait donc très cher en temps. Intéressant.

[Jedai]

Ok... donc la création des fermetures couterait donc très cher en temps. Intéressant.

Je ne suis pas sûr que ce soit la création des fermetures elle-même qui soit coûteuse, le fait que insert_3 est aussi rapide que insert_2 pour des petites valeurs de r (~ 20000) semble montrer le contraire. Je pense plutôt que l'espace nécessaire pour stocker une fermeture est nettement plus important que pour stocker un simple maillon d'une liste (la valeur contenue est stockée pareillement dans les deux cas), ce qui expliquerait la dégradation des performances lorsqu'on commence à en stocker beaucoup.

--
Jedaï

[Garulfo]

Je ne suis pas sûr que ce soit la création des fermetures elle-même qui soit coûteuse, le fait que insert_3 est aussi rapide que insert_2 pour des petites valeurs de r (~ 20000) semble montrer le contraire. Je pense plutôt que l'espace nécessaire pour stocker une fermeture est nettement plus important que pour stocker un simple maillon d'une liste (la valeur contenue est stockée pareillement dans les deux cas), ce qui expliquerait la dégradation des performances lorsqu'on commence à en stocker beaucoup.

--
Jedaï

C'est ce que j'entendais par la création est coûteuse. Ce n'était pas le moment même de la création. Mais le fait d'utiliser une fermeture. J'aurais donc du utiliser ce mot

J'avoue que je ne comprends pas bien pourquoi le fait d'avoir consommé plus d'espace nuit à ce point à la vitesse d'exécution: c'est dû à la vitesse d'accés sur la pile c'est ça ?

[gasche]

Lala, je suis beau, j'ai fait des benchmarks et voici mes fantastiques résultats.

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
23
24
25
26
27
28
29
30
(* version naïve, marche pour n petit *)
let rec insert r x ys = 
  if r = 0 
  then x :: ys 
  else match ys with
  | [] -> []
  | t :: q -> t :: insert (r-1) x q
 
 
(* version tail-rec simple *) 
let insert_2 r x ys = 
  let rec insert_aux r element liste tete =
    if r = 0
    then List.rev_append tete (element :: liste) 
    else match liste with
    | [] -> ys
    | t :: q -> insert_aux (r-1) element q (t :: tete)
  in
  insert_aux r x ys []
 
(* version par continuations *)
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
    | [] -> ys  
    | t :: q -> insert_aux (r-1) element q (fun l -> k (t :: l))
  in
  insert_aux r x ys (fun x -> x)

Voici les trois versions de départ.

Dans tout le reste du post, je donne en paramètre le nombre désignant la place à laquelle on insère. Toutes les mesures sont faites en natif, sur mon PC (seulement 512 Mo de ram).

Les tests de base

Comme Jedai l'a montré, la première version est la plus rapide pour des petits listes. Ensuite, les deux autres versions (tail-rec et continuations) sont à peu près équivalentes, mais au bout d'un moment la première devient plus rapide. Pour 3_000_000 (les chiffres que je donne sont la position où insérer dans la liste, et tous les tests sont fait en natif) :
- insert_2 : 3.2s
- insert_3 : 3.6s


Le poids du GC, le choc du tas mineur
Un rapide profiling montre que les temps d'exécution sont largement dominés par le GC. Apercu de sortie de gprof pour insert_2 (c'est pareil pour l'autre) :

% cumulative self self total
time seconds seconds calls s/call s/call name
37.34 0.87 0.87 329 0.00 0.00 mark_slice
15.88 1.24 0.37 222 0.00 0.00 sweep_slice
12.66 1.53 0.29 5992770 0.00 0.00 caml_oldify_one
10.30 1.77 0.24 5992722 0.00 0.00 caml_alloc_shr
9.23 1.99 0.21 551 0.00 0.00 caml_oldify_mopup
4.94 2.10 0.12 5992995 0.00 0.00 caml_fl_allocate
4.29 2.21 0.10 1 0.10 1.20 camlList__rev_append_79

Comment régler le problème ? Il y a des moyens plus ou moins subtil, mais j'ai pris la position suivante : je veux mesurer les performances de ma fonction, et je vais considérer que je n'ai pas de restrictions au niveau de la mémoire. Je peux donc faire exploser la taille de mon tas mineur en tout honnêteté.
À l'aide de la variable OCAMLRUNPARAM, j'ai augmenté progressivement la contenance du tas mineur (le truc qui contient les objets de la génération jeune du GC). Les résultats sont plutôt impressionnant (la valeur par défaut est 256K, ou 512K, je ne sais pas. Je commence à 1M), voyez plutôt :

[bluestorm@myhost Prog]$ time echo 2 3_000_000 | OCAMLRUNPARAM="" ./test.nat
real 0m3.186s
[bluestorm@myhost Prog]$ time echo 2 3_000_000 | OCAMLRUNPARAM="s=1M" ./test.nat
real 0m2.990s
[bluestorm@myhost Prog]$ time echo 2 3_000_000 | OCAMLRUNPARAM="s=5M" ./test.nat
real 0m1.752s
[bluestorm@myhost Prog]$ time echo 2 3_000_000 | OCAMLRUNPARAM="s=10M" ./test.nat
real 0m1.340s
[bluestorm@myhost Prog]$ time echo 2 3_000_000 | OCAMLRUNPARAM="s=20M" ./test.nat
real 0m0.283s

Au delà de 30M, la fête est finie, ça ne s'améliore plus : toutes les allocations du programme se font dans le tas mineur, rien ne passe dans le tas majeur, et le coût lié au GC a donc complètement disparu :

time seconds seconds calls ms/call ms/call name
52.94 0.09 0.09 1 90.00 90.00 camlInsert__insert_aux_68
47.06 0.17 0.08 1 80.00 80.00 camlList__rev_append_79

Une fois que le bruit lié au GC a disparu, la différence entre récursion naïve et continuations est toujours nette. Pour 3_000_000 :
- insert_2 : 0.250s
- insert_3 : 0.310s


Une optimisation efficace : traiter la liste par tranches

Ce qui ralentit les deux versions, c'est la quantité d'opérations qui est faite. La deuxième est particulièrement pénalisée parce que le coût d'application d'une fermeture est plus élevé que celui de l'allocation de listes (même si avec les listes on a en pratique deux passages du fait du rev_append), comme l'avait supposé Jedai, à ceci près que le coût semble se passer sur l'appel (en chaîne) des fermetures construites, et pas sur leur allocation :

time seconds seconds calls ms/call ms/call name
66.67 0.08 0.08 1 80.00 80.00 camlInsert__insert_aux_79
33.33 0.12 0.04 2000000 0.00 0.00 camlInsert__fun_305

Ma méthode dans ce cas est de limiter le nom de closures construites. Comment faire ? Actuellement on construit une closure par élément de la liste. On pourrait closure une closure pour plusieurs éléments de la liste.

Aussitôt dit, aussitôt fait, voici une modification hideuse qui manipule les éléments de la liste 10 par 10 :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
(* version par continuations, tranches de 10 *)
let insert_4 r x ys =
  let rec insert_aux r element liste k =
    if r = 0
    then k (element :: liste)
    else match liste with
    | [] -> ys
    | a::b::c::d::e::
      f::g::h::i::j:: q -> insert_aux (r-10) element q
        (fun l -> k (a::b::c::d::e:: f::g::h::i::j:: l))
    | t :: q -> insert_aux (r-1) element q (fun l -> k (t :: l))
  in
  insert_aux r x ys (fun x -> x)

Cette version est tout de suite beaucoup plus rapide (toujours sur 3_000_000) :
- insert_2 : 0.240s (tailrec)
- insert_3 : 0.310s (continuations)
- insert_4 : 0.160s (continuations par tranches de 10)

Plus rapide que la version tail_rec ! J'ai l'impression que cette optimisation n'est pas applicable tel quel à la version tail_rec à cause du rev_append qui procède élément par élément de toute façon (mais on pourrait recoder rev_append aussi, remarque). Bref, je n'ai pas montré la supériorité des continuations (puisque cette optimisation n'est pas continuation-spécifique), mais il faut bien reconnaître que la version avec continuations est plus facile à optimiser de la sorte.

J'ai aussi écrit une version par tranches de 20 (beurk !). C'est un peu plus rapide mais pas tellement (0.150 s). On pourrait écrire un programme camlp4 remplaçant l'immonde couple matching/application de 10 éléments par une élégante macro, mais je me suis arrêté là dans cette voie.


Plongée dans l'horreur : les manipulations unsafe

Tu es certain que c'est plus performant ? C'est plus sûr en cela que tu ne risques pas de Stack Overflow mais plus performant (c'est vrai que c'est de la tail-rec...) ? Il y a des benchs ?

Motivé par l'incrédulité de Jedai, j'ai décidé de me salir les mains. L'idée c'est en gros d'implémenter setcdr en Caml (accrochez bien votre serviette).

Ma première approche a été d'utiliser directement le module Obj, de façon similaire au machin ésotérique et intéressant que j'ai trouvé sur ce blog. Attention les yeux :

Code ocaml :

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

1
2
3
4
5
let setcdr (li : 'a list) (tl : 'a list) =
  if li = [] then invalid_arg "setcdr";
  let o = Obj.repr li in
  Obj.set_field o 1 (Obj.repr tl);
  tl

setcdr li tl modifie brutalement li pour que sa queue soit tl, et renvoie tl.

Code ocaml :

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

1
2
3
4
5
6
7
8
9
10
11
let insert_6 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let res = [y] in
    let rec ins r res = function
    | tail when r = 0 -> ignore (setcdr res (x::tail))
    | [] -> invalid_arg "insert"
    | y::ys -> ins (r - 1) (setcdr res [y]) ys in
    ins (r - 1) res ys;
    res

Le code est assez bizarre au départ, mais pas trop compliqué en pratique.

On commence par créer une liste 'res' qui contient uniquement le premier élément de la liste, dans laquelle on veut insérer l'élément. Ensuite, on itère sur la liste où insérer, et on rajoute chaque élément à la queue de la liste 'res'. Quand on a rajouté r élément (en pratique on en ajoute r-1 parce que le premier a été ajouté à la création de 'res'), on colle l'élément à insérer puis la queue de la liste où insérer. On renvoie enfin la liste "res".
Ce code est haskeller-proof, parce que la liste dans laquelle on veut insérer n'est jamais modifiée. Les seules listes sur lesquelles on applique l'infâme setcdr sont les listes créées localement dans la fonction, à commencer par "res". De l'extérieur, cette fonction est donc bien fonctionnelle pure.

Pour ce qui est des performances, les résultats sont à première vue assez décevants :
- insert_2 : 0.240s (tailrec)
- insert_3 : 0.310s (continuations)
- insert_4 : 0.160s (continuations par tranches de 10)
- insert_6 : 0.270s (setcdr)

Pas terrible, puisque c'est quasiment le plus lent pour l'instant. En regardant un peu, je me suis rendu compte qu'en fait, on pouvait augmenter pas mal les performances en inlinant la fonction setcdr (ick !), en profitant au passage pour virer le test de sûreté (if li = [] ...). J'ai donc écrit une fonction insert_7, inlinée :
- insert_2 : 0.240s (tailrec)
- insert_3 : 0.310s (continuations)
- insert_4 : 0.160s (continuations par tranches de 10)
- insert_6 : 0.270s (setcdr)
- insert_7 : 0.230s (setcdr inline)

Remarque : la fonction n'est pas exactement équivalente aux précédentes, parce que quand r est trop grand par rapport à la liste, je renvoie un message d'erreur. Ça me paraît être le comportement le plus sain, et de toute façon ça ne change rien aux performances.

Ensuite, j'ai décidé d'essayer la version "Extlib", dont j'avais parlée au départ.

Code ocaml :

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
(* Thanks to Jacques Garrigue for suggesting the following structure *)
type 'a mut_list =  {
	hd: 'a; 
	mutable tl: 'a list
}
external inj : 'a mut_list -> 'a list = "%identity"
 
let insert_8 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let rec loop r acc = function
    | tail when r = 0 -> acc.tl <- x::tail
    | [] -> invalid_arg "insert"
    | y::ys ->
        let ynode = { hd = y; tl = [] } in
        acc.tl <- inj ynode;
        loop (r - 1) ynode ys in
    let res = { hd = y; tl = [] } in
    loop (r - 1) res ys;
    inj res

C'est tout aussi unsafe, mais le hack très malin permet de manipuler les listes comme un enregistrement avec champ mutable, ce qui est plus naturel et effraie moins les petits enfants que la version avec Obj.set_field. D'ailleurs les performances sont aussi là, puisque cette version est aussi rapide que le setcdr inline. Pour 4_000_000 :
- insert_2 : 0.310s (tailrec)
- insert_4 : 0.200s (continuations par tranches de 10)
- insert_6 : 0.410s (setcdr)
- insert_7 : 0.300s (setcdr inline)
- insert_8 : 0.295s (hack extlib)


Le meilleur des deux mondes

On peut en fait réunir le meilleur des deux mondes, en combinant les dégoutantes manipulations unsafe et le découpage par tranches de 10.
Je n'ai pas réussi à le faire avec la version extlib, donc j'ai repris la version setcdr (c'est pour ça que je les montre alors qu'elles sont plus laides que l'extlib) :

Code ocaml :

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
23
24
25
let insert_9 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let r = r - 1 in
    let res = [y] in
    let rec ins r res = function
    | tail when r = 0 -> Obj.set_field (Obj.repr res) 1 (Obj.repr (x::tail))
    | [] -> invalid_arg "insert"
    | y::ys ->
        let node = [y] in
        Obj.set_field (Obj.repr res) 1 (Obj.repr node);
        ins (r - 1) node ys in
    let rec ins10 r10 res = function
    | tail when r10 = 0 -> (res, tail) 
    | a::b::c::d::e::
      f::g::h::i::j:: q ->
        let node = [j] in
        Obj.set_field (Obj.repr res) 1 (Obj.repr (a::b::c::d::e:: f::g::h::i::j:: node));
        ins10 (r10 - 1) node q
    | _ -> invalid_arg "insert" in
 
    let partial_res, tail = ins10 (r / 10) res ys in
    ins (r mod 10) partial_res tail;
    res

C'est pas joli joli, mais ça marche vraiment très bien :
- insert_2 : 0.310s (tailrec)
- insert_4 : 0.200s (continuations par tranches de 10)
- insert_6 : 0.410s (setcdr)
- insert_7 : 0.300s (setcdr inline)
- insert_8 : 0.295s (hack extlib)
- insert_9 : 0.185s (setcdr par 10)

C'est la version la plus performante que j'aie.


Une fois revenu en conditions mémoire normales

Quand on refait le test en conditions mémoires "normales", c'est à dire sans changer la taille du tas mineur, les versions unsafe sont les claires gagnantes. Pour 2_000_000 à nouveau :
- insert_2 : 1.815s (tail-rec)
- insert_3 : 2.065s (continuations)
- insert_4 : 1.160s (continuations par 10)
- insert_5 : 1.100s (continuations par 20)
- insert_6 : 1.000s (setcdr)
- insert_7 : 1.000s (setcdr inline)
- insert_8 : 0.965s (hack extlib)
- insert_9 : 0.970s (setcdr par 10)

Ça ne veut cependant pas dire que ce sont les performances "réelles" de ces fonctions. Les performances réelles sont celles que l'on peut se permettre d'utiliser dans notre programme, en réglant le GC (on peut le faire en interne avec le module Gc) finement, de manière à avoir le plus de performances possibles, en respectant les contraintes de mémoire que l'on a en production. Bref, ce sera probablement un compromis entre la situation "GC très restrictif pour des entrées très grandes", et "GC pas restrictif parce qu'on claque plein de RAM dedans".


Pour les intéressés, voici l'ensemble de mon code de test :

Code ocaml :

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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
(* version naïve, marche pour n petit *)
let rec insert r x ys = 
  if r = 0 
  then x :: ys 
  else match ys with
  | [] -> []
  | t :: q -> t :: insert (r-1) x q
 
 
(* version tail-rec simple *) 
let insert_2 r x ys = 
  let rec insert_aux r element liste tete =
    if r = 0
    then List.rev_append tete (element :: liste) 
    else match liste with
    | [] -> ys
    | t :: q -> insert_aux (r-1) element q (t :: tete)
  in
  insert_aux r x ys []
 
(* version par continuations *)
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
    | [] -> ys  
    | t :: q -> insert_aux (r-1) element q (fun l -> k (t :: l))
  in
  insert_aux r x ys (fun x -> x)
 
 
(* version par continuations, tranches de 10 *)
let insert_4 r x ys =
  let rec insert_aux r element liste k =
    if r = 0
    then k (element :: liste)
    else match liste with
    | [] -> ys
    | a::b::c::d::e::
      f::g::h::i::j:: q -> insert_aux (r-10) element q
        (fun l -> k (a::b::c::d::e:: f::g::h::i::j:: l))
    | t :: q -> insert_aux (r-1) element q (fun l -> k (t :: l))
  in
  insert_aux r x ys (fun x -> x)
 
 
(* tranches de 20 *)
let insert_5 r x ys =
  let rec insert_aux r element liste k =
    if r = 0
    then k (element :: liste)
    else match liste with
    | [] -> ys
    | a::b::c::d::e::
      f::g::h::i::j::
      a'::b'::c'::d'::e'::
      f'::g'::h'::i'::j':: q -> insert_aux (r-20) element q
        (fun l -> k 
           (a::b::c::d::e:: f::g::h::i::j::
              a'::b'::c'::d'::e'::
              f'::g'::h'::i'::j':: l))
    | t :: q -> insert_aux (r-1) element q (fun l -> k (t :: l))
  in
  insert_aux r x ys (fun x -> x)
 
 
(* Version unsafe, setcdr *)
let setcdr (li : 'a list) (tl : 'a list) =
  if li = [] then invalid_arg "setcdr";
  let o = Obj.repr li in
  Obj.set_field o 1 (Obj.repr tl);
  tl
 
let insert_6 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let res = [y] in
    let rec ins r res = function
    | tail when r = 0 -> ignore (setcdr res (x::tail))
    | [] -> invalid_arg "insert"
    | y::ys -> ins (r - 1) (setcdr res [y]) ys in
    ins (r - 1) res ys;
    res
 
(* setcdr inline *)
let insert_7 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let res = [y] in
    let rec ins r res = function
    | tail when r = 0 -> Obj.set_field (Obj.repr res) 1 (Obj.repr (x::tail))
    | [] -> invalid_arg "insert"
    | y::ys ->
        let node = [y] in
        Obj.set_field (Obj.repr res) 1 (Obj.repr node);
        ins (r - 1) node ys in
    ins (r - 1) res ys;
    res
 
(* Version unsafe, hack extlib *)
(* Thanks to Jacques Garrigue for suggesting the following structure *)
type 'a mut_list =  {
	hd: 'a; 
	mutable tl: 'a list
}
external inj : 'a mut_list -> 'a list = "%identity"
 
let insert_8 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let rec loop r acc = function
    | tail when r = 0 -> acc.tl <- x::tail
    | [] -> invalid_arg "insert"
    | y::ys ->
        let ynode = { hd = y; tl = [] } in
        acc.tl <- inj ynode;
        loop (r - 1) ynode ys in
    let res = { hd = y; tl = [] } in
    loop (r - 1) res ys;
    inj res
 
 
(* Version unsafe par tranches *)
let insert_9 r x = function
| li when r = 0 -> x::li
| [] -> invalid_arg "insert"
| y::ys ->
    let r = r - 1 in
    let res = [y] in
    let rec ins r res = function
    | tail when r = 0 -> Obj.set_field (Obj.repr res) 1 (Obj.repr (x::tail))
    | [] -> invalid_arg "insert"
    | y::ys ->
        let node = [y] in
        Obj.set_field (Obj.repr res) 1 (Obj.repr node);
        ins (r - 1) node ys in
    let rec ins10 r10 res = function
    | tail when r10 = 0 -> (res, tail) 
    | a::b::c::d::e::
      f::g::h::i::j:: q ->
        let node = [j] in
        Obj.set_field (Obj.repr res) 1 (Obj.repr (a::b::c::d::e:: f::g::h::i::j:: node));
        ins10 (r10 - 1) node q
    | _ -> invalid_arg "insert" in
 
    let partial_res, tail = ins10 (r / 10) res ys in
    ins (r mod 10) partial_res tail;
    res
 
 
(* Fonction de test *)
let test num_fonc n =
  let fonctions = [| insert; insert_2; insert_3; insert_4; insert_5; insert_6; insert_7; insert_8; insert_9 |] in
  let rec li = ()::li in
  ignore (fonctions.(num_fonc - 1) n () li)
 
 
let () = Scanf.scanf " %d %d" test

[Garulfo]

Et bin... j'ai lu en diagonal mais ça a l'air d'être un joli travail !
Mais finalement 2 et 3 sont équivalent non ? Parce que certes il y a une différence mais c'est du même acabit (pour ne pas dire « ordre » qui a une sens particulier). Il ne semble pas y avoir de pertes flagrantes. Parce que 60ms (avec ton effacement du bruit du GC) pour une taille de 3 millions... c'est largement acceptable je pense

C'était ma première intuition, mais je n'ai rien pour le démontrer.
Par contre si c'est le cas c'est important car la forme par continuation est plus aisée à extraire d'une fonction récursive que la forme tail-rec puisque cette dernière revient à faire un while (là c'est l'expérience de tonnes d'exercices personnels qui parle).

Ce sujet est devenu réellement intéressant.

Alors dites moi si c'est correct. Entre 2 et 3:
- 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

Les autres versions sont à utiliser avec parcimonies je pense... parce qu'on perd tout l'intérêt d'un code lisible -_- Enfin c'est mon avis bien sûr.