Fix a severe performance bug in `Conversion::Convert` that caused O(N^2) complexity.
authorCarbo Kuo <byvoid@byvoid.com>
Thu, 25 Feb 2021 12:13:38 +0000 (21:13 +0900)
committerShengjing Zhu <zhsj@debian.org>
Sun, 7 Mar 2021 06:20:40 +0000 (06:20 +0000)
commitcbc353f7449ced19d2fb65fa8aa7a90a452f8110
treee027980efd79afd36dab8d19110267ead770f2ff
parentac8a01b1e7401733647421000f33f5f35be789f1
Fix a severe performance bug in `Conversion::Convert` that caused O(N^2) complexity.

In `Conversion.cpp`, line 27:
```
    Optional<const DictEntry*> matched = dict->MatchPrefix(pstr);
```
pstr is a `const char*`. However, there is no overloaded function which parameter `const char*`.
Therefore it matches `Optional<const DictEntry*> MatchPrefix(const std::string& word) const`.
There is an implicit type conversion from `char*` to `std::string` with time complexity O(N).

I added new benchmark tests. Before the fix:

1: ------------------------------------------------------------------
1: Benchmark                        Time             CPU   Iterations
1: ------------------------------------------------------------------
1: BM_Initialization/hk2s        1.17 ms         1.12 ms          645
1: BM_Initialization/hk2t       0.116 ms        0.116 ms         5922
1: BM_Initialization/jp2t       0.206 ms        0.201 ms         3500
1: BM_Initialization/s2hk        18.2 ms         17.9 ms           40
1: BM_Initialization/s2t         18.2 ms         18.1 ms           39
1: BM_Initialization/s2tw        17.9 ms         17.8 ms           39
1: BM_Initialization/s2twp       18.6 ms         18.4 ms           39
1: BM_Initialization/t2hk       0.055 ms        0.054 ms        12907
1: BM_Initialization/t2jp       0.120 ms        0.117 ms         5978
1: BM_Initialization/t2s        0.988 ms        0.984 ms          710
1: BM_Initialization/tw2s        1.08 ms         1.05 ms          672
1: BM_Initialization/tw2sp       1.26 ms         1.24 ms          563
1: BM_Initialization/tw2t       0.088 ms        0.083 ms         8528
1: BM_Convert2M                   413 ms          413 ms            2
1: BM_Convert/100                1.09 ms         1.09 ms          629
1: BM_Convert/1000               33.2 ms         33.2 ms           21
1: BM_Convert/10000              2822 ms         2822 ms            1
1: BM_Convert/100000 (took longer than 5 minutes, killed)

Now:
1: ------------------------------------------------------------------
1: Benchmark                        Time             CPU   Iterations
1: ------------------------------------------------------------------
1: BM_Initialization/hk2s        1.07 ms         1.07 ms          650
1: BM_Initialization/hk2t       0.114 ms        0.114 ms         6092
1: BM_Initialization/jp2t       0.204 ms        0.200 ms         3503
1: BM_Initialization/s2hk        18.2 ms         18.0 ms           40
1: BM_Initialization/s2t         17.6 ms         17.6 ms           39
1: BM_Initialization/s2tw        18.0 ms         17.9 ms           40
1: BM_Initialization/s2twp       17.9 ms         17.9 ms           39
1: BM_Initialization/t2hk       0.055 ms        0.055 ms        12855
1: BM_Initialization/t2jp       0.125 ms        0.124 ms         5772
1: BM_Initialization/t2s        1.000 ms        0.989 ms          695
1: BM_Initialization/tw2s        1.09 ms         1.07 ms          668
1: BM_Initialization/tw2sp       1.29 ms         1.26 ms          558
1: BM_Initialization/tw2t       0.082 ms        0.082 ms         8558
1: BM_Convert2M                   361 ms          361 ms            2
1: BM_Convert/100               0.741 ms        0.740 ms          948
1: BM_Convert/1000               7.54 ms         7.52 ms           94
1: BM_Convert/10000              76.3 ms         76.3 ms            9
1: BM_Convert/100000              786 ms          786 ms            1

This bug was reported in https://github.com/BYVoid/OpenCC/issues/478 and https://github.com/BYVoid/OpenCC/issues/517.

Gbp-Pq: Name 0007-Fix-a-severe-performance-bug-in-Conversion-Convert-t.patch
src/Dict.hpp
src/benchmark/Performance.cpp