Comment author: administrator

Dans la documentation de caml, il est écrit que Sort.array est
obsolète et que Array.sort doit lui être préférée et est plus rapide.

Bon, il faudrait ecrire "generalement plus rapide".

let t = Array.init 1000000 (fun _ -> Random.int 1000000)
let _ = Array.sort/Sort.array compare t

compilé avec ocamlopt -unsafe, montre au contraire que Sort.array est
plus rapide (6.57 s) que Array.sort (8.49 s). Surprenant...

Ca se discute... Avec Array.sort, on fait 25150766 comparaisons, alors
qu'on en fait 28900932 avec Sort.array. Si ta fonction de comparaison
est un peu plus compliquee, c'est Array.sort qui ira plus vite au chrono.

En plus, dans le cas le pire Array.sort ne degenere pas en n^2.

Evidemment, heap-sort ternaire ca a un peu d'overhead, mais je pense
que ca vaut le coup en termes de robustesse.

D'autre part, je note que dans le code de Array.sort, get et set sont
utilisées là où unsafe_get et unsafe_set pourraient l'être.

La il y a une vraie question: est-ce qu'on veut prendre le risque d'utiliser
unsafe_get et unsafe_set ? N'ayant pas prouve le code, je me demande si
la difference de vitesse justifie le risque de bug non detecte.

De plus,
de façon surprenante, l'option -unsafe est sans effet sur les
performances (avec ou sans -unsafe on obtient 8.49 s).

Est-ce que tu as vraiment recompile la librairie avec -unsafe ? Sur mon
alpha, il y a environ 20% de difference de vitesse sur ton programme.

-- Damien

Comment author: administrator

Est-ce qu'on doit utiliser unsafe_* ou non ?

Comment author: administrator

Merci pour ces précisions. (Je n'avais jamais vu de heap-sort
ternaire, d'ailleurs, et c'était intéressant de ce point de vue là.)

Pour répondre à ta question, j'avais bien recompilé la librairie en
-unsafe (en fait j'avais mis le code dans mon programme de test et
compilé en -unsafe pour être sûr).

Mais encore une fois, ce n'est pas très important. Merci d'avoir
répondu.

--
Jean-Christophe Filliatre (http://www.lri.fr/~filliatr)