Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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)
>
>



  • Prev by Date: Re: What is the ESC sequence for the "Matching Double Brakets"? From
  • Next by Date: Re: Tutorial for running remote kernels?
  • Previous by thread: How to explain these variations in execution speeds?
  • Next by thread: Re: How to explain these variations in execution speeds?