Speed differences between Table, Replace, Array, Map, and AssociationMap

EDIT: Actually, it looks like part of this is bogus—Array doesn't actually work on this input (I'm often a little shaky on what kind of input, exactly, works for interpolated functions...) which I should have realized from the flat timing curve. Array is now in line with the non-Table cluster, making Table the fastest (but still slower than I'd like). The image has been updated. I also think that I should maybe rerun these with AbsoluteTiming; I'm seeing some disparity here and there.

I have a function f which is an Interpolation of two variables, say x and y. In my full use case, I have 200 different such fs, and each one should act on a simple 674x674 array which is just an array of coordinates (i.e. just {{{1, 1}, {1, 2}, {1, 3}}, {{2, 1},... if the arrays in question were only 3x3).

There seem to be a lot of ways to do this, and I don't know how to pick the best one, why the best one is the best one, or even whether the best one that I've found is indeed the best! Array seems to be tailor-made for this use-case, but I don't understand why everything else is so much worse (also, I could swear I had clocked AssociationMap as faster last night, but it looks like I must not have—I think that the Table vs. ParallelTable issue mentioned below must account for that).

Here are the ways I've tried, as well as the Timing results for running them for arrays of size up to 100x100.

TableTiming = Table[First@Timing@Table[f, {x, i}, {y, i}], {i, 100}];

ReplaceTiming = Table[With[{z = Table[{x -> a, y -> b}, {a, i}, {b,i}]}, First@Timing[f /. z]], {i, 100}];

g2[i_, j_] := f /. {x -> i, y -> j}

ArrayTiming = Table[First@Timing[g2~Array~{i, i}], {i, 100}];

g[{i_, j_}] := f /. {x -> i, y -> j}

MapTiming = Table[With[{z = Flatten[Table[{a, b}, {a, i}, {b, i}], 1]}, First@Timing[g /@ z]], {i, 100}];

AssociationMapTiming = Table[With[{z = Flatten[Table[{a, b}, {a, i},{b, i}], 1]}, First@Timing[Values@AssociationMap[g, z]]], {i, 100}];


The results:

Results using AbsoluteTiming:

Array works basically like I'd expect—after all, even though f is not a beautiful function given that it's a ListInterpolation over a surface, finding these values amounts to plugging two integers into a polynomial—it doesn't seem like it should take very long. My curiosity is regarding why Replace, Map, and AssociationMap all seem to come out the same, Table seems to be middling, and Array destroys them all. I don't understand the underlying mechanisms that should determine these trends.

I also stumbled upon a weird (to me) issue where using ParallelTable to calculate these Timings resulted in huge disparities, as shown below.

I don't understand why this is happening, either, and it has me wondering whether I have code hanging around that would run much more quickly with Table vs. ParallelTable :/. This turned out not to be unique to AssociationMap, either—why does this happen, and how can I avoid falling prey to it in the future?

I have two followup questions, as well:

1. Is Array Table the best way to implement this, or is there another way to go about this?

2. If I don't care about the individual values, but only care about applying Mean@Abs@Flatten@#& to the final arrays, is there trick I could use to speed this up further? (UPDATE: Sum[Abs@f,{x,674},{y,674}]/674^2 is the fastest yet, actually—very reasonably so.)

• Just a few remarks... Since your operations all run quite fast, you might want to use RepeatedTiming to benchmark the speed. This averages over multiple runs and is "better" I believe if your operations just take a few seconds at most. W.r.t. (Parallel)Table timings: your calculations are pretty fast, so ParallelTable will not help because there's a huge overhead due to data exchange between local and master kernel. ParallelTable is useful when each evaluation takes quite a long time, if you search SE here you will find many questions on that Jun 12, 2016 at 7:44
• @Lukas good call on ParallelTable; I knew about that but never considered that the overhead would be that massive. At least the other operations that I use that and ParallelMap for are much more complicated, so that jives with what you've said as well. I could use RepeatedTiming, but the given results for CPU timing are pretty replicable and I'm not too worried about them. Jun 12, 2016 at 8:31
• Try setting your function Listable, that can, in most cases, surpass all these solutions in speed. :)
– Wjx
Jun 12, 2016 at 8:46
• @Wjx that's a great idea! I'm having trouble figuring out how to do this with the results of an InterpolatingFunction, though. I start out with such a function, but the f in my above post is in terms of derivatives of that interpolating function. I just slightly rewrote it so that I keep f a pure function instead of plugging in x and y to take explicit derivatives—but now I can't even feed it arguments, it seems. Regardless of that: Setting, say, g to Listable causes it to act come out like {{g[1], g[1]}, {g[1], g[2]},... instead of making it take the {i,j} input. Jun 12, 2016 at 20:37