skroutz/string_metric — pull request #16 by charkost (2014-02-03 07:59:52+00:00)
Title: Increase IterativeWithTwoMatrixRowsOptimized performance about 10%

Hello @chief

We have good news again :)

Replacing array of characters(Strings) with array of Fixnums gives us another 10% boost since checking equality of Fixnums is faster than checking equality of Strings.

We are very close to reach the performance of jruby with MRI.

Benchmarks:

MRI 2.1.0:

Rehearsal -----------------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 1.700000 0.000000 1.700000 ( 1.692338)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 2.260000 0.000000 2.260000 ( 2.264586)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.990000 0.000000 1.990000 ( 1.989128)
StringMetric::Levenshtein::IterativeWithTwoMatrixRowsOptimized implementation 1.280000 0.000000 1.280000 ( 1.276185)
Text::Levenshtein implementation 2.210000 0.000000 2.210000 ( 2.217667)
-------------------------------------------------------------------------------------------------------- total: 9.440000sec

user system total real
StringMetric::Levenshtein::Experiment implementation 1.680000 0.000000 1.680000 ( 1.684419)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 2.260000 0.000000 2.260000 ( 2.265873)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.970000 0.000000 1.970000 ( 1.971205)
StringMetric::Levenshtein::IterativeWithTwoMatrixRowsOptimized implementation 1.270000 0.000000 1.270000 ( 1.269643)
Text::Levenshtein implementation 2.180000 0.000000 2.180000 ( 2.186258)

jruby 1.7.9:

Rehearsal -----------------------------------------------------------------------------------------------------------------
StringMetric::Levenshtein::Experiment implementation 4.600000 0.080000 4.680000 ( 3.295000)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 3.270000 0.020000 3.290000 ( 2.604000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.520000 0.000000 1.520000 ( 1.286000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRowsOptimized implementation 3.440000 0.050000 3.490000 ( 2.436000)
Text::Levenshtein implementation 3.530000 0.020000 3.550000 ( 2.554000)
------------------------------------------------------------------------------------------------------- total: 16.530000sec

user system total real
StringMetric::Levenshtein::Experiment implementation 1.430000 0.000000 1.430000 ( 1.380000)
StringMetric::Levenshtein::IterativeWithFullMatrix implementation 1.520000 0.010000 1.530000 ( 1.584000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRows implementation 1.090000 0.000000 1.090000 ( 1.145000)
StringMetric::Levenshtein::IterativeWithTwoMatrixRowsOptimized implementation 1.630000 0.010000 1.640000 ( 1.504000)
Text::Levenshtein implementation 1.320000 0.030000 1.350000 ( 1.382000)