[Axiom-developer] understanding domain vectors, optimization etc., was: Re: [fricas-devel] Re: Solving linear equations

[Martin Rubey]

Dear all,

Waldek Hebisch <address@hidden> writes:

> Some source of inefficiency is clear: profile shows that access to matrix
> elements is done via function calls and that those calls take substantial
> time (more than arithmetic).  Also aritmetic in Z_p is done via function
> calls which is much slower than inline code.

and a little later:

> Let us at maxColIndex.  In IIARRAY2.lsp we have:
> 
> (DEFUN |IIARRAY2;maxColIndex;$I;7| (|m| $)
>   (- (+ (SPADCALL |m| (QREFELT $ 28)) (QREFELT $ 8)) 1))
> 
> which means: 
>  1) maxColIndex get m as normal argument, and has the second argument
>     called '$' which is a "domain vector" (a vector which is a runtime
>     representation of a type).
>  2) first we take element 28 from domain vector of current domain and call
>     it giving it m as argument.  The call also must pass correct domain
>     vector, I am too lazy to check what this will be, but the SPADCALL
>     macro is responsible for passing it.
>  3) next, we fetch element number 8 from domain vestor and add it
>     to the result of previous call.
>  4) finally we substract 1 to get final result.
> 
> Note that Lisp compiler have no idea what m can be.  Also, since we have:
> 
>     maxColIndex m == ncols m + mnCol - 1
> 
> I can deduce that (SPADCALL |m| (QREFELT $ 28)) corresponds to ncols m, but
> Lisp compiler have no idea which function will be called.

I was looking a little closer at the lisp code generated by the SPAD compiler.
There are still a few things I do not understand:

a) how is some function like |IIARRAY2;maxColIndex;$I;7| actually called?  More
   precisely, where does it get it's second argument (the domain vector) from?

b) isn't the domain vector constant for domains and packages?  I guess it won't
   be constant for default domains, right?  I believe it should be that way,
   because there is no way that a function definition in a domain or package
   can be overridden, contrary to default definitions in categories.

c) how does SPADCALL work?  I tried:

    (1) -> )lisp (macroexpand '(SPADCALL |m| (QREFELT $ 28)))
    
    Value = (LET ((#:G1406 (QREFELT $ 28)))
              (THE (VALUES T) (FUNCALL (CAR #:G1406) |m| (CDR #:G1406))))


   and I know that (QREFELT $ 28) produces element number 28 from the domain
   vector, but I was (so far) unable to find out what it looks like precisely.

   At the end of IIARRAY2.NRLIB/code.lsp I find a MAKEPROP statement which
   seems to take three arguments, the third one being a list with a couple of
   elements, whose car is a vector that has as element 28
   |IIARRAY2;ncols;$Nni;9|.  So, that has clearly something to do with the
   domain vector, but it's only half the story...


In fact, b) may be the most important question: if I'm right and the domain
vector is indeed constant for domains, then there may be some room for
optimization -- given that a lisp compiler will not optimize away the FUNCALL
in

    (LET ((#:G1406 (QREFELT $ 28)))
      (THE (VALUES T) (FUNCALL (CAR #:G1406) |m| (CDR #:G1406))))

???


I believe -- since IIARRAY2 is a domain --

    maxColIndex m == ncols m + mnCol - 1 

which currently translates to

    (DEFUN |IIARRAY2;maxColIndex;$I;7| (|m| $)
        (- (+ (SPADCALL |m| (QREFELT $ 28)) (QREFELT $ 8)) 1))

could become something like

    (DEFUN |IIARRAY2;maxColIndex;$I;7| (|m| $)
        (- (+ (|IIARRAY2;ncols;$Nni;9| |m| $) (QREFELT $ 8)) 1))


Martin