agnivade / levenshtein

Go implementation to calculate Levenshtein Distance.
MIT License
358 stars 28 forks source link

[Optimized]: Removed several bounds checks #6

Closed agnivade closed 5 years ago

agnivade commented 5 years ago

This effectively reduces the number of bounds checks from 7 to just 1, which is the dummy call to x[lenS1]. The compiler, as of 1.12, is unable to determine that lenS1 is indeed a positive number. So lenS1+1 will be positive, and hence x[lenS1] should be within bounds of x. As a result, this is unavoidable.

name              old time/op  new time/op  delta
Simple/ASCII-4     473ns ± 2%   365ns ± 1%  -22.85%  (p=0.000 n=10+10)
Simple/French-4    897ns ± 2%   680ns ± 2%  -24.23%  (p=0.000 n=10+10)
Simple/Nordic-4   1.83µs ± 1%  1.33µs ± 2%  -27.23%  (p=0.000 n=8+9)
Simple/Tibetan-4  1.40µs ± 2%  1.15µs ± 2%  -17.56%  (p=0.000 n=10+10)