<functional>: Boyer-Moore's delta_2 table contains an unnecessary last entry
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 11.1k
- Forks
- 1.7k
- Avg merge
- 4d 15h
- Merged PRs (30d)
- 22
Description
Boyer-Moore's delta_2 table is used here:
It's calculated by:
And the callers allocate tables of the specified size.
After looking at this code and the algorithms, I believe that the last entry in the delta_2 table is never accessed, so it doesn't need to be calculated and stored. According to my still-developing understanding, this table is used when we're inspecting a potential occurrence of the pattern in the target text, from the back of the pattern to the front. When we encounter an incomplete match - i.e. at least the final pattern character matches, but not all of them - then _Idx is the index of the mismatched character in the pattern (again, encountered right-to-left), and _Delta2[_Idx] records how much we need to advance the text _UFirst. Given this understanding (confirmed by inspection of the control flow), we never inspect _Delta2[_Pat_size - 1] because that would be used for the final pattern character not matching at all. (The // that is, *_UFirst == "_Pat.back()" branch prevents this from happening.)
vNext note: Resolving this issue will require breaking binary compatibility. We won't be able to accept pull requests for this issue until the vNext branch is available. See #169 for more information.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with stl/inc/functional at the linked Boyer-Moore table calculation and use sites around lines 1770-1835. Verify the control-flow claim that the final delta_2 entry is never accessed, then adjust the allocation and calculation when the vNext branch is available; resolving this requires breaking binary compatibility.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100