Reduce memory use of GetLevenshteinDistance() by almost 50%

Reduce memory use of GetLevenshteinDistance() by almost 50%

Probably not measurable, but it's also a bit shorter, so probably worth it.
This is a port of my change
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150713/286948.html
where I explained the idea like so:

  // Although the algorithm is typically described using an m x n
  // array, only one row plus one element are used at a time, so this
  // implementation just keeps one vector for the row.  To update one entry,
  // only the entries to the left, top, and top-left are needed.  The left
  // entry is in row[x-1], the top entry is what's in row[x] from the last
  // iteration, and the top-left entry is stored in previous.

No intended behavior change.

BUG=none

Committed: https://crrev.com/4967b70a63b618a6e508db88c2fa9c5dbef206f4
Cr-Commit-Position: refs/heads/master@{#376015}

[Nico, 2016-02-10 15:28:32]

thakis@chromium.org changed reviewers:
+ felt@chromium.org, radhikabhar@chromium.org

[felt, 2016-02-10 20:24:40]

Thanks for the improvement!

Can you add a test or two in error_classification_unittest? The simplest way to
do it is to invoke IsCertLikelyFromMultiTenantHosting with different
request_urls that are varying distances away from the url in the test cert, and
then see if it is true or false.

[Nico, 2016-02-10 20:31:21]

This is a behavior-preserving change – shouldn't this be covered by existing
tests? :-P

[felt, 2016-02-10 20:36:58]

On 2016/02/10 20:31:21, Nico wrote:
> This is a behavior-preserving change – shouldn't this be covered by
existing
> tests? :-P

indeed it should be! but yet here we are. 

a few lines of unit tests will prove it's a behavior-preserving change. :)

[Nico, 2016-02-10 20:57:00]

I added a  few (using a more direct approach). (I haven't tried running them
locally, so it's possible they don't build / pass yet, but the trybots will tell
me that :-) )

[Nico, 2016-02-10 20:58:09]

Now the diff is pretty hard to read since the code's moving around and changing
at the same time. I like patch set 1 more, it's easier to see that nothing
changes there imo.

[Nico, 2016-02-10 20:59:57]

…so if this approach looks generally alright to you, I propose I land the tests
first in a separate CL, and the actual change after the tests are in.

[felt, 2016-02-11 00:10:42]

lgtm, i'm OK with landing it in two CLs (and see the nit)

https://codereview.chromium.org/1690593002/diff/80001/components/ssl_errors/e...
File components/ssl_errors/error_classification.h (right):

https://codereview.chromium.org/1690593002/diff/80001/components/ssl_errors/e...
components/ssl_errors/error_classification.h:67: size_t
GetLevenshteinDistance(const std::string& str1, const std::string& str2);
Could you move this into the "helper methods" section below?

[Nico, 2016-02-17 20:30:37]

Ok, rebased, PTAL. Tests landed in a prior CL.

[Nico, 2016-02-17 20:36:06]

…oh, you already lgtm'd, never mind :-)

[Nico, 2016-02-17 20:36:13]

The CQ bit was checked by thakis@chromium.org

[Nico, 2016-02-17 20:36:13]

The patchset sent to the CQ was uploaded after l-g-t-m from felt@chromium.org
Link to the patchset: https://codereview.chromium.org/1690593002/#ps100001
(title: ".")

[commit-bot: I haz the power, 2016-02-17 20:37:55]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1690593002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1690593002/100001

[Nico, 2016-02-17 20:45:07]

The CQ bit was unchecked by thakis@chromium.org

[Nico, 2016-02-17 20:45:50]

The CQ bit was checked by thakis@chromium.org

[commit-bot: I haz the power, 2016-02-17 20:46:04]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1690593002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1690593002/100001

[commit-bot: I haz the power, 2016-02-17 22:00:18]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-17 22:00:19]

Try jobs failed on following builders:
  linux_chromium_asan_rel_ng on tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[Nico, 2016-02-17 22:05:20]

The CQ bit was checked by thakis@chromium.org

[commit-bot: I haz the power, 2016-02-17 22:06:51]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1690593002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1690593002/100001

[commit-bot: I haz the power, 2016-02-17 22:49:29]

Committed patchset #6 (id:100001)

[commit-bot: I haz the power, 2016-02-17 22:50:38]

Description was changed from

==========
Reduce memory use of GetLevenshteinDistance() by almost 50%

Probably not measurable, but it's also a bit shorter, so probably worth it.
This is a port of my change
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150713/286948.html
where I explained the idea like so:

  // Although the algorithm is typically described using an m x n
  // array, only one row plus one element are used at a time, so this
  // implementation just keeps one vector for the row.  To update one entry,
  // only the entries to the left, top, and top-left are needed.  The left
  // entry is in row[x-1], the top entry is what's in row[x] from the last
  // iteration, and the top-left entry is stored in previous.

No intended behavior change.

BUG=none
==========

to

==========
Reduce memory use of GetLevenshteinDistance() by almost 50%

Probably not measurable, but it's also a bit shorter, so probably worth it.
This is a port of my change
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150713/286948.html
where I explained the idea like so:

  // Although the algorithm is typically described using an m x n
  // array, only one row plus one element are used at a time, so this
  // implementation just keeps one vector for the row.  To update one entry,
  // only the entries to the left, top, and top-left are needed.  The left
  // entry is in row[x-1], the top entry is what's in row[x] from the last
  // iteration, and the top-left entry is stored in previous.

No intended behavior change.

BUG=none

Committed: https://crrev.com/4967b70a63b618a6e508db88c2fa9c5dbef206f4
Cr-Commit-Position: refs/heads/master@{#376015}
==========

[commit-bot: I haz the power, 2016-02-17 22:50:40]

Patchset 6 (id:??) landed as
https://crrev.com/4967b70a63b618a6e508db88c2fa9c5dbef206f4
Cr-Commit-Position: refs/heads/master@{#376015}