«Связанные списки» и производительность Mathematica

В системе Mathematica я создаю односвязные списки следующим образом:

toLinkedList[x_List] := Fold[pair[#2, #1] &, pair[], Reverse[x]];

fromLinkedList[ll_pair] := List @@ Flatten[ll];

emptyQ[pair[]] := True;
emptyQ[_pair] := False;    

Использование пары символов для cons-ячеек дает преимущество Flatten , работающее безопасно, даже если Списки содержат List в стиле Mathematica и позволяют определять пользовательскую нотацию с помощью MakeExpression / MakeBoxes , что делает все намного более приятным. Чтобы не возиться с $ IterationLimit , я написал функции для работы с этими списками, используя либо циклы While , либо NestWhile вместо использования рекурсии. Естественно, я хотел посмотреть, какой подход будет быстрее, поэтому я написал двух кандидатов, чтобы посмотреть, как они сражаются:

nestLength[ll_pair] := 
 With[{step = {#[[1, -1]], #[[-1]] + 1} &},
  Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];

whileLength[ll_pair] := 
 Module[{result = 0, current = ll},
  While[! emptyQ@current,
   current = current[[2]];
   ++result];
  result];

Результаты были очень странными. Я тестировал функции на связанных списках длиной 10000, и whileLength обычно был примерно на 50% быстрее, примерно на 0,035 секунды против 0,055 секунды nestLength . Однако иногда whileLength занимает около 4 секунд. Я подумал, что может быть какое-то кеширование, поэтому я начал генерировать свежие случайные списки для проверки, и whileLength не обязательно будет медленным при первом запуске с новым списком; может потребоваться несколько десятков раз, чтобы увидеть замедление, но тогда оно не повторится (по крайней мере, не для 200 запусков, которые я пробовал с каждым списком).

Что может происходить?

Для справки, я использовал следующую функцию для тестирования:

getTimes[f_, n_] :=
 With[{ll = toLinkedList@RandomInteger[100, 10000]},
  Table[Timing[f@ll], {n}][[All, 1]]]

РЕДАКТИРОВАТЬ: Я забыл упомянуть версию ранее; Я получил эти результаты с помощью Mathematica 8.

ИЗМЕНИТЬ второй: Когда я прочитал Daniel Lichtblau ' s answer , я понял, что мои времена для "типичных" прогонов опускали начальный 0. Это было исправлено.

ИЗМЕНИТЬ третий: Я думаю, что Леонид Шифрин правильно связывает проблему с модулем ; Я могу получить такое же поведение в версии на основе NestWhile , заменив на на модуль :

nestModuleLength[ll_pair] := 
  Module[{step = {#[[1, -1]], #[[-1]] + 1} &}, 
   Last@NestWhile[step, {ll, 0}, ! emptyQ@First@# &]];

In[15]:= Select[getTimes[nestModuleLength, 100], # > 3 &]
Out[15]= {3.797}