##// END OF EJS Templates
encoding: fix trim() to be O(n) instead of O(n^2)...
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

File last commit:

r44255:7857bd9b default
r49518:f1ed5c30 default
Show More
bdiff.cc
39 lines | 969 B | text/x-c | CppLexer
Augie Fackler
contrib: add some basic scaffolding for some fuzz test targets...
r35688 /*
* bdiff.cc - fuzzer harness for bdiff.c
*
* Copyright 2018, Google Inc.
*
* This software may be used and distributed according to the terms of
* the GNU General Public License, incorporated herein by reference.
*/
Augie Fackler
fuzz: extract some common utilities and use modern C++ idioms...
r38191 #include <memory>
Augie Fackler
contrib: add some basic scaffolding for some fuzz test targets...
r35688 #include <stdlib.h>
Augie Fackler
fuzz: use a more standard approach to allow local builds of fuzzers...
r44265 #include "FuzzedDataProvider.h"
Augie Fackler
fuzz: extract some common utilities and use modern C++ idioms...
r38191
Augie Fackler
contrib: add some basic scaffolding for some fuzz test targets...
r35688 extern "C" {
#include "bdiff.h"
Augie Fackler
fuzz: always define LLVMFuzzerInitialize() even if we don't need it...
r44261 extern "C" int LLVMFuzzerInitialize(int *argc, char ***argv)
{
return 0;
}
Augie Fackler
contrib: add some basic scaffolding for some fuzz test targets...
r35688 int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size)
{
Augie Fackler
fuzz: migrate bdiff fuzzer to use FuzzedDataProvider...
r44011 FuzzedDataProvider provider(Data, Size);
std::string left = provider.ConsumeRandomLengthString(Size);
std::string right = provider.ConsumeRemainingBytesAsString();
Augie Fackler
contrib: add some basic scaffolding for some fuzz test targets...
r35688
struct bdiff_line *a, *b;
Augie Fackler
fuzz: migrate bdiff fuzzer to use FuzzedDataProvider...
r44011 int an = bdiff_splitlines(left.c_str(), left.size(), &a);
int bn = bdiff_splitlines(right.c_str(), right.size(), &b);
Augie Fackler
contrib: add some basic scaffolding for some fuzz test targets...
r35688 struct bdiff_hunk l;
bdiff_diff(a, an, b, bn, &l);
free(a);
free(b);
bdiff_freehunks(l.next);
return 0; // Non-zero return values are reserved for future use.
}
} // extern "C"