Association vs Pair - Creation performance, Selection performance

Question

Suppose that we

Ass = AssociationThread[Range[1000000], Range[1000000]^2]; // Timing
KeySelect[Ass, PrimeQ]; // Timing
Tra = Transpose[{Range[1000000], Range[1000000]^2}]; // Timing
Select[Tra, PrimeQ[#[[1]]] &]; // Timing

Here We create a list of mathematical pairs, and extract elements that meet a certain criteria. The criteria only concerns its 1st component. (1st component should be a prime number).

There are 2 method : Association vs list of pairs

It is much faster to create such list by list of pairs method. Association took 0.375 seconds, whereas Tra took 0. seconds.

Interestingly, once such list(or association) is made, selection-job is faster in Association. Keyselect took 0.484 seconds, whereas Select took 0.922 seconds.

Not so important, but to sum up,
0.375 + 0.484 < 0.+0.922
so Association method won in this case.

Now what you think right now and my question might be the same :

I want to create such list of pairs(equivalent) in no seconds (0. seconds like Tra method), simultaneously,
I want to select elements by a criteria(that only concerns 1st component) as fast as Keyselect. I want to combine the advantages of both.

And in fact I've never used Association before. In the past, list of pairs was sufficient tool for me. But now there is a new aspects of Association - the performance.

Do you agree that when there are some filtering jobs(with criteria only concerns 1st component or only 2nd component)to do, it is recommended to create Association rather then list of pairs ?

To recap,
Q1) Can we construct list of mathematical pairs (anything equivalent) with good performance of both creation and selection ?
Q2) If there are many selection jobs for a fixed structure of matheatica pairs, is it good to start with association rather then list of pairs?

Answer 1

Simply use

keys = Range[1000000]; 
vals = Range[1000000]^2; 
result = Pick[vals, PrimeQ[keys]];

to get the best of both worlds (zero construction cost and even faster lookup). After all, Association is a quite heavy data structure (both in terms of storage requirements and algorithmic complexity). Build Associations only when

1. you need a structured dictionary or
2. you want to do random read/write access and the keys are either no positive integers or the spread of the keys is too large to use a classical array/vector for that.

Also note that most of the cost here is actually due to evaluating PrimeQ[keys].

Why is Select[Tra, PrimeQ[#[[1]]] &] slower? There are several possible reasons.

1. Tra stores the data in interleaved form. So it probably does not allow any vectorization(*). In any case, this might require to pump more memory through the cache hierarchy than need.
2. Select is generally a bit slower than a properly setup Pick. Which is weird because Pick is more memory bound because an additional list of True/False has to be created first. But at least vectorized functions(*) can profit from this.
3. Mapping PrimeQ[#[[1]]] & is substantially slower than mapping PrimeQ.

With regard to point 3. compare this:

 bla = Tra[[All, {1}]];
 Map[PrimeQ[#[[1]]] &, bla]; // AbsoluteTiming // First
 Map[PrimeQ, keys]; // AbsoluteTiming // First

0.580334

0.185707

One point of this is additional indirection in the function call:

Map[PrimeQ[#] &, keys]; // AbsoluteTiming // First
Map[PrimeQ, keys]; // AbsoluteTiming // First

0.284284

0.180143

But I think the major reason is that Part has to apply a bound check every time it is called to prevent segfaults.

(*) I don't think PrimeQ is vectorized, btw., albeit it is Listable. Map[PrimeQ, keys] and PrimeQ[keys] takes about the same time.