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- <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 > > <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 > <mailto:andybalh...@gmail.com>> wrote: > Here is a simpler reproducer: https://play.golang.org/p/82UBmyfyqV- > <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 >> <mailto: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 >>> <mailto: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 >>>> <mailto:andybalh...@gmail.com>> wrote: >>>> >>>> It’s apparently quadratic in some cases. Yesterday fuzzing on >>>> github.com/andybalholm/cascadia <http://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 >>>> <mailto: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 <mailto:golang-nuts@googlegroups.com>> >>>>> wrote: >>>>> >>>>> On Tue, Jun 9, 2020 at 11:23 AM Axel Wagner >>>>> <axel.wagner...@googlemail.com <mailto: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 >>>>> <mailto: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 >>>> <mailto: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 > <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 > <mailto: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/F80359A1-AE2E-4723-AEFA-1CDE82C9D8E0%40gmail.com.
