<execution>: Parallel find_end() for forward-only iterators could process chunks right-to-left
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 11.1k
- Forks
- 1.7k
- Avg merge
- 4d 15h
- Merged PRs (30d)
- 22
Description
@CaseyCarter observed:
I think there's perf on the floor: for forward ranges,
find_endprocesses all chunks in the partition from left-to-right, when it could instead process chunks right-to-left and cancel early.
After partitioning, we always have a random access range of chunks, each of which is a subrange of the input.find_endcan traverse the range of chunks from right-to-left and stop processing new chunks when a match is found regardless of the traversal category of the individual chunk ranges. TLDR: we don't have to process chunks in the same order we process elements within chunks.
Here's a test case demonstrating how find_end currently performs left-to-right processing:
C:\Temp>type meow.cpp
#include <algorithm>
#include <chrono>
#include <execution>
#include <forward_list>
#include <iostream>
#include <mutex>
#include <thread>
#include <utility>
#include <vector>
using namespace std;
mutex g_mutex;
template <typename... Args>
void locked_cout(const Args&... args) {
lock_guard guard{g_mutex};
(cout << ... << args);
}
int main() {
vector<pair<int, chrono::milliseconds>> vec(30'000);
for (int i = 0; i < 30'000; i += 1'000) {
vec[i] = pair{i, 1s};
}
vec[22'221] = pair{22'221, 2s};
vec[22'222] = pair{1729, 1ms};
vec[22'223] = pair{22'223, 2s};
const vector<int> needle = {1729};
auto lambda = [](const auto& h, const auto& n) {
if (h.second != 0s) {
locked_cout("Processing {", h.first, ", ", h.second.count(), "ms} on thread ", this_thread::get_id(), "\n");
this_thread::sleep_for(h.second);
}
return h.first == n;
};
const forward_list<pair<int, chrono::milliseconds>> haystack(vec.cbegin(), vec.cend());
const auto result =
find_end(execution::par, haystack.cbegin(), haystack.cend(), needle.cbegin(), needle.cend(), lambda);
cout << "Found result at index " << distance(haystack.cbegin(), result) << ".\n";
}
C:\Temp>cl /EHsc /nologo /W4 /MTd /std:c++17 meow.cpp
meow.cpp
C:\Temp>meow
Processing {0, 1000ms} on thread 32332
Processing {1000, 1000ms} on thread 12596
Processing {2000, 1000ms} on thread 20784
Processing {3000, 1000ms} on thread 30136
Processing {4000, 1000ms} on thread 32332
Processing {5000, 1000ms} on thread 32332
Processing {6000, 1000ms} on thread 32332
Processing {7000, 1000ms} on thread 32332
Processing {8000, 1000ms} on thread 32332
Processing {9000, 1000ms} on thread 32332
Processing {10000, 1000ms} on thread 32332
Processing {11000, 1000ms} on thread 32332
Processing {12000, 1000ms} on thread 32332
Processing {13000, 1000ms} on thread 32332
Processing {14000, 1000ms} on thread 32332
Processing {15000, 1000ms} on thread 32332
Processing {16000, 1000ms} on thread 32332
Processing {17000, 1000ms} on thread 32332
Processing {18000, 1000ms} on thread 32332
Processing {19000, 1000ms} on thread 32332
Processing {20000, 1000ms} on thread 32332
Processing {21000, 1000ms} on thread 32332
Processing {22000, 1000ms} on thread 32332
Processing {22221, 2000ms} on thread 32332
Processing {1729, 1ms} on thread 32332
Processing {22223, 2000ms} on thread 32332
Processing {23000, 1000ms} on thread 32332
Processing {24000, 1000ms} on thread 32332
Processing {25000, 1000ms} on thread 32332
Processing {26000, 1000ms} on thread 32332
Processing {27000, 1000ms} on thread 32332
Processing {28000, 1000ms} on thread 32332
Processing {29000, 1000ms} on thread 32332
Found result at index 22222.
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 at the parallel find_end entry point and reproduce the behavior with the supplied meow.cpp forward_list example. Trace how the input is partitioned into chunks and how chunks are traversed, then verify that right-to-left processing can stop after the latest match while preserving the reported result at index 22222.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100