-
Notifications
You must be signed in to change notification settings - Fork 10.8k
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
[libc++][PSTL] Dispatching to default algorithms is broken in some cases (at least std::any_of) #70718
Comments
ldionne
added
the
libc++
libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi.
label
Oct 30, 2023
Was the solution that we talked about just to change |
I am not sure |
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
Apr 9, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
Apr 12, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 27, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 28, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL: calling a front-end algorithm inside the implementation of a back-end is incorrect for exception-safety. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness, appropriate forwarding, etc. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 28, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL: calling a front-end algorithm inside the implementation of a back-end is incorrect for exception-safety. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness, appropriate forwarding, etc. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 28, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL: calling a front-end algorithm inside the implementation of a back-end is incorrect for exception-safety. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness, appropriate forwarding, etc. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 28, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL: calling a front-end algorithm inside the implementation of a back-end is incorrect for exception-safety. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness, appropriate forwarding, etc. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 28, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL: calling a front-end algorithm inside the implementation of a back-end is incorrect for exception-safety. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness, appropriate forwarding, etc. Fixes llvm#70718
ldionne
added a commit
to ldionne/llvm-project
that referenced
this issue
May 28, 2024
The experimental PSTL's current dispatching mechanism was designed with flexibility in mind. However, while reviewing the in-progress OpenMP backend, I realized that the dispatching mechanism based on ADL and default definitions in the frontend had several downsides. To name a few: 1. The dispatching of an algorithm to the back-end and its default implementation is bundled together via `_LIBCPP_PSTL_CUSTOMIZATION_POINT`. This makes the dispatching really confusing and leads to annoyances such as variable shadowing and weird lambda captures in the front-end. 2. The distinction between back-end functions and front-end algorithms is not as clear as it could be, which led us to call one where we meant the other in a few cases. This is bad due to the exception requirements of the PSTL: calling a front-end algorithm inside the implementation of a back-end is incorrect for exception-safety. 3. There are two levels of back-end dispatching in the PSTL, which treat CPU backends as a special case. This was confusing and not as flexible as we'd like. For example, there was no straightforward way to dispatch all uses of `unseq` to a specific back-end from the OpenMP backend, or for CPU backends to fall back on each other. This patch rewrites the backend dispatching mechanism to solve these problems, but doesn't touch any of the actual implementation of algorithms. Specifically, this rewrite has the following characteristics: - All back-ends are full top-level backends defining all the basis operations required by the PSTL. This is made realistic for CPU backends by providing the CPU-based basis operations as simple helpers that can easily be reused when defining the PSTL basis operations. - The default definitions for algorithms are separated from their dispatching logic and grouped in families instead, based on the basis operation they require for their default implementation. - The front-end is thus simplified a whole lot and made very consistent for all algorithms, which makes it easier to audit the front-end for things like exception-correctness, appropriate forwarding, etc. Fixes llvm#70718
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The default implementation of
std::none_of
in the PSTL is (here):Notice how this calls
std::__any_of
with lvalues__g_first, __g_last, __g_pred
. Now,__any_of
is implemented like (here):Since
__any_of
is called with lvalues and we're taking universal references, whennone_of
calls__any_of
we get the following deduction:_ForwardIterator&& == _Iter& &&
for some ref-unqualified type_Iter
. As a result, the lambda declaration inside__any_of
basically has signature[&](_Iter&, _Iter&, _Predicate)
and that doesn't work since we're trying to pass it a rvalue (std::move(__first)
& al).This issue happens whenever the default implementation of
std::any_of
is used. It can be seen by removing:Normally, things should work even in that case because
any_of
is not a mandatory algorithm for general backends.The text was updated successfully, but these errors were encountered: