Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

PRIVATE: Complexité de l'inférence de type et objets #3296

Closed
vicuna opened this issue Apr 12, 2002 · 7 comments
Closed

PRIVATE: Complexité de l'inférence de type et objets #3296

vicuna opened this issue Apr 12, 2002 · 7 comments
Labels
bug

Comments

@vicuna
Copy link

vicuna commented Apr 12, 2002

Original bug ID: 1085
Reporter: administrator
Status: closed
Resolution: not a bug
Priority: normal
Severity: minor
Category: ~DO NOT USE (was: OCaml general)

Bug description

Full_Name: Michael Marchegay
Version: 3.04
OS: Linux - Solaris
Submission from: machine107.rd.francetelecom.com (193.49.124.107)

Je suis en train d'écrire un programme réalisant des opération sur un arbre dont
les noeuds sont représentés par des objets OCAML.

Tout marchait très bien jusau'à ce que j'ajoute à l'une de mes classe une
méthode prenant en paramètre des noeuds héritant de cette classe. L'ajout de
cette méthode semble avoir modifié la complexité de l'inférence de type pour les
fonction utilisant les classes de mon arbre.

La compilation de mon programme qui prenait une trentaine de secondes
auparavant, nécessite maintenant un peu plus d'une heure.

Je vous joint ci après le sequelète de mes classes, pratiquement épuré de toutes
leurs méthodes, ainsi qu'une petite fonction qui utilise ses classe.
La méthode qui fait augmenter mon temps de compilation est la méthode
collect_environment de la class child_node.

-------fichier.ml
module OS =
struct
type t = string
let compare (s1 : string) (s2 : string) = Pervasives.compare s1 s2
end

module OSO=
struct
type t = string option
let compare (s1 : string option) (s2 : string option) =
match (s1, s2) with
(None, None) -> 0
| (None, Some _) -> -1
| (Some _, None) -> 1
| (Some v1, Some v2) -> Pervasives.compare v1 v2
end

module MapString = Map.Make OS

module MapStringOption = Map.Make OSO

class virtual node =
object (self)
val mutable children : childNode list = []

method sub_nodes = children

method append_subnode subnode  = 
  children <- children@[subnode]

end

and rootNode =
object (self)
inherit node

end

and virtual childNode (parent : node) =
object (self)
inherit node

method get_parent : node = parent	
	  
method collect_environment : 
((referenceableRefNode * string) list *  (userTypeRefNode * string) list *

(referenceableNode MapString.t) * (userTypeNode MapString.t)) MapStringOption.t
-> ((referenceableRefNode * string) list * (userTypeRefNode * string) list *
(referenceableNode MapString.t) * (userTypeNode MapString.t)) MapStringOption.t

  fun env -> env

(* should be List.fold_left (fun env (n : childNode) -> n#collect_environment
env) env children*)

end
and virtual typedNode (parent : node) =
object (self)
inherit childNode parent

end

and virtual typeBuilderNode (parent : node) =
object(self)
inherit typedNode parent
val mutable _content : typedNode option = None

  method set_content : typedNode -> unit = fun content -> _content <- Some

content

end

and virtual userTypeNode (parent : node) =
object(self)
inherit typeBuilderNode parent

end

and virtual baseTypeNode (name : string) (parent : node) =
object(self)
inherit typedNode parent

val mutable _name : string = name

end

and userTypeRefNode (name : string) (parent : node) =
object(self)
inherit baseTypeNode name parent
end

and virtual referenceableNode (parent : node) =
object
inherit typedNode parent
end

and virtual referenceableRefNode (parent : node) =
object
inherit typedNode parent
end

class stringTypeNode (base : string) (parent : node) =
object(self)
inherit baseTypeNode base parent
end

class integerTypeNode (base : string) (parent : node) =
object(self)
inherit baseTypeNode base parent
end

class booleanTypeNode (parent : node) =
object(self)
inherit baseTypeNode "boolean" parent
end

let getTypeForName : node -> string -> typedNode =
fun parent_node type_name ->
match type_name with
"string" as _type -> (new stringTypeNode _type parent_node :> typedNode)

| "foo" as _type ->
failwith ("this type is not available yet: " ^ _type)
 
  (* boolean type *)
| "boolean" -> (new booleanTypeNode parent_node :> typedNode)

  (* integer types *)
| "integer" as _type -> (new integerTypeNode _type parent_node :>

typedNode)

| ref -> (new userTypeRefNode ref parent_node :> typedNode)

-----fin fichier.ml

lorsque je compile ce morceau de fichier (avec ocamlc -c -pp ocamlp4o), la
compilation prend 1 min 11s sur mon sun. Par contre, si j'enlève la fonction
collect_environment, la compilation se fait en 0.66 s.

Si dans la fonction, je remplace les classes de noeud dérivées de node, par la
classe "node" elle-même, la compilation ne prend plus que 1 s.

Je voudrais donc savoir si cette augmentation de la complexité de l'inférence
est normale ?

Merci.
@vicuna
Copy link
Author

vicuna commented Apr 15, 2002

Comment author: administrator

Bonjour,

Le probleme que vous decrivez semble different du #3192.
Toutefois, la branche poly_meth2 du CVS ameliore considerablement la
vitesse d'inference aussi dans votre cas, par un rapport de 1 a 5.
Ces modifications devraient etre integrees avant la prochaine release.

Je vais quand meme regarder si on ne peut pas faire mieux que ca.

Jacques Garrigue

1 similar comment
@vicuna
Copy link
Author

vicuna commented Apr 15, 2002

Comment author: administrator

Bonjour,

Le probleme que vous decrivez semble different du #3192.
Toutefois, la branche poly_meth2 du CVS ameliore considerablement la
vitesse d'inference aussi dans votre cas, par un rapport de 1 a 5.
Ces modifications devraient etre integrees avant la prochaine release.

Je vais quand meme regarder si on ne peut pas faire mieux que ca.

Jacques Garrigue

@vicuna
Copy link
Author

vicuna commented Apr 15, 2002

Comment author: administrator

Un collegue a ecrit pour moi un programme reproduisant le probleme
que j'ai observe. Je vous envoie donc cette version, en esperant
qu'elle vous aide a identifier d'ou il peut venir.

Cuihtlauac ALVARADO a ecrit :

Finalement ton exemple se reduit a ca :

class x = object
method bar (x : a0 * a1 * a2 * a3 * a4 * a5) = x
end

and a0 = object inherit x end
and a1 = object inherit x end
and a2 = object inherit x end
and a3 = object inherit x end
and a4 = object inherit x end
and a5 = object inherit x end

let _ = (new a0 :> x)

Le temps devient redibitoire avec le nombre de classes "a" (le passage de
5 a 6 est assez impressionant).

Tu peux faire l'upcast avec Obj.magic

let (_ : x) = new a0

mais ca n'est pas tres propre.

Je ne suis pas sur que tu ne fasse pas un un usage un peu trop
border-line des objets. Les types sommes c'est pas mal normalement.

--
Cuihtlauac ALVARADO - France Telecom R&D - DTL/TAL
2, avenue Pierre Marzin - 22307 Lannion - France
Tel: +33 2 96 05 32 73 - Mob: +33 6 08 10 80 41

-----Message d'origine-----
De : Jacques Garrigue [mailto:caml-bugs@pauillac.inria.fr]
Envoye : lundi 15 avril 2002 11:38
A : michael.marchegay@rd.francetelecom.com
Objet : Re: PRIVATE: Complexiti de l'infirence de type et objets
(#3296)

Bonjour,

Le probleme que vous decrivez semble different du #3192.
Toutefois, la branche poly_meth2 du CVS ameliore considerablement la
vitesse d'inference aussi dans votre cas, par un rapport de 1 a 5.
Ces modifications devraient etre integrees avant la prochaine release.

Je vais quand meme regarder si on ne peut pas faire mieux que ca.

Jacques Garrigue

<TITLE>RE: PRIVATE: Complexiti de l'infirence de type et objets (#3296)</TITLE>

Un collegue a ecrit pour moi un programme reproduisant le probleme
que j'ai observe. Je vous envoie donc cette version, en esperant
qu'elle vous aide a identifier d'ou il peut venir.

Cuihtlauac ALVARADO a ecrit :
> Finalement ton exemple se reduit a ca :
>
> class x = object
>  method bar (x : a0 * a1 * a2 * a3 * a4 * a5) = x
> end       
>
> and a0 = object inherit x end
> and a1 = object inherit x end
> and a2 = object inherit x end
> and a3 = object inherit x end
> and a4 = object inherit x end
> and a5 = object inherit x end
>
> let _ = (new a0 :> x)
>
> Le temps devient redibitoire avec le nombre de classes "a" (le passage de 5 a 6 est assez impressionant).
>
> Tu peux faire l'upcast avec Obj.magic
>
> let (_ : x) = new a0
>
> mais ca n'est pas tres propre.
>
> Je ne suis pas sur que tu ne fasse pas un un usage un peu trop
> border-line des objets. Les types sommes c'est pas mal normalement.
>
> --
> Cuihtlauac ALVARADO - France Telecom R&D - DTL/TAL
> 2, avenue Pierre Marzin - 22307 Lannion - France
> Tel: +33 2 96 05 32 73 - Mob: +33 6 08 10 80 41


-----Message d'origine-----
De : Jacques Garrigue [mailto:caml-bugs@pauillac.inria.fr]
Envoye : lundi 15 avril 2002 11:38
A : michael.marchegay@rd.francetelecom.com
Objet : Re: PRIVATE: Complexiti de l'infirence de type et objets
(#3296)


Bonjour,

Le probleme que vous decrivez semble different du #3192.
Toutefois, la branche poly_meth2 du CVS ameliore considerablement la
vitesse d'inference aussi dans votre cas, par un rapport de 1 a 5.
Ces modifications devraient etre integrees avant la prochaine release.

Je vais quand meme regarder si on ne peut pas faire mieux que ca.

Jacques Garrigue

---------------- ---------------- ---------------- ----------------

@vicuna
Copy link
Author

vicuna commented Apr 15, 2002

Comment author: administrator

Apres quelques recherches plus approfondies, il semblerait que le meme type
de probleme soit rencontre avec :

class x = object
let bar (x0:a0) (x1:a1) (x2:a2) (x3:a3) (x4:a4) (x5:a5) (x6:a6) (x7:a7) =
(x0, x1, x2, x3, x4, x5, x6, x7)
end

and a0 = object inherit x end
and a1 = object inherit x end
and a2 = object inherit x end
and a3 = object inherit x end
and a4 = object inherit x end
and a5 = object inherit x end
and a6 = object inherit x end
and a7 = object inherit x end

let _ = (new x :> x)

Pensez-vous que l'ecriture de fonctions x_to_x, a0_to_x, ... du style

let x_to_x : x -> x = fun o -> (Obj.magic o : x)

puissent etre une solution envisageable pour mon probleme ?

En effet, si une future version du compilateur s'averait plus veloce avec ce
genre de programme, il me suffirait de les reecrire sous la forme:

let a0_to_x : a0 -> x = fun a -> a :> x

cela me permettrait de ne pas trop modifier le programme que j'ai commence a
ecrire (qui fait deja plus de 4000 lignes).

Merci d'avance.

<TITLE>RE: PRIVATE: Complexiti de l'infirence de type et objets (#3296)</TITLE>

Apres quelques recherches plus approfondies, il semblerait que le meme type de probleme soit rencontre avec :

class x = object
  let bar (x0:a0) (x1:a1) (x2:a2) (x3:a3) (x4:a4) (x5:a5) (x6:a6) (x7:a7) =
    (x0, x1, x2, x3, x4, x5, x6, x7)
end       

and a0 = object inherit x end
and a1 = object inherit x end
and a2 = object inherit x end
and a3 = object inherit x end
and a4 = object inherit x end
and a5 = object inherit x end
and a6 = object inherit x end
and a7 = object inherit x end

let _ = (new x :> x)

Pensez-vous que l'ecriture de fonctions x_to_x, a0_to_x, ... du style

let x_to_x : x -> x = fun o -> (Obj.magic o : x)

puissent etre une solution envisageable pour mon probleme ?

En effet, si une future version du compilateur s'averait plus veloce avec ce genre de programme, il me suffirait de les reecrire sous la forme:

let a0_to_x : a0 -> x = fun a -> a :> x

cela me permettrait de ne pas trop modifier le programme que j'ai commence a ecrire (qui fait deja plus de 4000 lignes).

Merci d'avance.

---------------- ---------------- ---------------- ----------------

@vicuna
Copy link
Author

vicuna commented Apr 17, 2002

Comment author: administrator

Apres quelques recherches plus approfondies, il semblerait que le meme type
de probleme soit rencontre avec :

class x = object
let bar (x0:a0) (x1:a1) (x2:a2) (x3:a3) (x4:a4) (x5:a5) (x6:a6) (x7:a7) =
(x0, x1, x2, x3, x4, x5, x6, x7)
end

and a0 = object inherit x end
and a1 = object inherit x end
and a2 = object inherit x end
and a3 = object inherit x end
and a4 = object inherit x end
and a5 = object inherit x end
and a6 = object inherit x end
and a7 = object inherit x end

let _ = (new x :> x)

Cet exemple est beaucoup plus lisible.
Et le probleme est claire: la taille du type produit par (_ :> x) explose.
Ca ne peut pas etre ameliore', car c'est lie' a la definition meme de cette operation, qui doit etre reservee a des cas ou` le type de destination n'est
pas pris dans des recursions mutuelles complexes.

Si vous connaissez le type d'origine de la coercion, il faut utiliser une
coercion double, de la forme:
(_ : t :> x)
Elle sera beaucoup moins couteuse.
A noter que dans le cas precedent, new x ayant deja le type x,
(new x : x :> x) ne fait absolument rien.

Pensez-vous que l'ecriture de fonctions x_to_x, a0_to_x, ... du style
let x_to_x : x -> x = fun o -> (Obj.magic o : x)
puissent etre une solution envisageable pour mon probleme ?

Obj.magic n'est jamais une solution envisageable.
Surtout que ces fonctions s'ecrivent naturellement

let a0_to_x o = (o : a0 :> x)

pour un cout d'inference negligeable.

Cordialement,

Jacques Garrigue

1 similar comment
@vicuna
Copy link
Author

vicuna commented Apr 17, 2002

Comment author: administrator

Apres quelques recherches plus approfondies, il semblerait que le meme type
de probleme soit rencontre avec :

class x = object
let bar (x0:a0) (x1:a1) (x2:a2) (x3:a3) (x4:a4) (x5:a5) (x6:a6) (x7:a7) =
(x0, x1, x2, x3, x4, x5, x6, x7)
end

and a0 = object inherit x end
and a1 = object inherit x end
and a2 = object inherit x end
and a3 = object inherit x end
and a4 = object inherit x end
and a5 = object inherit x end
and a6 = object inherit x end
and a7 = object inherit x end

let _ = (new x :> x)

Cet exemple est beaucoup plus lisible.
Et le probleme est claire: la taille du type produit par (_ :> x) explose.
Ca ne peut pas etre ameliore', car c'est lie' a la definition meme de cette operation, qui doit etre reservee a des cas ou` le type de destination n'est
pas pris dans des recursions mutuelles complexes.

Si vous connaissez le type d'origine de la coercion, il faut utiliser une
coercion double, de la forme:
(_ : t :> x)
Elle sera beaucoup moins couteuse.
A noter que dans le cas precedent, new x ayant deja le type x,
(new x : x :> x) ne fait absolument rien.

Pensez-vous que l'ecriture de fonctions x_to_x, a0_to_x, ... du style
let x_to_x : x -> x = fun o -> (Obj.magic o : x)
puissent etre une solution envisageable pour mon probleme ?

Obj.magic n'est jamais une solution envisageable.
Surtout que ces fonctions s'ecrivent naturellement

let a0_to_x o = (o : a0 :> x)

pour un cout d'inference negligeable.

Cordialement,

Jacques Garrigue

@vicuna
Copy link
Author

vicuna commented Apr 17, 2002

Comment author: administrator

Inference speed problems with objects, modules and subtyping.
poly_meth2 modifications can help, but not on the subtyping part.

@vicuna vicuna closed this as completed Apr 17, 2002
@vicuna vicuna added the bug label Mar 19, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@vicuna