What's going on with performance of Tally here?

Question

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...

Answer 1

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

Answer 2

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.)