Marc:
I'm going over c#prim-procs to see which other routines could be inlined.
First, I'm comparing
(##define-macro (macro-number-dispatch num err fix big rat flo cpx) `(cond ((##fixnum? ,num) ,fix) ((##flonum? ,num) ,flo) ((##subtyped? ,num) (let ((##s (##subtype ,num))) (cond ((##fixnum.= ##s (macro-subtype-bignum)) ,big) ((##fixnum.= ##s (macro-subtype-ratnum)) ,rat) ((##fixnum.= ##s (macro-subtype-cpxnum)) ,cpx) (else ,err)))) (else ,err)))
in _num#.scm with
(define-prim (##flonum? obj) (and (##subtyped? obj) (##eq? (##subtype obj) (macro-subtype-flonum))))
in sys.scm, and I suggest macro-number-dispatch be redefined as
(##define-macro (macro-number-dispatch num err fix big rat flo cpx) `(cond ((##fixnum? ,num) ,fix) ((##subtyped? ,num) (let ((##s (##subtype ,num))) (cond ((##fixnum.= ##s (macro-subtype-flonum)) ,flo) ((##fixnum.= ##s (macro-subtype-bignum)) ,big) ((##fixnum.= ##s (macro-subtype-ratnum)) ,rat) ((##fixnum.= ##s (macro-subtype-cpxnum)) ,cpx) (else ,err)))) (else ,err)))
Now, I look at
(define-prim (##eqv? obj1 obj2) (macro-number-dispatch obj1 (##eq? obj1 obj2) (and (##fixnum? obj2) (##fixnum.= obj1 obj2)) ; obj1 = fixnum (and (##bignum? obj2) (##bignum.= obj1 obj2)) ; obj1 = bignum (and (##ratnum? obj2) (##ratnum.= obj1 obj2)) ; obj1 = ratnum (and (##flonum? obj2) (##bvector-equal? obj1 obj2)) ; obj1 = flonum (and (##cpxnum? obj2) ; obj1 = cpxnum (##eqv? (macro-cpxnum-real obj1) (macro-cpxnum-real obj2)) (##eqv? (macro-cpxnum-imag obj1) (macro-cpxnum-imag obj2)))))
in sys.scm. I think one can (should?) inline (##eqv? x y) as
(or (##eq? x y) (and (##subtyped? x) (##subtyped? y) (let ((##sx (##subtype x))) (and (##fixnum.= ##sx (##subtype y)) (or (##fixnum.= ##sx (macro-subtype-flonum)) (##fixnum.= ##sx (macro-subtype-bignum)) (##fixnum.= ##sx (macro-subtype-ratnum)) (##fixnum.= ##sx (macro-subtype-cpxnum))) (##eqv? x y)))))
The second limb of the first "or" can be be eliminated for many compile-time constants (please use the commutativity of ##eqv? if y happens to be a compile-time constant and x isn't), which can be especially important for compiling "case" forms.
There are a number of "case" forms in the files compiler, dynamic, early, graphs, lattice, matrix, nboyer, nucleic, sboyer, scheme, and test in bench/src. In your latest benchmarks Bigloo beat Gambit in boyer, dynamic, and scheme; maybe the lack of inlining of eqv? in case contributed.
Perhaps one can use a similar strategy for inlining equal?
Other things that could (should?) be inlined (perhaps some of these already are inlined for special values of the arguments):
boolean?
list-ref (like memv)
memv (now that eqv? can be inlined)
assv (ditto)
number?, complex?, real?, rational?, integer?, exact?, inexact? (it doesn't seem so bad to inline macro-number-dispatch since the results are boolean, or at least these could be tested for fixnum and flonum)
abs (for fixnum, using ##fixnum.-? if the argument is negative)
gcd and lcm (for one argument)
numerator and denominator (for fixnums)
floor, ceiling, truncate, round (for fixnums)
real-part, imag-part, magnitude (for fixnum and flonum arguments)
string
string=? and friends with 0 and 1 arguments.
Generally, I went through all the items in prim-procs, and generated little programs that used them with varying number of arguments, then visually inspected the expanded code and (sometimes) the C code to see what's going on. I'm including my little test file at the end.
Brad
Afficher les réponses par date
Marc:
Sorry, I see that you already expand the eqv? in case statements to eq? for fixnum and symbol clauses.
Brad
I changed eqv? in dynamic.scm to be macro-expanded the way I suggested in the previous e-mail. It didn't make a whole lot of difference (note the compile time on my 2.something GHz opteron server; this is getting obscene).
Old way:
euler-83% ./bench gambit dynamic
Testing dynamic under Gambit-C-r5rs Compiling... 144.25user 5.18system 2:30.64elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1214690minor)pagefaults 0swaps Running...
(time (run-bench name count ok? run)) 1315 ms real time 1265 ms cpu time (1231 user, 34 system) 33 collections accounting for 288 ms real time (265 user, 7 system) 245641224 bytes allocated 8696 minor faults no major faults
New way:
euler-81% ./bench gambit dynamic
Testing dynamic under Gambit-C-r5rs Compiling... 146.31user 5.43system 2:35.02elapsed 97%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+1220725minor)pagefaults 0swaps Running...
(time (run-bench name count ok? run)) 1231 ms real time 1190 ms cpu time (1160 user, 30 system) 33 collections accounting for 289 ms real time (270 user, 6 system) 245641224 bytes allocated 8696 minor faults no major faults
Under r6rs it doesn't seem to help at all; I don't know what's going on here:
old way:
euler-90% ./bench -c no -s r6rs gambit dynamic
Testing dynamic under Gambit-C-r6rs Compiling... 39.17user 1.81system 0:41.40elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+405124minor)pagefaults 0swaps Running...
(time (run-bench name count ok? run)) 1083 ms real time 1079 ms cpu time (1039 user, 40 system) 34 collections accounting for 279 ms real time (268 user, 7 system) 244653128 bytes allocated 7686 minor faults no major faults
new way:
euler-88% ./bench -c no -s r6rs gambit dynamic
Testing dynamic under Gambit-C-r6rs Compiling... 40.13user 1.65system 0:42.21elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+410675minor)pagefaults 0swaps Running...
(time (run-bench name count ok? run)) 1090 ms real time 1086 ms cpu time (1046 user, 40 system) 34 collections accounting for 281 ms real time (275 user, 4 system) 244653128 bytes allocated 7686 minor faults no major faults
Brad
(PS: You should really copy dynamic.scm to dynamic-data.scm and apply the program to that file; it would make it a lot easier to hack dynamic.scm without worrying about crashing the program or getting different results.)
Unification is an algorithm where eqv? is often the slow part in Gambit; I fired up schelog with the reverse benchmark and got the following. So inlining eqv? does seem to be worth something.
With r5rs semantics:
without inlining eqv?
[brad:~/Desktop/schelog] lucier% gsi -:m100000 reverse.o1 (time (do ((i 0 (+ i 1))) ((= i 100) (void)) (%which (l) (%reverse data l)))) 344 ms real time 314 ms cpu time (308 user, 6 system) no collections 47933504 bytes allocated no minor faults no major faults
with inlining eqv?:
[brad:~/Desktop/schelog] lucier% gsi -:m100000 reverse.o2 (time (do ((i 0 (+ i 1))) ((= i 100) (void)) (%which (l) (%reverse data l)))) 235 ms real time 214 ms cpu time (209 user, 5 system) no collections 47933504 bytes allocated no minor faults no major faults
With r6rs semantics:
No inlining eqv?
[brad:~/Desktop/schelog] lucier% gsi -:m100000 reverse.o4 (time (do ((i 0 (+ i 1))) ((= i 100) (void)) (%which (l) (%reverse data l)))) 365 ms real time 237 ms cpu time (228 user, 9 system) no collections 49325408 bytes allocated no minor faults no major faults
with inlining eqv?:
[brad:~/Desktop/schelog] lucier% gsi -:m100000 reverse.o3 (time (do ((i 0 (+ i 1))) ((= i 100) (void)) (%which (l) (%reverse data l)))) 155 ms real time 131 ms cpu time (124 user, 7 system) no collections 49325408 bytes allocated no minor faults no major faults
Just for info, with (standard-bindings)(block)(fixnum)(not safe) (so eqv? == eq?)
[brad:~/Desktop/schelog] lucier% gsi -:m100000 reverse.o6 (time (do ((i 0 (+ i 1))) ((= i 100) (void)) (%which (l) (%reverse data l)))) 131 ms real time 106 ms cpu time (99 user, 7 system) no collections 49325728 bytes allocated no minor faults no major faults
At 0:08 Uhr -0400 10.10.2006, Bradley Lucier wrote:
Perhaps one can use a similar strategy for inlining equal?
I'm sometimes defining functions like |equal?| or |force| myself in some module (or more precisely: in some compilation block (I'm almost always using the block compilation declaration)), which is kind like inlining -- the compiler may actually inline it in some cases; but at least it's cheaper to call when inside the same block than across block/module/sharedobject (not sure which word I should choose to name it accurately) boundaries.
I'm wondering: in which step of the compilation phase are inlinings of the kind that you are suggesting done? Is it in the code generation step? So will it inline the code *always*, even multiple times in the same compilation block, and not be subject to the inlining-limit declaration? If so, wouldn't it be better to change that to actually create a function, but in the same block, and let the function inliner decide how to handle that? In my measurements, a real function call in the same block is only about 30-40 cycles or so, whereas a function call across block boundaries is about 200 cycles (or was it 240?). Probably for something like |equal?| it's good enough to reduce the overhead from ~200 cycles down to 30-40. This should help reduce the code bloat.
Handling "optional inlining" is something I plan to do in chjmodule (I'm continuing to work on it currently), so that one can export functions from some module A as "inlinable", which means that they will be copied verbatim (but within the original namespace, by putting a ##namespace declaration around/into it) into caller modules, so e.g. module B importing module A will contain such a copy in it's toplevel. That doesn't necessarily mean that it is being inlined into every call site inside B: it's open to the normal Gambit inliner. At the very least the costs drop from ~200 to 30-40 cycles.
Using such module techniques, instead of hard coding functions like |equal?| into Gambit, they could be defined in a standard module like "R5RS" with an inlinable export flag and be imported from there.
(BTW one could also split |equal?| like that:
(define (equal? a b) (or (eq? a b) (real-equal? a b))) (define (real-equal? a b) ..recursive definition))
and so make it possible that the first part, which doesn't generate much code bloat, can be inlined whereas the rest still isn't.
Christian.
Marc is likely in a better position to comment, and I hope I don't misunderstand your questions, but I'll give it a go.
On Oct 12, 2006, at 9:48 AM, Christian wrote:
I'm wondering: in which step of the compilation phase are inlinings of the kind that you are suggesting done? Is it in the code generation step? So will it inline the code *always*, even multiple times in the same compilation block, and not be subject to the inlining-limit declaration?
If (declare (runtime-bindings)) (which is the default), then each occurrence of the primitive will be inlined.
If, in addition, (declare (standard-bindings)) is in effect, then there will be no check that the current value of the global variable is indeed the primitive.
Finally, if (declare (not safe)) is in effect, then there will be no check that the arguments are suitable for the primitive.
And the behavior of some primitives changes if some numerical declarations are in effect; in particular, eqv? is changed to eq? if (declare (fixnum))
If so, wouldn't it be better to change that to actually create a function, but in the same block, and let the function inliner decide how to handle that?
I don't know that there's an absolute answer to that question.
Handling "optional inlining" is something I plan to do in chjmodule (I'm continuing to work on it currently), so that one can export functions from some module A as "inlinable", which means that they will be copied verbatim (but within the original namespace, by putting a ##namespace declaration around/into it) into caller modules, so e.g. module B importing module A will contain such a copy in it's toplevel. That doesn't necessarily mean that it is being inlined into every call site inside B: it's open to the normal Gambit inliner. At the very least the costs drop from ~200 to 30-40 cycles.
This seems similar to (declare (not core)), which makes a function available for inlining, but does not include a separate copy of the function in the file. It's used a lot in the files in the gsc directory, in the macro include-adt, which is defined in fixnum.scm.
If you want some information of what beta-20 inlines by default, take the test-code.scm I sent in my previous e-mail and run it through
euler-35% gsc -c -expansion test-code.scm > ! crap.scm
This expands macros and shows some of the default inlining, so that
(define (test-map-2 x0 x1) (map x0 x1))
gets expanded to
(define test-map-2 (lambda (x0 x1) (if (and ('#<procedure #2 ##eq?> map '#<procedure #185 map>) ('#<procedure #184 ##procedure?> x0)) (letrec ((loop2.248 (lambda (x0 lst2.249) (if ('#<procedure #7 ##pair?> lst2.249) (let ((x.250 (x0 ('#<procedure #11 ##car> lst2.249)))) ('#<procedure #9 ##cons> x.250 (loop2.248 x0 ('#<procedure #13 ##cdr> lst2.249)))) '())))) (loop2.248 x0 x1)) (map x0 x1))))
and
(define (test-s8vector-set!-3 x0 x1 x2) (s8vector-set! x0 x1 x2))
gets expanded to
(define test-s8vector-set!-3 (lambda (x0 x1 x2) (if (and ('#<procedure #2 ##eq?> s8vector-set! '#<procedure #287 s8vector-set!>) (and (and ('#<procedure #282 ##s8vector?> x0) ('#<procedure #171 ##subtyped-mutable?> x0)) (and (and ('#<procedure #60 ##fixnum?> x1) (and ('#<procedure #71 ##fx<=> 0 x1) ('#<procedure #65 ##fx<> x1 ('#<procedure #284 ##s8vector- length> x0)))) (and ('#<procedure #60 ##fixnum?> x2) (and ('#<procedure #71 ##fx<=> -128 x2) ('#<procedure #71 ##fx<=> x2 127)))))) ('#<procedure #288 ##s8vector-set!> x0 x1 x2) (s8vector-set! x0 x1 x2))))
with (declare (standard-bindings) (extended-bindings)) (I needed to comment out test-##return-dynamic-env-bind?-1 and test-##procedure- info-1), these are expanded to
(define test-map-2 (lambda (x0 x1) (if ('#<procedure #150 ##procedure?> x0) (letrec ((loop2.228 (lambda (x0 lst2.229) (if ('#<procedure #7 ##pair?> lst2.229) (let ((x.230 (x0 ('#<procedure #9 ##car> lst2.229)))) ('#<procedure #8 ##cons> x.230 (loop2.228 x0 ('#<procedure #10 ##cdr> lst2.229)))) '())))) (loop2.228 x0 x1)) (map x0 x1))))
and
(define test-s8vector-set!-3 (lambda (x0 x1 x2) (if (and (and ('#<procedure #225 ##s8vector?> x0) ('#<procedure #130 ##subtyped-mutable?> x0)) (and (and ('#<procedure #35 ##fixnum?> x1) (and ('#<procedure #43 ##fx<=> 0 x1) ('#<procedure #39 ##fx<> x1 ('#<procedure #228 ##s8vector-length> x0)))) (and ('#<procedure #35 ##fixnum?> x2) (and ('#<procedure #43 ##fx<=> -128 x2) ('#<procedure #43 ##fx<=> x2 127))))) ('#<procedure #230 ##s8vector-set!> x0 x1 x2) (s8vector-set! x0 x1 x2))))
and with (declare (standard-bindings)(extended-bindings)(not safe))
(define test-map-2 (lambda (x0 x1) (letrec ((loop2.94 (lambda (x0 lst2.95) (if ('#<procedure #7 ##pair?> lst2.95) (let ((x.96 (x0 ('#<procedure #9 ##car> lst2.95)))) ('#<procedure #8 ##cons> x.96 (loop2.94 x0 ('#<procedure #10 ##cdr> lst2.95)))) '())))) (loop2.94 x0 x1))))
and
(define test-s8vector-set!-3 (lambda (x0 x1 x2) ('#<procedure #260 ##s8vector-set!> x0 x1 x2)))
I think my suggested expansion of eqv? is at least comparable to these expansions.
Using such module techniques, instead of hard coding functions like |equal?| into Gambit, they could be defined in a standard module like "R5RS" with an inlinable export flag and be imported from there.
(BTW one could also split |equal?| like that:
(define (equal? a b) (or (eq? a b) (real-equal? a b))) (define (real-equal? a b) ..recursive definition))
and so make it possible that the first part, which doesn't generate much code bloat, can be inlined whereas the rest still isn't.
This definition of equal? doesn't help much if most often two things are not equal?, because there is not a quick test that (equal? a b) is false. Better might be
(define (equal? a b) (or (eq? a b) (and (subtyped? a) (subtyped? b) (real-equal? a b))))
Brad