13
$\begingroup$

I knew that Module is slower than With or Block, often by several times. But it surprises me that Module can slow down StringMatchQ by 180 times.

Starting with a fresh kernel, define the test functions (This test function comes from some complicated functions. I reduce the original one preserving the slow-down feature and find this least example.)

fModule[string_String] :=
    Module[ {str2},
        str2="x";
        StringMatchQ[string, 
            str1___/;str1==str2
        ]
    ];
fWith[string_String] :=
    With[ {str2="x"},
        StringMatchQ[string, 
            str1___/;str1==str2
        ]
    ];
fBlock[string_String] :=
    Block[ {str2},
        str2="x";
        StringMatchQ[string, 
            str1___/;str1==str2
        ]
    ];
fBare[string_String]:=
    StringMatchQ[string,
        str1___/;str1=="x"
    ];

then

fModule["x"]//RepeatedTiming
fWith["x"]//RepeatedTiming
fBlock["x"]//RepeatedTiming
fBare["x"]//RepeatedTiming

fModule["xa"]//AbsoluteTiming
fWith["xa"]//AbsoluteTiming
fBlock["xa"]//AbsoluteTiming
fBare["xa"]//AbsoluteTiming

gives enter image description here

How to understand this? Does this occur only for StringMatchQ, or for string manipulations, or even for some larger class of functions?


For convenience,

compare[f_,timing_] :=
    (
        fModule//Clear;
        fBare//Clear;
        fModule[string_String] :=
            Module[ {str2},
                str2 = "x";
                f[string, 
                    str1___/;str1==str2
                ]
            ];
        fBare[string_String] :=
            f[string,
                str1___/;str1=="x"
            ];
        fModule["x"]//timing//Sow;
        fBare["x"]//timing//Sow;
    )//Reap//Part[#,2,1]&//Replace[{list1_,list2_}:>{list1,list2,list1[[1]]/list2[[1]]}]

enter image description here

The AbsoluteTiming without Module is not accurate, but still shows the features.


As suggested by @rnotlnglgq, we modify the condition with a decorator, then this magic slow-down disappears!

compare[f_,timing_,decorator_] :=
    (
        fModule//Clear;
        fBare//Clear;
        fModule[string_String] :=
            Module[ {str2 = "x"},
                f[string, 
                    str1___/;decorator[str1==str2]
                ]
            ];
        fBare[string_String] :=
            f[string,
                str1___/;str1=="x"
            ];
        fModule["x"]//timing//Sow;
        fBare["x"]//timing//Sow;
    )//Reap//Part[#,2,1]&//Replace[{list1_,list2_}:>{list1,list2,list1[[1]]/list2[[1]]}]

enter image description here

$\endgroup$
6
  • 3
    $\begingroup$ I think the reason is that Module allocates memory each time it is called. $\endgroup$ Feb 15, 2023 at 15:19
  • $\begingroup$ @DanielHuber The AbsoluteTiming is also much slower. I hopefully expect this slow-down is rare and only for some special functions, since Module has not been deprecated during this thirty years. $\endgroup$
    – Lacia
    Feb 15, 2023 at 15:26
  • $\begingroup$ I think @DanielHuber is correct fBlock3[string_String] := Block[ {str2}, StringMatchQ[string, str1___/;str1=="x" ] ]; is not significantly slower. The slow down is on str2="x". $\endgroup$
    – rhermans
    Feb 15, 2023 at 15:41
  • $\begingroup$ Hi guys, I test more examples with AbsoluteTiming and RepeatedTiming. $\endgroup$
    – Lacia
    Feb 15, 2023 at 15:44
  • 1
    $\begingroup$ A minimal example for this magic: Do[Module[{sym}, StringMatchQ[_/;(sym;True)]@"x"],1*^4] //AbsoluteTiming. It will be much faster if you add a Evaluate in the Condition. $\endgroup$
    – rnotlnglgq
    Feb 15, 2023 at 16:15

3 Answers 3

10
$\begingroup$

I think this the discrepancy is caused by some type of caching of the string pattern. And since Module is the only version that causes the string pattern to change each time (since the variable name is localized to a different one each time), it's the only one not benefitting from this caching.

Some tests showing that this is likely what's happening:

  • On a fresh kernel:

    Table[AbsoluteTiming@StringMatchQ["x", str1___ /; str1 == "x"], 10]
    (* {{0.0006325, True}, {5.8*10^-6, True}, {2.4*10^-6, 
      True}, {2.4*10^-6, True}, {2.6*10^-6, True}, {2.2*10^-6, 
      True}, {2.4*10^-6, True}, {2.3*10^-6, True}, {2.5*10^-6, 
      True}, {2.5*10^-6, True}} *)
    

    As you can see, the first run is ~100x slower than the following ones. (there is still some warm-up on subsequent runs of the line above, but not nearly as severe)

  • Adding a fDelayedModule variant that "removes" Module from the timing, and only keeps the localized variables:

    fModule[string_String] := Module[{str2}, str2 = "x";
       StringMatchQ[string, str1___ /; str1 == str2]];
    fWith[string_String] := 
      With[{str2 = "x"}, StringMatchQ[string, str1___ /; str1 == str2]];
    fBlock[string_String] := Block[{str2}, str2 = "x";
       StringMatchQ[string, str1___ /; str1 == str2]];
    fBare[string_String] := StringMatchQ[string, str1___ /; str1 == "x"];
    fDelayedModule[string_String] := Module[{str2}, str2 = "x";
       Hold[StringMatchQ[string, str1___ /; str1 == str2]]];
    
    Table[fModule["x"], 1000] // AbsoluteTiming // First
    With[{t = Table[fDelayedModule["x"], 1000]},
      t // ReleaseHold // AbsoluteTiming // First]
    Table[fWith["x"], 1000] // AbsoluteTiming // First
    Table[fBlock["x"], 1000] // AbsoluteTiming // First
    Table[fBare["x"], 1000] // AbsoluteTiming // First
    (* 0.35875 *)
    (* 0.322435 *)
    (* 0.0037334 *)
    (* 0.0030231 *)
    (* 0.0043415 *)
    

    As you can see, most of the slowdown is present even if we run the Module outside of the timed part, and simply return the expression to be run as Hold[StringMatchQ[...]]

  • Running the test against 1000 unique characters in place of "x":

    (
         fModule[string_String] := Module[{str2}, str2 = #;
           StringMatchQ[string, str1___ /; str1 == str2]];
         fModule[#]
         ) & /@ FromCharacterCode /@ Range@1000 // AbsoluteTiming // First
    (* 0.391135 *)
    
    (
         fBare[string_String] :=
          StringMatchQ[string, str1___ /; str1 == #];
         fBare[#]
         ) & /@ FromCharacterCode /@ Range@1000 // AbsoluteTiming // First
    (* 0.344281 *)
    

    As you can see, the bare version has almost no speed advantage over Module when encountering the pattern for the first time.

  • Adding ClearSystemCache[] before the calls:

    Table[ClearSystemCache[]; fModule["x"], 1000] // AbsoluteTiming // First
    Table[ClearSystemCache[]; fBare["x"], 1000] // AbsoluteTiming // First
    (* 0.498588 *)
    (* 0.506117 *)
    

    Again, both versions are now equally fast.

$\endgroup$
3
  • $\begingroup$ Convicing. The ClearSystemCache[] test is determinate. $\endgroup$
    – rnotlnglgq
    Feb 16, 2023 at 18:50
  • $\begingroup$ It seems not configurable, as I don't see something like "StringPatternCache" in SystemOptions[]. And it depends neither on "Numeric" nor "Symbolic" cache option. $\endgroup$
    – rnotlnglgq
    Feb 16, 2023 at 19:00
  • 1
    $\begingroup$ There is this StringPattern`SetStringPatternCache though I don't know what is it. $\endgroup$
    – Silvia
    Feb 21, 2023 at 6:53
6
$\begingroup$

A smaller example for reduplicating it:

Do[Module[{sym},
    StringMatchQ[___/;(sym;True)]@""
],1*^4] //AbsoluteTiming //First

I got 2.15651 on my machine, while the following edition with an extra Evaluate

Do[Module[{sym},
    StringMatchQ[___/;Evaluate[sym;True]]@""
],1*^4] //AbsoluteTiming //First

gives 0.030968 (70x faster).

And this seems a unique behavior for string pattern matching, expression matching(including sequence matching) doesn't have this problem. And no matter if the basic pattern is Blank or BlankSequence.

Not only Evaluate, the slowing behavior can be eliminated by this:

Union@Table[Module[{sym="x"},
    StringMatchQ[_/;(ToExpression["sym$"<>ToString@--$ModuleNumber]=="x")]@"x"
],1*^4] //AbsoluteTiming
(* {0.077667, {True}} *)

The ToExpression breaks the lexicon scoping, but has reserved many other missions(create symbols, assignment, symbol reference, etc.)

Still confusing.

$\endgroup$
1
  • $\begingroup$ Thanks for this magic to bypass this problem! $\endgroup$
    – Lacia
    Feb 15, 2023 at 16:43
6
$\begingroup$

I did some tests to see the difference between Module and Block because I usually use Module and it would scare me if it is really so slow in general.

Lets start with a very simple code that more or less only check the setup:

f1 := Module[{a}, a = 2];
f2 := Block[{a}, a = 2];

Do[f1, 10^6] // RepeatedTiming
Do[f2, 10^6] // RepeatedTiming

{1.19221, Null}
{0.304252, Null}

No much difference here. Now with a bit more calculations:

f1 := Module[{a, b}, a = Sqrt[2.]; b = a; b^2];
f2 := Block[{a, b}, a = Sqrt[2.]; b = a; b^2];

Do[f1, 10^6] // RepeatedTiming
Do[f2, 10^6] // RepeatedTiming

{3.13645, Null}}
{1.09971, Null}

This shows also no difference. Next let us check with StringMatchQ to see if this is the culprit:

f1 := Module[{a = "one", b = "one"}, StringMatchQ[a, b]];
f2 := Block[{a = "one", b = "one"}, StringMatchQ[a, b]];

Do[f1, 10^6] // RepeatedTiming
Do[f2, 10^6] // RepeatedTiming

{2.04834, Null}
{0.641031, Null}

Next we can add a condition:

f1 := Module[{a = "one", b = "one"}, 
   StringMatchQ[a, b] /; a == "one"];
f2 := Block[{a = "one", b = "one"}, StringMatchQ[a, b] /; a == "one"];

Do[f1, 10^6] // RepeatedTiming
Do[f2, 10^6] // RepeatedTiming

{3.05893, Null}
{1.03161, Null}

Therefore it looks like Module is in general about 3 time slower than Block.

$\endgroup$
1
  • $\begingroup$ I have already been scared XD, since most of my functions use Module to avoid the extra features of With and Block. I hope this only occurs for string manipulation functions. $\endgroup$
    – Lacia
    Feb 15, 2023 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.