Add turbochargers

[PythonNut]

This PR adds the following optimizations:

1. Let bindings are moved out of inner loops, saving stack trashing.
2. Match collection is now implemented with a dynamic programming table.
3. Unpromising branches (i.e. all non-optimal matches) are pruned immediately

The code is, unfortunately, very dense and difficult to follow. I did my best, but I'm pretty sure I broke my brain making this.

Scoring should behave identically, according to my testing.

See also:

• 34

• https://github.com/PythonNut/helm-flx/issues/9
• https://github.com/syl20bnr/spacemacs/issues/3327#issuecomment-150109947
• https://github.com/syl20bnr/spacemacs/issues/3500

This is preliminary and needs some heavy testing. I'm not too sure how the math works out for (3). I think it shouldn't cause any incompatibilities, but I'm to tired to prove it right now.

[TheBB]

Wow, I never expected this so quickly.

If you can get the tests to pass I would love to see this merged. Keep your brain intact though, please.

[PythonNut]

The only two tests that fail do so because of code I removed (the tests are no longer necessary).

Not sure why literally everything fails on the 24.3 build.

[fbergroth]

Cools! Just to avoid confusion, this is memoization and not dynamic programming.

[PythonNut]

I'm not too sure how the math works out for (3). I think it shouldn't cause any incompatibilities, but I'm to tired to prove it right now.

Turns out I didn't actually flip the switch for that. I flipped it in Small performance tweaks and some more test are breaking. :/ I guess that's one optimization we can't afford to make. EDIT. or maybe I'm just being sloppy. It looks like some regular old errors have creeped in.

Cools! Just to avoid confusion, this is memoization and not dynamic programming.

I could be mistaken, but I think that dynamic programming is a correct term for what I'm doing. Sure, it's backed by memoization. But the concept of overlapping subproblems is still present.

[fbergroth]

I could be mistaken, but I think that dynamic programming is a correct term for what I'm doing. Sure, it's backed by memoization. But the concept of overlapping subproblems is still present.

You're right. Sorry, I overlooked that.

[PythonNut]

Okay. New version passes all test for me.

[lewang]

haha. I guess apologies are in order. I recently tried to refactor some flx code, and it was quite /challenging/. :)

I have a flight in a couple of days and I'll look at this.

[PythonNut]

@lewang oh, no. I was talking about my own code. It's even more dense that it was before.

[lewang]

@PythonNut It would be good to have some tests around the speedups.

[PythonNut]

@lewang you mean like the case found in https://github.com/lewang/flx/issues/34?

[lewang]

yeah, with an upper bound time limit to indicate failure.

[lewang]

@PythonNut I gave the PR a spin and it works really well. I've added you as a collaborator to the project so you can push your branches to this remote and it's easier to collaborate.

Can you write up a rough explanation of your changes? I want to make it it easier for others to understand and contribute.

[PythonNut]

I've added you as a collaborator to the project so you can push your branches to this remote and it's easier to collaborate.

Thanks a ton. I've pushed to a topic branch on this repo. I'll close this PR and make a new one for that branch.