Dear Gaby, Juegen, Waldek, Dear all,
here is a report on what I found in the last few days. I believe it's quite
encouraging. (Juergen, I CC you since I hope you might know something about
(1) below...)
Waldek Hebisch <[EMAIL PROTECTED]> writes:
[...]
> Below is a simple input script which on my machine can solve 100x100 system
> of linear equation in 5.30s when using SBCL as underlying Lisp and about 13s
> when using gcl.
[...]
> SBCL profiler shows that about 1.32s of execution time goes into inverting
> matix over finite field and 1.25s into matrix times vector multiplicatin.
[...]
> Now, speeding up all those stages seem to be a big job.
[...]
Here is part of the original profile:
Self Total Cumul
Nr Count % Count % Count % Function
-------------------------------------------------------------
1 26 9.7 26 9.7 26 9.7 SB-C::COMPACT-INFO-LOOKUP
2 17 6.3 23 8.6 43 16.0 SB-KERNEL:%COERCE-CALLABLE-TO-FUN
3 16 5.9 25 9.3 59 21.9 SB-BIGNUM:BIGNUM-TRUNCATE
4 13 4.8 33 12.3 72 26.8 |IIARRAY2;qelt;$2IR;10|
5 12 4.5 44 16.4 84 31.2 |MATCAT-;*;S2Col;32|
6 8 3.0 14 5.2 92 34.2 ELT
7 7 2.6 7 2.6 99 36.8 (FLET #:CLEANUP-FUN-4)
8 7 2.6 39 14.5 106 39.4 (FLET SB-C::LOOKUP)
9 7 2.6 7 2.6 113 42.0 SB-KERNEL:SEQUENCEP
10 6 2.2 41 15.2 119 44.2 |IMATLIN;rowEchelon;2M;3|
11 6 2.2 6 2.2 125 46.5 SB-VM::GENERIC-+
12 6 2.2 6 2.2 131 48.7
SB-BIGNUM::BIGNUM-ASHIFT-LEFT-UNALIGNED
13 5 1.9 5 1.9 136 50.6 (FLET #:CLEANUP-FUN-77)
14 5 1.9 5 1.9 141 52.4 SB-C::VOLATILE-INFO-LOOKUP
15 4 1.5 4 1.5 145 53.9 SB-IMPL::OPTIMIZED-DATA-VECTOR-REF
I did the following things:
1) modify SPADCALL so that it doesn't need to check anymore whether it gets a
function. This makes *all* of axiom *a lot faster*!
Unfortunately, I was unable to find out how to make this work for anonymous
functions, as "i +-> i" in map(i +-> i, [1,2,3]). Help would be greatly
appreciated. Maybe somebody at least knows how I could go about to find
out? As a hint, these functions are always named
|*1;anonymousFunction;0;initial;internal|.
2) I started to declare some of the variables in the macros used in
SingleInteger. That made hardly a difference.
3) I modified PrimitiveArray to use svref$Lisp instead of elt$Lisp.
Originally, svref$Lisp with fixnum indices was used, but that was commented
out. I guess it would make sense to restrict PrimitiveArrays to fixnum
indices - they are 0-based, so it is quite unlikely that one will need more.
This made a big difference, too.
-------------------------------------------------------------------------------
What to try next:
as you can see below, the next biggest offenders are SB-C::COMPACT-INFO-LOOKUP,
SB-BIGNUM:BIGNUM-TRUNCATE, IIARRAY2;qelt.
* I know nothing about SB-C::COMPACT-INFO-LOOKUP
* SB-BIGNUM:BIGNUM-TRUNCATE seems to be mostly called by divide. I guess we
cannot optimise much here, except possibly the algorithm
rationalReconstruction2 itself.
* IIARRAY2;qelt however points to what I believe to be the most important
optimisation. I include the code here for completeness:
in IIARRAY.spad:
qelt(m,i,j) ==
qelt(qelt(m,i - minRowIndex m)$Rep,j - minColIndex m)
(it calls qelt$PRIMARRAY, which I coded as svref$Lisp.)
this is translated into the following piece of lisp (svref = PRIMMARRQELT):
(DEFUN |IIARRAY2;qelt;$2IR;10| (|m| |i| |j| $)
(PRIMARRQELT (PRIMARRQELT |m| (- |i| (SPADCALL |m| (QREFELT $ 24))))
(- |j| (SPADCALL |m| (QREFELT $ 25)))))
So, (QREFELT $ 24) evaluates to the function minRowIndex, and (QREFELT $ 25) to
the function minColIndex. Always. But there is no way the lisp compiler could
guess that.
So, my hope is that we could actually get rid of such calls, where we happen to
know that they are constant. There is one particularly easy case:
+ if we are defining an operation in a package or domain (i.e., not a default
operation in a category), and
+ if we are calling a function in the same domain.
==> then there is no need to call QREFELT.
I must admit, however, that I have no idea how to modify the compiler to take
advantage of this fact. Since it happens very frequently, I do believe however
that it would have a very noticable effect on the whole system. I guess that
before someone embarks on this, more analysis would be needed, however.
Ideas?
Martin
Here is part of the new profile:
Nr Count % Count % Count % Function
-------------------------------------------------------------
1 19 10.8 19 10.8 19 10.8 SB-C::COMPACT-INFO-LOOKUP
2 14 8.0 26 14.8 33 18.8 SB-BIGNUM:BIGNUM-TRUNCATE
3 12 6.8 14 8.0 45 25.6 |IIARRAY2;qelt;$2IR;10|
4 11 6.3 38 21.6 56 31.8 (FLET SB-C::LOOKUP)
5 9 5.1 9 5.1 65 36.9
SB-BIGNUM::BIGNUM-ASHIFT-LEFT-UNALIGNED
6 8 4.5 8 4.5 73 41.5 SB-C::VOLATILE-INFO-LOOKUP
7 5 2.8 21 11.9 78 44.3 |IMATLIN;rowEchelon;2M;3|
8 5 2.8 17 9.7 83 47.2 |MATCAT-;*;S2Col;32|
9 4 2.3 4 2.3 87 49.4 (FLET #:CLEANUP-FUN-77)
10 4 2.3 4 2.3 91 51.7 (FLET #:CLEANUP-FUN-4)
11 4 2.3 4 2.3 95 54.0 SB-VM::GENERIC-+
12 3 1.7 3 1.7 98 55.7 SB-BIGNUM::%NORMALIZE-BIGNUM
13 3 1.7 3 1.7 101 57.4 SB-BIGNUM:ADD-BIGNUMS
14 3 1.7 3 1.7 104 59.1 ASSOC
15 3 1.7 3 1.7 107 60.8 SB-KERNEL:TWO-ARG--
16 3 1.7 3 1.7 110 62.5 SB-BIGNUM:SUBTRACT-BIGNUM
17 2 1.1 2 1.1 112 63.6 |ZMOD;*;3$;30|
18 2 1.1 76 43.2 114 64.8 |coerceInt1|
and some details:
Callers
Total. Function
Count % Count % Callees
-----------------------------------------------------------------------
19 10.8 (FLET SB-C::LOOKUP) [4]
19 10.8 19 10.8 SB-C::COMPACT-INFO-LOOKUP [1]
-----------------------------------------------------------------------
22 12.5 |INT;divide;2$R;45| [153]
4 2.3 REM [33]
14 8.0 26 14.8 SB-BIGNUM:BIGNUM-TRUNCATE [2]
9 5.1 SB-BIGNUM::BIGNUM-ASHIFT-LEFT-UNALIGNED [5]
3 1.7 SB-BIGNUM::%NORMALIZE-BIGNUM [12]
-----------------------------------------------------------------------
5 2.8 |MATCAT-;*;S2Col;32| [8]
9 5.1 |IMATLIN;rowEchelon;2M;3| [7]
12 6.8 14 8.0 |IIARRAY2;qelt;$2IR;10| [3]
2 1.1 |IIARRAY2;minColIndex;$I;5| [25]
-----------------------------------------------------------------------
2 1.1 SB-EVAL::SPECIALP [157]
16 9.1 MACRO-FUNCTION [22]
2 1.1 SB-KERNEL:VALUES-SPECIFIER-TYPE [21]
17 9.7 SB-KERNEL:FDEFINITION-OBJECT [131]
1 0.6 SB-EVAL::GET-VARIABLE [69]
11 6.3 38 21.6 (FLET SB-C::LOOKUP) [4]
1 0.6 (LABELS SB-IMPL::SXHASH-RECURSE) [20]
7 4.0 SB-C::VOLATILE-INFO-LOOKUP [6]
19 10.8 SB-C::COMPACT-INFO-LOOKUP [1]
-----------------------------------------------------------------------
9 5.1 SB-BIGNUM:BIGNUM-TRUNCATE [2]
9 5.1 9 5.1 SB-BIGNUM::BIGNUM-ASHIFT-LEFT-UNALIGNED [5]
-----------------------------------------------------------------------
1 0.6 SB-C::TYPE-INFO-OR-LOSE [19]
7 4.0 (FLET SB-C::LOOKUP) [4]
8 4.5 8 4.5 SB-C::VOLATILE-INFO-LOOKUP [6]
-----------------------------------------------------------------------
21 11.9 |IMATLIN;inverse;MU;9| [103]
5 2.8 21 11.9 |IMATLIN;rowEchelon;2M;3| [7]
1 0.6 |ZMOD;*;3$;30| [17]
4 2.3 REM [33]
1 0.6 SB-KERNEL:HAIRY-DATA-VECTOR-SET/CHECK-BOUNDS [32]
9 5.1 |IIARRAY2;qelt;$2IR;10| [3]
1 0.6 |IIARRAY2;qsetelt!;$2I2R;12| [31]
-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
open-axiom-devel mailing list
open-axiom-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open-axiom-devel
