Re: How to explain these variations in execution speeds?
- To: mathgroup at smc.vnet.net
- Subject: [mg113141] Re: How to explain these variations in execution speeds?
- From: Sseziwa Mukasa <mukasa at jeol.com>
- Date: Fri, 15 Oct 2010 13:50:30 -0400 (EDT)
- References: <201010140327.XAA06171@smc.vnet.net>
The short answer to your questions is that you are not evaluating the
same expression so your assumption that the expressions represent the
same amount of work is not true. Secondly you seem to have found some
indication that the algorithm used is not what one would naively expect.
I don't know the details of the internals os Mathematica so some of the
following responses are guesses on my part.
I'm guessing the reason lines 2,3,5,7 and 9 take longer is because when
the number of terms in the sum is less than 10^6 Mathematica computes
the sum using an explicit loop and thus incurs all the overhead of
arbitrary precision mathematics. You can accelerate these calculations
by using NSum, which is much faster albeit less accurate.
It seems when the the number of terms is greater than 10^6 Mathematica
first tries to solve the sum symbolically, and if it can evaluates the
result. In this case your sum has a simple solution n*(n+1)/2 which the
symbolic solver apparently can find very quickly, evaluation of that
expression is likewise very fast, hence the evaluation times of 4, 10, 6
and 8. The timings of these expressions varies as I execute the
expressions, implying there is also some caching behavior that explains
the variation in times among these expressions. The second time they
are evaluated the timing is nearly equivalent.
The Rule speeds things up because m is not numeric so the symbolic
solution is computed first, then the resulting expression evaluated when
the Replace is evaluated. You can see this by using Trace on the
expression.
There is no general rule to extract from this example, except perhaps
the behavior of Sum with respect to the magnitude of numeric index
ranges. With respect to Sum. when possible, solve for a simpler
expression equivalent to the sum, then evaluate that numerically. Or
use NSum when precision isn't a problem. Since Mathematica is closed
source and Wolfram may change the algorithms underlying the built in
functions there is little to be gained in trying to guess at the
behavior of the internals, but it is useful to explore that behavior
with respect to a specific problem. The change in behavior of Sum with
respect to iterator specification of the form {n,k} where k is numeric
is interesting, but the specific values of k which change behavior may
vary from version to version.
Your question about replacing the values does seem to reflect caching
behavior, the Evaluate causes speed changes because the result of the
Replace is simpler to compute.
You can't start the kernel programmatically (what would be executing to
cause it to start?), but you can control remote or parallel kernels from
a notebook.
Quitting the kernel then evaluating an expression will cause it to be
evaluated from the startup state.
Regards,
Ssezi
On Oct 13, 2010, at 11:27 PM, James Stein wrote:
>
> Stop your kernel; paste the following 14 lines in a notebook cell;
then
> evaluate the cell.
>
> (*1*)n=10^6;
> (*2*)Timing[Sum[k,{k,n}]]
> (*3*)Timing[Sum[k,{k,Evaluate[n]}]]
> (*4*)Timing[Sum[k,{k,n+1}]]
> (*5*)Timing[Sum[k,{k,n-1}]]
> (*6*)Timing[Sum[k,{k,n+2}]]
> (*7*)Timing[Sum[k,{k,n-2}]]
> (*8*)Timing[Sum[k,{k,n+3}]]
> (*9*)Timing[Sum[k,{k,n-3}]]
> (*10*)Timing[Sum[k,{k,m}]/.m->n-4]
> (*11*)Timing[Sum[k,{k,m}]/.m->Evaluate[n-5]]
> (*12*)Timing[Sum[k,{k,m}]/.m->10^6+6]
> (*13*)Timing[Sum[k,{k,m}]/.m->10^6-6]
>
> Each sum represents approximately the same amount of "work",
> but some sums are computed significantly faster than others.
> What results of previous computations are being used? when? where are
they
> stored? how are they accessed?
> Why does the use of 'Rule' (in lines 10-13) speed things up?
> Do these examples suggest good ways to speed code in general?
> Or are they merely exceptional because 'Sum' is a built-in function?
> (If documentation answers these questions, just point me there. I
searched
> w/o success.)
>
> On my computer, the execution times are approximately:
> 0.3500 second: Out lines 2,3,5,7,9
> 0.1000 second: Out lines 4,10
> 0.0044 second: Out lines 6,8
> 0.0003 second: Out lines 11,12,13
>
> Some of the puzzle is either explained or compounded (but I'm not sure
> which!) by comparing lines 1 and 2 with lines 10 and 11. Why does
'Evaluate'
> speed 11 wrt 10, but not 2 wrt 1?
>
> My head began to whirl when I compared these two pairs of lines:
>
> Pair 1: (as above, lines 10 and 11)
> Timing[Sum[k, {k, m}] /. m -> n - 4]
> Timing[Sum[k, {k, m}] /. m -> Evaluate[n - 4]]
>
> Pair 2: (same as Pair 1, except "dummy" variable 'm' replaced by 'z'
in
> second line only)
> Timing[Sum[k, {k, m}] /. m -> n - 4]
> Timing[Sum[k, {k, z}] /. z -> Evaluate[n - 4]]
>
> In each pair (assuming a fresh Kernel for each pair), the second line
is
> much faster than the first; but in the first pair, the speed increase
is
> much greater that the speed increase in the second pair. It seems
like the
> symbol chosen for the "dummy variable" is somewhere retained, and
affects
> further evaluations. (If so, how?)
>
>
> Two ancillary questions:
> 1. Is there a programmatic way (from a notebook) to stop then restart
the
> Kernel?
> 2. Is there a set of commands that effectively return the Kernel to
its
> initial state?
> (i.e., clear all user-defined symbols and history and reclaim memory)
>
>
- References:
- How to explain these variations in execution speeds?
- From: James Stein <mathgroup@stein.org>
- How to explain these variations in execution speeds?