Dfyjkt

I was comparing RAM and CPU efficiency for List, Rule, Association, Function. The following code

n=10^6; 
tbl=Table[2i,i,n]; ByteCount[tbl]
rls=Table[2i->i,i,n]; ByteCount[rls]
asc=Association@Table[2i->i,i,n]; ByteCount[asc]
Do[fnc[2i]=i,i,n]; ByteCount[fnc]
AbsoluteTiming[Position[tbl,2n][[1,1]]]
AbsoluteTiming[2n/.rls]
AbsoluteTiming[asc[2n]]
AbsoluteTiming[fnc[2n]]

gave the following results:

8000144

96000080

128382000

0

0.142235, 1000000

0.805691, 1000000

0.00001, 1000000

4.*10^-6, 1000000

Thus Function is the fastest, but how do I get its real memory requirement?

Since you are using positive integer labels with rather high density in their range you should also try a classical array as lookup table. A further variant that works well when the keys are integers or lists of integers with fixed length is by using a BSP tree like with Nearest:

n = 10^6;
tbl = Table[2 i, i, n]; ByteCount[tbl]
rls = Table[2 i -> i, i, n]; ByteCount[rls]
rls2 = Dispatch[rls]; ByteCount[rls2]
asc = AssociationThread[Range[2, 2 n, 2], Range[n]]; ByteCount[asc]
ClearAll[fnc];
Do[fnc[2 i] = i, i, n]; ByteCount[DownValues[fnc]]
lookuptable = ConstantArray[0, 2 n];
lookuptable[[2 ;; ;; 2]] = Range[1, n]; ByteCount[lookuptable]
nf = Nearest[Range[2, 2 n, 2] -> Automatic];values = Range[n];ByteCount[nf] + ByteCount[values]

8000144

96000080

126473520

126473432

192000080

16000144

16000488

a = 2 RandomInteger[1, n, 100000];
RepeatedTiming[r2 = a /. rls2][[1]]
RepeatedTiming[r3a = asc /@ a][[1]]
RepeatedTiming[r3b = Lookup[asc, a]][[1]]
RepeatedTiming[r4 = fnc /@ a][[1]]
RepeatedTiming[r5 = lookuptable[[a]]][[1]]
RepeatedTiming[r6 = values[[Flatten[nf[a, 1]]]]][[1]]
r2 = r3a == r3b == r4 == r5 == r6

0.907

0.8451

0.614

1.0

0.011

0.11

True

Also notice that these methods behave very differently to each other when looking up invalid keys.

DownValues should get close to the actual value I believe.

ByteCount[DownValues[fnc]]

192000080

You could also use MaxMemoryUsed during the construction:

ClearAll[fnc]

MaxMemoryUsed[Do[fnc[2 i] = i, i, 10^6];]

168327840

In your example the value of the argument is a part of the definition. Value of fnc[2 i], where i is a symbol, is not defined in your MWE.

Total@Table[ByteCount[fnc[2 i]], i, n]

16 000 000

(Edit: note, that my solution only gives only the size of the right hand side and probably underestimates the real memory cost. See the other solution.)

Note also, that your timing measurement lead to misleading results as you apply it to so simple operations. Compare to

n2 = 10;
AbsoluteTiming[Position[tbl, #] & /@ (2 RandomInteger[n, n2])] // First
AbsoluteTiming[Replace[rls] /@ (2 RandomInteger[n, n2]);] // First

2.19423 
1.8028 

Both of these approaches are very slow, as they require going through the whole list to fine the element.

These are much much faster:

n2 = 100000;
AbsoluteTiming[fnc /@ (2 RandomInteger[n, n2]);] // First
AbsoluteTiming[asc /@ (2 RandomInteger[n, n2]);] // First
AbsoluteTiming[Lookup[asc, 2 RandomInteger[n, n2]];] // First

> 0.267781
> 0.226777
> 0.171752

I think it is misleading to call fnc[i] a function, as a function usually is evaluated runtime. In your MWE you save a precomputed value. This technique is referred to as memoization.

When you wonder which one you should use, I would always use what makes sense semantically, because the engineers behind the kernel and native commands have but a lot of effort into finding a balance between all the features one usually needs from a List, Rules, Associations and Symbols. Associations and Symbols are the ones, which require fast random access.