-
Notifications
You must be signed in to change notification settings - Fork 4
Open
Description
Let me open an issue to capture my notes about performance improvement opportunities in compute_finder_penalty_score. Frequent boxing should be taken care of by 29296f0, but there may be additional improvement opportunities:
- It seems that this function implements a substring search algorithm. The current implementation uses naive string searchwhich works in O(N x M) time, where N is the size of the "hay" (e.g. the width of the QR code) and M is the size of the "needle" (e.g. the size of the undesirable locator pattern - always 7 items in length). O(N + M) time should be possible using KMP or Rabin-Karp algorithm.
- This function extracts rows/columns with the indirection of a
getlambda. Maybe the indirection is optimized away by the compiler, but maybe using subslicing ofCanvas::moduleswould be more efficient (since rows are just continuous slices). Avoiding this indirection may also be applicable tocompute_adjacent_penalty_scoreandcompute_block_penalty_score.
I don't plan to work on this, but I hope that leaving the notes above will help the next person who might want to pick it up.
Reactions are currently unavailable
Metadata
Metadata
Assignees
Labels
No labels