# ByteCount on Function

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.

• What a nice overview of methods. Commented Sep 17, 2018 at 7:49
• Thanks! When you say that, I really appreciate it! Commented Sep 17, 2018 at 8:39

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

• DownValues returns way more, than only the right hand side. Is it a fair comparison? I guess all memory structures should be compared by DownValues then.
– Johu
Commented Aug 25, 2018 at 18:17
• @Johu I think it's a good first order approximation at least. I did provide a second method that I presume is more accurate. Commented Aug 25, 2018 at 18:18

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.

• Hmm, this is very low RAM usage, comparable to Table, yet faster than all of them. Why wouldn't one use Function instead of Table or Association?
– Leo
Commented Aug 25, 2018 at 17:21
• Your problem is that foo /@ 2 RandomInteger[n, n2] is parsed as (foo /@ 2) RandomInteger[n, n2]. Commented Aug 25, 2018 at 20:42
• I fixed it now and adjusted my conclusions. I did think it had to be impossible for the lookup from List to be that fast. Now it all makes sense.