microsoft / microsoft/STL

Possible missed optimization for non-common bidirectional ranges in `<algorithm>`

Open
#5,903 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance ranges
Dominant language
C++
Stars
11.1k
Forks
1.7k
Avg merge
4d 15h
Merged PRs (30d)
22

Description

This issue is an extension of #5886 (and the corresponding PR #5887), as it appears that there are other locations where _Bidi_common<_It, _Se> is checked, where I believe the less strict bidirectional_iterator<_It> would suffice.

In the following cases, for a non-common range with bidirectional iterators, the search runs from the beginning instead of from the end, resulting in more applications of projection and predicate than necessary.

_Find_last_unchecked
https://github.com/microsoft/STL/blob/5459853bf78ceef1137d845bfeca98f658659691/stl/inc/algorithm#L3439

_Find_last_if_unchecked
https://github.com/microsoft/STL/blob/5459853bf78ceef1137d845bfeca98f658659691/stl/inc/algorithm#L3522

However I have not checked all references to _Bidi_common (e.g. in _Shift_right_impl), so there could be more.

Note that _Partition_unchecked is already covered by #5886
https://github.com/microsoft/STL/blob/5459853bf78ceef1137d845bfeca98f658659691/stl/inc/algorithm#L6989

I can look into it, but I would like someone with more experience to first confirm that I have not come to an incorrect conclusion.

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 in stl/inc/algorithm at the _Find_last_unchecked and _Find_last_if_unchecked locations, and compare the prior discussion in #5886 and PR #5887. Inspect other _Bidi_common references, including _Shift_right_impl, and verify that non-common bidirectional ranges search from the end with no unnecessary projection or predicate applications.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.