Re: [math] Performance optimization in the vector classes

[Jake Mannix]

Hey all,

  In digging through ArrayRealVector and OpenMapRealVector, while trying to
draw up patches for MATH-312 and MATH-314, I found a number of performance (
and other) issues:

1) in add(double[]), subtract(double[]), and mapXXX methods, the idiom is:

  double[] v = new double[data.length];
  for(int i=0; i<v.length; i++) {
    v[i] = data[i] + otherVector[i]; // for example, for add()
  }
  return new ArrayRealVector(v);

if this were instead:

  double[] v = data.clone();
  for(int i=0; i<v.length; i++) {
    v[i] += otherVector[i];
  }
  return new ArrayRealVector(v, false);   // <- ack!  not passing false here
forces a clone() call when you least need it!

The difference of doing only one array access inside the loop alone saved
30% on profiling tests on my laptop with 1M long double arrays.  I don't
even want to think about the cost of making superflous array copies as well.

2) In OpenMapRealVector, any case where two OpenMapRealVectors are combined
together, iterating over the smaller should be preferred, but this is never
checked for.

3) what's with the idiom of:

  try { return methodName( (ArrayRealVector) v); } catch (ClassCastException
cce) {

instead of the standard

  if(v instanceof ArrayRealVector) { return methodName( (ArrayRealVector)
v); } else {

Is there something I'm missing on why the former shows up all over the
place?  Maybe this isn't a performance issue, but I just noticed it.

4) ArrayRealVector#unitVector() calls norm() once, and then it calls it
again.  That's clearly unnecessary.  Also, why the special case for
ArithmeticExcption here, for the zero norm case?  Why not just let java just
try to divide, and if it divides by zero, well, it'll throw an
ArithmeticException itself...  seems like the whole method should just be
implemented as " return mapDivide(norm()); "

I've fixed many of these in my patch on MATH-312, but there's another
version of that I need to post once I correctly handle the sparse nonzero
defaultValue case.   I also wasn't sure if you guys usually liked to
separate your fixes into a bunch of little ones or not.  It's just hard for
me to keep a dozen different patches in sync my end without conflicting with
myself now and again.

  -jake

[Luc Maisonobe]

----- "Jake Mannix" <[hidden email]> a écrit :

> Hey all,
>
>   In digging through ArrayRealVector and OpenMapRealVector, while
> trying to
> draw up patches for MATH-312 and MATH-314, I found a number of
> performance (
> and other) issues:
>
> 1) in add(double[]), subtract(double[]), and mapXXX methods, the idiom
> is:
>
>   double[] v = new double[data.length];
>   for(int i=0; i<v.length; i++) {
>     v[i] = data[i] + otherVector[i]; // for example, for add()
>   }
>   return new ArrayRealVector(v);
>
> if this were instead:
>
>   double[] v = data.clone();
>   for(int i=0; i<v.length; i++) {
>     v[i] += otherVector[i];
>   }
>   return new ArrayRealVector(v, false);   // <- ack!  not passing
> false here
> forces a clone() call when you least need it!

This is the reason why the boolean is there.

>
> The difference of doing only one array access inside the loop alone
> saved
> 30% on profiling tests on my laptop with 1M long double arrays.  I
> don't
> even want to think about the cost of making superflous array copies as
> well.

Fine, good catch. Let's implement it.

>
> 2) In OpenMapRealVector, any case where two OpenMapRealVectors are
> combined
> together, iterating over the smaller should be preferred, but this is
> never
> checked for.

I think we discussed about similar things in the last few months, and simply forgot to do it.

>
> 3) what's with the idiom of:
>
>   try { return methodName( (ArrayRealVector) v); } catch
> (ClassCastException
> cce) {
>
> instead of the standard
>
>   if(v instanceof ArrayRealVector) { return methodName(
> (ArrayRealVector)
> v); } else {
>
> Is there something I'm missing on why the former shows up all over
> the
> place?  Maybe this isn't a performance issue, but I just noticed it.

In the cast, the check for the class is done internally, and can be optimised by the compiler, particularly when this method is inlined. So this is an attempt to avoid one if and to let the compiler directly call the specific methods for ArrayRealVector which is much faster than the generic one. I understand it is a bit weird.

>
> 4) ArrayRealVector#unitVector() calls norm() once, and then it calls
> it
> again.  That's clearly unnecessary.

You are right. the lat line should simply use the norm local variable which in fact was introduced just for this reason.

> Also, why the special case for
> ArithmeticExcption here, for the zero norm case?  Why not just let
> java just
> try to divide, and if it divides by zero, well, it'll throw an
> ArithmeticException itself...  seems like the whole method should just
> be
> implemented as " return mapDivide(norm()); "

No. A division by zero does not lead to ArithmeticException when dealing with double variables, it leads to a NaN being produced. ArithmeticException is triggered when an integer division by zero occurs.

>
> I've fixed many of these in my patch on MATH-312, but there's another
> version of that I need to post once I correctly handle the sparse
> nonzero
> defaultValue case.   I also wasn't sure if you guys usually liked to
> separate your fixes into a bunch of little ones or not.  It's just
> hard for
> me to keep a dozen different patches in sync my end without
> conflicting with
> myself now and again.

We really prefer separate patches as we commit them separately.
This allows having a clear history in the svn repository.

Luc

>
>   -jake

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

[Jake Mannix]

On Mon, Nov 2, 2009 at 7:41 AM, <[hidden email]> wrote:

>
> This is the reason why the boolean is there.
>

Yeah, I know, my point is that in the current method implementation,
the boolean is not used properly - it's currently: return new
ArrayRealVector(v)
which forces a copy.  return new ArrayRealVector(v, false) fixes this bug.


> > The difference of doing only one array access inside the loop alone
> > saved
> > 30% on profiling tests on my laptop with 1M long double arrays.  I
> > don't
> > even want to think about the cost of making superflous array copies as
> > well.
>
> Fine, good catch. Let's implement it.
>

I'll open a separate JIRA and patch for it then.


> > 2) In OpenMapRealVector, any case where two OpenMapRealVectors are
> > combined
> > together, iterating over the smaller should be preferred, but this is
> > never
> > checked for.
>
> I think we discussed about similar things in the last few months, and
> simply forgot to do it.
>

Ditto for this one.


> In the cast, the check for the class is done internally, and can be
> optimised by the compiler, particularly when this method is inlined. So this
> is an attempt to avoid one if and to let the compiler directly call the
> specific methods for ArrayRealVector which is much faster than the generic
> one. I understand it is a bit weird.
>

It really works this way?  The JIT compiler takes a situation where an
exception is thrown, and optimizes it away into calling the other methods,
without doing any stack jumping?  If at runtime, the method only gets passed
ArrayRealVectors for a while, how does the JIT know that OpenMapRealVector
won't be called in the future?  It seems that if a runtime configuration had
a large mixture of calls to this method with different vector
implementations, there could be no inlining, and instead there would be tons
of superfluous Exception object creation and stack jumping.  Or am I missing
how this works?

> 4) ArrayRealVector#unitVector() calls norm() once, and then it calls
> > it
> > again.  That's clearly unnecessary.
>
> You are right. the lat line should simply use the norm local variable which
> in fact was introduced just for this reason.
>

JIRA and patch, coming up.

>
> > Also, why the special case for
> > ArithmeticExcption here, for the zero norm case?  Why not just let
> > java just
> > try to divide, and if it divides by zero, well, it'll throw an
> > ArithmeticException itself...  seems like the whole method should just
> > be
> > implemented as " return mapDivide(norm()); "
>
> No. A division by zero does not lead to ArithmeticException when dealing
> with double variables, it leads to a NaN being produced. ArithmeticException
> is triggered when an integer division by zero occurs.
>

Duh of course, right.


> We really prefer separate patches as we commit them separately.
> This allows having a clear history in the svn repository.
>

Fair enough.

  -jake

[Luc Maisonobe]

Jake Mannix a écrit :

> On Mon, Nov 2, 2009 at 7:41 AM, <[hidden email]> wrote:
>
>> This is the reason why the boolean is there.
>>
>
> Yeah, I know, my point is that in the current method implementation,
> the boolean is not used properly - it's currently: return new
> ArrayRealVector(v)
> which forces a copy.  return new ArrayRealVector(v, false) fixes this bug.
>
>
>>> The difference of doing only one array access inside the loop alone
>>> saved
>>> 30% on profiling tests on my laptop with 1M long double arrays.  I
>>> don't
>>> even want to think about the cost of making superflous array copies as
>>> well.
>> Fine, good catch. Let's implement it.
>>
>
> I'll open a separate JIRA and patch for it then.
>
>
>>> 2) In OpenMapRealVector, any case where two OpenMapRealVectors are
>>> combined
>>> together, iterating over the smaller should be preferred, but this is
>>> never
>>> checked for.
>> I think we discussed about similar things in the last few months, and
>> simply forgot to do it.
>>
>
> Ditto for this one.
>
>
>> In the cast, the check for the class is done internally, and can be
>> optimised by the compiler, particularly when this method is inlined. So this
>> is an attempt to avoid one if and to let the compiler directly call the
>> specific methods for ArrayRealVector which is much faster than the generic
>> one. I understand it is a bit weird.
>>
>
> It really works this way?  The JIT compiler takes a situation where an
> exception is thrown, and optimizes it away into calling the other methods,
> without doing any stack jumping?  If at runtime, the method only gets passed
> ArrayRealVectors for a while, how does the JIT know that OpenMapRealVector
> won't be called in the future?  It seems that if a runtime configuration had
> a large mixture of calls to this method with different vector
> implementations, there could be no inlining, and instead there would be tons
> of superfluous Exception object creation and stack jumping.  Or am I missing
> how this works?

There are several cases. If you do:

  RealVector v = new ArrayRealVector(...);

and later use v, a static analysis would be sufficient to know v is
really an ArrayRealVector instance.

If you have a more complex code, but at the beginning of the loops the
JVM knows it has only loaded one class implementing RealVector, then the
compiler will use that information when optimising the native code it
creates at run time. If later a new implementation is loaded, then the
JVM invalidates this code and redo the compilation using different
assumptions for optimisation. This is one of the great things with
dynamic compilation and optimisation. It adjusts itself according to how
the code is used. Modern optimizers are really smart.

>
>> 4) ArrayRealVector#unitVector() calls norm() once, and then it calls
>>> it
>>> again.  That's clearly unnecessary.
>> You are right. the lat line should simply use the norm local variable which
>> in fact was introduced just for this reason.
>>
>
> JIRA and patch, coming up.

Thanks.

Luc

>
>
>>> Also, why the special case for
>>> ArithmeticExcption here, for the zero norm case?  Why not just let
>>> java just
>>> try to divide, and if it divides by zero, well, it'll throw an
>>> ArithmeticException itself...  seems like the whole method should just
>>> be
>>> implemented as " return mapDivide(norm()); "
>> No. A division by zero does not lead to ArithmeticException when dealing
>> with double variables, it leads to a NaN being produced. ArithmeticException
>> is triggered when an integer division by zero occurs.
>>
>
> Duh of course, right.
>
>
>> We really prefer separate patches as we commit them separately.
>> This allows having a clear history in the svn repository.
>>
>
> Fair enough.
>
>   -jake
>

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

[Jake Mannix]

On Mon, Nov 2, 2009 at 12:43 PM, Luc Maisonobe <[hidden email]>wrote:

>
> There are several cases. If you do:
>
>  RealVector v = new ArrayRealVector(...);
>
> and later use v, a static analysis would be sufficient to know v is
> really an ArrayRealVector instance.
>

Ok, I was familiar with this, yes, and in this case, you never even
fall into the method which has the whole "try { return methodCall((ARV)v);
}"
implementation - you just skip right to the correct method, and all is good,
no if(), not thrown exception, top speed all around.


> If you have a more complex code, but at the beginning of the loops the
> JVM knows it has only loaded one class implementing RealVector, then the
> compiler will use that information when optimising the native code it
> creates at run time. If later a new implementation is loaded, then the
> JVM invalidates this code and redo the compilation using different
> assumptions for optimisation. This is one of the great things with
> dynamic compilation and optimisation. It adjusts itself according to how
> the code is used. Modern optimizers are really smart.
>

What I'm not sure about is that if you have complex code with lots of
mixtures
between different implementations of the interface, then my understanding
was
that eventually the JVM realizes it can't keep inlining and throwing away
the
inline, then doing it again and again, and drops back to the unoptimized
version, because, as you say, the compiler is smart, and realizes that it
can't win by continually changing this implementation.

In this scenario, the JVM has to throw exceptions and then catch them on
each method call where the cast is wrong.  This seems like a really nasty
performance bug to track down if this was the case.

Either way, I see that this idiom is not consistently applied: in
OpenMapRealVector,
the far more common if/else instead of try/catch is used for the flow
control.

  -jake

[Jake Mannix]

On Mon, Nov 2, 2009 at 9:05 AM, Jake Mannix <[hidden email]> wrote:

> > Also, why the special case for
>> > ArithmeticExcption here, for the zero norm case?  Why not just let
>> > java just
>> > try to divide, and if it divides by zero, well, it'll throw an
>> > ArithmeticException itself...  seems like the whole method should just
>> > be
>> > implemented as " return mapDivide(norm()); "
>>
>> No. A division by zero does not lead to ArithmeticException when dealing
>> with double variables, it leads to a NaN being produced. ArithmeticException
>> is triggered when an integer division by zero occurs.
>>
>
> Duh of course, right.
>

So about this, actually... it seems that this is not done consistently
throughout the vector classes - mapDivide could divide by zero, but does not
explicitly throw ArithmeticException, so why does unitVector() ?
Similarly, projection doesn't bother to check if you're projecting onto the
zero vector, and would end up with a vector of NaN which is just what
unitVector() is avoiding.

It actually looks like the isNaN() and isInfinite() methods aren't used
anywhere except in unit tests.  Does this mean that they are not checked in
any of the solvers?

  -jake

[Luc Maisonobe]

Jake Mannix a écrit :

> On Mon, Nov 2, 2009 at 9:05 AM, Jake Mannix <[hidden email]> wrote:
>
>>> Also, why the special case for
>>>> ArithmeticExcption here, for the zero norm case?  Why not just let
>>>> java just
>>>> try to divide, and if it divides by zero, well, it'll throw an
>>>> ArithmeticException itself...  seems like the whole method should just
>>>> be
>>>> implemented as " return mapDivide(norm()); "
>>> No. A division by zero does not lead to ArithmeticException when dealing
>>> with double variables, it leads to a NaN being produced. ArithmeticException
>>> is triggered when an integer division by zero occurs.
>>>
>> Duh of course, right.
>>
>
> So about this, actually... it seems that this is not done consistently
> throughout the vector classes - mapDivide could divide by zero, but does not
> explicitly throw ArithmeticException, so why does unitVector() ?

Because I am inconsistent with myself :-)
Well, unitVector comes from an old former implementation, in a previous
library that was written years ago and partly merged into commons-math
in 2007 (merging is not completed yet). Now, after more than 20 years
working in the science/computation/simulation/space/numerical analysis
field I finally trust IEEE754 and how it is implemented in modern
languages and processors. So I changed my mind and now let NaN occurs
automatically and do not check each and every division, just as I don't
check each square root for negative arguments or arc sines for arguments
 out of [-1; 1]. One drawback is that when a NaN occurs, you don't know
exactly where it started. You usually see a bunch of NaNs in the output
and have to reproduce the problem with a debugger to understand what
happened. If you explicitly checks an operation and throws an exception,
you immediately knows where it is triggered, but the drawback of this
choice is that code is slower (lots of tests and branching) and
difficult to read and maintain.

So the trade-off is to check only some important operations, and to let
other operations unchecked. There is no simple absolute solution, it is
only a compromise and depending on the mood of the day one specific
operation may be protected or not.

I feel unitVector is worth being checked and mapDivide is not, but it's
only one person's feelings.

> Similarly, projection doesn't bother to check if you're projecting onto the
> zero vector, and would end up with a vector of NaN which is just what
> unitVector() is avoiding.
>
> It actually looks like the isNaN() and isInfinite() methods aren't used
> anywhere except in unit tests.  Does this mean that they are not checked in
> any of the solvers?

I don't think they are used in solvers.
They will probably be used in eigen decomposition soon because one bug
recently raised should probably be handled with it.

Luc

>
>   -jake
>


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

[Jake Mannix]

On Mon, Nov 2, 2009 at 1:29 PM, Luc Maisonobe <[hidden email]> wrote:

> Jake Mannix a écrit :
> > On Mon, Nov 2, 2009 at 9:05 AM, Jake Mannix <[hidden email]>
> wrote:
> >
> >>> Also, why the special case for
> >>>> ArithmeticExcption here, for the zero norm case?  Why not just let
> >>>> java just
> >>>> try to divide, and if it divides by zero, well, it'll throw an
> >>>> ArithmeticException itself...  seems like the whole method should just
> >>>> be
> >>>> implemented as " return mapDivide(norm()); "
> >>> No. A division by zero does not lead to ArithmeticException when
> dealing
> >>> with double variables, it leads to a NaN being produced.
> ArithmeticException
> >>> is triggered when an integer division by zero occurs.
> >>>
> >> Duh of course, right.
> >>
> >
> > So about this, actually... it seems that this is not done consistently
> > throughout the vector classes - mapDivide could divide by zero, but does
> not
> > explicitly throw ArithmeticException, so why does unitVector() ?
>
> Because I am inconsistent with myself :-)
> Well, unitVector comes from an old former implementation, in a previous
> library that was written years ago and partly merged into commons-math
> in 2007 (merging is not completed yet). Now, after more than 20 years
> working in the science/computation/simulation/space/numerical analysis
> field I finally trust IEEE754 and how it is implemented in modern
> languages and processors. So I changed my mind and now let NaN occurs
> automatically and do not check each and every division, just as I don't
> check each square root for negative arguments or arc sines for arguments
>  out of [-1; 1]. One drawback is that when a NaN occurs, you don't know
> exactly where it started. You usually see a bunch of NaNs in the output
> and have to reproduce the problem with a debugger to understand what
> happened. If you explicitly checks an operation and throws an exception,
> you immediately knows where it is triggered, but the drawback of this
> choice is that code is slower (lots of tests and branching) and
> difficult to read and maintain.
>

Yeah, in my own libraries, I tend to say that either don't force checks
ever,
and at most throw unchecked exceptions that people can choose to only
catch at the top level (if at all, if they consider it a "fatal" bug then
they can
crash if they want to), or else if they've got ways of dealing with NaN/Inf,
they can explicitly catch the runtime exception.

The other alternative is, as you say, to throw the exceptions on method
calls which *aren't* in an inner loop.  But then I'd say that unitVector()
falls into the same category with mapXXX and ebeXXX - before doing
the O(n) loop, do one check at the beginning for NaN/Inf on the doubles
and isNaN or isInf on the vectors, and throw a MathException at this
point if that's the contract.  Of course, I still think this should be a
runtime
exception, as should FunctionEvaluationException when calling
UnivariateRealFunction.

  -jake

[Ted Dunning]

This makes me think that we need to have containsNan and containsInfinite
methods on vectors and matrices so that it is easy to check.

On Mon, Nov 2, 2009 at 1:46 PM, Jake Mannix <[hidden email]> wrote:

> ... Yeah, in my own libraries, I tend to say that either don't force checks
>  ever and at most throw unchecked exceptions that people can choose to only
> catch at the top level (if at all, if they consider it a "fatal" bug then
> they can crash if they want to), or else if they've got ways of dealing
> with NaN/Inf,
> they can explicitly catch the runtime exception.
>
> The other alternative is, as you say, to throw the exceptions on method
> calls which *aren't* in an inner loop.  But then I'd say that unitVector()
> falls into the same category with mapXXX and ebeXXX - before doing
> the O(n) loop, do one check at the beginning for NaN/Inf on the doubles
> and isNaN or isInf on the vectors, and throw a MathException at this
> point if that's the contract.  Of course, I still think this should be a
> runtime
> exception, as should FunctionEvaluationException when calling
> UnivariateRealFunction.
>
>  -jake
>

--
Ted Dunning, CTO
DeepDyve

[Jake Mannix]

Er, there already is, right?  RealVector#isNaN() and RealVector#isInfinite()
- they're
just not used anywhere except for as verification purposes in the unit
tests.  No
actual internal use as of yet.

  -jake

On Mon, Nov 2, 2009 at 1:58 PM, Ted Dunning <[hidden email]> wrote:

> This makes me think that we need to have containsNan and containsInfinite
> methods on vectors and matrices so that it is easy to check.
>
> On Mon, Nov 2, 2009 at 1:46 PM, Jake Mannix <[hidden email]> wrote:
>
> > ... Yeah, in my own libraries, I tend to say that either don't force
> checks
> >  ever and at most throw unchecked exceptions that people can choose to
> only
> > catch at the top level (if at all, if they consider it a "fatal" bug then
> > they can crash if they want to), or else if they've got ways of dealing
> > with NaN/Inf,
> > they can explicitly catch the runtime exception.
> >
> > The other alternative is, as you say, to throw the exceptions on method
> > calls which *aren't* in an inner loop.  But then I'd say that
> unitVector()
> > falls into the same category with mapXXX and ebeXXX - before doing
> > the O(n) loop, do one check at the beginning for NaN/Inf on the doubles
> > and isNaN or isInf on the vectors, and throw a MathException at this
> > point if that's the contract.  Of course, I still think this should be a
> > runtime
> > exception, as should FunctionEvaluationException when calling
> > UnivariateRealFunction.
> >
> >  -jake
> >
>
>
>
> --
> Ted Dunning, CTO
> DeepDyve
>

[Ted Dunning]

Oops.

Right.  Not paying full attention this morning.  Sorry.

On Mon, Nov 2, 2009 at 2:11 PM, Jake Mannix <[hidden email]> wrote:

> Er, there already is, right?




--
Ted Dunning, CTO
DeepDyve