It seems the specific layout of dicts doesn't matter.
Using 2 dicts, 1 dict and a list, 1 dict all had identical memory
and CPU numbers. The only thing that matters is:

a) We can't use mixed mode with a single dictionary, because
   it gets very confused and performs poorly.
b) If you always use tuples, you cut memory from 410MB => 272MB, but
   performance jumps 42s => 50s
c) 'mixed' mode is inbetween, with 400MB and 43s. However, it is
   pretty much just the 'frozenset' performance.