Maybe this is better suited for an external package rather than in standard library ? Please see https://golang.org/doc/faq#x_in_std

Possibly, but qsufsort.go is already in the library, and forking it just to export one symbol doesn't feel right somehow.

Patch here: https://go-review.googlesource.com/c/go/+/151982

Suffix arrays are a relatively simple data structure with complex algorithms to construct them (see SACA). Qsufsort is a relatively simply algorithm, but is not state of the art. Exposing QSufSort is an implementation detail of index/suffixarray that I do not believe should be user visible. I believe this should be outside the standard library.

I don't have an objection exposing it; the signature and semantics are very well-defined and clean: Given a byte array, return an array of indices of the sorted substrings. It seems to me independent of algorithm for this specific function.

But I'd use a different name when exporting. Perhaps just Sort as in suffixarray.Sort.

I'm still not a fan of exposing this, but if we were I'd suggest a signature like:

func Sort(b []byte, sa []int)

rather than the current internal signature. This gives us flexibility to reuse memory provided by the user.

Also, state-of-the-art SACAs are several times faster than the current suffixarray package. IIRC, I think my own implementation of SAIS was 30 times faster than QSufSort. Do we want for the Go authors to be on the hook for optimizing the suffix array algorithm more? SAIS was not trivial for me to learn.

@dsnet +1 on the signature suggestion.

Regarding the Go authors being on the hook: We currently are to some extend as this is already in the std library. It doesn't mean we have to provide the best implementation (it's already not the case).

What we should decide is whether this package should be in the std library in the first place, or whether it should be deprecated in favor of external high-performance implementations. Hence deference to the proposal committee for now.

Per discussion with @golang/proposal-review, our plan is to move this outside of the standard library eventually, so we’re not going to make any changes.

In the meantime, we encourage you to fork the code into its own repo and experiment as you see fit.