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][]
RepeatedTiming[r3a = asc /@ a][]
RepeatedTiming[r3b = Lookup[asc, a]][]
RepeatedTiming[r4 = fnc /@ a][]
RepeatedTiming[r5 = lookuptable[[a]]][]
RepeatedTiming[r6 = values[[Flatten[nf[a, 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. Sep 17 '18 at 7:49
• Thanks! When you say that, I really appreciate it! Sep 17 '18 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
Aug 25 '18 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. Aug 25 '18 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
Aug 25 '18 at 17:21