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

Question

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