Things in that last version weren't robust/efficient with regards to zero
length strings being in the mix. This fixes that:
proc lcpLenVRange(strs: openArray[string]): int =
if strs.len == 0: return -1 # raise?
if strs[0].len == 0: return 0 # ANY "" anywhere => 0
let byte0 = strs[0][0]
var minAt, maxAt: int
for i in 1 ..< strs.len:
if strs[i].len == 0: return 0
if strs[i] < strs[minAt]: minAt = i
if strs[i] > strs[maxAt]: maxAt = i
if strs[i][0] != byte0: return 0
for i, c in strs[minAt]:
if c != strs[maxAt][i]: return i
return strs[minAt].len
Run
In the interests of being mostly self-contained, I also pushed a better
`timeIt` to `cligen#head` and updated my driver to use the new `timeIt` and to
**not** time the `stdout.write` parts:
proc timeAlgo(algo=lcpVRange, reps=1, strs: seq[string]) =
var x: int
timeIt(stdout.write, "", 1e-6, 3, " usec via " & ($algo)[3..^1], reps):
x += strs.lcpLen(algo)
echo " ", int(x.float / reps.float + 0.5)
Run
Finally, I created a `benchLcp.zsh` script:
#!/bin/zsh
lcp=`pwd`/lcp #We need Zsh only for its **
echo "L3 data, 19 answer"
for a in lcpVe lcpR lcpB lcpVR; do $lcp -r10 -a$a /usr/lib/python3.6/**;
done
echo "L2 data, 9 answer"
for a in lcpVe lcpR lcpB lcpVR; do $lcp -r10 -a$a /usr/bin/*; done
echo "L3 data, 0 answer"
for a in lcpVe lcpR lcpB lcpVR; do (cd /usr/lib/python3.6; $lcp -r10 -a$a
**); done
echo "L2 data, 0 answer"
for a in lcpVe lcpR lcpB lcpVR; do (cd /usr/bin; $lcp -r10 -a$a *); done
Run
and used a little `nim-pgo` wrapper I have to use gcc's profile guided
optimization (`-fprofile-generate` and `-fprofile-use`), compiling, running a
test/bench, then re-compiling. With all that, I get:
L3 data, 19 answer
1910.448..2253.771 1959.491 +- 32.812 usec via Vertical 19
686.884..1150.131 777.125 +- 48.653 usec via Range 19
922.680..1522.064 996.113 +- 58.569 usec via BinSearch 19
693.560..1163.244 786.591 +- 49.932 usec via VRange 19
L2 data, 9 answer
41.246..63.181 45.848 +- 2.480 usec via Vertical 9
37.193..54.359 40.936 +- 1.778 usec via Range 9
22.650..25.511 23.413 +- 0.353 usec via BinSearch 9
36.716..55.075 41.509 +- 2.292 usec via VRange 9
L3 data, 0 answer
0.000..0.954 0.167 +- 0.094 usec via Vertical 0
535.488..1017.570 627.780 +- 48.740 usec via Range 0
58.651..205.994 82.874 +- 15.300 usec via BinSearch 0
0.715..3.576 1.097 +- 0.278 usec via VRange 0
L2 data, 0 answer
0.000..0.000 0.000 +- 0.000 usec via Vertical 0
32.663..38.862 33.927 +- 0.650 usec via Range 0
3.099..4.768 3.290 +- 0.166 usec via BinSearch 0
0.000..0.238 0.048 +- 0.032 usec via VRange 0
Run
which makes total sense to me. The @marks performance discrepancies (except his
mysterious `foldl` bit), probably just come from the "mix"/averaging of how
many zero length answers are in his inputs.
So, this new variant of that VRange hybrid method would make the most sense to
recommend for general usage (of the above selection, anyway). It's never that
slow, fastest at large scale when performance matters most, and can leverage
early exit in easy cases.
The binary search way for smaller scale data may be best if the caller already
knows and can pass in a data scale parameter. If we must measure the data size,
that takes a whole pass through the length fields. That measurement eats into
the 36/22=1.6x L2-non-zero speed ratio, probably reducing it to like 1.3x which
isn't that much a boost for all the complexity of measurement+algorithm
switching. I got about a 1.15x boost from PGO and most probably skip that
entirely to avoid build complexity.
