Mercurial > hg
annotate tests/README @ 48671:f1ed5c304f45
encoding: fix trim() to be O(n) instead of O(n^2)
`encoding.trim()` iterated over the possible lengths smaller than the
input and created a slice for each. It then calculated the column
width of the result, which is of course O(n), so the overall algorithm
was O(n). This patch rewrites it to iterate over the unicode
characters, keeping track of the length so far. Also, the old
algorithm started from the end of the string, which made it much worse
when the input is large and the limit is small (such as the typical 72
we pass to it).
You can time it by running something like this:
```
time python3 -c 'from mercurial.utils import stringutil; print(stringutil.ellipsis(b"0123456789" * 1000, 5))'
```
That drops from 4.05 s to 83 ms with this patch (and most of that is
of course startup time).
Differential Revision: https://phab.mercurial-scm.org/D12089
author | Martin von Zweigbergk <martinvonz@google.com> |
---|---|
date | Wed, 26 Jan 2022 10:11:01 -0800 |
parents | 4b0fc75f9403 |
children |
rev | line source |
---|---|
332 | 1 To run the tests, do: |
2 | |
3 cd tests/ | |
2207
8a2a7f7d9df6
Delete the shell version of run-tests
Stephen Darnell <stephen@darnell.plus.com>
parents:
1933
diff
changeset
|
4 python run-tests.py |
332 | 5 |
26421
4b0fc75f9403
urls: bulk-change primary website URLs
Matt Mackall <mpm@selenic.com>
parents:
8936
diff
changeset
|
6 See https://mercurial-scm.org/wiki/WritingTests for |
3934
d0bbd8ee50c7
Move test suite docs to the wiki
Matt Mackall <mpm@selenic.com>
parents:
3199
diff
changeset
|
7 more information on writing tests. |