Understanding Regex Performance

Question

When working on a recent project, I discovered a massive performance difference between these two regex queries that I believe are logically equivalent.

stack.match(/.*\n([A-Z][A-Za-z$]+)@/)
stack.split("\n")[1].match(/^([A-Z][A-Za-z$]+)@/)

let stack = `Error
    at File (http://localhost:10400/foo/bar/Combo?WZC6ZC&1ECYELF&12FP1RC&17F9LE8&P29J1Z&19IF3L2&AS09Z5&DHIG3C&EZJOER&13HZV70&1Y0F1JC&7UNIX3&SXHPTZ&K2YF13&11KMHHF&ZT36EV&Z44N8N&1QZW1DM&O16D0M&CW2QNS&1FH6TF2&ZWDLTF&1X87ICA&6LRWIZ&ME66AT&1SR9GT&1YH9ZQP&HHC8F2&1DB0VYO&FKOBET&1MJ8I38&JLAULY&1CH0G0Z&1TVRXYJ&SPNXDO&1JYOJGK&1LO9VOK&11TND7U&1YWNKYV&1DXWRM&TK6KOI&154ANPU&RWT5PA&19HGOKC&1YUJVCR&VFG0H0&172UQH&WFFZOK&1G8KK9P&Z4U2ZW&9UOM25&CBEUA3&1BURRUK&34VP40&CT8SCX&C5EGO8&XBSA9O&LL4E3N&1G5530W&R7QR2I&11ZITTG&1OIUGH1&ZN50OK&19R3ZDC&68ZZJF&413IE5&P0AYR7&1SMIEQU&1I34GN7&1GCT1EE&165FEOI&1NN6TMC&1FGT66H&1CP9Y2C&1R3WFPP&16Z97O3&1HGGWC2&AL9WFH&JXOSA2&QUXERX&NU7E4G&3HPVD3&16NVKFB&1JO5LOD&PIJWGC&1HD0KL3&A5KQ0E&UVG8ZT&156786I&1EGYRX&931PJP&71A44J&K4T5RR&YJS0J6&6NKXDV&15LGDNT&DK4XFH:6963:17)
    at File (http://localhost:10400/foo/bar/Combo?WZC6ZC&1ECYELF&12FP1RC&17F9LE8&P29J1Z&19IF3L2&AS09Z5&DHIG3C&EZJOER&13HZV70&1Y0F1JC&7UNIX3&SXHPTZ&K2YF13&11KMHHF&ZT36EV&Z44N8N&1QZW1DM&O16D0M&CW2QNS&1FH6TF2&ZWDLTF&1X87ICA&6LRWIZ&ME66AT&1SR9GT&1YH9ZQP&HHC8F2&1DB0VYO&FKOBET&1MJ8I38&JLAULY&1CH0G0Z&1TVRXYJ&SPNXDO&1JYOJGK&1LO9VOK&11TND7U&1YWNKYV&1DXWRM&TK6KOI&154ANPU&RWT5PA&19HGOKC&1YUJVCR&VFG0H0&172UQH&WFFZOK&1G8KK9P&Z4U2ZW&9UOM25&CBEUA3&1BURRUK&34VP40&CT8SCX&C5EGO8&XBSA9O&LL4E3N&1G5530W&R7QR2I&11ZITTG&1OIUGH1&ZN50OK&19R3ZDC&68ZZJF&413IE5&P0AYR7&1SMIEQU&1I34GN7&1GCT1EE&165FEOI&1NN6TMC&1FGT66H&1CP9Y2C&1R3WFPP&16Z97O3&1HGGWC2&AL9WFH&JXOSA2&QUXERX&NU7E4G&3HPVD3&16NVKFB&1JO5LOD&PIJWGC&1HD0KL3&A5KQ0E&UVG8ZT&156786I&1EGYRX&931PJP&71A44J&K4T5RR&YJS0J6&6NKXDV&15LGDNT&DK4XFH:13679:15)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:78801:18)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:80490:19)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:81500:13)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:85175:11)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:85215:22)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:85298:5)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:86205:5)
    at File (http://localhost:10400/foo/bar/Combo?1J6XZOQ&CV1G7Q&178CDN5&8GO7HW&1NEWTVK&11D8SWR&EUW1RW&B0SNY0&UKYKU8&Z2LJ32&OMFXIN&1CKRK5M&1DCE7I2&BTKQMZ&BF6IS9&IGMBPD&17GLBW0&F1NR3R&1BYJ6GK&1QMDI0S&1YBURTD&N3FA6J&1OKN2Q4&1VX6R8D&1RN5YOY&1PGEWZS&186NYSC&6OOHB&DAQXGM&18F8OG0&IEBF22&16BSJS0&270VGN&220EF0&PP2DW2&EXOH0W&1UI8QOX&BESS5A&SYNC6D&3EWNSZ&TX0EOZ&YHES22&SS37DN&155I4KT&SBSDY7&G2CFJM&1L12OEG&189382Y&4IWM93&RVOAXW&NMAEHJ&A3HW6D&react_v16.8.4&react-dom_v16.8.4&1I1OITG&1ZY465&1R86UXI&WLU3QX&1OO689&1N913EH&RZP360&15WCYOM&17TCHPC&115R68D&1VRCLJ7&12F8G3T&QXNNQC&128FRJB&1OH35FB&CHPVZ7&15VJLWF&DXTQHG&TI7NW9&8F7DFB&3ER51Q&1DTSSTA&1PQZ3V&1CA54WE&1GEM33A&OC7AMR&3AYWID&1KYS5DS&O76Y7S&1CD2C6F&1SB1JQ0&1DMMKMS&OCFDX4&1MO3710&1GVEDEZ&1FT6HVF&4JF9F9&1F8VFMW&1GAQQYW&149YUOT&12GEY49&4MFMGQ&16N8W14&12SV68C&2F7EYB&23HVSL&4TAXU8&1YL1F3&14H19K&1WHTWL7&1PYNLWK&1RUO08N&1PLVRSS&126YWXW&1TAPDE6&18TCRAP:86117:5)`;


var elapsedMethod1 = 0;
start = new Date()
for (var i = 0; i < 1000; i++) {
    stack.match(/.*\n([A-Z][A-Za-z$]+)@/)
}
elapsedMethod1 = new Date() - start;

var elapsedMethod2 = 0;
start = new Date()
for (var i = 0; i < 1000; i++) {
    stack.split("\n")[1].match(/^([A-Z][A-Za-z$]+)@/)
}
elapsedMethod2 = new Date() - start;

console.log(`1000 runs of method 1 ${elapsedMethod1}`)
console.log(`1000 runs of method 2 ${elapsedMethod2}`)

Running this script, I got the following results:

>> 1000 runs of method 1 5034
>> 1000 runs of method 2 3

I have two questions about this result.

First, are these regex queries truly equivalent, or am I missing an important detail?
Second, if these regex queries are truly equivalent, why is one over 1000 times faster?

They would find the same things but that doesn't mean they work the same. It's MUCH easier to check if your string starts with an alphanumeric and discard at that point, than search potentially the entire string if it contains something. At the very least the second regex has way less to check - the first one would scan the entire scan tract if any part of it matches, the latter will only check about 1/10th of it. — VLAZ
– VLAZ, Commented Jul 30, 2020 at 13:50

rootkonda · Accepted Answer · 2020-07-30 15:06:12Z

1

/.*\n([A-Z][A-Za-z$]+)@/
/^([A-Z][A-Za-z$]+)@/

Whenever we use .* it first matches the entire string and then it backtracks step by step to match rest of the regular expression. Morever . is a wildcard so it considers any character. Compared to the second one, here we are not using ^ to check only the beginnings of line. These two options makes a big difference and hence the second one is faster.

answered Jul 30, 2020 at 15:06

rootkonda

1,7831 gold badge8 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Chris Over a year ago

I did not know about the backtracking. That makes a lot of sense! I assumed that the match() function would scan until it sees a newline (which would happen almost immediately), and then it would continue matching the rest of the query. But I guess it's dangerous to assume how a black box function works.

Collectives™ on Stack Overflow

Understanding Regex Performance

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related