C++ to Go Port of Google/re2
Budget: $750 – $1,500 USD
I'm looking for an experienced software engineer to port the C++ project google/re2 to pure Go.
The original repo is here:
https://github.com/google/re2
The main motivation for this transition is to enhance ease of maintenance because we are now using a cgo library:
https://github.com/wasilibs/go-re2
This can be integrate using cgo or wasm - but both are not pure Go implementations.
Key Responsibilities:
- Port the C++ google/re2 project to Go with exact feature parity.
- Utilize the existing google/re2 tests for validation of the Go implementation.
- The port has to be performant. The current regex implementation in Go is written by the same author as google/re2 but appears to use only NFA (non-deterministic finite automata) while google/re2 also uses DFA (deterministic finite automata):
https://news.ycombinator.com/item?id=18554693
The DFA does not always work well - but when it works it's extremely fast and google/re2 switches the two implementations as needed.
There is a discussion in the golang repo:
https://github.com/golang/go/issues/11646
Attempts to include DFA were made but apparently nobody succeeded yet.
It would make sense to explore a fork of Go's existing regexp code and add DFA (while keeping the NFA implementation) - or whether Russ Cox (the author of both google/re2 and golang/regexp) used shortcuts even for the NFA implementation which makes it slower.
Performance of a Go implementation should be similar to the cgo version based on wafbench as described in:
https://github.com/wasilibs/go-re2
Skills and Experience Required:
- Proficiency in C++ and Go is essential.
- Prior experience with the google/re2 project might be useful.
The original repo is here:
https://github.com/google/re2
The main motivation for this transition is to enhance ease of maintenance because we are now using a cgo library:
https://github.com/wasilibs/go-re2
This can be integrate using cgo or wasm - but both are not pure Go implementations.
Key Responsibilities:
- Port the C++ google/re2 project to Go with exact feature parity.
- Utilize the existing google/re2 tests for validation of the Go implementation.
- The port has to be performant. The current regex implementation in Go is written by the same author as google/re2 but appears to use only NFA (non-deterministic finite automata) while google/re2 also uses DFA (deterministic finite automata):
https://news.ycombinator.com/item?id=18554693
The DFA does not always work well - but when it works it's extremely fast and google/re2 switches the two implementations as needed.
There is a discussion in the golang repo:
https://github.com/golang/go/issues/11646
Attempts to include DFA were made but apparently nobody succeeded yet.
It would make sense to explore a fork of Go's existing regexp code and add DFA (while keeping the NFA implementation) - or whether Russ Cox (the author of both google/re2 and golang/regexp) used shortcuts even for the NFA implementation which makes it slower.
Performance of a Go implementation should be similar to the cgo version based on wafbench as described in:
https://github.com/wasilibs/go-re2
Skills and Experience Required:
- Proficiency in C++ and Go is essential.
- Prior experience with the google/re2 project might be useful.