3
$\begingroup$

I'm trying to speed up the calculation such like:

repeat=RandomChoice[{-1.,1.},1000000]
E^repeat

the calculation of E^1. is repetitive thus can be greatly accelerated if Mathematica stored the result and directly return the pre-calculated result when repetitive calls occurs.

Obviously Once cannot do this stuff as itself costs too much time, storing the result in some function also won't help as the function call already costs too much.

So the first question is:

How to speed up such evaluation?

When I'm trying to check whether Mathematica cached the result, I tried the following code:

dat = RandomChoice[{-1., 1.}, 10000000];
E^dat; // AbsoluteTiming

dat = RandomChoice[{-1., 1.}, 10000000] + RandomReal[{-1.*^-10, 1.*^-10}, 10000000];
E^dat; // AbsoluteTiming

However, to my surprise, the second one requires lot less computation time, why?


Update

Oh, sorry that I forgot packing issues, so the only problem left is how to speed things up.

$\endgroup$

1 Answer 1

3
$\begingroup$

Removing overhead of an unpacked array

The performance difference appears because RandomChoice produces an unpacked array, but your second command forces array packing. Large vector operations on packed arrays are much more efficient.

You can check packed/unpacked status of any array using:

Developer`PackedArrayQ[dat]

For your first example it gives False for the second True.

You can force array packing using Developer`ToPackedArray. In your example it will give large performance boost:

dat = Developer`ToPackedArray@RandomChoice[{-1., 1.}, 10000000];
E^dat; // AbsoluteTiming

{0.014406, Null}

More information on packed arrays: What is a Mathematica packed array?, Guidelines for avoiding the unpacking of a packed array.

Feasibility of caching

Modern processors have built in instructions for calculating exponents. This means that recalculating exponent each time takes only one instruction, while searching in some sort of precalculated table will take much more instructions and will take longer.

If you have such a simple operation as exponent, there is no sense to organize software-defined caching mechanism. It is faster to recalculate than to lookup in a cache.

Theoretical limit

There is an upper limit of how many exponents a processor can evaluate in one second. Very roughly this can be estimated as (processors frequency)x(number of cores). E.g. a 1 GHz 4-core processor can maximum perform 4x10^9 operations. This is without any overhead and ignoring that exponentiation takes more than one cycle.

When you look at Timing results of packed array operation above, you see that they are not far from the theoretical limit. This means that there is not much overhead left.

This means that the main strategy is to:

Optimize your algorithm

In your example you can first calculate exponents and then generate a list.

dat = Developer`ToPackedArray@RandomChoice[{Exp[-1.], Exp[1.]}, 10000000];
AbsoluteTiming[dat;]

In this case there will be no exponentiation step at all.

$\endgroup$
7
  • $\begingroup$ Oh, I forgot that……Thanks! $\endgroup$
    – Wjx
    Apr 15, 2017 at 11:41
  • $\begingroup$ Oh, btw, still it didn't solve my original problem, how to speed up this process by some sort of caching? $\endgroup$
    – Wjx
    Apr 15, 2017 at 11:42
  • $\begingroup$ @Wjx I have included some information about caching in the anwer. $\endgroup$
    – Shadowray
    Apr 15, 2017 at 13:22
  • $\begingroup$ but in C one can create an array of reference and simply calculate exponent twice and change the reference target, this will obviously be much faster. Are there any sort of memory sharing technique like this in MMA? $\endgroup$
    – Wjx
    Apr 15, 2017 at 13:40
  • $\begingroup$ @Wjx RandomChoice[{Exp[-1.], Exp[1.]}, 10000000] calculates exponent exactly twice. Is that what you are looking for? $\endgroup$
    – Shadowray
    Apr 15, 2017 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.