microsoft / microsoft/STL

<functional>: Boyer-Moore's delta_2 table contains an unnecessary last entry

Open
#714 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance vNext
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:

https://github.com/microsoft/STL/blob/ae34ee631f808edf5fb247851d61014283a56cbf/stl/inc/functional#L1818-L1835

It's calculated by:

https://github.com/microsoft/STL/blob/ae34ee631f808edf5fb247851d61014283a56cbf/stl/inc/functional#L1770-L1774

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.