You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Gilles Sadowski <gi...@harfang.homelinux.org> on 2012/07/21 02:39:08 UTC
[Math] Synchronization (Was: svn commit: r1364024 - ...)
Hi.
> Author: erans
> Date: Sat Jul 21 00:08:18 2012
> New Revision: 1364024
>
> URL: http://svn.apache.org/viewvc?rev=1364024&view=rev
> Log:
> MATH-797
> Performance: synchronization should ensure that the computation of each
> rule will be performed once, even if the factory is accessed from multiple
> threads.
>
> Modified:
> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java
>
> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java
> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java?rev=1364024&r1=1364023&r2=1364024&view=diff
> ==============================================================================
> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java (original)
> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java Sat Jul 21 00:08:18 2012
> @@ -68,13 +68,14 @@ public abstract class BaseRuleFactory<T
>
> /**
> * Gets a rule.
> - * Rules are computed once, and cached.
> + * Synchronization ensures that rules will be computed and added to the
> + * cache at most once.
> * The returned rule is a reference into the cache.
> *
> * @param numberOfPoints Order of the rule to be retrieved.
> * @return the points and weights corresponding to the given order.
> */
> - protected Pair<T[], T[]> getRuleInternal(int numberOfPoints) {
> + protected synchronized Pair<T[], T[]> getRuleInternal(int numberOfPoints) {
> final Pair<T[], T[]> rule = pointsAndWeights.get(numberOfPoints);
> if (rule == null) {
> addRule(computeRule(numberOfPoints));
Any idea about how to set up a unit test that proves the claim?
Thanks,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Synchronization
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
Hello.
> On 22/07/2012 02:43, Gilles Sadowski wrote:
> > On Sat, Jul 21, 2012 at 11:44:43AM -0700, Ted Dunning wrote:
> >> Synchronization in low level code is generally really bad. This is the
> >> whole point of why Vector was essentially thrown away in Java collections
> >> in favor of ArrayList.
> >
> > I might be wrong, but I don't think that's the reason.
> > At the beginning there was the "Vector"... and nothing else. In singly
> > threaded code or as a thread local variable, synchronization is an
> > unnecessary waste of time. Since most code falls into this category,
> > "ArrayList" is indeed much more useful. That doesn't imply that there is
> > never a need for synchronization in low-level code.
> >
> > In the present case, AFAICT the synchronization is a performance gain during
> > the creation of the data (to be cached). Once that part is done, user code
> > do not call any "synchronized" methods, so no loss there.
> >
> >>
> >> Better to synchronize in the caller who knows about the multi-threading.
> >> Or simply build a synchronized wrapper in an inner class.
>
> Note that there are also other mechanisms apart from synchronization
> that could be used. The lazy holder idiom can be used to ensure single
> execution and both locks and atomic variables from the concurrency
> package can be used for thread safety (I strongly prefer them to
> synchronization).
AIUI, this amounts to "manually" replicating what "synchronized" probides.
[Well, not in all cases, I know; but here, using "synchronized" seems right
to the point, in that it solves the problem (as demonstrated by the unit
test).]
As I pointed out previously, this use of "synchronized" is an
implementation detail which API users don't have to worry about.[1]
This "improvement" of the initial code makes it possible for a class like
the new "IterativeLegendreGaussIntegrator" to use a singleton factory (also
an implementation detail), which is a huge advantage when a application will
instantitate many such integrators:
- The singleton is nice because rules are stored once for the whole
application instead of in each "IterativeLegendreGaussIntegrator"
instance.
- The singleton is problematic in a multi-threaded environment since the
rules will be computed several times; "synchronized" solves that issue.
> One important point too is that regardless of the fact we use
> multi-threading in [math] or not by ourselves, we should take care to
> allow upper level application to use our classes in multi-threaded
> environments. This is simple for small container classes (3D vectors,
> complex numbers ...) that can be made immutable (at least the original
> class we provide, not the derived class users may create). This is much
> more complex or can even be impossible for long algorithms with an API
> providing lots of different functions (core engine run, setters,
> getters, retrieval of partial results ...). Documenting everything about
> thread safety would be a daunting task, but it would be a nice thing to
> have, at least for some classes or methods.
I agree and didn't mean that CM should be entirely thread-safe.
[However I think that the "IterativeLegendreGaussIntegrator" case shows that
there is a potential gain when certain part are coded with this in mind.]
Also, I'm not in favour of introducing complex code for the sake of a
thread safety, especially when that could be implemented at a higher
level.[2]
But there are cases where there is an inherently "simple" parallelization,
and where users would probably expect that a math library would take
advantage of it. That was mainly the reason for the post about
multi-threading.
I think that whenever there is an algorithm where parallelization provides
a huge gain (in these times of mutiple cores), we should include it in the
implementation of that algorithm, or refrain from providing a crippled
feature (as maintaining it will drain our scarce human resources for
something that will be superseded by a more performant implementation).
In that respect, I agree with Ted (in the other ML thread): Currently CM is
probably not as good as Atlas wrappers for large matrices. But, since we
rule out depending on other projects, especially if they wrap JNI calls),
the conclusion I draw is that we should not provide a feature set related to
large matrices. [This of course points towards the bugs related to sparse
matrices, recently uncovered by Sébastien: Better (IMHO) to provide an
enhanced feature set for dense matrices rather than spend time to fix
features that are rarely used, if ever, by CM users.]
Best regards,
Gilles
[1] Unless I got it wrong of course! :-}
[2] In the case of the "IterativeLegendreGaussIntegrator" I think that it is
not possible to do it at a higher level: the concerned field is
"private". And the fix is not complex, but just a single keyword.
>
> >
> > Please show how this fits with the current case, and improves the
> > implementation.
> >
> >
> > Thanks,
> > Gilles
> >
> >>
> >> On Sat, Jul 21, 2012 at 6:08 AM, Gilles Sadowski <
> >> gilles@harfang.homelinux.org> wrote:
> >>
> >>>>
> >>>> Note that there is a performance price for the synchronization,
> >>>> which may outweigh the benefit of adding it.
> >>>
> >>> I thought of adding that because one might want to parallelize the
> >>> integration computations while the quadrature rules factory is shared.
> >>> [See e.g. MATH-827, line 41 in the posted code.]
> >>> Without "synchronized", all threads will compute all the rules.
> >>>
> >>> On my machine (4 cores), in the absence of synchronization, the above test
> >>> indicated that the "computeRule" method was called 18 times!
> >>>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Synchronization
Posted by Luc Maisonobe <Lu...@free.fr>.
Hi Gilles,
On 22/07/2012 02:43, Gilles Sadowski wrote:
> On Sat, Jul 21, 2012 at 11:44:43AM -0700, Ted Dunning wrote:
>> Synchronization in low level code is generally really bad. This is the
>> whole point of why Vector was essentially thrown away in Java collections
>> in favor of ArrayList.
>
> I might be wrong, but I don't think that's the reason.
> At the beginning there was the "Vector"... and nothing else. In singly
> threaded code or as a thread local variable, synchronization is an
> unnecessary waste of time. Since most code falls into this category,
> "ArrayList" is indeed much more useful. That doesn't imply that there is
> never a need for synchronization in low-level code.
>
> In the present case, AFAICT the synchronization is a performance gain during
> the creation of the data (to be cached). Once that part is done, user code
> do not call any "synchronized" methods, so no loss there.
>
>>
>> Better to synchronize in the caller who knows about the multi-threading.
>> Or simply build a synchronized wrapper in an inner class.
Note that there are also other mechanisms apart from synchronization
that could be used. The lazy holder idiom can be used to ensure single
execution and both locks and atomic variables from the concurrency
package can be used for thread safety (I strongly prefer them to
synchronization).
One important point too is that regardless of the fact we use
multi-threading in [math] or not by ourselves, we should take care to
allow upper level application to use our classes in multi-threaded
environments. This is simple for small container classes (3D vectors,
complex numbers ...) that can be made immutable (at least the original
class we provide, not the derived class users may create). This is much
more complex or can even be impossible for long algorithms with an API
providing lots of different functions (core engine run, setters,
getters, retrieval of partial results ...). Documenting everything about
thread safety would be a daunting task, but it would be a nice thing to
have, at least for some classes or methods.
Luc
>
> Please show how this fits with the current case, and improves the
> implementation.
>
>
> Thanks,
> Gilles
>
>>
>> On Sat, Jul 21, 2012 at 6:08 AM, Gilles Sadowski <
>> gilles@harfang.homelinux.org> wrote:
>>
>>>>
>>>> Note that there is a performance price for the synchronization,
>>>> which may outweigh the benefit of adding it.
>>>
>>> I thought of adding that because one might want to parallelize the
>>> integration computations while the quadrature rules factory is shared.
>>> [See e.g. MATH-827, line 41 in the posted code.]
>>> Without "synchronized", all threads will compute all the rules.
>>>
>>> On my machine (4 cores), in the absence of synchronization, the above test
>>> indicated that the "computeRule" method was called 18 times!
>>>
>
> ---------------------------------------------------------------------
> 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] Synchronization
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Sat, Jul 21, 2012 at 11:44:43AM -0700, Ted Dunning wrote:
> Synchronization in low level code is generally really bad. This is the
> whole point of why Vector was essentially thrown away in Java collections
> in favor of ArrayList.
I might be wrong, but I don't think that's the reason.
At the beginning there was the "Vector"... and nothing else. In singly
threaded code or as a thread local variable, synchronization is an
unnecessary waste of time. Since most code falls into this category,
"ArrayList" is indeed much more useful. That doesn't imply that there is
never a need for synchronization in low-level code.
In the present case, AFAICT the synchronization is a performance gain during
the creation of the data (to be cached). Once that part is done, user code
do not call any "synchronized" methods, so no loss there.
>
> Better to synchronize in the caller who knows about the multi-threading.
> Or simply build a synchronized wrapper in an inner class.
Please show how this fits with the current case, and improves the
implementation.
Thanks,
Gilles
>
> On Sat, Jul 21, 2012 at 6:08 AM, Gilles Sadowski <
> gilles@harfang.homelinux.org> wrote:
>
> > >
> > > Note that there is a performance price for the synchronization,
> > > which may outweigh the benefit of adding it.
> >
> > I thought of adding that because one might want to parallelize the
> > integration computations while the quadrature rules factory is shared.
> > [See e.g. MATH-827, line 41 in the posted code.]
> > Without "synchronized", all threads will compute all the rules.
> >
> > On my machine (4 cores), in the absence of synchronization, the above test
> > indicated that the "computeRule" method was called 18 times!
> >
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Synchronization
Posted by Ted Dunning <te...@gmail.com>.
Synchronization in low level code is generally really bad. This is the
whole point of why Vector was essentially thrown away in Java collections
in favor of ArrayList.
Better to synchronize in the caller who knows about the multi-threading.
Or simply build a synchronized wrapper in an inner class.
On Sat, Jul 21, 2012 at 6:08 AM, Gilles Sadowski <
gilles@harfang.homelinux.org> wrote:
> >
> > Note that there is a performance price for the synchronization,
> > which may outweigh the benefit of adding it.
>
> I thought of adding that because one might want to parallelize the
> integration computations while the quadrature rules factory is shared.
> [See e.g. MATH-827, line 41 in the posted code.]
> Without "synchronized", all threads will compute all the rules.
>
> On my machine (4 cores), in the absence of synchronization, the above test
> indicated that the "computeRule" method was called 18 times!
>
Re: [Math] Synchronization
Posted by Gilles Sadowski <gi...@harfang.homelinux.org>.
On Fri, Jul 20, 2012 at 07:26:59PM -0700, Phil Steitz wrote:
> On 7/20/12 5:39 PM, Gilles Sadowski wrote:
> > Hi.
> >
> >> Author: erans
> >> Date: Sat Jul 21 00:08:18 2012
> >> New Revision: 1364024
> >>
> >> URL: http://svn.apache.org/viewvc?rev=1364024&view=rev
> >> Log:
> >> MATH-797
> >> Performance: synchronization should ensure that the computation of each
> >> rule will be performed once, even if the factory is accessed from multiple
> >> threads.
> >>
> >> Modified:
> >> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java
> >>
> >> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java
> >> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java?rev=1364024&r1=1364023&r2=1364024&view=diff
> >> ==============================================================================
> >> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java (original)
> >> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java Sat Jul 21 00:08:18 2012
> >> @@ -68,13 +68,14 @@ public abstract class BaseRuleFactory<T
> >>
> >> /**
> >> * Gets a rule.
> >> - * Rules are computed once, and cached.
> >> + * Synchronization ensures that rules will be computed and added to the
> >> + * cache at most once.
> >> * The returned rule is a reference into the cache.
> >> *
> >> * @param numberOfPoints Order of the rule to be retrieved.
> >> * @return the points and weights corresponding to the given order.
> >> */
> >> - protected Pair<T[], T[]> getRuleInternal(int numberOfPoints) {
> >> + protected synchronized Pair<T[], T[]> getRuleInternal(int numberOfPoints) {
> >> final Pair<T[], T[]> rule = pointsAndWeights.get(numberOfPoints);
> >> if (rule == null) {
> >> addRule(computeRule(numberOfPoints));
> > Any idea about how to set up a unit test that proves the claim?
>
> Have a look at the unit tests in [pool]. There are lots of examples
> there setting up race conditions. IIUC what is going on here, you
> could set up a unit test that failed before this change and
> succeeded after by creating a rule factory that has latency in its
> addRule or computeRule method (add a sleep in the body somewhere).
> Modify its addRule to track the number of times it is called. Then
> create the race by launching two threads with no delay between that
> both invoke getRuleInternal. Before adding the synch, the addRule
> counter will be 2 (assuming there is enough latency in it or
> computeRule to ensure the first thread does not complete before the
> second enters the block). After this patch, the counter should be 1.
Indeed, I needed some "sleep". :-)
Test added in revision 1364075.
>
> Note that there is a performance price for the synchronization,
> which may outweigh the benefit of adding it.
I thought of adding that because one might want to parallelize the
integration computations while the quadrature rules factory is shared.
[See e.g. MATH-827, line 41 in the posted code.]
Without "synchronized", all threads will compute all the rules.
On my machine (4 cores), in the absence of synchronization, the above test
indicated that the "computeRule" method was called 18 times!
Regards,
Gilles
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [Math] Synchronization (Was: svn commit: r1364024 - ...)
Posted by Phil Steitz <ph...@gmail.com>.
On 7/20/12 5:39 PM, Gilles Sadowski wrote:
> Hi.
>
>> Author: erans
>> Date: Sat Jul 21 00:08:18 2012
>> New Revision: 1364024
>>
>> URL: http://svn.apache.org/viewvc?rev=1364024&view=rev
>> Log:
>> MATH-797
>> Performance: synchronization should ensure that the computation of each
>> rule will be performed once, even if the factory is accessed from multiple
>> threads.
>>
>> Modified:
>> commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java
>>
>> Modified: commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java
>> URL: http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java?rev=1364024&r1=1364023&r2=1364024&view=diff
>> ==============================================================================
>> --- commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java (original)
>> +++ commons/proper/math/trunk/src/main/java/org/apache/commons/math3/analysis/integration/gauss/BaseRuleFactory.java Sat Jul 21 00:08:18 2012
>> @@ -68,13 +68,14 @@ public abstract class BaseRuleFactory<T
>>
>> /**
>> * Gets a rule.
>> - * Rules are computed once, and cached.
>> + * Synchronization ensures that rules will be computed and added to the
>> + * cache at most once.
>> * The returned rule is a reference into the cache.
>> *
>> * @param numberOfPoints Order of the rule to be retrieved.
>> * @return the points and weights corresponding to the given order.
>> */
>> - protected Pair<T[], T[]> getRuleInternal(int numberOfPoints) {
>> + protected synchronized Pair<T[], T[]> getRuleInternal(int numberOfPoints) {
>> final Pair<T[], T[]> rule = pointsAndWeights.get(numberOfPoints);
>> if (rule == null) {
>> addRule(computeRule(numberOfPoints));
> Any idea about how to set up a unit test that proves the claim?
Have a look at the unit tests in [pool]. There are lots of examples
there setting up race conditions. IIUC what is going on here, you
could set up a unit test that failed before this change and
succeeded after by creating a rule factory that has latency in its
addRule or computeRule method (add a sleep in the body somewhere).
Modify its addRule to track the number of times it is called. Then
create the race by launching two threads with no delay between that
both invoke getRuleInternal. Before adding the synch, the addRule
counter will be 2 (assuming there is enough latency in it or
computeRule to ensure the first thread does not complete before the
second enters the block). After this patch, the counter should be 1.
Note that there is a performance price for the synchronization,
which may outweigh the benefit of adding it.
Phil
>
>
> Thanks,
> 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