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