Performance optimization of numerous simple but repetitive calculation

Question

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.

Answer 1

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.