You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Emmanuel Bourg <eb...@apache.org> on 2011/10/14 16:47:26 UTC
[math] OpenGamma library
Hi,
I just saw this article, that might be of interest for some of the
[math] devs. They claim to have found an optimization that is 1.6 times
faster than Commons Math :
http://www.opengamma.com/blog/2011/10/14/maths-library-development
Emmanuel Bourg
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hello.
> > [...]
>
> >> > I don't think that CM development should be focused on performance
> >> > improvements that are so sensitive to the actual hardware (if it's indeed
> >> > the varying amount of CPU cache that is responsible for this discrepancy).
> >> >
> >> That would apparently require fine tuning indeed, just like BLAS
> >> itself, which has -I believe- specific implementations for specific
> >> architectures. So it's a bit going against the philosophy of Java. I
> >> wonder how a JNI interface to BLAS would perform ? That would leave
> >> the architecture specific issues out of the Java code (which could
> >> even provide a basic implementation of basic linear algebra operations
> >> if people do not want to use native code.
> >
> > The author of the paper proposes to indeed clone the BLAS tuning
> > methodology.
> > However, I don't think that this should be a priority for CM (as a
> > general-purpose math toolbox).
> >
>
> I agree with you, and I don't think that what the author proposes is a
> viable solution. I personnaly would be more in favor of reusing a well
> established, low level library, together with a well-designed,
> high-level, Java interface. But that's just a vague feeling, and I'm
> certainly not saying that this should be considered (especially
> considering the definition of the CM project on the web site "Limited
> dependencies. No external dependencies beyond Commons components and
> the core Java platform"). I just feel that the optimizations the
> author is willing to implement require a deep knowledge on how your
> CPU work, while my understanding of the CM philosophy is to focus on
> more high level, more mathematical, hardware independent algorithms.
> Finally, since BLAS has several different optimized versions for
> different platforms, I can't see how a unique Java library could hope
> to be optimized for all platforms. So even pure java implementations
> of the BLAS would require platform specific tuning, or am I wrong?
IIUC the "Future work" section, the author means exactly that ("platform"
comprising both CPU and JVM).
> Now, as a user of CM, I would like to say that speed is not always a
> concern. I know others have other requirements, but my simulations
> usually run during several days. So whether it takes 1 day or 1.6 days
> still requires appropriate organization of my workflow... Reliability
> of the code, ease of use are more a concern to me.
I share this view.
> >> >
> >> > If there are (human) resources inclined to rewrite CM algorithms in order to
> >> > boost performance, I'd suggest to also explore the multi-threading route, as
> >> > I feel that the type of optimizations described in this paper are more in the
> >> > realm of the JVM itself.
> >> >
> >> I would be very interested, but know nothing on multi-threading. I
> >> will need to explore multi-threading for work anyway, so maybe in the
> >> future?
> >
> > Yes, 3.1, 3.2, ... , 4.0, ... whatever.
> >
>
> Which is consistent with Phil's objection: let's focus on more
> specific issues...
In the perspective of 3.0, I agree.
However, the move towards taking advantage of multi-threading is of a
general nature.
> >> In the meantime, may I bring to you attention the JTransforms
> >> library? (http://sites.google.com/site/piotrwendykier/Home)
> >> It's a multi-threaded library for various FFT calculations. I've used
> >> it a lot, and have been involved in the correction of some bugs. I've
> >> never benchmarked it against CM, but the site claims (if my memory
> >> does not fail me) greater performance.
> >
> > Yes, I did not perform benchmarks; however, Luc already pointed out that he
> > had not pay particular attention to the speed efficiency of the code in CM.
> > Also, there are other problems, cf. issue
> > https://issues.apache.org/jira/browse/MATH-677
> >
> >> Also it can handle
> >> non-power-of-two array dimensions. Plus, the author seems to have no
> >> longer time to spend on this library, and may be willing to share it
> >> with CM. That would be a first step in the multi-threading realm.
> >
> > Unfortunately, no; he doesn't want to donate his code.
> >
> >> Beware, though; the basic code is a direct translation of C code, and
> >> is sometimes difficult to read (thousands of lines, with loads of
> >> branching: code coverage analysis was simply a nightmare!).
> >
> > So, the above information is only half bad news! ;-)
> >
> I wasn't aware of this JIRA issue, and wasn't aware of its author not
> wanting to share it. Besides the non-power of two thingy, a feature I
> do like is the ability to perform real FFT (no need to have an array
> twice the size of the data, with zero imaginary part). I don't think
> the current CM implementation has that, it can be usefull when you
> deal with large 3d FFTs of real data.
Maybe that you could open a specific issue (or add comments to issue
MATH-677) for the usage shortcomings which you've spotted in the current
code. This would help keep track of all the things which a redesign should
address.
Thanks,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Phil Steitz <ph...@gmail.com>.
On 10/15/11 8:46 AM, Phil Steitz wrote:
> On 10/15/11 5:41 AM, Gilles Sadowski wrote:
>> Hi.
>>
>>> first of all, I was the author of this very usefull statement on
>>> factories... Very constructive indeed.
>> Liking something or not is an impression that could well be justified
>> afterwards. It also pushes to look for arguments that ascertain the
>> feeling. ;-)
>>
>>>> However it also shows that the improvement is only ~13% instead of the ~30%
>>>> reported by the benchmark in the paper...
>>>>
>>> could it be that their "naive" implementation as a 2D array is very
>>> naive indeed? I notice in the listings provided in the paper that they
>>> constantly refer to a[i][j]. I think the strength of having a row
>>> representation is to define a temporary variable ai = a[i], and access
>>> to a[i][j] as ai[j]. That's what is done in CM anyway, maybe that
>>> explains why the gain is not so big in the end.
>> You are right; the "naïve" code repeatedly access a[i][j].
>>
>> But this alone doesn't make up for the difference (cf. table below).
>>
>> operate (calls per timed block: 10000, timed blocks: 100, time unit: ms)
>> name time/call std error total time ratio difference
>> Commons Math 1.19770542e-01 2.85011660e-04 1.1977e+05 1.0000e+00 0.00000000e+00
>> OpenGamma naive 1.23798907e-01 4.01495625e-04 1.2380e+05 1.0336e+00 4.02836495e+03
>> OpenGamma 1D 1.04352827e-01 2.08970600e-04 1.0435e+05 8.7127e-01 -1.54177153e+04
>> OpenGamma 2D 1.12666770e-01 3.50012912e-04 1.1267e+05 9.4069e-01 -7.10377213e+03
>>
>>
>>>> I don't think that CM development should be focused on performance
>>>> improvements that are so sensitive to the actual hardware (if it's indeed
>>>> the varying amount of CPU cache that is responsible for this discrepancy).
>>>>
>>> That would apparently require fine tuning indeed, just like BLAS
>>> itself, which has -I believe- specific implementations for specific
>>> architectures. So it's a bit going against the philosophy of Java. I
>>> wonder how a JNI interface to BLAS would perform ? That would leave
>>> the architecture specific issues out of the Java code (which could
>>> even provide a basic implementation of basic linear algebra operations
>>> if people do not want to use native code.
>> The author of the paper proposes to indeed clone the BLAS tuning
>> methodology.
>> However, I don't think that this should be a priority for CM (as a
>> general-purpose math toolbox).
>>
>>>> If there are (human) resources inclined to rewrite CM algorithms in order to
>>>> boost performance, I'd suggest to also explore the multi-threading route, as
>>>> I feel that the type of optimizations described in this paper are more in the
>>>> realm of the JVM itself.
>>>>
>>> I would be very interested, but know nothing on multi-threading. I
>>> will need to explore multi-threading for work anyway, so maybe in the
>>> future?
> Any references to specific optimizations or algorithm improvements here?
>> Yes, 3.1, 3.2, ... , 4.0, ... whatever.
>>
>>> In the meantime, may I bring to you attention the JTransforms
>>> library? (http://sites.google.com/site/piotrwendykier/Home)
>>> It's a multi-threaded library for various FFT calculations. I've used
>>> it a lot, and have been involved in the correction of some bugs. I've
>>> never benchmarked it against CM, but the site claims (if my memory
>>> does not fail me) greater performance.
>> Yes, I did not perform benchmarks; however, Luc already pointed out that he
>> had not pay particular attention to the speed efficiency of the code in CM.
> I don't think Luc meant to make a broad general statement there.
> IIRC, he was talking about one matrix representation class. Lets
> focus on specific problems and solutions.
Pls ignore. I misread the comment above as applying to the original
subject, which was the linear package. I agree that the FFT impl
needs work.
Phil
>
> Phil
>> Also, there are other problems, cf. issue
>> https://issues.apache.org/jira/browse/MATH-67
>>
>>> Also it can handle
>>> non-power-of-two array dimensions. Plus, the author seems to have no
>>> longer time to spend on this library, and may be willing to share it
>>> with CM. That would be a first step in the multi-threading realm.
>> Unfortunately, no; he doesn't want to donate his code.
>>
>>> Beware, though; the basic code is a direct translation of C code, and
>>> is sometimes difficult to read (thousands of lines, with loads of
>>> branching: code coverage analysis was simply a nightmare!).
>> So, the above information is only half bad news! ;-)
>>
>>
>> Best,
>> Gilles
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Phil Steitz <ph...@gmail.com>.
On 10/15/11 5:41 AM, Gilles Sadowski wrote:
> Hi.
>
>> first of all, I was the author of this very usefull statement on
>> factories... Very constructive indeed.
> Liking something or not is an impression that could well be justified
> afterwards. It also pushes to look for arguments that ascertain the
> feeling. ;-)
>
>>> However it also shows that the improvement is only ~13% instead of the ~30%
>>> reported by the benchmark in the paper...
>>>
>> could it be that their "naive" implementation as a 2D array is very
>> naive indeed? I notice in the listings provided in the paper that they
>> constantly refer to a[i][j]. I think the strength of having a row
>> representation is to define a temporary variable ai = a[i], and access
>> to a[i][j] as ai[j]. That's what is done in CM anyway, maybe that
>> explains why the gain is not so big in the end.
> You are right; the "naïve" code repeatedly access a[i][j].
>
> But this alone doesn't make up for the difference (cf. table below).
>
> operate (calls per timed block: 10000, timed blocks: 100, time unit: ms)
> name time/call std error total time ratio difference
> Commons Math 1.19770542e-01 2.85011660e-04 1.1977e+05 1.0000e+00 0.00000000e+00
> OpenGamma naive 1.23798907e-01 4.01495625e-04 1.2380e+05 1.0336e+00 4.02836495e+03
> OpenGamma 1D 1.04352827e-01 2.08970600e-04 1.0435e+05 8.7127e-01 -1.54177153e+04
> OpenGamma 2D 1.12666770e-01 3.50012912e-04 1.1267e+05 9.4069e-01 -7.10377213e+03
>
>
>>> I don't think that CM development should be focused on performance
>>> improvements that are so sensitive to the actual hardware (if it's indeed
>>> the varying amount of CPU cache that is responsible for this discrepancy).
>>>
>> That would apparently require fine tuning indeed, just like BLAS
>> itself, which has -I believe- specific implementations for specific
>> architectures. So it's a bit going against the philosophy of Java. I
>> wonder how a JNI interface to BLAS would perform ? That would leave
>> the architecture specific issues out of the Java code (which could
>> even provide a basic implementation of basic linear algebra operations
>> if people do not want to use native code.
> The author of the paper proposes to indeed clone the BLAS tuning
> methodology.
> However, I don't think that this should be a priority for CM (as a
> general-purpose math toolbox).
>
>>> If there are (human) resources inclined to rewrite CM algorithms in order to
>>> boost performance, I'd suggest to also explore the multi-threading route, as
>>> I feel that the type of optimizations described in this paper are more in the
>>> realm of the JVM itself.
>>>
>> I would be very interested, but know nothing on multi-threading. I
>> will need to explore multi-threading for work anyway, so maybe in the
>> future?
Any references to specific optimizations or algorithm improvements here?
> Yes, 3.1, 3.2, ... , 4.0, ... whatever.
>
>> In the meantime, may I bring to you attention the JTransforms
>> library? (http://sites.google.com/site/piotrwendykier/Home)
>> It's a multi-threaded library for various FFT calculations. I've used
>> it a lot, and have been involved in the correction of some bugs. I've
>> never benchmarked it against CM, but the site claims (if my memory
>> does not fail me) greater performance.
> Yes, I did not perform benchmarks; however, Luc already pointed out that he
> had not pay particular attention to the speed efficiency of the code in CM.
I don't think Luc meant to make a broad general statement there.
IIRC, he was talking about one matrix representation class. Lets
focus on specific problems and solutions.
Phil
> Also, there are other problems, cf. issue
> https://issues.apache.org/jira/browse/MATH-67
>
>> Also it can handle
>> non-power-of-two array dimensions. Plus, the author seems to have no
>> longer time to spend on this library, and may be willing to share it
>> with CM. That would be a first step in the multi-threading realm.
> Unfortunately, no; he doesn't want to donate his code.
>
>> Beware, though; the basic code is a direct translation of C code, and
>> is sometimes difficult to read (thousands of lines, with loads of
>> branching: code coverage analysis was simply a nightmare!).
> So, the above information is only half bad news! ;-)
>
>
> Best,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Sébastien Brisard <se...@m4x.org>.
2011/10/15 Gilles Sadowski <gi...@harfang.homelinux.org>:
> Hi.
>
>> first of all, I was the author of this very usefull statement on
>> factories... Very constructive indeed.
>
> Liking something or not is an impression that could well be justified
> afterwards. It also pushes to look for arguments that ascertain the
> feeling. ;-)
>
The only problem being I'm not sure I'm comfortable enough (if at all)
to state such an argument...
>> >
>> > However it also shows that the improvement is only ~13% instead of the ~30%
>> > reported by the benchmark in the paper...
>> >
>> could it be that their "naive" implementation as a 2D array is very
>> naive indeed? I notice in the listings provided in the paper that they
>> constantly refer to a[i][j]. I think the strength of having a row
>> representation is to define a temporary variable ai = a[i], and access
>> to a[i][j] as ai[j]. That's what is done in CM anyway, maybe that
>> explains why the gain is not so big in the end.
>
> You are right; the "naïve" code repeatedly access a[i][j].
>
> But this alone doesn't make up for the difference (cf. table below).
>
> operate (calls per timed block: 10000, timed blocks: 100, time unit: ms)
> name time/call std error total time ratio difference
> Commons Math 1.19770542e-01 2.85011660e-04 1.1977e+05 1.0000e+00 0.00000000e+00
> OpenGamma naive 1.23798907e-01 4.01495625e-04 1.2380e+05 1.0336e+00 4.02836495e+03
> OpenGamma 1D 1.04352827e-01 2.08970600e-04 1.0435e+05 8.7127e-01 -1.54177153e+04
> OpenGamma 2D 1.12666770e-01 3.50012912e-04 1.1267e+05 9.4069e-01 -7.10377213e+03
>
>
>> >
>> > I don't think that CM development should be focused on performance
>> > improvements that are so sensitive to the actual hardware (if it's indeed
>> > the varying amount of CPU cache that is responsible for this discrepancy).
>> >
>> That would apparently require fine tuning indeed, just like BLAS
>> itself, which has -I believe- specific implementations for specific
>> architectures. So it's a bit going against the philosophy of Java. I
>> wonder how a JNI interface to BLAS would perform ? That would leave
>> the architecture specific issues out of the Java code (which could
>> even provide a basic implementation of basic linear algebra operations
>> if people do not want to use native code.
>
> The author of the paper proposes to indeed clone the BLAS tuning
> methodology.
> However, I don't think that this should be a priority for CM (as a
> general-purpose math toolbox).
>
I agree with you, and I don't think that what the author proposes is a
viable solution. I personnaly would be more in favor of reusing a well
established, low level library, together with a well-designed,
high-level, Java interface. But that's just a vague feeling, and I'm
certainly not saying that this should be considered (especially
considering the definition of the CM project on the web site "Limited
dependencies. No external dependencies beyond Commons components and
the core Java platform"). I just feel that the optimizations the
author is willing to implement require a deep knowledge on how your
CPU work, while my understanding of the CM philosophy is to focus on
more high level, more mathematical, hardware independent algorithms.
Finally, since BLAS has several different optimized versions for
different platforms, I can't see how a unique Java library could hope
to be optimized for all platforms. So even pure java implementations
of the BLAS would require platform specific tuning, or am I wrong?
Now, as a user of CM, I would like to say that speed is not always a
concern. I know others have other requirements, but my simulations
usually run during several days. So whether it takes 1 day or 1.6 days
still requires appropriate organization of my workflow... Reliability
of the code, ease of use are more a concern to me.
>> >
>> > If there are (human) resources inclined to rewrite CM algorithms in order to
>> > boost performance, I'd suggest to also explore the multi-threading route, as
>> > I feel that the type of optimizations described in this paper are more in the
>> > realm of the JVM itself.
>> >
>> I would be very interested, but know nothing on multi-threading. I
>> will need to explore multi-threading for work anyway, so maybe in the
>> future?
>
> Yes, 3.1, 3.2, ... , 4.0, ... whatever.
>
Which is consistent with Phil's objection: let's focus on more
specific issues...
>> In the meantime, may I bring to you attention the JTransforms
>> library? (http://sites.google.com/site/piotrwendykier/Home)
>> It's a multi-threaded library for various FFT calculations. I've used
>> it a lot, and have been involved in the correction of some bugs. I've
>> never benchmarked it against CM, but the site claims (if my memory
>> does not fail me) greater performance.
>
> Yes, I did not perform benchmarks; however, Luc already pointed out that he
> had not pay particular attention to the speed efficiency of the code in CM.
> Also, there are other problems, cf. issue
> https://issues.apache.org/jira/browse/MATH-677
>
>> Also it can handle
>> non-power-of-two array dimensions. Plus, the author seems to have no
>> longer time to spend on this library, and may be willing to share it
>> with CM. That would be a first step in the multi-threading realm.
>
> Unfortunately, no; he doesn't want to donate his code.
>
>> Beware, though; the basic code is a direct translation of C code, and
>> is sometimes difficult to read (thousands of lines, with loads of
>> branching: code coverage analysis was simply a nightmare!).
>
> So, the above information is only half bad news! ;-)
>
>
> Best,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
I wasn't aware of this JIRA issue, and wasn't aware of its author not
wanting to share it. Besides the non-power of two thingy, a feature I
do like is the ability to perform real FFT (no need to have an array
twice the size of the data, with zero imaginary part). I don't think
the current CM implementation has that, it can be usefull when you
deal with large 3d FFTs of real data.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hi.
> first of all, I was the author of this very usefull statement on
> factories... Very constructive indeed.
Liking something or not is an impression that could well be justified
afterwards. It also pushes to look for arguments that ascertain the
feeling. ;-)
> >
> > However it also shows that the improvement is only ~13% instead of the ~30%
> > reported by the benchmark in the paper...
> >
> could it be that their "naive" implementation as a 2D array is very
> naive indeed? I notice in the listings provided in the paper that they
> constantly refer to a[i][j]. I think the strength of having a row
> representation is to define a temporary variable ai = a[i], and access
> to a[i][j] as ai[j]. That's what is done in CM anyway, maybe that
> explains why the gain is not so big in the end.
You are right; the "naïve" code repeatedly access a[i][j].
But this alone doesn't make up for the difference (cf. table below).
operate (calls per timed block: 10000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Commons Math 1.19770542e-01 2.85011660e-04 1.1977e+05 1.0000e+00 0.00000000e+00
OpenGamma naive 1.23798907e-01 4.01495625e-04 1.2380e+05 1.0336e+00 4.02836495e+03
OpenGamma 1D 1.04352827e-01 2.08970600e-04 1.0435e+05 8.7127e-01 -1.54177153e+04
OpenGamma 2D 1.12666770e-01 3.50012912e-04 1.1267e+05 9.4069e-01 -7.10377213e+03
> >
> > I don't think that CM development should be focused on performance
> > improvements that are so sensitive to the actual hardware (if it's indeed
> > the varying amount of CPU cache that is responsible for this discrepancy).
> >
> That would apparently require fine tuning indeed, just like BLAS
> itself, which has -I believe- specific implementations for specific
> architectures. So it's a bit going against the philosophy of Java. I
> wonder how a JNI interface to BLAS would perform ? That would leave
> the architecture specific issues out of the Java code (which could
> even provide a basic implementation of basic linear algebra operations
> if people do not want to use native code.
The author of the paper proposes to indeed clone the BLAS tuning
methodology.
However, I don't think that this should be a priority for CM (as a
general-purpose math toolbox).
> >
> > If there are (human) resources inclined to rewrite CM algorithms in order to
> > boost performance, I'd suggest to also explore the multi-threading route, as
> > I feel that the type of optimizations described in this paper are more in the
> > realm of the JVM itself.
> >
> I would be very interested, but know nothing on multi-threading. I
> will need to explore multi-threading for work anyway, so maybe in the
> future?
Yes, 3.1, 3.2, ... , 4.0, ... whatever.
> In the meantime, may I bring to you attention the JTransforms
> library? (http://sites.google.com/site/piotrwendykier/Home)
> It's a multi-threaded library for various FFT calculations. I've used
> it a lot, and have been involved in the correction of some bugs. I've
> never benchmarked it against CM, but the site claims (if my memory
> does not fail me) greater performance.
Yes, I did not perform benchmarks; however, Luc already pointed out that he
had not pay particular attention to the speed efficiency of the code in CM.
Also, there are other problems, cf. issue
https://issues.apache.org/jira/browse/MATH-677
> Also it can handle
> non-power-of-two array dimensions. Plus, the author seems to have no
> longer time to spend on this library, and may be willing to share it
> with CM. That would be a first step in the multi-threading realm.
Unfortunately, no; he doesn't want to donate his code.
> Beware, though; the basic code is a direct translation of C code, and
> is sometimes difficult to read (thousands of lines, with loads of
> branching: code coverage analysis was simply a nightmare!).
So, the above information is only half bad news! ;-)
Best,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Sébastien Brisard <se...@m4x.org>.
Hello,
first of all, I was the author of this very usefull statement on
factories... Very constructive indeed.
>
> However it also shows that the improvement is only ~13% instead of the ~30%
> reported by the benchmark in the paper...
>
could it be that their "naive" implementation as a 2D array is very
naive indeed? I notice in the listings provided in the paper that they
constantly refer to a[i][j]. I think the strength of having a row
representation is to define a temporary variable ai = a[i], and access
to a[i][j] as ai[j]. That's what is done in CM anyway, maybe that
explains why the gain is not so big in the end.
>
> I don't think that CM development should be focused on performance
> improvements that are so sensitive to the actual hardware (if it's indeed
> the varying amount of CPU cache that is responsible for this discrepancy).
>
That would apparently require fine tuning indeed, just like BLAS
itself, which has -I believe- specific implementations for specific
architectures. So it's a bit going against the philosophy of Java. I
wonder how a JNI interface to BLAS would perform ? That would leave
the architecture specific issues out of the Java code (which could
even provide a basic implementation of basic linear algebra operations
if people do not want to use native code.
>
> If there are (human) resources inclined to rewrite CM algorithms in order to
> boost performance, I'd suggest to also explore the multi-threading route, as
> I feel that the type of optimizations described in this paper are more in the
> realm of the JVM itself.
>
I would be very interested, but know nothing on multi-threading. I
will need to explore multi-threading for work anyway, so maybe in the
future? In the meantime, may I bring to you attention the JTransforms
library? (http://sites.google.com/site/piotrwendykier/Home)
It's a multi-threaded library for various FFT calculations. I've used
it a lot, and have been involved in the correction of some bugs. I've
never benchmarked it against CM, but the site claims (if my memory
does not fail me) greater performance. Also it can handle
non-power-of-two array dimensions. Plus, the author seems to have no
longer time to spend on this library, and may be willing to share it
with CM. That would be a first step in the multi-threading realm.
Beware, though; the basic code is a direct translation of C code, and
is sometimes difficult to read (thousands of lines, with loads of
branching: code coverage analysis was simply a nightmare!).
Sébastien
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
> [...]
>
> I think that there was an important remark in the paper referred to in this
> thread (2nd paragraph, page 10) saying (IIUC) that changing the storage
> layout, from 2D to 1D, effectively led to a speed improvement *only* for
> matrices of sizes larger than 1010. Which leads me to think that such
> changes are certainly not always worth it. Do we really want a code more
> difficult to understand and maintain on the ground that it will be faster
> for "large" matrices. What if some CM users are only interested in "small"
> matrices?
>
My own benchmark shows (cf. the "ratio" column in the following table) that
there is already an improvement for a matrix of size 303 (instead of 1010):
operate (calls per timed block: 10000, timed blocks: 100, time unit: ms)
name time/call std error total time ratio difference
Commons Math 1.19667835e-01 2.70020491e-04 1.1967e+05 1.0000e+00 0.00000000e+00
OpenGamma 1D 1.04407216e-01 2.56229711e-04 1.0441e+05 8.7248e-01 -1.52606192e+04
OpenGamma 2D 1.13865944e-01 1.82887474e-04 1.1387e+05 9.5152e-01 -5.80189118e+03
However it also shows that the improvement is only ~13% instead of the ~30%
reported by the benchmark in the paper...
I don't think that CM development should be focused on performance
improvements that are so sensitive to the actual hardware (if it's indeed
the varying amount of CPU cache that is responsible for this discrepancy).
If there are (human) resources inclined to rewrite CM algorithms in order to
boost performance, I'd suggest to also explore the multi-threading route, as
I feel that the type of optimizations described in this paper are more in the
realm of the JVM itself.
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hello.
> > [...]
> >
> > I might have missed the goal of your proposal but I think that main point
> > of the discussion had been about having a separate class for operations. I
> > don't recall that a new implementation ("SymmetricMatrix") with a
> > specifically optimized storage was not approved.
> >
> > In fact, it has been a few weeks that I wanted to ask whether someone would
> > be interested in providing a symmetric matrix; the primary motivation for
> > me
> > would be that it will simplify some code in "BOBYQAOptimizer".
> > I see no reason why you would not be welcome to create a new
> > "SymmetricMatrix" class.
> >
> I would be delighted to collaborate.
As I said, I would be an interested *user* of the symmetric matrix
implementation. ;-)
> The proposal was not denied, but the
> response was overwhelmingly negative. Perhaps we can start a new discussion
> so I don't start top posting... ;-)
Certainly.
> As I mentioned already, I am very
> impressed by BOBYQA.
I guess that you mean "impressed by [the performance]".
I am worried about the code complexity, for long term maintainance. When
including the C-to-Java translation, it was on the ground that it would be
transformed into understandable Java code.
> [...]
>
>
> Additionally, I was hoping you would give your thoughts on the BlockMatrix
> design.
I have no particular thoughts about it at the moment.
I agree that this implementation should not be thrown away unless all
operations are proven (benchmarks?) to be always less efficient than
alternative implementations.[1] But this discussion should also go into its
own thread...
I think that there was an important remark in the paper referred to in this
thread (2nd paragraph, page 10) saying (IIUC) that changing the storage
layout, from 2D to 1D, effectively led to a speed improvement *only* for
matrices of sizes larger than 1010. Which leads me to think that such
changes are certainly not always worth it. Do we really want a code more
difficult to understand and maintain on the ground that it will be faster
for "large" matrices. What if some CM users are only interested in "small"
matrices?
Best regards,
Gilles
[1] Actually I've micro-benchmarked square matrix multiplication and, at
least up to size 100, "Array2DRowRealMatrix" (the *new* version of
"multiply", inspired from Jama) was faster than "BlockMatrix"...
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Greg Sterijevski <gs...@gmail.com>.
On Fri, Oct 14, 2011 at 4:12 PM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> Hello.
>
> >
> > I believe that the BlockMatrix approach you have taken is actually quite
> > good and might yield a bit more stable optimization improvement than
> simple
> > loop unrolling. Consider operations on non-overlapping blocks. You could
> > easily dispatch those in parallel. I agree that it is a bit painful to
> use,
> > but in solver (for example) it is very quick. I would not be quick to
> > dispatch it. Its taken me a couple of months to appreciate its subtle
> > elegance. There is many more tricks you can play with your approach.
> Also,
> > don't forget the timings they present are for one very specific
> > operation-one where the block approach is at a slight disadvantage.
> >
> > One place where the Open Gamma approach is better is using single
> dimension
> > arrays, but that's not compatible with your block approach. If you
> recall, I
> > asked to add a SymmetricMatrix implementation storing the data in a
> single
> > dimension array with compressed row major storage. That proposal was not
> > well received.
>
> I might have missed the goal of your proposal but I think that main point
> of the discussion had been about having a separate class for operations. I
> don't recall that a new implementation ("SymmetricMatrix") with a
> specifically optimized storage was not approved.
>
> In fact, it has been a few weeks that I wanted to ask whether someone would
> be interested in providing a symmetric matrix; the primary motivation for
> me
> would be that it will simplify some code in "BOBYQAOptimizer".
> I see no reason why you would not be welcome to create a new
> "SymmetricMatrix" class.
>
> I would be delighted to collaborate. The proposal was not denied, but the
response was overwhelmingly negative. Perhaps we can start a new discussion
so I don't start top posting... ;-) As I mentioned already, I am very
impressed by BOBYQA.
> I suspect when the time comes to debate 'their' approach with
> > the commons approach the same issues will crop up.
> >
> > On other aspects, the group will not like use of factories. They seem to
> be
> > everywhere in the code. Again, there is reticence in this community with
> > respect to non constructor construction.
>
> This is not an accurate summary of the discussion we had on that subject.
> The point (mine, at least) was not that we should or should not use
> factories; it was that we should not mix both styles. As it happens, the
> codebase is currently written with the "explicit" construction style (and
> the rare uses of factories that still existed in 2.2 were not appropriate
> IMHO), so the argument went that the proponents of factories did not
> provide
> explicit examples of why the codebase should be moved to another paradigm
> (I
> recall people only saying: "I like factories").
>
I only noted the reluctance. I used 2.1 very sparingly and cannot recall
what factories existed.
> Finally, I can connect this with what you report about "OpenGamma" being a
> framework for finance computations; the keyword is "framework" which CM is
> not: It's "just" a low-level library, a collection of algorithms not
> targetted toward a specific application domain. My impression is that is
> much easier to get the framework wrong for CM (meaning: not appropriate for
> certain uses of those low-level tools).
>
Yes, the Open Gamma project has elements of low level library like CM
(certain packages could be removed from their jar and put into a separate
jar). It also has a messaging, calculation, information folding (like olap)
which are definitely more framework type components. I am very surprised by
the completeness. Most trading desks don't have access to such comprehensive
systems.
> Regards,
> Gilles
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Additionally, I was hoping you would give your thoughts on the BlockMatrix
design.
-Greg
Re: [math] OpenGamma library
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hello.
>
> I believe that the BlockMatrix approach you have taken is actually quite
> good and might yield a bit more stable optimization improvement than simple
> loop unrolling. Consider operations on non-overlapping blocks. You could
> easily dispatch those in parallel. I agree that it is a bit painful to use,
> but in solver (for example) it is very quick. I would not be quick to
> dispatch it. Its taken me a couple of months to appreciate its subtle
> elegance. There is many more tricks you can play with your approach. Also,
> don't forget the timings they present are for one very specific
> operation-one where the block approach is at a slight disadvantage.
>
> One place where the Open Gamma approach is better is using single dimension
> arrays, but that's not compatible with your block approach. If you recall, I
> asked to add a SymmetricMatrix implementation storing the data in a single
> dimension array with compressed row major storage. That proposal was not
> well received.
I might have missed the goal of your proposal but I think that main point
of the discussion had been about having a separate class for operations. I
don't recall that a new implementation ("SymmetricMatrix") with a
specifically optimized storage was not approved.
In fact, it has been a few weeks that I wanted to ask whether someone would
be interested in providing a symmetric matrix; the primary motivation for me
would be that it will simplify some code in "BOBYQAOptimizer".
I see no reason why you would not be welcome to create a new
"SymmetricMatrix" class.
> I suspect when the time comes to debate 'their' approach with
> the commons approach the same issues will crop up.
>
> On other aspects, the group will not like use of factories. They seem to be
> everywhere in the code. Again, there is reticence in this community with
> respect to non constructor construction.
This is not an accurate summary of the discussion we had on that subject.
The point (mine, at least) was not that we should or should not use
factories; it was that we should not mix both styles. As it happens, the
codebase is currently written with the "explicit" construction style (and
the rare uses of factories that still existed in 2.2 were not appropriate
IMHO), so the argument went that the proponents of factories did not provide
explicit examples of why the codebase should be moved to another paradigm (I
recall people only saying: "I like factories").
Finally, I can connect this with what you report about "OpenGamma" being a
framework for finance computations; the keyword is "framework" which CM is
not: It's "just" a low-level library, a collection of algorithms not
targetted toward a specific application domain. My impression is that is
much easier to get the framework wrong for CM (meaning: not appropriate for
certain uses of those low-level tools).
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Greg Sterijevski <gs...@gmail.com>.
On Fri, Oct 14, 2011 at 1:28 PM, Luc Maisonobe <Lu...@free.fr>wrote:
> Le 14/10/2011 20:08, Greg Sterijevski a écrit :
>
> I looked more closely at the package and it am impressed with the breadth
>> of
>> material covered. Moreover, this package will do to finance what Mahout is
>> doing to companies like SAS and SPSS. Having spent a good part of my
>> career
>> in finance, this package (and others) will put a lot of small 'analytics'
>> companies out of business (as well as people like me). There is excellent
>> coverage of pricing models (options and otherwise), fitting techniques (as
>> it pertains to term structures, volatility surfaces and so forth), but the
>> most impressive thing is that all of the functionality is presented in
>> framework. You can integrate what is called front office functionality
>> (trading, pricing, hedging) with middle and back office (risk and
>> clearing)
>> operations. Most closed source packages are not this good.
>>
>> So, a bit amateurish on the 'optimization' front, but the big picture is
>> very strong. Comparable closed source packages like this would run upward
>> of
>> 1M USD.
>>
>> -Greg
>>
>> On Fri, Oct 14, 2011 at 11:24 AM, Phil Steitz<ph...@gmail.com>
>> wrote:
>>
>> On 10/14/11 7:47 AM, Emmanuel Bourg wrote:
>>>
>>>> Hi,
>>>>
>>>> I just saw this article, that might be of interest for some of the
>>>> [math] devs. They claim to have found an optimization that is 1.6
>>>> times faster than Commons Math :
>>>>
>>>> http://www.opengamma.com/blog/**2011/10/14/maths-library-**development<http://www.opengamma.com/blog/2011/10/14/maths-library-development>
>>>>
>>>
>>> Thanks for sharing this. We can certainly look at the specific case
>>> and evaluate pros and cons; but it looks like there may be some
>>> interesting areas for collaboration. The license and CLA-type
>>> thingy look compatible and it looks like there are [math]
>>> dependencies and maybe some [math] source already used in there, so
>>> it would be great to get some collaboration going.
>>>
>>
> Yes, this would be a very good thing. Our linear algabra is not fast, we
> already know that. I think we need to address several different needs like
> simple API, numerical accuracy, robustness and speed. We concentrated on
> robustness up to now, mainly because our SVD was really really bad on this
> point. Now that this part seems to be OK, I would very much like to see some
> speed improvements (and sparse matrices too, as we also suck at this).
>
> Our block matrices implementation seems to improve some operations
> computation time, but it has a very awkward design and is not backed by any
> theoretical studies so it is probably also amateurish with respect to cache.
> I designed and wrote it but would really be happy to get rid of it and have
> it replaced by something more efficient. I would also like to know how it
> behaves in the article bench.
>
> So a big +1 for collaboration if the author is ready for this.
>
> Luc
>
>
>
>>> Phil
>>>
>>>>
>>>>
>
Luc,
I believe that the BlockMatrix approach you have taken is actually quite
good and might yield a bit more stable optimization improvement than simple
loop unrolling. Consider operations on non-overlapping blocks. You could
easily dispatch those in parallel. I agree that it is a bit painful to use,
but in solver (for example) it is very quick. I would not be quick to
dispatch it. Its taken me a couple of months to appreciate its subtle
elegance. There is many more tricks you can play with your approach. Also,
don't forget the timings they present are for one very specific
operation-one where the block approach is at a slight disadvantage.
One place where the Open Gamma approach is better is using single dimension
arrays, but that's not compatible with your block approach. If you recall, I
asked to add a SymmetricMatrix implementation storing the data in a single
dimension array with compressed row major storage. That proposal was not
well received. I suspect when the time comes to debate 'their' approach with
the commons approach the same issues will crop up.
On other aspects, the group will not like use of factories. They seem to be
everywhere in the code. Again, there is reticence in this community with
respect to non constructor construction.
-Greg
Re: [math] OpenGamma library
Posted by Luc Maisonobe <Lu...@free.fr>.
Le 14/10/2011 20:08, Greg Sterijevski a écrit :
> I looked more closely at the package and it am impressed with the breadth of
> material covered. Moreover, this package will do to finance what Mahout is
> doing to companies like SAS and SPSS. Having spent a good part of my career
> in finance, this package (and others) will put a lot of small 'analytics'
> companies out of business (as well as people like me). There is excellent
> coverage of pricing models (options and otherwise), fitting techniques (as
> it pertains to term structures, volatility surfaces and so forth), but the
> most impressive thing is that all of the functionality is presented in
> framework. You can integrate what is called front office functionality
> (trading, pricing, hedging) with middle and back office (risk and clearing)
> operations. Most closed source packages are not this good.
>
> So, a bit amateurish on the 'optimization' front, but the big picture is
> very strong. Comparable closed source packages like this would run upward of
> 1M USD.
>
> -Greg
>
> On Fri, Oct 14, 2011 at 11:24 AM, Phil Steitz<ph...@gmail.com> wrote:
>
>> On 10/14/11 7:47 AM, Emmanuel Bourg wrote:
>>> Hi,
>>>
>>> I just saw this article, that might be of interest for some of the
>>> [math] devs. They claim to have found an optimization that is 1.6
>>> times faster than Commons Math :
>>>
>>> http://www.opengamma.com/blog/2011/10/14/maths-library-development
>>
>> Thanks for sharing this. We can certainly look at the specific case
>> and evaluate pros and cons; but it looks like there may be some
>> interesting areas for collaboration. The license and CLA-type
>> thingy look compatible and it looks like there are [math]
>> dependencies and maybe some [math] source already used in there, so
>> it would be great to get some collaboration going.
Yes, this would be a very good thing. Our linear algabra is not fast, we
already know that. I think we need to address several different needs
like simple API, numerical accuracy, robustness and speed. We
concentrated on robustness up to now, mainly because our SVD was really
really bad on this point. Now that this part seems to be OK, I would
very much like to see some speed improvements (and sparse matrices too,
as we also suck at this).
Our block matrices implementation seems to improve some operations
computation time, but it has a very awkward design and is not backed by
any theoretical studies so it is probably also amateurish with respect
to cache. I designed and wrote it but would really be happy to get rid
of it and have it replaced by something more efficient. I would also
like to know how it behaves in the article bench.
So a big +1 for collaboration if the author is ready for this.
Luc
>>
>> Phil
>>>
>>> Emmanuel Bourg
>>>
>>> ---------------------------------------------------------------------
>>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>>> For additional commands, e-mail: dev-help@commons.apache.org
>>>
>>>
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Greg Sterijevski <gs...@gmail.com>.
I looked more closely at the package and it am impressed with the breadth of
material covered. Moreover, this package will do to finance what Mahout is
doing to companies like SAS and SPSS. Having spent a good part of my career
in finance, this package (and others) will put a lot of small 'analytics'
companies out of business (as well as people like me). There is excellent
coverage of pricing models (options and otherwise), fitting techniques (as
it pertains to term structures, volatility surfaces and so forth), but the
most impressive thing is that all of the functionality is presented in
framework. You can integrate what is called front office functionality
(trading, pricing, hedging) with middle and back office (risk and clearing)
operations. Most closed source packages are not this good.
So, a bit amateurish on the 'optimization' front, but the big picture is
very strong. Comparable closed source packages like this would run upward of
1M USD.
-Greg
On Fri, Oct 14, 2011 at 11:24 AM, Phil Steitz <ph...@gmail.com> wrote:
> On 10/14/11 7:47 AM, Emmanuel Bourg wrote:
> > Hi,
> >
> > I just saw this article, that might be of interest for some of the
> > [math] devs. They claim to have found an optimization that is 1.6
> > times faster than Commons Math :
> >
> > http://www.opengamma.com/blog/2011/10/14/maths-library-development
>
> Thanks for sharing this. We can certainly look at the specific case
> and evaluate pros and cons; but it looks like there may be some
> interesting areas for collaboration. The license and CLA-type
> thingy look compatible and it looks like there are [math]
> dependencies and maybe some [math] source already used in there, so
> it would be great to get some collaboration going.
>
> Phil
> >
> > Emmanuel Bourg
> >
> > ---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > For additional commands, e-mail: dev-help@commons.apache.org
> >
> >
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
Re: [math] OpenGamma library
Posted by Phil Steitz <ph...@gmail.com>.
On 10/14/11 7:47 AM, Emmanuel Bourg wrote:
> Hi,
>
> I just saw this article, that might be of interest for some of the
> [math] devs. They claim to have found an optimization that is 1.6
> times faster than Commons Math :
>
> http://www.opengamma.com/blog/2011/10/14/maths-library-development
Thanks for sharing this. We can certainly look at the specific case
and evaluate pros and cons; but it looks like there may be some
interesting areas for collaboration. The license and CLA-type
thingy look compatible and it looks like there are [math]
dependencies and maybe some [math] source already used in there, so
it would be great to get some collaboration going.
Phil
>
> Emmanuel Bourg
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] OpenGamma library
Posted by Greg Sterijevski <gs...@gmail.com>.
Interesting that they are making such heavy wind of their 'innovations' like
loop unrolling. I would be interested in how much mileage they will get out
of those tricks in more complicated code. I do not intend to disparage their
approach, but maintaining code with too many cute optimizations costs a lot
of man hours to debug and extend. Additionally you are never sure (at least
with java) how the code is actually executed across the different jvm
implementations (as we have seen with the whole FastMath.exp function debate
here on the list). Good press for Apache Commons Math!
-Greg
On Fri, Oct 14, 2011 at 9:47 AM, Emmanuel Bourg <eb...@apache.org> wrote:
> Hi,
>
> I just saw this article, that might be of interest for some of the [math]
> devs. They claim to have found an optimization that is 1.6 times faster than
> Commons Math :
>
> http://www.opengamma.com/blog/**2011/10/14/maths-library-**development<http://www.opengamma.com/blog/2011/10/14/maths-library-development>
>
> Emmanuel Bourg
>
> ------------------------------**------------------------------**---------
> To unsubscribe, e-mail: dev-unsubscribe@commons.**apache.org<de...@commons.apache.org>
> For additional commands, e-mail: dev-help@commons.apache.org
>
>