Oops, I screwed up the plot in google sheets. I was only plotting the regexp length values. I fixed the plot, and only plotted the y values, runtime. The x-values are linearly spaced.
There is a curve. It doesn't look linear. I think Andy is right. I did a quadratic curve fit with https://mycurvefit.com/ y = 7.763291 - 0.002980518*x + 0.000008260165*x^2 with an R^2 value 0.9998 Ray On Thu, Jun 11, 2020 at 2:18 PM Andy Balholm <andybalh...@gmail.com> wrote: > It’s more than linear. 10000 repetitions take 73 times the time of 1000 > repetitions. > > Andy > > On Jun 11, 2020, at 2:11 PM, Ray Pereda <rayper...@gmail.com> wrote: > > 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 > > > -- 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/CANZUSA%2BBhhysbOJkAyXHABd9vrYwqkdkS5JzkBw-d38RKN%2B04Q%40mail.gmail.com.
