regexp compilation can be roughly 20x slower compared to gc.

[dmitshur]

This is not quite as bad a performance difference as #276, but I thought it worth bringing up and seeing if this can be improved.

I've looked at regexp and regexp/syntax packages, and it appears they use pure Go code, there is no assembly to optimize it for certain architectures.

Given the following regexp:

// ISO8601 according to the W3 group is only a subset of the ISO8601
// standard: http://www.w3.org/TR/NOTE-datetime
//
// Used in places like time.datetime
// https://developer.mozilla.org/en-US/docs/Web/HTML/Element/time#attr-datetime
//
// Matches patterns:
//  Year:
//     YYYY (eg 1997)
//  Year and month:
//     YYYY-MM (eg 1997-07)
//  Complete date:
//     YYYY-MM-DD (eg 1997-07-16)
//  Complete date plus hours and minutes:
//     YYYY-MM-DDThh:mmTZD (eg 1997-07-16T19:20+01:00)
//  Complete date plus hours, minutes and seconds:
//     YYYY-MM-DDThh:mm:ssTZD (eg 1997-07-16T19:20:30+01:00)
//  Complete date plus hours, minutes, seconds and a decimal fraction of a
//  second
//      YYYY-MM-DDThh:mm:ss.sTZD (eg 1997-07-16T19:20:30.45+01:00)
ISO8601 = regexp.MustCompile(
    `^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})` +
        `?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`,
)

It takes about 200 µs to compile it using gc compiler:

$ goexec -quiet -compiler=gc 'started := time.Now(); _ = regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`); fmt.Println(time.Since(started))'
207.928µs
$ goexec -quiet -compiler=gc 'started := time.Now(); _ = regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`); fmt.Println(time.Since(started))'
210.953µs
$ goexec -quiet -compiler=gc 'started := time.Now(); _ = regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`); fmt.Println(time.Since(started))'
224.785µs

But it's closer to 20 ms to compile the same regexp using gopherjs compiler:

$ goexec -quiet -compiler=gopherjs 'started := time.Now(); _ = regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`); fmt.Println(time.Since(started))'
20ms
$ goexec -quiet -compiler=gopherjs 'started := time.Now(); _ = regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`); fmt.Println(time.Since(started))'
17ms
$ goexec -quiet -compiler=gopherjs 'started := time.Now(); _ = regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`); fmt.Println(time.Since(started))'
19ms

I really don't like regexpes and wish they didn't exist, but unfortunately some Go packages use them (for example, github.com/microcosm-cc/bluemonday, /cc @buro9) quite significantly even at package level, meaning any Go package that imports bluemonday will take an additional 200 ms~ just to initialize (imagine 10 regexpes compiled at package level, if each one takes 20 ms, that's 200 ms).

Since regexp package is pure Go, hopefully general performance improvements can translate to better results here.

/cc @neelance @slimsag

[nevkontakte]

I wrote a quick and dirty benchmark to confirm whether this is still the case:

package main

import (
        "regexp"
        "runtime"
        "testing"
)

var sideEffect interface{}

func BenchmarkCompile(b *testing.B) {
        for i := 0; i < b.N; i++ {
                re := regexp.MustCompile(`^[0-9]{4}(-[0-9]{2}(-[0-9]{2}([ T][0-9]{2}(:[0-9]{2}){1,2}(.[0-9]{1,6})` +
                        `?Z?([\+-][0-9]{2}:[0-9]{2})?)?)?)?$`)
                runtime.KeepAlive(re)
        }
}

...and the difference appears to still be about an order of magnitude:

 $ gopherjs test --bench=. --benchtime=30s
goos: linux
goarch: js
BenchmarkCompile          106006            327538 ns/op

$ go test -bench=. -benchtime=30s
goos: linux
goarch: amd64
pkg: repro/016-regexp-compile-perf
cpu: Intel(R) Core(TM) i5-10600KF CPU @ 4.10GHz
BenchmarkCompile-12      2120029             16992 ns/op

I'm not perfectly sure that Go compiler didn't sneak in some uninvited optimization, but generally I can believe this result.

I've looked at a couple of profiles and it seems like a lot of time is spent cloning objects and appending to slices.