On my laptop, I compiled Andy's code from here: https://play.golang.org/p/82UBmyfyqV- I imported the output into google sheets and plotted it with a bar chart. https://docs.google.com/spreadsheets/d/1Pp8FBfHXgdMU54v6STutzDbb7SITGscFd84sUuJQ_gk/edit#gid=0 The runtime strongly looks linear.
Still, the constant in the O(n) runtime can possibly be improved with effort profiling the code and pull requests. There many man-months in fine-tuning the regexp engines in other languages like Perl, Python, C PCRE libraries, and Java. Any recommendations for Go profilers for this work would be appreciated. Ray On Thu, Jun 11, 2020 at 1:36 PM Andy Balholm <andybalh...@gmail.com> wrote: > Here is a simpler reproducer: https://play.golang.org/p/82UBmyfyqV- > > (Running it on the playground isn’t much use because of the playground’s > fake time, though.) > > It just repeats the string “D||” (with two vertical bars) to make the > regex. The runtime is roughly quadratic in the number of repetitions. > > Andy > > On Jun 11, 2020, at 12:55 PM, Andy Balholm <andybalh...@gmail.com> wrote: > > Obviously any reasonable input validation or length limit would disallow > it. > > The time requirement is only quadratic, not exponential, so it takes > ridiculously long inputs to cause a problem. > > Andy > > On Jun 11, 2020, at 12:26 PM, Robert Engels <reng...@ix.netcom.com> wrote: > > Why would you ever allow that regex? > > On Jun 11, 2020, at 11:01 AM, Andy Balholm <andybalh...@gmail.com> wrote: > > It’s apparently quadratic in some cases. Yesterday fuzzing on > github.com/andybalholm/cascadia found an input that triggered a timeout. > The time was being spent compiling a 180-KB regex (which I’m attaching to > this message). If I concatenate two copies of this file, the combined regex > takes at least four times as long to compile. > > I plan to investigate further, and see if I can find a way to reproduce > the issue that doesn’t look like it was generated by a fuzzer. > > Andy > > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com > <https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com?utm_medium=email&utm_source=footer> > . > <regex.txt> > > > On Jun 9, 2020, at 8:42 AM, 'Thomas Bushnell, BSG' via golang-nuts < > golang-nuts@googlegroups.com> wrote: > > On Tue, Jun 9, 2020 at 11:23 AM Axel Wagner <axel.wagner...@googlemail.com> > wrote: > >> If you actually read OPs second E-Mail, they did and they didn't find it >> very clear. With that in mind, your message isn't very nice. >> (Also, not to be repetitive or anything: ~80% of the messages in this >> thread aren't actually concerned with what the complexity class *is*, but >> whether it matters) >> > > The OP stopped participating in this exciting thread a long time ago. I > went and read through the code, and it seems pretty clear to me that it's > linear. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/CA%2BYjuxvQgnTKMM4FF4%3D4pspM-2nBJScNfCNinDv-2cNA09N%3DaQ%40mail.gmail.com > <https://groups.google.com/d/msgid/golang-nuts/CA%2BYjuxvQgnTKMM4FF4%3D4pspM-2nBJScNfCNinDv-2cNA09N%3DaQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > > > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com > <https://groups.google.com/d/msgid/golang-nuts/885CBC71-3268-4BEA-983E-A67B824AC654%40gmail.com?utm_medium=email&utm_source=footer> > . > > > > -- > You received this message because you are subscribed to a topic in the > Google Groups "golang-nuts" group. > To unsubscribe from this topic, visit > https://groups.google.com/d/topic/golang-nuts/8M-qVbRKIWA/unsubscribe. > To unsubscribe from this group and all its topics, send an email to > golang-nuts+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/golang-nuts/DECADAAC-2F98-463C-9202-132D6D0F93F6%40gmail.com > <https://groups.google.com/d/msgid/golang-nuts/DECADAAC-2F98-463C-9202-132D6D0F93F6%40gmail.com?utm_medium=email&utm_source=footer> > . > -- Ray -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CANZUSAJf6%3DdfGiy6LSqTkpx3z-AKRcxEgwmfY%2Bh5EQA%3DYD1DqA%40mail.gmail.com.
