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
Class compilation shows non-linear runtime behaviour. #6542
Comments
Comment author: @chambart It seams that this creates long lists of linked types that are not compressed. The majority of the run time is taken following those links in Btype.repr. |
Comment author: @alainfrisch I think Jacques recently added compression of Tlinks. Could this have improved this case? |
Comment author: @alainfrisch Actually, it seems this is getting worse. With current trunk, ocamlc.opt compiles test.ml in 1.39s, while it took 0.4s in a version from a few months ago. Jacques: do you have any idea where the slowdown could come from? |
Comment author: @alainfrisch I bump the severity, since there seems to be some quite serious compile-time degradation here. |
Comment author: @garrigue I tested with ocamlc and only 500 methods. |
Comment author: @garrigue Actually the tests for ocamlc.opt show that the real problem is gadt-warnings, the impact of compress-Tlink being negative but small. ocamlc.opt test.ml (1000 methods) test2.ml (2000 methods) The quadratic behavior itself cannot be completely avoided, because objects are represented as linked lists of methods (same problem as for polymorphic variants). However, I admit this is pretty bad in this case. |
Comment author: @garrigue I could track down the two causes:
The code is on github: #327 Concerning the quadratic behavior, I see no easy solution: the type of each method contains the type of the whole object, and we end up having to copy it repeatedly... |
Comment author: @alainfrisch Thanks Jacques! Pierre noticed that:
I'm not sure how to interpret your comment:
Is this because the copy is done before the compression? |
Comment author: @garrigue Well, is it really the majority of the time? My point was just that copying can be costly, but in the new instance there are no Tlinks. |
Comment author: @garrigue By the way, the fact that optimizing repr for the non-recursive case improves performance noticeably suggests that actually there are not many long Tlink chains. |
Comment author: choeger I played around with this some weeks ago and came up with at least one regression due to the handling of method types. Since methods are basically handled like ordinary functions, there is some redundancy in the processing of the self-pattern. I cannot check my changes right now, but I recall that this modification was sound and provided some enhancements. Does the attached patch (against 4.02.3) provide any insights? |
Comment author: @alainfrisch
Did you observe a regression between different versions (independently of those fixed by Jacques)? |
Comment author: choeger No, at that point I focused solely on 4.02.3, I noticed however that some unification of the self-variable was invoked once per method in the post-processing (which is of course O(n²) and non-necessary since self has the same type in all methods). |
Comment author: @alainfrisch Ok, thanks for clarifying. Proper regression between versions have higher priority, but it's certainly worth looking at your suggestion. Jacques is again the one competent to comment on it. |
Comment author: @garrigue Concretely, which unification are you talking about? If you're convinced some unification is useless, you can always try removing it, and see whether this improves performance, and whether the testsuite goes through. |
Comment author: @alainfrisch Jacques: cf the attached patch. choeger mentions that it improved performance and that it looked safe (I guess here ran the testsuite?). |
Comment author: @garrigue After fixing the badly placed end_def, which cause failure in 7 tests, this tests indeed appears to pass all the tests, and improve perfomance by a factor of 2, but I don't think this solves the quadratic problem: 2000 methods still takes almost 4 times as much as 1000. Actually I need to correct a bit more: the begin_def/end_def pair should be completely avoided for methods. |
Comment author: @alainfrisch Thanks! We know the type-checker has non-linear behaviors all over the place, and it's good to track those that can be eliminated (without degrading common cases too much); but then significant constant-factor optimizations are also important. |
Original bug ID: 6542
Reporter: choeger
Assigned to: @garrigue
Status: closed (set by @xavierleroy on 2017-02-16T14:18:23Z)
Resolution: fixed
Priority: normal
Severity: major
Target version: 4.03.0+dev / +beta1
Fixed in version: 4.03.0+dev / +beta1
Category: ~DO NOT USE (was: OCaml general)
Tags: compiler-time-or-space-regression
Monitored by: @jmeber
Bug description
I also asked for this on stackoverflow, but apparantly there is no simple solution:
http://stackoverflow.com/questions/25639619/performance-of-class-compilation
Basically, when compiling large classes, the process takes O(n²) amount of time for n methods:
This indicates that the compilation of a method somehow depends on the presence of other methods. This may be due to some optimization regarding the method lookup, but I am not convinced it is necessary.
Steps to reproduce
(echo "class foo = object" ; for ((i = 0; i < 2000; i++)) do echo method x$i = $i; done ; echo end) > test.ml
ocamlc test.ml
File attachments
The text was updated successfully, but these errors were encountered: