Throwaway memoization makes built-ins faster?
Cause of speed up
This is definitely not memoization. The reason for the observed speed up is that for large arrays (e.g. 10^8 elements), the memory clean up operations may take noticeable time. If one doesn't free memory, one can perform some operations a bit faster.
Here is a simple example:
Let's create a large array, then perform a calculation, and remove the array:
AbsoluteTiming[
Total[ConstantArray[0, 10^8]];
]
{0.422509, Null}
It takes 0.42 seconds. Let's now do the same thing, but keep the array in memory:
AbsoluteTiming[
Total[garbage = ConstantArray[0, 10^8]];
]
{0.366755, Null}
This evaluation is a bit faster.
Let's check how long does it take to remove the large array:
AbsoluteTiming[
Remove[garbage]
]
{0.061982, Null}
Note that 0.06 seconds is the difference of the calculation times above. This example shows that if we keep the large array instead of removing it, our code can run faster, because we don't need to spent time on freeing memory.
Your example
In the example you provide, removing the result of Unitize@data[[All, n]] from memory takes some time. If one saves this array in a redundant variable, one avoids immediate memory clean-up and the evaluation seems to be faster.
In case of pseudo-memoization the Clear[pick, unitize] command will take extra time to free the memory, but this command is placed outside the AbsoluteTiming[] scope. That is why "memoization" seems to speed up the calculation.
How to make a representative test?
You should put Clear[pick, unitize] inside your timing function. This test will show that the pseudo-memoization technique is actually slower than built-in functions:
Table[
Clear[data];
data=RandomInteger[{0,10},{i*10^7,3}];
{
Pick[data,Unitize@data[[All,-1]],1]; // AbsoluteTiming // First
,
Clear[pick,unitize];
unitize[x_]:=unitize[x]=Unitize[x];
pick[xs_,sel_,patt_]:=pick[xs,sel,patt]=Pick[xs,sel,patt];
pick[data,unitize@data[[All,-1]],1]; // AbsoluteTiming // First
},
{i,5}]
(*
{{0.534744, 0.469538},
{1.03776, 1.05842},
{1.58536, 1.65404},
{2.10422, 2.11284},
{2.48129, 2.71405}}
*)
Technical note: as noted by Carl Woll in comments, if one wants to measure the symbol-removing-time using the following code:
In[1] := garbage = ConstantArray[0, 10^8];
In[2] := AbsoluteTiming[Remove[garbage]]
one should set $HistoryLength to zero, otherwise the Out[1] variable will retain the contents of the large array. If Out[1] retains the large data, Remove[garbage] will only delete the reference, but not the data itself. Deletion time of a reference is almost zero, but it doesn't correspond to the deletion time for large data.
You are absolutely correct that this memoization is completely unnecessary.
What seems to happens is that from the second run onwards on the same data, the builtin functions become faster. I do not understand why (perhaps some internal caching), but it does show that it has absolutely nothing to do with the memoization:
In[38]:= AbsoluteTiming[Pick[data, Unitize@data[[All, n]], 1] // Length]
AbsoluteTiming[Pick[data, Unitize@data[[All, n]], 1] // Length]
AbsoluteTiming[Pick[data, Unitize@data[[All, n]], 1] // Length]
Out[38]= {10.6117, 90909421}
Out[39]= {8.08706, 90909421}
Out[40]= {7.96311, 90909421}
Another comment:
RandomSeed is an option, not a function. It should be SeedRandom, otherwise it does nothing.
I can't reproduce claimed speedup on "11.0.1 for Linux x86 (64-bit) (September 21, 2016)".
In my tests, custom function wrappers without memoization (as suggested by Szabolcs) consistently add overhead of about 1 µs, functions with memoization add 2-3 µs overhead, compared to built-ins. This overhead is measurable only for small lists, for larger lists it's completely negligible.
Important thing is that results of AbsoluteTiming are very volatile with median deviation from minimal value, for larger lists, from few to ten percent. I'm sure there are better ways to measure this volatility, I used median deviation just to have any estimate.
Code used for timings:
$HistoryLength = 0;
minDev // ClearAll
minDev // Attributes = HoldFirst;
minDev[expr_, n_Integer?Positive] := Module[{res, min},
res = Table[expr, n];
min = Min@res;
{min, Median[res - min]}
]
testBuiltin@data_ := (
ClearSystemCache[];
Pick[data, Unitize@data, 1] // AbsoluteTiming // First
)
testCustom@data_ := (
ClearSystemCache[];
ClearAll[unitize, pick];
unitize[x_] := Unitize[x];
pick[xs_, sel_, patt_] := Pick[xs, sel, patt];
pick[data, unitize@data, 1] // AbsoluteTiming // First
)
testMemo@data_ := (
ClearSystemCache[];
ClearAll[unitize, pick];
unitize[x_] := unitize[x] = Unitize[x];
pick[xs_, sel_, patt_] := pick[xs] = Pick[xs, sel, patt];
pick[data, unitize@data, 1] // AbsoluteTiming // First
)
testAll[k_, n_] :=
With[{data = (SeedRandom[1]; RandomChoice[Range[0, 10], k])},
minDev[#@data, n] & /@ {testMemo, testCustom, testBuiltin}
]
format = TableForm@Map[
NumberForm[#, ExponentFunction -> (Null &)] &,
SetAccuracy[#, Min[Accuracy@SetPrecision[Min@#, 2], 7]],
{-1}
] &;
First argument of testAll is size of used data, second is number of repeated timings. First column of result is minimal absolute timing, second is median deviation from this minimal value. First rows are results for memoized custom pick and unitize, second rows are results for non-memoized custom functions, third rows are for built-in Pick and Unitize.
testAll[10^1, 10^5]//format
(* 0.000004 0.*10^(-7)
0.000002 0.000001
0.000001 0.000001 *)
testAll[10^2, 10^5]//format
(* 0.000005 0.000001
0.000003 0.000001
0.000002 0.000001 *)
testAll[10^3, 10^5]//format
(* 0.000015 0.000001
0.000014 0.*10^(-7)
0.000013 0.000001 *)
testAll[10^4, 10^5]//format
(* 0.000124 0.000002
0.000122 0.000002
0.000121 0.000001 *)
testAll[10^5, 10^4]//format
(* 0.001297 0.000093
0.001296 0.000069
0.001295 0.000103 *)
testAll[10^6, 10^3]//format
(* 0.0201 0.0014
0.0201 0.0011
0.0201 0.0012 *)
testAll[10^7, 10^2]//format
(* 0.2004 0.0148
0.2003 0.0099
0.2004 0.0088 *)
testAll[5 10^7, 2 10^1]//format
(* 0.972 0.021
0.974 0.017
0.973 0.022 *)
Fresh kernel
To make sure that we're not using any Mathematica's internal cache, that might not be cleared by ClearSystemCache, we can launch separate kernel for each test using:
freshKernelEvaluate // ClearAll
freshKernelEvaluate // Attributes = HoldAll;
freshKernelEvaluate@expr_ := Module[{link, result},
link = LinkLaunch[First@$CommandLine <> " -mathlink -noprompt"];
LinkWrite[link, Unevaluated@EvaluatePacket@expr];
result = LinkRead@link;
LinkClose@link;
Replace[result, ReturnPacket@x_ :> x]
]
Timings of built-ins:
resBuiltin = Table[
freshKernelEvaluate[
SeedRandom@1;
data = RandomChoice[Range[0, 10], 5 10^7];
Pick[data, Unitize@data, 1] // AbsoluteTiming // First
],
100
]
{1.28392, 1.23527, 1.25863, 1.23625, 1.33601, 1.24361, 1.26809, 1.23502, 1.34473, 1.23813, 1.24654, 1.23617, 1.27127, 1.25661, 1.22674, 1.58978, 1.26939, 1.37024, 1.24581, 1.54075, 1.23516, 1.23805, 1.3053, 1.40044, 1.42726, 1.39822, 1.46109, 1.27038, 1.39617, 1.2588, 1.29047, 1.23082, 1.25069, 1.34985, 1.27281, 1.24016, 1.2642, 1.2511, 1.23745, 1.27978, 1.24066, 1.38282, 1.32234, 1.30623, 1.26118, 1.58021, 1.27522, 1.24706, 1.27051, 1.2493, 1.24819, 1.28184, 1.46254, 1.24269, 1.26356, 1.24011, 1.35468, 1.27491, 1.35288, 1.24462, 1.27119, 1.26811, 1.23685, 1.33249, 1.23138, 1.29139, 1.23725, 1.28638, 1.23906, 1.27579, 1.3872, 1.31602, 1.29556, 1.26464, 1.27076, 1.24602, 1.25735, 1.24667, 1.27297, 1.23757, 1.34311, 1.26616, 1.35083, 1.24861, 1.23788, 1.25357, 1.24262, 1.28117, 1.25753, 1.28231, 1.23406, 1.27971, 1.22885, 1.27199, 1.24191, 1.23346, 1.26387, 1.24803, 1.27653, 1.23953}
Timings of memoized custom functions:
resMemo = Table[
freshKernelEvaluate[
SeedRandom@1;
data = RandomChoice[Range[0, 10], 5 10^7];
unitize[x_] := unitize[x] = Unitize[x];
pick[xs_, sel_, patt_] := pick[xs] = Pick[xs, sel, patt];
pick[data, unitize@data, 1] // AbsoluteTiming // First
],
100
]
{1.35284, 1.23307, 1.27167, 1.23678, 1.27437, 1.25009, 1.27847, 1.2418, 1.23227, 1.39655, 1.26371, 1.26179, 1.27424, 1.27965, 1.236, 1.28489, 1.25988, 1.26318, 1.24007, 1.24381, 1.2672, 1.25462, 1.26703, 1.24123, 1.28868, 1.24192, 1.27177, 1.23488, 1.23468, 1.27525, 1.26571, 1.27287, 1.23757, 1.26981, 1.25737, 1.2729, 1.23705, 1.24429, 1.26927, 1.23292, 1.28266, 1.23352, 1.28423, 1.23743, 1.26883, 1.23515, 1.27272, 1.25892, 1.23213, 1.23746, 1.3435, 1.27545, 1.23472, 1.49113, 1.42916, 1.56421, 1.5238, 1.37695, 1.27734, 1.23146, 1.2388, 1.24054, 1.27661, 1.23467, 1.43818, 1.51605, 1.28172, 1.24674, 1.34043, 1.36447, 1.28034, 1.23788, 1.3027, 1.25299, 1.26136, 1.24514, 1.23405, 1.26157, 1.24994, 1.27737, 1.23637, 1.26785, 1.411, 1.24163, 1.2301, 1.29223, 1.25492, 1.25177, 1.26862, 1.25825, 1.23715, 1.25327, 1.2694, 1.6624, 1.24317, 1.26682, 1.27915, 1.25705, 1.23258, 1.25804}
I don't see any consistent difference, distribution of results seems similar:
res = <|"Built-in" -> resBuiltin, "Memo" -> resMemo|>;
ListPlot[res, PlotRange -> All]
Histogram[res, PlotRange -> All, ChartStyle -> {Blue, Orange}, ChartLegends -> Automatic]
Edit
UnchartedWorks writes in a comment that unitize is enough to show difference in speed and pick is not necessary. Carl Woll points out that data matrix should be used instead of data vector.
After changing above I see a difference between memoized and built-in version. Memoized function is consistently slower than built-in.
Used test functions:
testBuiltin = freshKernelEvaluate[
$HistoryLength = 0;
SeedRandom@1;
data = RandomChoice[Range[0, 10], {#, 3}];
Pick[data, Unitize@data[[All, -1]], 1] // AbsoluteTiming // First
] &;
testCustom = freshKernelEvaluate[
$HistoryLength = 0;
SeedRandom@1;
data = RandomChoice[Range[0, 10], {#, 3}];
unitize[x_] := Unitize[x];
Pick[data, unitize@data[[All, -1]], 1] // AbsoluteTiming // First
] &;
testMemo = freshKernelEvaluate[
$HistoryLength = 0;
SeedRandom@1;
data = RandomChoice[Range[0, 10], {#, 3}];
unitize[x_] := unitize[x] = Unitize[x];
Pick[data, unitize@data[[All, -1]], 1] // AbsoluteTiming // First
] &;
Timings:
SetDirectory@NotebookDirectory[];
s = OpenWrite@"results.dat";
k = 3 10^7;
Do[
Write[s,
If[OddQ@i,
{testBuiltin@k, testCustom@k, testMemo@k},
Reverse@{testMemo@k, testCustom@k, testBuiltin@k}
]
],
{i, 10^2}
] // AbsoluteTiming
file = Close@s;
(* {898.653, Null} *)
Result analysis:
results = AssociationThread[{"Built-in", "Custom", "Memo"} -> Transpose@ReadList@file]
colors = {Blue, Orange, Darker@Green};
ListPlot[results, PlotRange -> All, PlotStyle -> colors]
Histogram[results, PlotRange -> All, ChartStyle -> colors, ChartLegends -> Automatic]
<|"Built-in" -> {1.22985, 1.22461, 1.23061, 1.23184, 1.2402, 1.22937, 1.25221, 1.21342, 1.23612, 1.22765, 1.23061, 1.23409, 1.25464, 1.21786, 1.23144, 1.24461, 1.24803, 1.24498, 1.24818, 1.23294, 1.2348, 1.51256, 1.51016, 1.46498, 1.48277, 1.49113, 1.38432, 1.23417, 1.23139, 1.23475, 1.23356, 1.22846, 1.23629, 1.25202, 1.23593, 1.24975, 1.22473, 1.23137, 1.2266, 1.25627, 1.21828, 1.2525, 1.23725, 1.24693, 1.24163, 1.23324, 1.28597, 1.23083, 1.22618, 1.23927, 1.22844, 1.23095, 1.21823, 1.23546, 1.23057, 1.22338, 1.22514, 1.23199, 1.23086, 1.21832, 1.22947, 1.22668, 1.2302, 1.24527, 1.23862, 1.48311, 1.48445, 1.47365, 1.24457, 1.25607, 1.26731, 1.22819, 1.23567, 1.23589, 1.27261, 1.22645, 1.22554, 1.23832, 1.22731, 1.2334, 1.25166, 1.26591, 1.22114, 1.24653, 1.22359, 1.22788, 1.22567, 1.25535, 1.23223, 1.24091, 1.24912, 1.23169, 1.23663, 1.23177, 1.2278, 1.55135, 1.4796, 1.49146, 1.49611, 1.23101}, "Custom" -> {1.23652, 1.23587, 1.23412, 1.22896, 1.22707, 1.23646, 1.25783, 1.26341, 1.24158, 1.22581, 1.22999, 1.24083, 1.23376, 1.23851, 1.24782, 1.22384, 1.2431, 1.23661, 1.23801, 1.24318, 1.23982, 1.53433, 1.48343, 1.54463, 1.48097, 1.47601, 1.23676, 1.24323, 1.2311, 1.22642, 1.23351, 1.23296, 1.23254, 1.23407, 1.23169, 1.24395, 1.24042, 1.24769, 1.23167, 1.21756, 1.2301, 1.23421, 1.24282, 1.23704, 1.23525, 1.2351, 1.25029, 1.23524, 1.22839, 1.22839, 1.23667, 1.26583, 1.22544, 1.22955, 1.22292, 1.22819, 1.27443, 1.24958, 1.24789, 1.22195, 1.21883, 1.22279, 1.21813, 1.22052, 1.23921, 1.5044, 1.49484, 1.50915, 1.23095, 1.23694, 1.22373, 1.24806, 1.22945, 1.24085, 1.23373, 1.22282, 1.2362, 1.23099, 1.23932, 1.24258, 1.25047, 1.26868, 1.23042, 1.22579, 1.2229, 1.23243, 1.2368, 1.22925, 1.2387, 1.23014, 1.21772, 1.2259, 1.22549, 1.23208, 1.26501, 1.33781, 1.48822, 1.48658, 1.25979, 1.26228}, "Memo" -> {1.29497, 1.29798, 1.29918, 1.29907, 1.31014, 1.29503, 1.29095, 1.3249, 1.29036, 1.30051, 1.2789, 1.29959, 1.2988, 1.2882, 1.29519, 1.28946, 1.31952, 1.32948, 1.32447, 1.29627, 1.31841, 1.5721, 1.57097, 1.55392, 1.56358, 1.55974, 1.28744, 1.3029, 1.28567, 1.2914, 1.29167, 1.29062, 1.29471, 1.29797, 1.30193, 1.30423, 1.30097, 1.29706, 1.29027, 1.29005, 1.29543, 1.2929, 1.29996, 1.29386, 1.29502, 1.31621, 1.31506, 1.29105, 1.30462, 1.28348, 1.30922, 1.28715, 1.30386, 1.29361, 1.29596, 1.30149, 1.28943, 1.29833, 1.31909, 1.2911, 1.31163, 1.28986, 1.29063, 1.28847, 1.29451, 1.46695, 1.55118, 1.55433, 1.29779, 1.29201, 1.29947, 1.29045, 1.28494, 1.29003, 1.29385, 1.2856, 1.31603, 1.33432, 1.28929, 1.29873, 1.29259, 1.28694, 1.28868, 1.28838, 1.29824, 1.29435, 1.29401, 1.30137, 1.2971, 1.29248, 1.29333, 1.2847, 1.28666, 1.28647, 1.29923, 1.30116, 1.56112, 1.56282, 1.29155, 1.2936}|>
