list manipulation - Bad performance of LengthWhile?

The performance of LengthWhile has been improved in v11.1, now the lengthwhile below is no longer faster.

---

A friend of mine showed me this example, it's a test comparing LengthWhile to a self-made lengthwhile written in a direct and conventional way:

lengthwhile[x_, t_] := Module[{i = 0, l = Length@x}, While[i < l && t@x[[i + 1]], i++]; i]

lst = RandomInteger[{-2, 2}, {10^4, 10}];
rst1 = LengthWhile[#, # >= 0 &] & /@ lst; // AbsoluteTiming

rst2 = lengthwhile[#, # >= 0 &] & /@ lst; // AbsoluteTiming
rst1 == rst2

{3.941000, Null}
{0.474000, Null}
True

LengthWhile is much slower than the reinvented wheel! Why? Simply a bad performance of LengthWhile? Or LengthWhile isn't used in a proper way?

Answer

There are several reasons. Firstly the built-in function has some minor overhead to check the arguments and call the appropriate internal function depending on whether the first argument is a list, a sparse array or an association.

Secondly, with a packed array, LengthWhile uses compilation in an attempt to increase performance. There is some overhead in evaluating Compile, which is especially noticeable for your example with many small lists. (Note that if you do lst2 = Developer`FromPackedArray[lst] the built-in LengthWhile is faster than it is on the packed list.)

Finally, there appears to be a bug in the implementation of the compilation, such that the compiled function calls back to the main evaluator for the predicate function. You can see this by capturing the CompiledFunction from a Trace and examining it with CompilePrint:

Needs["CompiledFunctionTools`"];

CompilePrint @@ Cases[Trace[LengthWhile[lst[[1]], # >= 0 &]], _CompiledFunction, -1, 1]

blah...
7 B2 = MainEvaluate[ Hold[Statistics`TakeWhileDump`predfun$42706][I5]]

blah...

The internal function calling Compile is Statistics`TakeWhileDump`findLastPosition. It appears that the predicate function is not being inlined as we would desire (despite "InlineExternalDefinitions" being used). I'm not sure what the rules are about inlining external definitions, so I'm not sure if this is due to a change in Compile or bad code in Statistics`TakeWhileDump`findLastPosition.