[unicode-PERF]: use optmized BM algorithm to replace the brute-force finder - #8626

FYI,

1. this is the python blog in 2006, describing how they implemented the exact BM algorithm in that period of Python: https://web.archive.org/web/20201107074620/http://effbot.org/zone/stringlib.htm
2. this is about all kinds of string fast matching algorithms: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

but the code looks pretty similar to the one implemented in CPython.

Yeah. I did copy that piece of CPython code and modify based on it, and I add the code link in the comments. I think CPython impl should be a best practice, and Numba UnicodeType is also imitating the CPython UnicodeObject, so I think I don't need to re-design this algorithm if we don't have specific Numba-related issues to tackle.

Question: Have you measure the time using the new algorithm vs the older implementation?

No, not yet. I can work on that, make up some test cases to see the time difference. Will update it here when the perf test is ready.

Here's a made-up test case, copied from the method test_find in test_unicode.py, and add a very long test case in it. U can put this as a method in the class UnicodeTest in test_unicode.py and rerun this.

    def test_find_perf(self):
        pyfunc = find_usecase
        cfunc = njit(pyfunc)

        # pre-run cfunc
        cfunc("abc", "a")

        default_subs = [
            (s, ['', 'xx', s[:-2], s[3:], s]) for s in UNICODE_EXAMPLES
        ]

        cpython_subs = [
            ('a' * 100 + '\u0102', ['\u0102', '\u0201', '\u0120', '\u0220']),
            ('a' * 100 + '\U00100304', ['\U00100304', '\U00100204',
                                        '\U00102004']),
            ('\u0102' * 100 + 'a', ['a']),
            ('\U00100304' * 100 + 'a', ['a']),
            ('\U00100304' * 100 + '\u0102', ['\u0102']),
            ('a' * 100, ['\u0102', '\U00100304', 'a\u0102', 'a\U00100304']),
            ('\u0102' * 100, ['\U00100304', '\u0102\U00100304']),
            ('\u0102' * 100 + 'a_', ['a_']),
            ('\U00100304' * 100 + 'a_', ['a_']),
            ('\U00100304' * 100 + '\u0102_', ['\u0102_']),
        ]

        start_time = time.time()
        for _ in range(1000):
            for s, subs in default_subs + cpython_subs:
                for sub_str in subs:
                    cfunc(s, sub_str)
        print(f"consumed time in short test cases: {time.time() - start_time}")

        # made-up cases for fast search
        for leng in [10, 100, 1000, 10000]:
            s = "abcdefg" * leng + "hijk"
            sub_str = "hijk"
            start_time = time.time()
            for _ in range(1000):
                cfunc(s, sub_str)
            print(f"consumed time with len={len(s)}: {time.time() - start_time}")

Consumed time in Numba 0.56.3:

consumed time in short test cases: 0.19890618324279785
consumed time with len=74: 0.003802061080932617
consumed time with len=704: 0.006798982620239258
consumed time with len=7004: 0.03879284858703613
consumed time with len=70004: 0.44359922409057617

Consumed time in Numba main with this PR:

total time consumed: 0.18944501876831055
consumed time with len=74: 0.004054069519042969
consumed time with len=704: 0.003863811492919922
consumed time with len=7004: 0.007459163665771484
consumed time with len=70004: 0.04593682289123535

In short test cases, consumed time are similar (perhaps a minor degradation with this PR, but marginal, I think).
When putting the sub_str in the end of a very long s, the acceleration ratio is 1.76, 5.2, and 9.66, which is nice.

cc @guilhermeleobas

When putting the sub_str in the end of a very long s, the acceleration ratio is 1.76, 5.2, and 9.66, which is nice.

Can you share the source code for these?

Can you share the source code for these?

I have already shared the code, u can unfold the Details button in #8626 (comment), then u will see the source code!

@guilhermeleobas

Oh, sorry. I'll check it tomorrow morning.

Thanks @dlee992. I ran the code and your approach is way faster than the old one:

# your branch
consumed time in short test cases: 0.1025538444519043
consumed time with len=74: 0.0019850730895996094
consumed time with len=704: 0.002277851104736328
consumed time with len=7004: 0.006390094757080078
consumed time with len=70004: 0.04852104187011719
consumed time with len=700004: 0.45890283584594727
consumed time with len=7000004: 4.588933944702148

# Numba main
consumed time in short test cases: 0.10606002807617188
consumed time with len=74: 0.002021312713623047
consumed time with len=704: 0.003590106964111328
consumed time with len=7004: 0.01938009262084961
consumed time with len=70004: 0.17744994163513184
consumed time with len=700004: 1.744581937789917
consumed time with len=7000004: 17.453103065490723

Hi, @guilhermeleobas and @sklam

Since no obvious side effects with this PR, I feel this one can also be put into Numba 0.57 RC if possible.

Yes! I just tagged to 0.57