The Graph is clearly not linear. Another way to see this is to print out the ratio of time taken and i. If the cost is linear, you'd expect that ratio to be constant. When I run this code https://play.golang.org/p/v1JVQkOXnEH on my machine I get
1000 6.821361ms 6821.361 2000 27.229439ms 13614.7195 3000 65.352307ms 21784.102333333332 4000 118.262424ms 29565.606 5000 184.231412ms 36846.2824 6000 265.085287ms 44180.881166666666 7000 341.980378ms 48854.339714285714 8000 468.367349ms 58545.918625 9000 566.985419ms 62998.37988888889 10000 715.327926ms 71532.7926 11000 863.203647ms 78473.05881818182 12000 1.046590109s 87215.84241666667 13000 1.208058338s 92927.56446153847 14000 1.367802614s 97700.18671428571 15000 1.599170348s 106611.35653333334 16000 1.856199076s 116012.44225 17000 2.035878934s 119757.58435294118 18000 2.29658726s 127588.18111111112 19000 2.57228423s 135383.3805263158 You can see the ratio increasing by ~7K on each increment (though there's of course noise). This means the graph is pretty clearly quadratic. On Thu, Jun 11, 2020 at 11: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 > > > -- 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/CAEkBMfGV%3D4DuYuSb6yj3pxE8uLRxU9Yf2mbJ1TeKhyO2%3DJJwQg%40mail.gmail.com.
