# What's going on with performance of Tally here?

Observe:

l1 = l2 = RandomInteger[{1, 100000}, 1000000];
l2[[-1]] = -1;
t1 = First@Timing@Tally[l1];
t2 = First@Timing@Tally[l2];

l1 = l2 = RandomInteger[{1, 100000}, 1000100];
l2[[-1]] = -1;
t3 = First@Timing@Tally[l1];
t4 = First@Timing@Tally[l2];

l1 = l2 = RandomInteger[{1, 99999}, 1000000];
l2[[-1]] = -1;
t5 = First@Timing@Tally[l1];
t6 = First@Timing@Tally[l2];

{t1, t2, t3, t4, t5, t6}

(* {0.046800, 1.138807, 0.046800, 0.062400, 0.062400, 0.046800} *)


What's with the huge timing jump for t2? There's no unpacking or such going on - this has me scratching my noggin...

• I am glad to see you are still willing to ask questions here, and boy that's a strange result. May 9, 2015 at 2:10
• @Mr.Wizard: Well, of course - Don Quixote themed pursuits for rep justice (hmm, rep-justice warrior?) aside, this is the only game in town to tap brain power like yours and the other experts here, and to get feedback from WRI gang members. Glad you seem to find this tally behavior as interesting as I do... +1 on your comment / answer.
– ciao
May 9, 2015 at 6:06
• Which version are you using? May 9, 2015 at 8:46
• @YvesKlett: Sorry for delay in response - not here as much.... in any case , 9.0.1 on Windoze....
– ciao
May 9, 2015 at 21:29
• @ciao not to worry! Same effect on 10.1, in any case... May 10, 2015 at 7:18

My guess is that Tally preallocates a number of bins equal to 10% of the length of the list. If the need exceeds that, then it probably has to reallocate the bins, apparently in a time-consuming manner.

Table[
l1 = l2 = RandomInteger[{1, max}, 10 max];
l2[[-1]] = -1;
{First@Timing@Tally[l1],
First@Timing@Tally[l2]},
{max, 2^Range[12, 21]}] // Grid


Table[
l1 = l2 = RandomInteger[{1, max}, 10 max + 10];
l2[[-1]] = -1;
{First@Timing@Tally[l1],
First@Timing@Tally[l2]},
{max, 2^Range[12, 21]}] // Grid


• You won the coin flip... both your and Mr. W answers worthy. Thx!
– ciao
May 10, 2015 at 21:19

This is more of a comment than an answer but it's too long for a comment box and I hope to extend it as I learn more.

My first thought was that the negative value might be preventing some optimization so I looked for a counterexample and found something surprising:

Table[
With[{a = RandomInteger[{1, 100000}, 1000000 + x]},
First @ Timing @ Do[Tally[a], {10}] / 10
],
{x, -5000, 5000, 1000}
]

{0.121681, 0.117001, 0.113881, 0.115441, 0.118561, 0.00468003, 0.00468003,
0.00468003, 0.00312002, 0.00468003, 0.00468003}


It seems that Tally invokes an optimization on (some) packed lists of integers over length 1×10^6 and this optimization has been present since at least version 7. This seems similar to things like "ArrayCompileLength" but I cannot find a System Option that applies. At least on the given example the crossover point seems poorly chosen as there is 40X speed-up indicating that an earlier point would have been better.

Since we do not know the details of this or other optimizations used by Tally I can only presume, but it seems plausible that the presence of a negative value causes the heuristic to trigger only on a slightly longer list. (1000010 is sufficient for both timings to be similar.)

• I think it has to do with the range of values (or bins). Try l1 = l2 = RandomInteger[{1, 99999}, 1000000]; l2[[-1]] = -2; etc. The timings on this l2 are similar to the first l2. -- By "to do", I mean it's a factor. I don't have an explanation.... May 9, 2015 at 2:35
• @MichaelE2: I think you're on to something there (I've often wondered if for things like this, MMA does a quick sample of the data to use in deciding algo/set-up/optimizations)...
– ciao
May 9, 2015 at 6:01