Slow performance of SequenceCases

Question

While working on a solution to another question, I noticed some performance regression slow performance of SequenceCases and friends. Consider a problem of finding zeroes of a function, given a sorted table of its values:

$Version (* "13.2.0 for Mac OS X x86 (64-bit) (November 18, 2022)" *) zeros[lst_] := SequenceCases[lst, {a_, b_} /; Sign[a[[2]]] != Sign[b[[2]]]] 

For simplicity, instead of finding zeros, we find intervals containing them.

zeros[Table[{t, Sin[t]}, {t, 0, 5, 0.1}]] (* {{{0., 0.}, {0.1, 0.0998334}}, {{3.1, 0.0415807}, {3.2, -0.0583741}}} *) 

Using SequenceCases with pattern matching results in a very compact code. Unfortunately, this code has some terrible performance characteristics: e.g., asking SequenceCases to process a list of 1000 elements takes considerable time:

zeros[Table[{t, Sin[t]}, {t, 0, 100, 0.1}]] // Length // AbsoluteTiming (* {1.68121, 32} *) zeros[Table[{t, Sin[t]}, {t, 0, 200, 0.1}]] // Length // AbsoluteTiming (* {12.2768, 64} *) 

Notice that non-linear growth in the execution time: it increases by 7.3x while the input double in size.

Now compare this to a straightforward alternative using a loop, which is almost instantaneous:

fastZeros[lst_] := First[Reap[ Do[If[Sign[lst[[i, 2]]] != Sign[lst[[i + 1, 2]]], Sow[{lst[[i]], lst[[i + 1]]}]], {i, Length[lst] - 1}]][[2]], {}] With[{data = Table[{t, Sin[t]}, {t, 0, 5, 0.1}]}, fastZeros[data] == zeros[data]] (* True *) fastZeros[Table[{t, Sin[t]}, {t, 0, 200, 0.1}]] // Length // AbsoluteTiming (* {0.003667, 64} *) 

While I expect to have some speed tradeoff when using more powerful language constructs like pattern matching, it still seems like a severe performance penalty. Similar things were discussed before.

Does anyone has any more charitable explanation of the observed behavior other than "it's a bug that should be reported to Wolfram Research"?

Update. Notice, in particular, that it's not the pattern matching that is slow - it's speedy:

zeros2[lst_] := Cases[Partition[lst, 2, 1], {a_, b_} /; Sign[a[[2]]] != Sign[b[[2]]]] With[{data = Table[{t, Sin[t]}, {t, 0, 5, 0.1}]}, fastZeros[data] == zeros[data] == zeros2[data]] (* True *) zeros2[Table[{t, Sin[t]}, {t, 0, 200, 0.1}]] // Length // AbsoluteTiming (* {0.004051, 64} *) 

Update. Meanwhile, I've submitted [CASE:4999270].

Answer 1

As of 13.3.1, this particular performance issue is fixed: