Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Speed up the detection process #20

Open
sasi143 opened this issue Aug 25, 2020 · 5 comments
Open

Speed up the detection process #20

sasi143 opened this issue Aug 25, 2020 · 5 comments
Labels
help wanted Extra attention is needed performance Performance

Comments

@sasi143
Copy link

sasi143 commented Aug 25, 2020

First of all, really appreciate your work and time.

With small input data patterns, it is doing a good job, but when input data patterns crossing more than 1 lakh, it is taking too much time. Is there any possibility which can speed up the process (maybe using on GPU)

@gandersen101
Copy link
Owner

gandersen101 commented Aug 26, 2020

Hi @sasi143, thanks for your interest in Spaczz. I am very interested in improving the speed of the fuzzy matching process, however, for reasons I'll outline below, I unfortunately do not think this will happen in the near future without additional contributor(s).

I believe the performance bottleneck(s) in spaczz's fuzzy matching come from the amount of time the code spends in pure Python iterating through and processing text and potential matches. I do not believe the fuzzy comparisons themselves are a bottleneck because they are done with RapidFuzz which is already written in C++. I do need to do some profiling to confirm this though.

The pattern that spaCy proper uses to achieve it's rapid speed is dropping most of it's internal text processing code to C, and that is the pattern I would eventually like to follow. Unfortunately, I have almost no experience with C/C++, so without help from additional contributor(s) with C/C++ experience, my progress will be quite slow. That being said, I do intend to work on it myself, I just can't make any promises about timelines. Also, while I think incorporating GPU support is an interesting idea, to be honest I have even less of an idea about how to implement that than dropping portions of the code down to C/C++.

In the shorter term here are some possible actions:

  1. Raise the min_r1 threshold from the current value of 25 for your patterns. min_r1 is essentially a trade-off between speed and accuracy. Raising it will mean some potential matches will be missed because they won't be passed to further match optimization, but raising it should result in modest speed increases. Look at the documentation for the FuzzySearcher for details on min_r1 and the documentation for the FuzzyMatcher and SpaczzRuler for how to incorporate this into your patterns or change the default value for all patterns in an instance of those classes.
  2. Think about rewriting some of your fuzzy patterns as fuzzy regex patterns, look at the "Approximate “fuzzy” matching" section in the Regex package documentation. spaczz supports these kind of patterns and they will likely run faster as Regex is mostly implemented in lower-level code.
  3. I can run some profiling on spaczz to confirm my hypothesis of where the bottleneck(s) are. In addition I may discover some "easy-wins" where I have written something inefficiently even for Python.
  4. I can try to rethink/redesign aspect of the fuzzy matching algorithm to potentially reduce the number of comparisons it currently does.

I'm sorry I can't give you a more definite solution or timeline right now. Hopefully as people continue to discover/use spaczz some more experienced programmers may become interested in contributing. As things stand, I will slowly be working on accomplishing these speed improvements myself.

I'll use this issue as a place to keep track of these updates as they come.

@gandersen101 gandersen101 added the performance Performance label Aug 26, 2020
@sasi143
Copy link
Author

sasi143 commented Aug 26, 2020

@gandersen101 Really thankfull to your well explaination and appreciate for your time. Keep doing good work and stay safe.

@gandersen101 gandersen101 added the help wanted Extra attention is needed label Dec 10, 2020
@gandersen101
Copy link
Owner

Issue #41 has turned into a performance discussion and I am planning to make some performance improvements very soon. I will provide a summary of those changes on this thread soon.

@kwhumphreys
Copy link

@gandersen101 Thanks for the inspiration. I started a low-level integration of rapidfuzz into spaCy, to attempt to improve performance explosion/spaCy#11359
Any thoughts/ideas welcome there.

@gandersen101
Copy link
Owner

@kwhumphreys very cool. Best of luck! Obviously I have not put much time into spaczz over the past couple years but the functionality is something people have been looking for. Hopefully you can get an official implementation into spaCy proper.

I'm going to add an announcement to the README - essentially I intend to address some issues/ add some functionality with spaczz going forward but I don't know if I'll ever have the time to "Cythonize" this library to extent that it's fast-enough for many use-cases.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
help wanted Extra attention is needed performance Performance
Projects
None yet
Development

No branches or pull requests

3 participants