Reduce allocations in command suggestion edit distance calculation

[0xff-dev]

Optimize Levenshtein distance calculation used by command suggestions

Description

The current implementation of ld in cobra.go calculates Levenshtein distance using a full two-dimensional DP matrix.

SuggestionsFor calls this function when suggesting commands after an invalid command is entered. Since this calculation may be performed against multiple commands, the temporary allocations from the full matrix can add up.

The current implementation has O(n*m) memory usage, although Levenshtein distance only requires the previous row to calculate the next row.

Proposed change

Replace the full matrix implementation with a rolling array implementation:

• Keep the same Levenshtein distance behavior.
• Reduce memory usage from O(n*m) to O(min(n,m)).
• Reduce temporary heap allocations during command suggestion generation.

Benchmark

Benchmarking the current implementation against a rolling-array implementation:

goos: darwin
goarch: amd64
pkg: github.com/spf13/cobra
cpu: Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz
BenchmarkLd
BenchmarkLd/short/optimized
BenchmarkLd/short/optimized-12          37506042                31.21 ns/op            0 B/op          0 allocs/op
BenchmarkLd/short/reference
BenchmarkLd/short/reference-12           7329200               161.8 ns/op           224 B/op          5 allocs/op
BenchmarkLd/typical/optimized
BenchmarkLd/typical/optimized-12         3363799               356.3 ns/op           128 B/op          1 allocs/op
BenchmarkLd/typical/reference
BenchmarkLd/typical/reference-12         1000000              1102 ns/op            2304 B/op         16 allocs/op
BenchmarkLd/long/optimized
BenchmarkLd/long/optimized-12             319987              3539 ns/op             416 B/op          1 allocs/op
BenchmarkLd/long/reference
BenchmarkLd/long/reference-12             131908              8369 ns/op           21664 B/op         50 allocs/op
PASS
ok      github.com/spf13/cobra  8.461s