skroutz/string_metric — pull request #11 by charkost (2014-01-29 01:09:56+00:00)
Title: Improve StringMetric::Levenshtein::IterativeWithTwoMatrixRows performance for MRI

Hello @chief!
Congratulations for all of your gems. I have read almost all of them and learned quite a few things.
Since reading your code helped me a lot i wanted to contribute back to you and your gems.

ruby-prof showed that 20% of the execution time of StringMetric::Levenshtein#distance consumed by Enumerable#min method.

I searched a bit and found that it's quite faster to use Array#sort! and take the first object from the sorted array instead of using the Enumerable#min method.

I tested my changes with MRI-2.1.0, jruby-1.7.9 and rbx-2.2.3.
With MRI i achieved approximately 15% reduce in execution time but
with the other interpreters execution time increased a lot. This is why the code became a little uglier because i had to preprocess the optimal #min method to dispach to the array in order to keep the previous performance of jruby and rbx and
simultaneously increase MRI's performance.

Most likely my approuch would not feet your quality standards so feel free to reject it. Although you can use the Array#sort! part and implement the rest with your own way.

The same #optimal_min may be used at IterativeWithFullMatrix class too.

Finaly the benchmarks:

MRI-2.1.0 before changes

Rehearsal --------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 2.390000 0.010000 2.400000 ( 2.433699)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 2.310000 0.000000 2.310000 ( 2.358812)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 2.020000 0.000000 2.020000 ( 2.053717)
Text::Levenshtein implementation 2.240000 0.010000 2.250000 ( 2.281014)
----------------------------------------------------------------------------------------------- total: 8.980000sec

MRI-2.1.0 after changes

Rehearsal --------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 2.080000 0.000000 2.080000 ( 2.081061)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 2.300000 0.000000 2.300000 ( 2.304568)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.690000 0.000000 1.690000 ( 1.687412)
Text::Levenshtein implementation 2.260000 0.000000 2.260000 ( 2.260289)
----------------------------------------------------------------------------------------------- total: 8.330000sec

user system total real
StringMetric::Levenshtein::Experiment implementation 2.070000 0.000000 2.070000 ( 2.066825)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 2.300000 0.000000 2.300000 ( 2.295706)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.680000 0.000000 1.680000 ( 1.680046)
Text::Levenshtein implementation 2.230000 0.000000 2.230000 ( 2.236996)

jruby-1.7.9 before changes

Rehearsal --------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 4.570000 0.140000 4.710000 ( 3.270000)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 3.190000 0.040000 3.230000 ( 2.427000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.520000 0.000000 1.520000 ( 1.215000)
Text::Levenshtein implementation 3.240000 0.020000 3.260000 ( 2.406000)
---------------------------------------------------------------------------------------------- total: 12.720000sec

user system total real
StringMetric::Levenshtein::Experiment implementation 1.390000 0.000000 1.390000 ( 1.342000)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 1.500000 0.010000 1.510000 ( 1.522000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.080000 0.000000 1.080000 ( 1.096000)
Text::Levenshtein implementation 1.280000 0.000000 1.280000 ( 1.302000)

jruby-1.7.9 after changes

Rehearsal --------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 4.540000 0.120000 4.660000 ( 3.280000)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 3.250000 0.050000 3.300000 ( 2.419000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.510000 0.000000 1.510000 ( 1.249000)
Text::Levenshtein implementation 3.380000 0.020000 3.400000 ( 2.467000)
---------------------------------------------------------------------------------------------- total: 12.870000sec

user system total real
StringMetric::Levenshtein::Experiment implementation 1.410000 0.000000 1.410000 ( 1.390000)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 1.510000 0.010000 1.520000 ( 1.547000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.080000 0.000000 1.080000 ( 1.096000)
Text::Levenshtein implementation 1.310000 0.000000 1.310000 ( 1.325000)

rbx-2.2.3 before changes

Rehearsal --------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 6.086666 0.026666 6.113332 ( 4.372460)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 5.133333 0.036666 5.169999 ( 3.921773)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 2.570000 0.006667 2.576667 ( 2.613008)
Text::Levenshtein implementation 4.556666 0.030000 4.586666 ( 3.647320)
---------------------------------------------------------------------------------------------- total: 18.446664sec

user system total real
StringMetric::Levenshtein::Experiment implementation 3.283333 0.010000 3.293333 ( 3.096289)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 3.253333 0.006667 3.260000 ( 3.314387)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 2.553333 0.000000 2.553333 ( 2.597258)
Text::Levenshtein implementation 3.230000 0.010000 3.240000 ( 3.209600)

rbx-2.2.3 after changes

Rehearsal --------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 6.266666 0.036667 6.303333 ( 4.163026)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 5.133333 0.010000 5.143333 ( 3.822721)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 2.630000 0.010000 2.640000 ( 2.629449)
Text::Levenshtein implementation 4.573333 0.023333 4.596666 ( 3.594965)
---------------------------------------------------------------------------------------------- total: 18.683332sec

user system total real
StringMetric::Levenshtein::Experiment implementation 3.313333 0.023333 3.336666 ( 3.155632)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 3.230000 0.013334 3.243334 ( 3.241195)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 2.603333 0.003333 2.606666 ( 2.603230)
Text::Levenshtein implementation 3.203333 0.016667 3.220000 ( 3.134817)