Using Rules inside SequenceCases degrades Performance

Consider the following:

SequenceCases[Range[10^4], {a_?PrimeQ, b_, c_?PrimeQ}]; // AbsoluteTiming

{0.0058148, Null}

If we now try to use a rule to transform the matched cases, performance degrades considerably (about 2 orders of magnitude):

SequenceCases[Range[10^4], {a_?PrimeQ, b_, c_?PrimeQ} :> {a, c}]; // AbsoluteTiming

{0.635604, Null}

One can simply apply ReplaceAll afterwards and get much better performance:

SequenceCases[Range[10^4], {a_?PrimeQ, b_, c_?PrimeQ}] /. {a_, b_, c_} :> {a, c};
// AbsoluteTiming

{0.00655593, Null}

Why does a simple rule application cause SequenceCases to slow down considerably?

• I was going to say unpacking, but like Cases it appears as if SequenceCases always unpacks. – rcollyer Aug 4 '15 at 3:10
• Closely related: (83325) – Mr.Wizard Aug 4 '15 at 7:05

Let's start by looking at the code for SequenceCases:

<< GeneralUtilities
PrintDefinitions[SequenceCases]

We can see in this code that three different conditions determine whether the expression will be evaluated by sequenceCasesSublist or sequenceCasesPattern. Let's evaluate the two tests that matter on {a_?PrimeQ, b_, c_?PrimeQ} and {a_?PrimeQ, b_, c_?PrimeQ} :> {a, c} respectively.

{
SymbolicTensorsUtilitiesDumpVariableLengthPatternFreeQ[{a_?PrimeQ, b_, c_?PrimeQ}],
SymbolicTensorsUtilitiesDumpVariableLengthPatternFreeQ[{a_?PrimeQ, b_, c_?PrimeQ} :> {a, c}]
}

{True, True}

{
SymbolicTensorsUtilitiesDumpListRepresentationQ[{a_?PrimeQ, b_, c_?PrimeQ} :> {a, c}],
SymbolicTensorsUtilitiesDumpListRepresentationQ[{a_?PrimeQ, b_, c_?PrimeQ}]
}

{False, True}

Because they do not return the same result on this last test, they are actually handled by different functions, and it seems like sequenceCasesSublist is much faster than sequenceCasesPattern.

If we run

PrintDefinitions[SymbolicTensorsUtilitiesDumpsequenceCasesPattern]

we can see that the very first thing that sequenceCasesPattern does is to rewrite the expression in this form:

Replace[SequenceCases[Range[10^4], {a_?PrimeQ, b_, c_?PrimeQ}], {a_?PrimeQ, b_, c_?PrimeQ} :> {a, c}, 1]

which is fast like your ReplaceAll version, because it can be evaluated with sequenceCasesSublist. However, in the source code, instead of SequenceCases the function sequenceCasesPattern is used, which never runs the initial tests of SequenceCases; therefore it doesn't realize that it can choose the fast routine. That's why it's slow.

sequenceCasesPattern, I may add, is implemented with ReplaceList.

• Nice diagnosis! We're looking into it! – Stefan R Aug 4 '15 at 20:48

With Mathematica version 11.1.0 there is no slowdown anymore:

$Version SequenceCases[Range[10^6], {a_?PrimeQ, b_, c_?PrimeQ}]; // AbsoluteTiming SequenceCases[Range[10^6], {a_?PrimeQ, b_, c_?PrimeQ} :> {a, c}]; // AbsoluteTiming "11.1.0 for Microsoft Windows (64-bit) (March 13, 2017)" {1.13733, Null} {1.13629, Null} Here is output from version 11.0.1:$Version
SequenceCases[Range[10^4], {a_?PrimeQ, b_, c_?PrimeQ}]; // AbsoluteTiming
SequenceCases[Range[10^4], {a_?PrimeQ, b_, c_?PrimeQ} :> {a, c}]; // AbsoluteTiming
"11.0.1 for Microsoft Windows (64-bit) (September 20, 2016)"

{0.016909744048664993, Null}

{1.1500872252585508`, Null}

So the problem was fixed in version 11.1.0.