I’ve filed an issue: https://github.com/golang/go/issues/39542
> On Jun 11, 2020, at 6:08 PM, Ray Pereda <rayper...@gmail.com> wrote: > > > I think that regexp/syntax.patchlist.append refers to line 42 here > https://golang.org/src/regexp/syntax/compile.go > <https://golang.org/src/regexp/syntax/compile.go> > > Using a singly linked list with a pointer to the tail pointer would give > constant time append > > Ray > > On Thu, Jun 11, 2020 at 5:40 PM Andy Balholm <andybalh...@gmail.com > <mailto:andybalh...@gmail.com>> wrote: > Right. That’s why I left the double bar in my example. > > Basically all the time is spent appending to a linked list in > regexp/syntax.patchlist.append. Which makes sense, because appending to a > linked list when you only have a head pointer is O(n) in the length of the > list. So building the whole list that way is O(n^2). > > Andy > >> On Jun 11, 2020, at 4:47 PM, Kurtis Rader <kra...@skepticism.us >> <mailto:kra...@skepticism.us>> wrote: >> >> On Thu, Jun 11, 2020 at 2:57 PM 'Axel Wagner' via golang-nuts >> <golang-nuts@googlegroups.com <mailto:golang-nuts@googlegroups.com>> wrote: >> 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 >> <https://play.golang.org/p/v1JVQkOXnEH> on my machine I get... >> >> The poor scalability of the example provided by Andy is due to the empty >> alternation. Using "D|" repeated as many times as you desire results in >> linear time and a constant number of memory allocations to compile the >> sequence. Changing the segment to "D||" causes two allocations for every >> "||" instance. While "D||D" is legal it's also somewhat silly since it >> matches anything. Inserting a repetition between the two "|" (e.g., >> "D|d*|"), or a fixed length expression that is a different length (e.g., >> "D|xy|") results in the same behavior. Putting a fixed length expression >> between the two "|" that is the same length as the expression on the other >> side results in linear time even if the expression is a char class; e.g., >> "D|[xy]|". This doesn't surprise me given the research papers linked to >> earlier in this thread. Whether the pathological alternation case can be >> optimized to reduce the number of allocations is an open question. >> >> -- >> Kurtis Rader >> Caretaker of the exceptional canines Junior and Hank >> >> -- >> 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/CABx2%3DD-ciPs%3DRa9GAO9SqXqFM_AFRV6TR6h3n3g-_DSpnzu%3DBg%40mail.gmail.com >> >> <https://groups.google.com/d/msgid/golang-nuts/CABx2%3DD-ciPs%3DRa9GAO9SqXqFM_AFRV6TR6h3n3g-_DSpnzu%3DBg%40mail.gmail.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/C52F7F0C-1DCA-44B6-ACE8-2F96066D62CD%40gmail.com > > <https://groups.google.com/d/msgid/golang-nuts/C52F7F0C-1DCA-44B6-ACE8-2F96066D62CD%40gmail.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/61DDC42C-71A4-4BA4-A9CF-EEF2FCC9EE25%40gmail.com.
