microsoft / microsoft/STL

<execution>: Parallel find_end() for forward-only iterators could process chunks right-to-left

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

Nobody has claimed this yet.

performance
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_end processes 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_end can 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

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 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.