8
$\begingroup$

I was wondering, why is extracting from an Association slightly faster than extracting from a List?

assoc = Association[Table[i -> i^2, {i, 1000}]];
list = Table[i^2, {i, 1000}];
list[[10]] // RepeatedTiming
assoc[10] // RepeatedTiming
(* I'm not posting outputs because of the variance but the 2nd is usually faster *)

I would have expected nothing to be faster than extraction from a List since it should be just a memory access vs a more computationally-expensive lookup for Association.

MMA 11.2 Linux.

$\endgroup$
  • 2
    $\begingroup$ I was going to mention something about unpacking, but the version using ulst = Developer`FromPackedArray[list] is even slower. Huh. $\endgroup$ – J. M. will be back soon Apr 1 '18 at 3:33
  • $\begingroup$ I am not convinced that association-lookup is really faster. It could be some timing artefact. It is not easy to time such extremely short operations accurately. list[[#]] & /@ Range[100] is 9 times faster on my machine than assoc /@ Range[100]. $\endgroup$ – Szabolcs Apr 1 '18 at 9:20
  • 3
    $\begingroup$ The benchmark in my comment above is flawed. Part is faster because of auto-compilation. Change Range[100] to Range[99] and association lookup becomes almost precisely 2x faster than list indexing. I wonder if it has any significance that the factor is almost precisely 2. $\endgroup$ – Szabolcs Apr 1 '18 at 9:28
  • 2
    $\begingroup$ Lookup[assoc, 10] is consistently a little faster than assoc[10] for me. $\endgroup$ – Michael E2 Apr 1 '18 at 17:30
5
$\begingroup$

Recall that Mathematica is an interpreter language, so there is significant overhead in each single call. Only bulk access to data can show that Lists are significantly faster than Associations.

n = 1000;
assoc = AssociationThread[Range[n], Range[n]^2];
list = Range[n]^2;
idx = RandomInteger[{1, n}, 100000];
Do[x = list[[i]], {i, idx}]; // AbsoluteTiming
Do[y = assoc[i], {i, idx}]; // AbsoluteTiming
a = Table[assoc[i], {i, idx}]; // AbsoluteTiming
b = Table[list[[i]], {i, idx}]; // AbsoluteTiming
c = list[[idx]]; // AbsoluteTiming
d = Lookup[assoc, idx]; // AbsoluteTiming
a == b == c == d

{0.047621, Null}

{0.044828, Null}

{0.029103, Null}

{0.001618, Null}

{0.000347, Null}

{0.008003, Null}

True

(Mathematica 11.3 for macos)

$\endgroup$
  • 2
    $\begingroup$ Well, I am not an expert in dictionaries but the basic idea is to have a hash function f that maps keys to memory adresses. In order to lower the chances of collision, this hash function has to be rather "discontinuous", that means that f[key1] and f[key2] should map to different adresses, even if key1 and key2 are similar. Still, collision cannot completely avoided. So, compared to simple arrays, there is some overhead i) in computing f[key] and ii) in handling these collisions. $\endgroup$ – Henrik Schumacher Apr 1 '18 at 17:14
  • 1
    $\begingroup$ The advantage over arrays is that you do not have to rely on consecutive integer indices and that appending entries and dropping entries of a dictionary is of low cost. $\endgroup$ – Henrik Schumacher Apr 1 '18 at 17:15
  • 1
    $\begingroup$ I am not sure what you mean by "overhead during a list call". All I can say is that both Part and Lookup certainly have compiled libraries as backends and that the communication between the MathKernel and these libraries can be reduced by sending as few queries as possible. $\endgroup$ – Henrik Schumacher Apr 1 '18 at 17:31
  • 2
    $\begingroup$ Note that Table[list[[i]]...] is compiled, which greatly speeds up the performance, and there are differences in speed between packed and unpacked list and idx, for all four combinations. (Compilation can be prevented with SetSystemOptions["CompileOptions" -> "TableCompileLength" -> Infinity].) $\endgroup$ – Michael E2 Apr 1 '18 at 17:43
  • 3
    $\begingroup$ @anderstood The Mathematica Association is a hash array mapped trie, per mathematica.stackexchange.com/questions/52393/…. $\endgroup$ – Patrick Stevens Apr 1 '18 at 20:52
1
$\begingroup$

Association key-value pairs are indexed objects. Lists are not. As you increase the dimensionality of your association vs list comparison you will quickly see best practice is to put everything in associations and datasets.

$\endgroup$
  • 5
    $\begingroup$ That's not true - at least for purely numerical data. $\endgroup$ – Henrik Schumacher Apr 1 '18 at 9:00
  • $\begingroup$ @Henrik Schumacher - right, but I can't remember the last time I worked pure numerical list, so my lack of qualification. My context is n-dimensions with characteristic variables. Since M10 Association and Dataset have been a valuable help to my work saving lots of custom work indexing data and cpu cycles working on the data. $\endgroup$ – Mitch Apr 3 '18 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.