[gambit-list] code optimization & compilation

Guillaume Lathoud glathoud at yahoo.fr
Wed Apr 10 02:01:29 EDT 2013


Hello,

Thanks to both of you for the advice, I have obtained performance improvements using (declare .. (block) (not safe)) and removing the assignment to sum. My Gambit was configured with --enable-single-host only. I have to try to add--enable-gcc-opts


Removing the assignment to the result vector would be a bit more work I guess, but incidentally that is what the "flat" code avoids:
https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul342.scm#L31

...which brings me to Marc's questions:

"There are many things you can do to improve the performance of your 
code, but I wonder what you are trying to achieve.  For instance, your code is multiplying matrices of small exact integers.  Is this a given 
in your problem or you want the code to work also for floating point numbers?  Also, do you want the code to conform to a specific standard 
of Scheme, or you are willing to adapt your code to a specific Scheme 
implementation?  For Gambit you could store the numbers in a homogeneous numerical vector (e.g. s16vector, f64vector, etc) instead of a plain 
vector, and use fixnum specific operations for computing the indices of 
the matrix."

I first wanted to check whether generating flat code would help to bring big performance improvements without too much specific work - basically looking for a sweet spot. So I wrote such "flat code" on this small example - manually translating from the generated JavaScript code, see the links below - and wrote to the mailing list hereto make sure that I am not missing something obvious while compiling, as well as in the baselines I have been comparing with (classic and list_of_lists).


Now the real deal is to be able to express more complex mathematical expressions, and have "flat" code automaticallygenerated:

http://glat.info/flatorize/#dft
http://glat.info/flatorize/#push-dft1024
You can click on the "Try flatorize" buttons to see the generated JavaScript code. It was not straightforward to getthe code generation to work in a tractable time for significantly recursive cases such as the 1024-point DFT.


Back to Marc's questions: my first goal is to remain generic and see how far one can go with the code generation - at this point of time I only wanted to eliminate big mistakes, thanks for the help.


Now, in addition, since Gambit provides many interesting optimization possibilities, I certainly would like to try them as well. The challenge would be to provide means to specify where the generated code should use them (instead of writing or changing everything manually). Suggestions are welcome. 


Now, just speculating: could the Gambit compiler automatically detect and flatten such mathematical expressions? In such a case it would not be necessary to "pre-generate" flat code.


On a side note a quick try in C showed a speedup as well:
https://github.com/glathoud/flatorize/blob/master/explore/C/cAll_matmul.results.txt

Best regards,
Guillaume




________________________________
 De : "gambit-list-request at iro.umontreal.ca" <gambit-list-request at iro.umontreal.ca>
À : gambit-list at iro.umontreal.ca 
Envoyé le : Mardi 9 avril 2013 18h00
Objet : Gambit-list Digest, Vol 103, Issue 10
 
Today's Topics:

   1. code optimization & compilation (Guillaume Lathoud)
   2. Re: code optimization & compilation (Alex Queiroz)
   3. Re: code optimization & compilation (Alex Queiroz)
   4. Re: code optimization & compilation (Marc Feeley)


----------------------------------------------------------------------

Message: 1
Date: Tue, 9 Apr 2013 05:36:00 +0100 (BST)
From: Guillaume Lathoud <glathoud at yahoo.fr>
Subject: [gambit-list] code optimization & compilation
To: Gambit List <gambit-list at iro.umontreal.ca>
Message-ID:
    <1365482160.5341.YahooMailNeo at web171306.mail.ir2.yahoo.com>
Content-Type: text/plain; charset="utf-8"

Hello,

on a simple task - multiply two matrices mat_a and mat_b https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul_common.scm - I've been comparing 3 implementations, using interpretation and compilation.

To compile I used the line below. Is there a better way, at least a few straightforward optimization (options) ?

gsc -exe -o scheme_matmul_classic.bin tmp.scmDetails are below.

Best regards,
Guillaume


1. Functional implementation: 
https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul_list_of_lists.scm#L50

2. Ugly imperative implementation: 
https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul_classic.scm#L33

3. Flat implementation (for the specific matrix sizes): 
https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul342.scm#L31



To run both tests (interpreted and compiled), I used this: 

https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul.sh#L16

Results: 

https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul.results.txt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://webmail.iro.umontreal.ca/pipermail/gambit-list/attachments/20130409/df28cd69/attachment-0001.html 

------------------------------

Message: 2
Date: Tue, 9 Apr 2013 09:32:49 +0200
From: Alex Queiroz <asandroq at gmail.com>
Subject: Re: [gambit-list] code optimization & compilation
To: Guillaume Lathoud <glathoud at yahoo.fr>
Cc: Gambit List <gambit-list at iro.umontreal.ca>
Message-ID:
    <CABpjPc+x4-vqacb79VLiX2Z26y7boPQLPunFxL3SipF0i64DGg at mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

Hallo,

On Tue, Apr 9, 2013 at 6:36 AM, Guillaume Lathoud <glathoud at yahoo.fr> wrote:
>
> To compile I used the line below. Is there a better way, at least a few
> straightforward optimization (options) ?
>

Add this to the source file:

(declare
   (block)
   ; (not safe)
   (standard-bindings)
   (extended-bindings))

You can try with and without `(not safe)` and compare the results :)

Cheers,
--
-alex
http://unendli.ch/


------------------------------

Message: 3
Date: Tue, 9 Apr 2013 09:36:56 +0200
From: Alex Queiroz <asandroq at gmail.com>
Subject: Re: [gambit-list] code optimization & compilation
To: Guillaume Lathoud <glathoud at yahoo.fr>
Cc: Gambit List <gambit-list at iro.umontreal.ca>
Message-ID:
    <CABpjPcLwe_0D_jAUF7s1w8uxnnpvE3nrOJYXVHg16av_-JRYtw at mail.gmail.com>
Content-Type: text/plain; charset=UTF-8

Hallo again,

On Tue, Apr 9, 2013 at 9:32 AM, Alex Queiroz <asandroq at gmail.com> wrote:
>
> Add this to the source file:
>
> (declare
>    (block)
>    ; (not safe)
>    (standard-bindings)
>    (extended-bindings))
>
> You can try with and without `(not safe)` and compare the results :)
>

Also, have you configured Gambit-C with `--enable-single-host
--enable-gcc-opts`?

Cheers,
--
-alex
http://unendli.ch/


------------------------------

Message: 4
Date: Tue, 9 Apr 2013 09:26:07 -0400
From: Marc Feeley <feeley at iro.umontreal.ca>
Subject: Re: [gambit-list] code optimization & compilation
To: Guillaume Lathoud <glathoud at yahoo.fr>
Cc: Gambit List <gambit-list at iro.umontreal.ca>
Message-ID: <ACE203BD-9D74-429C-827D-10D93E70F357 at iro.umontreal.ca>
Content-Type: text/plain; charset=us-ascii


On 2013-04-09, at 12:36 AM, Guillaume Lathoud <glathoud at yahoo.fr> wrote:

> Hello,
> 
> on a simple task - multiply two matrices mat_a and mat_b https://github.com/glathoud/flatorize/blob/master/explore/scheme_matmul_common.scm - I've been comparing 3 implementations, using interpretation and compilation.
> 
> To compile I used the line below. Is there a better way, at least a few straightforward optimization (options) ?
> gsc -exe -o scheme_matmul_classic.bin tmp.scm
> Details are below.
> 
> Best regards,
> Guillaume

There are many things you can do to improve the performance of your code, but I wonder what you are trying to achieve.  For instance, your code is multiplying matrices of small exact integers.  Is this a given in your problem or you want the code to work also for floating point numbers?  Also, do you want the code to conform to a specific standard of Scheme, or you are willing to adapt your code to a specific Scheme implementation?  For Gambit you could store the numbers in a homogeneous numerical vector (e.g. s16vector, f64vector, etc) instead of a plain vector, and use fixnum specific operations for computing the indices of the matrix.  Finally, you should avoid using assignments if you can use iteration variables instead.  So, instead of

  (let ((sum 0))
    (let loop ((i 0))
      (if (< i n)
          (begin
            (set! sum (+ sum i))
            (loop (+ i 1)))))
    sum)

you should write

  (let loop ((i 0) (sum 0))
    (if (< i n)
        (loop (+ i 1) (+ sum i))
        sum))

Marc



------------------------------

_______________________________________________
Gambit-list mailing list
Gambit-list at iro.umontreal.ca
https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list


End of Gambit-list Digest, Vol 103, Issue 10
********************************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20130410/f281668c/attachment.htm>


More information about the Gambit-list mailing list