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