Mathematica "linked lists" and performance -

in mathematica, create singly linked lists so:

tolinkedlist[x_list] := fold[pair[#2, #1] &, pair[], reverse[x]];  fromlinkedlist[ll_pair] := list @@ flatten[ll];  emptyq[pair[]] := true; emptyq[_pair] := false;     

using symbol pair cons cells has advantage of flatten working safely if lists contain mathematica-style lists, , allows define custom notation using makeexpression/makeboxes, makes more pleasant. in order avoid having muck around $iterationlimit, wrote functions work these lists using either while loops or nestwhile instead of using recursion. naturally, wanted see approach faster, wrote 2 candidates watch 'em fight:

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]; 

the results strange. tested functions on linked lists of length 10000, , whilelength 50% faster, @ 0.035 seconds nestlength's 0.055 seconds. however, whilelength take ~4 seconds. thought there might caching behavior, started generating fresh, random lists check, , whilelength wouldn't slow on first run new list; might take dozens of times see slowdown, wouldn't recur (at least not 200 runs trying each list).

what might going on?

for reference, function used testing this:

gettimes[f_, n_] :=  with[{ll = tolinkedlist@randominteger[100, 10000]},   table[timing[f@ll], {n}][[all, 1]]] 

edit: neglected mention version earlier; got these results mathematica 8.

edit second: when read daniel lichtblau's answer, realized times "typical" runs omitted leading 0. it's been fixed.

edit third: think leonid shifrin correct associate issue module; can same sort of behavior nestwhile-based version replacing with module:

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} 

the examples below give typical results.

one slow example in length 20 run.

in[18]:= gettimes[whilelength, 20]  out[18]= {0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, \ 0.031, 0.047, 0.032, 0.031, 0.031, 3.547, 0.047, 0.031, 0.031, 0.032, \ 0.031, 0.031} 

i note in passing timings ~10x faster in original post, except slow cases comparable. not sure accounts difference in ratios.

no slow examples.

in[17]:= gettimes[nestlength, 20]  out[17]= {0.047, 0.047, 0.062, 0.047, 0.047, 0.062, 0.047, 0.047, \ 0.047, 0.063, 0.046, 0.047, 0.047, 0.063, 0.047, 0.046, 0.047, 0.063, \ 0.047, 0.047} 

one slow example in length 100 run.

in[19]:= gettimes[whilelength, 100]  out[19]= {0.031, 0.031, 0.031, 0.032, 0.031, 3.594, 0.047, 0.031, \ 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, \ 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.047, 0.031, 0.031, \ 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, \ 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, \ 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.031, \ 0.032, 0.031, 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.032, \ 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.031, 0.032, 0.046, 0.032, \ 0.031, 0.031, 0.031, 0.032, 0.031, 0.031, 0.047, 0.031, 0.032, 0.031, \ 0.031, 0.031, 0.032, 0.031, 0.047, 0.031, 0.031, 0.031, 0.032, 0.031, \ 0.031, 0.031} 

mathematica implements, imperfectly, called "infinite evaluation". say, expression reevaluates until stops changing. make reasonably fast there various optimizations attempt short circuit process whenever possible.

in cases can tricky discern (due effect similar hash collisions), , expressions might needlessly reevaluated. nested expressions tend worst case this. have further code address these in cases of collisions.

the culprit in instance code attempts determine whether expression requires reevaluation. peculiar possibly clue (to someone) happens @ once in run inside while loop. happens in bad cases prevents recurrence whilst inside same while.

at 1 time familiar reevaluation detection code, having written chunk of it. rewritten version 8. after seeing suboptimal behavior in debugger, is of mystery me. can right filed bug report.

as leonid shifrin observed, symbols attribute of holdallcomplete immune problem. using attribute can beneficial type of code.

daniel lichtblau wolfram research