Hello, Using gambit 4.6.0 I have a performance problem. It may be my mistake, but I can't see the problem. So I decided to make tests and send them here, so maybe you can point it out. The program fills a 500x500 array or list with values corresponding to its 2d euclidean distance to a reference point (200,200). 1.3gz centrino (very old computer) Filling a 500x500 uchar* in C: 30 ms. Filling a 500x500 list in gambit interpreter: ~3200 ms. with two different approaches, both with integer arithmetic. If I use floating points it takes roughly double. Compiling the code drops to ~800ms. still quite high (and I don't usually compile the module when working with it). what could I do to improve this? is something wrong with my code? I attach the two versions. Thank you Álvaro
Afficher les réponses par date
This function in C int distance_point_point(struct point *p1, struct point *p2) { return sqrt( pow( p1->x - p2->x, 2) + pow( p1->y - p2->y, 2) ); } is translated quite literally into (Gambit) scheme as (define (distance-point-point a b) (##flonum.->fixnum (flsqrt (fl+ (flexpt (fixnum->flonum (point-x a)) 2.) (flexpt (fixnum->flonum (point-y a)) 2.))))) The C type inference rules, the automatic conversion of int to double and back, and the header <math.h> takes care of all of that. And you're allocating manipulating lists in the Scheme version, but using an array in the C version, which you could also do in the scheme version. So these codes are in only a rough sense "equivalent". If you add the declarations (declare (standard-bindings)(extended-bindings)(block)(not safe)) then things should go a bit faster. Brad
And you're allocating manipulating lists in the Scheme version, but using an array in the C version, which you could also do in the scheme version.
Isn't the second version, with: (do ((vec (make-u8vector len)) allocating, and then writing with u8vector-set! doing that? Thanks for your explanations. Best regards, Álvaro
El 2 de abril de 2010 17:11, Bradley Lucier <lucier@math.purdue.edu>escribió:
This function in C
int distance_point_point(struct point *p1, struct point *p2) { return sqrt( pow( p1->x - p2->x, 2) + pow( p1->y - p2->y, 2) ); }
is translated quite literally into (Gambit) scheme as
(define (distance-point-point a b) (##flonum.->fixnum (flsqrt (fl+ (flexpt (fixnum->flonum (point-x a)) 2.) (flexpt (fixnum->flonum (point-y a)) 2.)))))
The C type inference rules, the automatic conversion of int to double and back, and the header <math.h> takes care of all of that.
And you're allocating manipulating lists in the Scheme version, but using an array in the C version, which you could also do in the scheme version.
So these codes are in only a rough sense "equivalent".
If you add the declarations
(declare (standard-bindings)(extended-bindings)(block)(not safe))
then things should go a bit faster.
Brad
Actually, I tried that code, and this runs faster: (define (distance-point-point-integer a b) (integer-sqrt (fx+ (expt (- (point-x a) (point-x b)) 2) (expt (- (point-y a) (point-y b)) 2)))) What does actually help (~2x) is the declaration: (declare (standard-bindings)(extended-bindings)(block)(not safe)) Now I have it down to ~350ms. which is 10-20x the C version. with floating point. I can't understand how the straightforward u8vector version (the second in the scheme code) is slower (~500ms) than the same thing with consed lists and afterwards transformed to a u8vector :S Best regards
On Apr 2, 2010, at 11:59 AM, Álvaro Castro-Castilla wrote:
Now I have it down to ~350ms. which is 10-20x the C version. with floating point. I can't understand how the straightforward u8vector version (the second in the scheme code) is slower (~500ms) than the same thing with consed lists and afterwards transformed to a u8vector :S
(floor (/ i size-y)))))))) (/ i size-y) is a rational number (make-point 200 200) keeps making the same point over and over again; in C you make the point once. Try (declare (standard-bindings)(extended-bindings)(block)(not safe)) (define-structure point x y) (define (fxsquare x) (fx* x x)) (define (distance-point-point-integer a b) (##flonum.->fixnum (flsqrt (fixnum->flonum (fx+ (fxsquare (fx- (point-x a) (point-x b))) (fxsquare (fx- (point-y a) (point-y b)))))))) (define (make-2d-field-v2 size-x size-y proc) (let ((point (make-point 0 0))) (let ((len (fx* size-x size-y))) (do ((vec (make-u8vector len)) (i 0 (fx+ i 1))) ((fx>= i len) vec) (point-x-set! point (fxmodulo i size-y)) (point-y-set! point (fxquotient i size-y)) (u8vector-set! vec i (proc point)))))) (time (make-2d-field-v2 500 500 (let ((stationary-point (make-point 200 200))) (lambda (p) (let ((d (distance-point-point-integer p stationary- point))) (if (fx> d 255) 255 d)))) ) )
El 2 de abril de 2010 19:17, Bradley Lucier <lucier@math.purdue.edu>escribió:
On Apr 2, 2010, at 11:59 AM, Álvaro Castro-Castilla wrote:
Now I have it down to ~350ms. which is 10-20x the C version. with floating point. I can't understand how the straightforward u8vector version (the second in the scheme code) is slower (~500ms) than the same thing with consed lists and afterwards transformed to a u8vector :S
(floor (/ i size-y))))))))
(/ i size-y) is a rational number
(make-point 200 200) keeps making the same point over and over again; in C you make the point once.
Try
(declare (standard-bindings)(extended-bindings)(block)(not safe))
(define-structure point x y)
(define (fxsquare x) (fx* x x))
(define (distance-point-point-integer a b) (##flonum.->fixnum (flsqrt (fixnum->flonum (fx+ (fxsquare (fx- (point-x a) (point-x b))) (fxsquare (fx- (point-y a) (point-y b))))))))
(define (make-2d-field-v2 size-x size-y proc) (let ((point (make-point 0 0))) (let ((len (fx* size-x size-y)))
(do ((vec (make-u8vector len)) (i 0 (fx+ i 1))) ((fx>= i len) vec) (point-x-set! point (fxmodulo i size-y)) (point-y-set! point (fxquotient i size-y)) (u8vector-set! vec i (proc point))))))
(time (make-2d-field-v2 500 500 (let ((stationary-point (make-point 200 200))) (lambda (p) (let ((d (distance-point-point-integer p stationary-point))) (if (fx> d 255) 255 d)))) ) )
Thank you very much. The clean benchmark seams to be only 30% slower in scheme compared to C. That's good enough for me. I've been also reorganizing my application code to compile those critical parts and seems to make a nice improvement. And learnt also things about optimizing scheme/gambit code. Best regards, Álvaro Castro-Castilla
Bradley Lucier <lucier@math.purdue.edu> writes:
This function in C
int distance_point_point(struct point *p1, struct point *p2) { return sqrt( pow( p1->x - p2->x, 2) + pow( p1->y - p2->y, 2) ); }
is translated quite literally into (Gambit) scheme as
(define (distance-point-point a b) (##flonum.->fixnum (flsqrt (fl+ (flexpt (fixnum->flonum (point-x a)) 2.) (flexpt (fixnum->flonum (point-y a)) 2.)))))
The C type inference rules, the automatic conversion of int to double and back, and the header <math.h> takes care of all of that.
And you're allocating manipulating lists in the Scheme version, but using an array in the C version, which you could also do in the scheme version.
So these codes are in only a rough sense "equivalent".
If you add the declarations
(declare (standard-bindings)(extended-bindings)(block)(not safe))
then things should go a bit faster.
Brad _______________________________________________ Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
Sorry for coming in late! I don't think that your C program is doing what you thing it should be. Certainly not what your list-based scheme program is. Specifically, the array indexing in : for (j=0; j< size_y; j++) { for (i=0; i< size_x; i++) { p.x = i; p.y = j; dist = distance_point_point(&p, &refp); if ( dist > 255 ) { block[i*j] = 255; } else { block[i*j] = dist; } } } should probably be block[j*size_x + i]. What you have there is only setting a very limited subset of the elements of the array. Cheers, -- Andrew
El 20 de abril de 2010 08:25, Andrew Reilly <areilly@bigpond.net.au>escribió:
Sorry for coming in late!
I don't think that your C program is doing what you thing it should be. Certainly not what your list-based scheme program is. Specifically, the array indexing in :
for (j=0; j< size_y; j++) { for (i=0; i< size_x; i++) { p.x = i; p.y = j; dist = distance_point_point(&p, &refp); if ( dist > 255 ) { block[i*j] = 255; } else { block[i*j] = dist; } } }
should probably be block[j*size_x + i]. What you have there is only setting a very limited subset of the elements of the array.
Cheers,
-- Andrew
Yes you are right about that and I realized later. I wrote that stuff very quickly just to measure times. I made the same mistake in the scheme code also IRCC :) Thanks for you reply! Álvaro
participants (4)
-
Andrew Reilly -
Bradley Lucier -
Ralf Schmitt -
Álvaro Castro-Castilla