I've changed some quadratic-time parts of internal-definition expansion to linear-time. It's very difficult to eliminate all of the quadratic parts of environment and syntax-object manipulation, though; I've tried before.
The changes at least reduce the constant on the quadratic for internal-definition expansion, so the linear part dominates for a while longer in your `expression-module' example: Old: 125 cpu time: 41 real time: 42 gc time: 0 250 cpu time: 112 real time: 116 gc time: 25 500 cpu time: 258 real time: 263 gc time: 19 1000 cpu time: 891 real time: 905 gc time: 44 2000 cpu time: 3032 real time: 3073 gc time: 64 4000 cpu time: 12922 real time: 13476 gc time: 113 New: 125 cpu time: 74 real time: 74 gc time: 36 250 cpu time: 46 real time: 46 gc time: 0 500 cpu time: 101 real time: 105 gc time: 17 1000 cpu time: 223 real time: 236 gc time: 49 2000 cpu time: 456 real time: 474 gc time: 69 4000 cpu time: 1089 real time: 1122 gc time: 123 8000 cpu time: 2939 real time: 3015 gc time: 333 16000 cpu time: 9006 real time: 9235 gc time: 709 32000 cpu time: 31223 real time: 32117 gc time: 1292 At Tue, 16 Feb 2010 19:25:30 -0700, Matthew Flatt wrote: > Yes, it's roughly quadratic, since each discovered internal `define' > adds an item to an environment represented as a linked list (and > recognizing the next `define' means walking through the environment to > check for shadowing bindings). I'll try to improve it. > > At Sun, 14 Feb 2010 19:41:21 -0500, Carl Eastlund wrote: > > Internal definition contexts (e.g. the body of let or lambda) appear > > to expand in exponential time based on the number of definitions. The > > exponential is very slow -- the exponent is probably not linear, but > > based on some root of the number of definitions -- but given a large > > enough program it does explode. > > > > Here is code I used to benchmark definitions in a module versus > > definitions in a let expression (also inside a module, in case it > > makes a difference): > > > > -------------------------------------------------- > > > > #lang scheme > > > > (define (definition-module n) > > #`(module M scheme #,(definitions n))) > > > > (define (expression-module n) > > #`(module M scheme #,(expressions n))) > > > > (define (expressions n) > > #`(let () #,(definitions n) (void))) > > > > (define (definitions n) > > #`(begin #,@(build-list n (lambda (i) #`(define #,(gensym) (void)))))) > > > > (define (show term) > > (for ([i (in-range 3)]) > > (time (expand-syntax term)))) > > > > -------------------------------------------------- > > > > And here are the timing results of expanding modules and expressions > > with 1,000 through 10,000 definitions, with three trials at each > > increment of 1,000: > > > > > (show (definition-module 1000)) > > cpu time: 409 real time: 416 gc time: 119 > > cpu time: 279 real time: 283 gc time: 0 > > cpu time: 366 real time: 374 gc time: 71 > > > (show (definition-module 2000)) > > cpu time: 690 real time: 702 gc time: 121 > > cpu time: 723 real time: 734 gc time: 147 > > cpu time: 723 real time: 738 gc time: 152 > > > (show (definition-module 3000)) > > cpu time: 1148 real time: 1171 gc time: 297 > > cpu time: 986 real time: 1001 gc time: 154 > > cpu time: 1138 real time: 1167 gc time: 278 > > > (show (definition-module 4000)) > > cpu time: 1430 real time: 1453 gc time: 319 > > cpu time: 1441 real time: 1467 gc time: 310 > > cpu time: 1682 real time: 1710 gc time: 531 > > > (show (definition-module 5000)) > > cpu time: 3089 real time: 3128 gc time: 1693 > > cpu time: 2920 real time: 2960 gc time: 1498 > > cpu time: 1899 real time: 1932 gc time: 498 > > > (show (definition-module 6000)) > > cpu time: 2220 real time: 2261 gc time: 514 > > cpu time: 2216 real time: 2256 gc time: 489 > > cpu time: 2182 real time: 2235 gc time: 461 > > > (show (definition-module 7000)) > > cpu time: 2702 real time: 2748 gc time: 670 > > cpu time: 5213 real time: 5301 gc time: 3207 > > cpu time: 2500 real time: 2558 gc time: 480 > > > (show (definition-module 8000)) > > cpu time: 3128 real time: 3182 gc time: 791 > > cpu time: 3042 real time: 3105 gc time: 721 > > cpu time: 3073 real time: 3128 gc time: 728 > > > (show (definition-module 9000)) > > cpu time: 5864 real time: 5937 gc time: 3329 > > cpu time: 3454 real time: 3518 gc time: 872 > > cpu time: 3267 real time: 3324 gc time: 690 > > > (show (definition-module 10000)) > > cpu time: 3884 real time: 3952 gc time: 1023 > > cpu time: 6234 real time: 6322 gc time: 3429 > > cpu time: 3685 real time: 3766 gc time: 800 > > > > > (show (expression-module 1000)) > > cpu time: 1152 real time: 1160 gc time: 0 > > cpu time: 1211 real time: 1223 gc time: 82 > > cpu time: 1166 real time: 1177 gc time: 0 > > > (show (expression-module 2000)) > > cpu time: 3895 real time: 3919 gc time: 108 > > cpu time: 4185 real time: 4215 gc time: 152 > > cpu time: 4430 real time: 4455 gc time: 157 > > > (show (expression-module 3000)) > > cpu time: 9354 real time: 9416 gc time: 185 > > cpu time: 8699 real time: 8750 gc time: 160 > > cpu time: 8860 real time: 8913 gc time: 149 > > > (show (expression-module 4000)) > > cpu time: 19506 real time: 19758 gc time: 303 > > cpu time: 18091 real time: 18254 gc time: 301 > > cpu time: 17669 real time: 17842 gc time: 175 > > > (show (expression-module 5000)) > > cpu time: 30103 real time: 30369 gc time: 1756 > > cpu time: 31301 real time: 31784 gc time: 1376 > > cpu time: 28922 real time: 29213 gc time: 279 > > > (show (expression-module 6000)) > > cpu time: 50572 real time: 50931 gc time: 401 > > cpu time: 42670 real time: 43028 gc time: 275 > > cpu time: 42491 real time: 42994 gc time: 320 > > > (show (expression-module 7000)) > > cpu time: 65161 real time: 65775 gc time: 427 > > cpu time: 72382 real time: 72834 gc time: 407 > > cpu time: 60682 real time: 61430 gc time: 463 > > > (show (expression-module 8000)) > > cpu time: 98473 real time: 99281 gc time: 3186 > > cpu time: 99311 real time: 100036 gc time: 372 > > cpu time: 106628 real time: 107104 gc time: 401 > > > (show (expression-module 9000)) > > cpu time: 120579 real time: 121512 gc time: 572 > > cpu time: 127369 real time: 128387 gc time: 418 > > cpu time: 125163 real time: 126157 gc time: 575 > > > (show (expression-module 10000)) > > cpu time: 157635 real time: 158839 gc time: 619 > > cpu time: 173710 real time: 174952 gc time: 3593 > > cpu time: 178207 real time: 179627 gc time: 553 > > > > The module-level definitions expand in linear time, taking 3-400 > > milliseconds per definition and completing a 10,000 definition module > > in around 3 seconds. The internal definitions start exploding > > quickly, doubling every 1,000 definitions or so; this slows down > > somewhat, but the final trials of 10,000 definitions take nearly 3 > > minutes instead of 3 seconds. > > > > Practical examples of internal definitions, such as units, classes, > > and (most important to me) Modular ACL2 components, explode even > > faster than this. This may be the internal definition explosion > > multiplied by greater constant factors, or it may be that certain uses > > of local-expand add another source of exponential explosion. One way > > or another, so long as internal definition contexts can take > > exponential time, language features based on them can't do any better > > in the general case. > > > > Is this an inherent drawback of internal definition expansion? Or is > > this a bug we can eliminate? > > > > Carl Eastlund > > _________________________________________________ > > For list-related administrative tasks: > > http://list.cs.brown.edu/mailman/listinfo/plt-dev > _________________________________________________ > For list-related administrative tasks: > http://list.cs.brown.edu/mailman/listinfo/plt-dev _________________________________________________ For list-related administrative tasks: http://list.cs.brown.edu/mailman/listinfo/plt-dev
