Fwd: RE: JAMA Improvement: Double JAMA's Speed

[boisvert@nist.gov]

Sender: "Castro, Giovanny A" <>
Subject: RE: JAMA Improvement: Double JAMA's Speed



All, 

> Why just for small matrices?

The performance benefit gained from switching to one-dimensional arrays
stops at a size of around [15 x 15] to [17 x 17]. After that,
one-dimensional arrays get increasingly (and substantially) slower than
two-dimensional arrays.

I didn't make it clear in the original post but the speed up doesn't
come
from doing anything computationally different. The speed up comes from a
combination of not having to create a two-dimensional array every time
and from the JVM having to jump around in memory (since two-dimensional
arrays in java are arrays of arrays).

http://www.kaourantin.net/2007/02/limits-of-software-rendering.html


> The 3x3 case is obvious, but I don't really know what 
else would be needed. (I'm not a graphics programmer.)

Actually, 4x4 matrices are needed for computer graphics as most things
are done with homogeneous coordinates.


> My experience is that the monolithic array design that ojAlgo has

JAMA should in no way have to adopt a "monolithic" array design on the
order of ojalgo. This "improvement" would only require a way of using
one-dim arrays sometimes and two-dim other times. 

As I said before, it seems warranted because of the special nature of
3x3s and 4x4s and the ability to double the performance at those sizes.



-----Original Message-----
From: Anders Peterson [mailto:anders_peterson@optimatika.se] 
Sent: Monday, November 12, 2007 10:48 AM
To: jama@nist.gov
Subject: Re: JAMA Improvement: Double JAMA's Speed

I now think that the reason ojAlgo seems to perform slower with small 
matrices in spite of its monolithic array design is a different aspect 
of the array design. To modify ojAlgo dense/physical matrices you 
typically call a method like this:


    protected void modifyAll(UnaryFunction<Double> aFunc) {
        for (int i = 0; i < myArray.length; i++) {
            myArray[i] = aFunc.invoke(myArray[i]);
        }
    }


For small matrices that design is not efficient, but for larger matrices

it is very efficient.

I've long thought about doing specific implementations for small, fixed 
size, matrices. The 3x3 case is obvious, but I don't really know what 
else would be needed. (I'm not a graphics programmer.)

/Anders
http://ojalgo.org/


Joe Hicklin wrote:
> Why just for small matrices?
>
>
> -----Original Message-----
>   
>> From: jama@nist.gov [mailto:jama@nist.gov] On Behalf Of
>>     
> boisvert@nist.gov
> Sent: Sunday, November 11, 2007 5:27 PM
> To: Multiple recipients of list
> Subject: Fwd: JAMA Improvement: Double JAMA's Speed
>
>
>
> ----- Forwarded message from "Castro, Giovanny A"
>     Date: Fri, 9 Nov 2007 20:26:04 -0500
>     From: "Castro, Giovanny A" <>
>  Subject: JAMA Improvement: Double JAMA's Speed
>       To: boisvert@nist.gov
>
>
> JAMA Authors, 
>
>
> I have a somewhat strange but valid proposal to improve the JAMA
> library:
>
> There should be a Matrix subclass for Matrix sizes under 15.
> Why? To take advantage of dramatic performance increases when using 
> one dimensional arrays at these sizes.
>
> For a 4x4 matrix a one dimensional array implementation is TWICE as
fast
> as the JAMA implementation. 
>
> Why are 4x4 and 3x3 matrices important? They are critical to computer
> graphics and engineering applications. It would be my guess that a
large
> percentage of people interested in a matrix library are interested in 
> using it in a computer graphics application - or in other engineering
> applications requiring scaling, translation and rotation.
>
> As it stands, JAMA is completely unacceptable for these applications.
>
> Especially in computer graphics applications, Java developers are
> already at a disadvantage compared to C/C++ (even Flash) developers. 
>
> If they could DOUBLE their Matrix and Vector multiplication (rotation)
> performance why would they choose JAMA?
>
> Unfortunately, implementing this proposal would require a redesigning
of
> the JAMA library which is why I know this is a strange proposal.
>
> Developers cant subclass the Matrix class to do this themselves
because
> it contains the double A[][] variable. Matrix might have to be an 
> abstract class with subclasses defining the data storage. There might 
> have to be a factory method by which to create matrices because
> it would have to return a one-dimensionally or two-dimensionally
backed
> matrix depending on the dimensions...
>
> Obviously, I haven't considered the specifics of what would have to be
> done to JAMA to achieve this but I hope ive piqued someone curiosity 
> on this subject.  
>
> This thread is extremely chaotic but by the end the disparity between
> one-dimensional and two-dimensional arrays is shown:
>
> http://forum.java.sun.com/thread.jspa?threadID=5234721&tstart=0
>
> These are the results of JAMA vs a one-dimensional implementation
doing 
> 2 million matrix multiplication operations on 4x4 matrices (in
> milliseconds):
>
> One Dim Time: 3626
> JAMA Time: 7625
>
> One Dim Time: 3438
> JAMA Time: 7610
>
> One Dim Time: 3235
> JAMA Time: 7516 
>
> One Dim Time: 3235
> JAMA Time: 7532
>
> One Dim Time: 3250
> JAMA Time: 7610
>  
>
> Giovanny Castro
>
> ----- End forwarded message -----
>
>
>
>
>
> ----- End forwarded message -----
>
>
>
>
>
>   



----- End forwarded message -----