Bad performance of LengthWhile?

Question

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 1

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.

Answer 2

Your test is quite synthetic: you take only few first elements. If you you have longer sequence of positive elements then build-in LengthWhile is faster

lst = RandomInteger[{-1, 30000}, 100000];
rst1 = LengthWhile[lst, # >= 0 &]; // AbsoluteTiming
rst2 = lengthwhile[lst, # >= 0 &]; // AbsoluteTiming
rst1 == rst2
(* {0.096340, Null} *)
(* {0.166603, Null} *)
(* True *)

Update:

Amazingly, the compiled version is considerably faster then LengthWhile.

cLengthWhile = Compile[{{x, _Integer, 1}, {thr, _Integer}}, 
   Module[{i = 0, l = Length@x}, 
    While[i < l && (x[[i + 1]] >= thr), i++]; i], 
   CompilationTarget -> "C", RuntimeAttributes -> {Listable}, 
   RuntimeOptions -> "Speed"];

rst3 = cLengthWhile[lst, 0]; // AbsoluteTiming
rst1 == rst3
(* {0.000138, Null} *)
(* True *)

Update 2:

For your set of short lists there is quite fast uncompiled function

lengthwhile[x_, t_] := 
 Module[{i = 0, l = Length@x}, While[i < l && t@x[[i + 1]], i++]; i]
lengthWhile2[x_, thr_] := 
 Dimensions[x][[2]] - Total@Unitize@Accumulate[Transpose@UnitStep[x - thr] - 1]

lst = RandomInteger[{-2, 2}, {10^4, 10}];
rst1 = LengthWhile[#, # >= 0 &] & /@ lst; // AbsoluteTiming
rst2 = lengthwhile[#, # >= 0 &] & /@ lst; // AbsoluteTiming
rst3 = lengthWhile2[lst, 0]; // AbsoluteTiming
rst4 = cLengthWhile[lst, 0]; // AbsoluteTiming
rst1 == rst2 == rst3 == rst4
(* {3.990231, Null} *)
(* {0.307152, Null} *)
(* {0.004986, Null} *)
(* {0.001347, Null} *)
(* True *)