Hi
I have this simple numerical algorithm that computes an integral. I compile it with
-prelude "(declare (standard-bindings) (block) (not safe))" -cc-options "-O4".
All functions are tail-call optimized.
The very last line of generated by ##gc-report-set! is
*** GC: 0 ms, 18.7G alloc, 1.52M heap, 45.3K live (3% 22896+23496)
The live area is consistently 45K throughout the entire execution.
Timing report indicates that 18% is spent on GC:
7904 ms real time 7784 ms cpu time (3684 user, 4100 system) 13048 collections accounting for 1404 ms real time (584 user, 724 system) 20078526600 bytes allocated 480 minor faults no major faults
Besides tail-calls, what else can i do to reduce GC?
Afficher les réponses par date
Hallo,
On Tue, Apr 23, 2013 at 3:50 PM, Zhen Shen zhenshen10@outlook.com wrote:
Besides tail-calls, what else can i do to reduce GC?
Start with a bigger heap, so GC will be less frequent.
-- -alex http://unendli.ch/
On Apr 23, 2013, at 9:50 AM, Zhen Shen wrote:
Besides tail-calls, what else can i do to reduce GC?
You know, it's really hard to say without seeing your code.
You say your code is a numerical algorithm.
Are you using generic arithmetic rather than floating-point specific operators? Are you mixing integers and floating-point numbers in arithmetic operations? Do you have loops with flonums as arguments? Do you try to save time by precomputing flonums before if statements rather than recomputing the expressions? Do you use / rather than quotient, generating rational numbers?
All those things could cause numbers to be boxed rather than used inline.
Brad
given the allocation rate, I'm willing to bet that you are doing exact arithmetic. Once you realize that each division turns into rationals of bignums, you begin to see that "exact" isn't all its cracked up to be. As Brad suggested, you should either use explicit flonum operators, or judiciously inject exact->inexact conversions into your code.
- d
On 23 April 2013 15:22, Bradley Lucier lucier@math.purdue.edu wrote:
On Apr 23, 2013, at 9:50 AM, Zhen Shen wrote:
Besides tail-calls, what else can i do to reduce GC?
You know, it's really hard to say without seeing your code.
You say your code is a numerical algorithm.
Are you using generic arithmetic rather than floating-point specific operators? Are you mixing integers and floating-point numbers in arithmetic operations? Do you have loops with flonums as arguments? Do you try to save time by precomputing flonums before if statements rather than recomputing the expressions? Do you use / rather than quotient, generating rational numbers?
All those things could cause numbers to be boxed rather than used inline.
Brad
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Havens!! Do gambit users launch rockets into space, is that the reason for having bignum arithmetic by default??!
Oh, and speaking of "exact" arithmetic, I thought that was impossible cause digital computers cant store reals?
Anyhow, thanks to your and brad's suggestions, I made significant improvements: memory usage is 3GB (down from 18GB!) and execution time descreased by 80%. This is mostly due to the flonums.
Now, doing (declare (flonum)) at the top level, does this stop gambit from boxing flonums across function calls?
Date: Tue, 23 Apr 2013 22:47:11 +0100 Subject: Re: [gambit-list] decreasing GC From: kumoyuki@gmail.com To: lucier@math.purdue.edu CC: zhenshen10@outlook.com; gambit-list@iro.umontreal.ca
given the allocation rate, I'm willing to bet that you are doing exact arithmetic. Once you realize that each division turns into rationals of bignums, you begin to see that "exact" isn't all its cracked up to be. As Brad suggested, you should either use explicit flonum operators, or judiciously inject exact->inexact conversions into your code.
- d
On 23 April 2013 15:22, Bradley Lucier lucier@math.purdue.edu wrote:
On Apr 23, 2013, at 9:50 AM, Zhen Shen wrote:
Besides tail-calls, what else can i do to reduce GC?
You know, it's really hard to say without seeing your code.
You say your code is a numerical algorithm.
Are you using generic arithmetic rather than floating-point specific operators? Are you mixing integers and floating-point numbers in arithmetic operations? Do you have loops with flonums as arguments? Do you try to save time by precomputing flonums before if statements rather than recomputing the expressions? Do you use / rather than quotient, generating rational numbers?
All those things could cause numbers to be boxed rather than used inline.
Brad
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
-- GPG Public key at http://cyber-rush.org/drr/gpg-public-key.txt
On 04/24/2013 12:37 PM, Zhen Shen wrote:
Oh, and speaking of "exact" arithmetic, I thought that was impossible cause digital computers cant store reals?
Computers can work with the computable reals if you like.
Now, doing (declare (flonum)) at the top level, does this stop gambit from boxing flonums across function calls?
No. Gambit keeps flonums unboxed inside a basic block, whenever there's a jump (or the possibility of a jump), Gambit boxes up all the still-needed flonums.
Brad
Hi Brad!
2013/4/24 Bradley Lucier lucier@math.purdue.edu
On 04/24/2013 12:37 PM, Zhen Shen wrote:
[...]
Now, doing (declare (flonum)) at the top level, does this stop gambit from boxing flonums across function calls?
No. Gambit keeps flonums unboxed inside a basic block, whenever there's a jump (or the possibility of a jump), Gambit boxes up all the still-needed flonums.
What about fixnums, would they remain unboxed in a loop?
Also btw, are there any tricks that can be applied to make it keep flonums and fixnums unboxed in loops, like, (declare (not interrupts-enabled)) or (not safe)?
Btw, there was a conversation on the following like ~4y ago though I don't remember the conclusion:
In a context where the user is allowed to enter any value, what's the most performant way to ensure the value is made a flonum or integer?
(Or, you made some nice calculation that made use of the numeric tower's exactness but you get to a point where you want to ensure a proper cast to flonum or integer:)
I.e,. what's the fastest way to do (exact->inexact n) and (inexact->exact (floor n)) respectively, where examples for n are 5 5. 3/7 1e25 ? :)
If I remember right from that conversation there were some Huge differences in performance between different approaches, like 500x.
Brgds, Mikael
Brad _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On 04/24/2013 01:33 PM, Mikael wrote:
Hi Brad!
2013/4/24 Bradley Lucier <lucier@math.purdue.edu mailto:lucier@math.purdue.edu>
On 04/24/2013 12:37 PM, Zhen Shen wrote:
[...]
> Now, doing (declare (flonum)) at the top level, does this stop gambit > from boxing flonums across function calls? No. Gambit keeps flonums unboxed inside a basic block, whenever there's a jump (or the possibility of a jump), Gambit boxes up all the still-needed flonums.
What about fixnums, would they remain unboxed in a loop?
Yes. Fixnums are always "immediate" (not boxed) values.
Also btw, are there any tricks that can be applied to make it keep flonums and fixnums unboxed in loops, like, (declare (not interrupts-enabled)) or (not safe)?
Use (declare (not safe)) and flonum-specific operations to keep flonums unboxed in a basic block. There's no way to keep them unboxed across jumps. (With generic operations, flonums are boxed even in a basic block.)
Or, you can use an f64vector as an explicit "box" for your flonum and write monstrous code like this.
(define (Array-sum a) (f64vector-ref (Array-reduce (lambda (result y) (f64vector-set! result 0 (fl+ (f64vector-ref result 0) y)) result) (f64vector 0.) a) 0))
Brad
On 2013-04-24, at 12:37 PM, Zhen Shen zhenshen10@outlook.com wrote:
Havens!! Do gambit users launch rockets into space, is that the reason for having bignum arithmetic by default??!
I'm not sure if you mean that question as a criticism of Scheme, a criticism of Gambit, or an actual question (in which case the answer is yes). It is not so much that bignum arithmetic is "on by default". It is really a consequence of the language design which specifies that Scheme arithmetic corresponds to mathematics when operating on exact numbers. There are plenty of languages to choose from if you prefer (expt 2 31) returning -2147483648 .
Oh, and speaking of "exact" arithmetic, I thought that was impossible cause digital computers cant store reals?
Anyhow, thanks to your and brad's suggestions, I made significant improvements: memory usage is 3GB (down from 18GB!) and execution time descreased by 80%. This is mostly due to the flonums.
Now, doing (declare (flonum)) at the top level, does this stop gambit from boxing flonums across function calls?
No, flonums are kept unboxed only within a basic-block of code (a block of code uninterrupted by a jump, such as an "if" or function call). So it pays to think carefully about where floating point calculations are placed. Sometimes it is beneficial to recompute a result if it prevents carrying an intermediate result accross a jump.
Marc
Marc,
Sorry if my joke didn't come across as one. I am new to scheme.
If I understand you correctly, the calculations in this stmt will be performed with bignum arith?
(declare (flonum)) (if (> x 0.01) (* x a 3.0) (/ x a))
and to avoid that for max speed, i'd rewrite it as follows??
(declare (flonum)) (define x ..) (define a ..)
(define p (* x a 3.0)) (define q (/ x a)) (define r (> x 0.01)) (if r p q)
Subject: Re: [gambit-list] decreasing GC From: feeley@iro.umontreal.ca Date: Wed, 24 Apr 2013 14:17:39 -0400 CC: kumoyuki@gmail.com; gambit-list@iro.umontreal.ca To: zhenshen10@outlook.com
On 2013-04-24, at 12:37 PM, Zhen Shen zhenshen10@outlook.com wrote:
Havens!! Do gambit users launch rockets into space, is that the reason for having bignum arithmetic by default??!
I'm not sure if you mean that question as a criticism of Scheme, a criticism of Gambit, or an actual question (in which case the answer is yes). It is not so much that bignum arithmetic is "on by default". It is really a consequence of the language design which specifies that Scheme arithmetic corresponds to mathematics when operating on exact numbers. There are plenty of languages to choose from if you prefer (expt 2 31) returning -2147483648 .
Oh, and speaking of "exact" arithmetic, I thought that was impossible cause digital computers cant store reals?
Anyhow, thanks to your and brad's suggestions, I made significant improvements: memory usage is 3GB (down from 18GB!) and execution time descreased by 80%. This is mostly due to the flonums.
Now, doing (declare (flonum)) at the top level, does this stop gambit from boxing flonums across function calls?
No, flonums are kept unboxed only within a basic-block of code (a block of code uninterrupted by a jump, such as an "if" or function call). So it pays to think carefully about where floating point calculations are placed. Sometimes it is beneficial to recompute a result if it prevents carrying an intermediate result accross a jump.
Marc
On 2013-04-24, at 3:21 PM, Zhen Shen zhenshen10@outlook.com wrote:
Marc,
Sorry if my joke didn't come across as one. I am new to scheme.
If I understand you correctly, the calculations in this stmt will be performed with bignum arith?
(declare (flonum)) (if (> x 0.01) (* x a 3.0) (/ x a))
Certainly not bignum arithmetic, but possibly flonum arithmetic depending on your declarations. You can verify by using the -expansion option:
% cat flo.scm (declare (standard-bindings) (flonum) (not safe))
(if (> x 0.01) (* x a 3.0) (/ x a)) % gsc -c -expansion flo.scm Expansion:
(if ('#<procedure #2 ##fl>> x .01) ('#<procedure #3 ##fl*> x a 3.) ('#<procedure #4 ##fl/> x a))
So here all operations are done on flonums.
and to avoid that for max speed, i'd rewrite it as follows??
(declare (flonum)) (define x ..) (define a ..)
(define p (* x a 3.0)) (define q (/ x a)) (define r (> x 0.01)) (if r p q)
That will probably run slower because the test won't be inlined. I was talking about this case:
(let ((x (+ a b))) (if (< a 0.0) (* x x) (/ 1.0 x)))
Here the x will be boxed because it crosses a jump (the if).
Marc
Hallo,
On Wed, Apr 24, 2013 at 9:42 PM, Marc Feeley feeley@iro.umontreal.ca wrote:
That will probably run slower because the test won't be inlined. I was talking about this case:
(let ((x (+ a b))) (if (< a 0.0) (* x x) (/ 1.0 x)))
Here the x will be boxed because it crosses a jump (the if).
I take it then that a LET is not compiled as a closed procedure application, and thus does not count as a jump?
Thanks, -- -alex http://unendli.ch/