{"action":"created","comment":{"url":"https://api.github.com/repos/nikomatsakis/rayon/pulls/comments/93407646","pull_request_review_id":13931125,"id":93407646,"diff_hunk":"@@ -0,0 +1,183 @@\n+use std::cell::Cell;\n+use std::sync::atomic::{AtomicUsize, Ordering};\n+use super::internal::*;\n+use super::*;\n+use super::len::*;\n+\n+// The consumer for find_first/find_last has fake indexes representing the lower\n+// and upper bounds of the \"range\" of data it consumes. This range does not\n+// correspond to indexes from the consumed iterator but rather indicate the\n+// consumer's position relative to other consumers. The purpose is to allow a\n+// consumer to know it should stop consuming items when another consumer finds a\n+// better match.\n+\n+// An indexed consumer could specialize to use the real indexes instead, but we\n+// don't implement that for now. The only downside of the current approach is\n+// that in some cases, iterators very close to each other will have the same\n+// range and therefore not be able to stop processing if one of them finds a\n+// better match than the others.\n+\n+#[derive(Copy, Clone)]\n+enum MatchPosition {\n+    Leftmost,\n+    Rightmost,\n+}\n+\n+pub fn find_first<PAR_ITER, FIND_OP>(pi: PAR_ITER, find_op: FIND_OP) -> Option<PAR_ITER::Item>\n+    where PAR_ITER: ParallelIterator,\n+          FIND_OP: Fn(&PAR_ITER::Item) -> bool + Sync\n+{\n+    let best_found = AtomicUsize::new(usize::max_value());\n+    let consumer = FindConsumer::new(&find_op, MatchPosition::Leftmost, &best_found);\n+    pi.drive_unindexed(consumer)\n+}\n+\n+pub fn find_last<PAR_ITER, FIND_OP>(pi: PAR_ITER, find_op: FIND_OP) -> Option<PAR_ITER::Item>\n+    where PAR_ITER: ParallelIterator,\n+          FIND_OP: Fn(&PAR_ITER::Item) -> bool + Sync\n+{\n+    let best_found = AtomicUsize::new(0);\n+    let consumer = FindConsumer::new(&find_op, MatchPosition::Rightmost, &best_found);\n+    pi.drive_unindexed(consumer)\n+}\n+\n+struct FindConsumer<'f, FIND_OP: 'f> {\n+    find_op: &'f FIND_OP,\n+    lower_bound: Cell<usize>,\n+    upper_bound: usize,\n+    match_position: MatchPosition,\n+    best_found: &'f AtomicUsize,\n+}\n+\n+impl<'f, FIND_OP> FindConsumer<'f, FIND_OP> {\n+    fn new(find_op: &'f FIND_OP,\n+           match_position: MatchPosition,\n+           best_found: &'f AtomicUsize) -> Self {\n+        FindConsumer {\n+            find_op: find_op,\n+            lower_bound: Cell::new(0),\n+            upper_bound: usize::max_value(),\n+            match_position: match_position,\n+            best_found: best_found,\n+        }\n+    }\n+}\n+\n+impl<'f, ITEM, FIND_OP> Consumer<ITEM> for FindConsumer<'f, FIND_OP>\n+    where ITEM: Send,\n+          FIND_OP: Fn(&ITEM) -> bool + Sync\n+{\n+    type Folder = FindFolder<'f, ITEM, FIND_OP>;\n+    type Reducer = FindReducer;\n+    type Result = Option<ITEM>;\n+\n+    fn cost(&mut self, cost: f64) -> f64 {\n+        cost * FUNC_ADJUSTMENT\n+    }\n+\n+    fn split_at(self, _index: usize) -> (Self, Self, Self::Reducer) {\n+        let dir = self.match_position;\n+        (self.split_off(),\n+         self,\n+         FindReducer { match_position: dir })\n+    }\n+\n+    fn into_folder(self) -> Self::Folder {\n+        FindFolder {\n+            find_op: self.find_op,\n+            boundary: match self.match_position {\n+                MatchPosition::Leftmost => self.lower_bound.get(),\n+                MatchPosition::Rightmost => self.upper_bound\n+            },\n+            match_position: self.match_position,\n+            best_found: self.best_found,\n+            item: None,\n+        }\n+    }\n+\n+    fn full(&self) -> bool {\n+        let best = self.best_found.load(Ordering::Relaxed);\n+        match self.match_position {\n+            // can stop consuming if the best found index so far is *strictly*\n+            // better than anything this consumer will find\n+            MatchPosition::Leftmost => best < self.lower_bound.get(),\n+            MatchPosition::Rightmost => best > self.upper_bound\n+        }\n+    }\n+}\n+\n+impl<'f, ITEM, FIND_OP> UnindexedConsumer<ITEM> for FindConsumer<'f, FIND_OP>\n+    where ITEM: Send,\n+          FIND_OP: Fn(&ITEM) -> bool + Sync\n+{\n+    fn split_off(&self) -> Self {\n+        // Upper bound for one consumer will be lower bound for the other. This\n+        // overlap is okay, because only one of the bounds will be used for\n+        // comparing against best_found; the other is kept only to be able to\n+        // divide the range in half\n+        let old_lower_bound = self.lower_bound.get();\n+        let median = old_lower_bound + ((self.upper_bound - old_lower_bound) / 2);\n+        self.lower_bound.set(median);\n+\n+        FindConsumer {\n+            find_op: self.find_op,\n+            lower_bound: Cell::new(old_lower_bound),\n+            upper_bound: median,\n+            match_position: self.match_position,\n+            best_found: self.best_found,\n+        }\n+    }\n+\n+    fn to_reducer(&self) -> Self::Reducer {\n+        FindReducer { match_position: self.match_position }\n+    }\n+}\n+\n+struct FindFolder<'f, ITEM, FIND_OP: 'f> {\n+    find_op: &'f FIND_OP,\n+    boundary: usize,\n+    match_position: MatchPosition,\n+    best_found: &'f AtomicUsize,\n+    item: Option<ITEM>,\n+}\n+\n+impl<'f, FIND_OP: 'f + Fn(&ITEM) -> bool, ITEM> Folder<ITEM> for FindFolder<'f, ITEM, FIND_OP> {\n+    type Result = Option<ITEM>;\n+\n+    fn consume(mut self, item: ITEM) -> Self {\n+        if (self.find_op)(&item) {\n+            // This may sometimes set best_found to a worse index than it was\n+            // before, depending on timing. This means more consumers will\n+            // continue to run than necessary, but the reducer will still ensure\n+            // the correct value is returned.\n+            self.best_found.swap(self.boundary, Ordering::Relaxed);","path":"src/par_iter/find_first_last.rs","position":153,"original_position":153,"commit_id":"febc7ed7a688305cde4ac532760a3f27eeb84b69","original_commit_id":"febc7ed7a688305cde4ac532760a3f27eeb84b69","user":{"login":"nikomatsakis","id":155238,"avatar_url":"https://avatars.githubusercontent.com/u/155238?v=3","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"body":"Yes, seems like it'd be worth using a compare-exchange here. I'd probably use `compare_exchange_weak`, but that's a minor thing.","created_at":"2016-12-21T09:58:39Z","updated_at":"2016-12-21T10:03:36Z","html_url":"https://github.com/nikomatsakis/rayon/pull/189#discussion_r93407646","pull_request_url":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189","_links":{"self":{"href":"https://api.github.com/repos/nikomatsakis/rayon/pulls/comments/93407646"},"html":{"href":"https://github.com/nikomatsakis/rayon/pull/189#discussion_r93407646"},"pull_request":{"href":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189"}}},"pull_request":{"url":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189","id":98779929,"html_url":"https://github.com/nikomatsakis/rayon/pull/189","diff_url":"https://github.com/nikomatsakis/rayon/pull/189.diff","patch_url":"https://github.com/nikomatsakis/rayon/pull/189.patch","issue_url":"https://api.github.com/repos/nikomatsakis/rayon/issues/189","number":189,"state":"open","locked":false,"title":"Implement find_first/last, position_first/last","user":{"login":"schuster","id":1322248,"avatar_url":"https://avatars.githubusercontent.com/u/1322248?v=3","gravatar_id":"","url":"https://api.github.com/users/schuster","html_url":"https://github.com/schuster","followers_url":"https://api.github.com/users/schuster/followers","following_url":"https://api.github.com/users/schuster/following{/other_user}","gists_url":"https://api.github.com/users/schuster/gists{/gist_id}","starred_url":"https://api.github.com/users/schuster/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/schuster/subscriptions","organizations_url":"https://api.github.com/users/schuster/orgs","repos_url":"https://api.github.com/users/schuster/repos","events_url":"https://api.github.com/users/schuster/events{/privacy}","received_events_url":"https://api.github.com/users/schuster/received_events","type":"User","site_admin":false},"body":"Fixes #151 \r\n\r\nThis is my first PR to Rayon, so any and all feedback is welcome.","created_at":"2016-12-20T16:22:44Z","updated_at":"2016-12-21T10:03:36Z","closed_at":null,"merged_at":null,"merge_commit_sha":"90f295e7a89a048e0c7f3e2fbe7b7d78755b0d47","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189/commits","review_comments_url":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189/comments","review_comment_url":"https://api.github.com/repos/nikomatsakis/rayon/pulls/comments{/number}","comments_url":"https://api.github.com/repos/nikomatsakis/rayon/issues/189/comments","statuses_url":"https://api.github.com/repos/nikomatsakis/rayon/statuses/febc7ed7a688305cde4ac532760a3f27eeb84b69","head":{"label":"schuster:find_first","ref":"find_first","sha":"febc7ed7a688305cde4ac532760a3f27eeb84b69","user":{"login":"schuster","id":1322248,"avatar_url":"https://avatars.githubusercontent.com/u/1322248?v=3","gravatar_id":"","url":"https://api.github.com/users/schuster","html_url":"https://github.com/schuster","followers_url":"https://api.github.com/users/schuster/followers","following_url":"https://api.github.com/users/schuster/following{/other_user}","gists_url":"https://api.github.com/users/schuster/gists{/gist_id}","starred_url":"https://api.github.com/users/schuster/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/schuster/subscriptions","organizations_url":"https://api.github.com/users/schuster/orgs","repos_url":"https://api.github.com/users/schuster/repos","events_url":"https://api.github.com/users/schuster/events{/privacy}","received_events_url":"https://api.github.com/users/schuster/received_events","type":"User","site_admin":false},"repo":{"id":75347427,"name":"rayon","full_name":"schuster/rayon","owner":{"login":"schuster","id":1322248,"avatar_url":"https://avatars.githubusercontent.com/u/1322248?v=3","gravatar_id":"","url":"https://api.github.com/users/schuster","html_url":"https://github.com/schuster","followers_url":"https://api.github.com/users/schuster/followers","following_url":"https://api.github.com/users/schuster/following{/other_user}","gists_url":"https://api.github.com/users/schuster/gists{/gist_id}","starred_url":"https://api.github.com/users/schuster/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/schuster/subscriptions","organizations_url":"https://api.github.com/users/schuster/orgs","repos_url":"https://api.github.com/users/schuster/repos","events_url":"https://api.github.com/users/schuster/events{/privacy}","received_events_url":"https://api.github.com/users/schuster/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/schuster/rayon","description":"Rayon: A data parallelism library for Rust","fork":true,"url":"https://api.github.com/repos/schuster/rayon","forks_url":"https://api.github.com/repos/schuster/rayon/forks","keys_url":"https://api.github.com/repos/schuster/rayon/keys{/key_id}","collaborators_url":"https://api.github.com/repos/schuster/rayon/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/schuster/rayon/teams","hooks_url":"https://api.github.com/repos/schuster/rayon/hooks","issue_events_url":"https://api.github.com/repos/schuster/rayon/issues/events{/number}","events_url":"https://api.github.com/repos/schuster/rayon/events","assignees_url":"https://api.github.com/repos/schuster/rayon/assignees{/user}","branches_url":"https://api.github.com/repos/schuster/rayon/branches{/branch}","tags_url":"https://api.github.com/repos/schuster/rayon/tags","blobs_url":"https://api.github.com/repos/schuster/rayon/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/schuster/rayon/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/schuster/rayon/git/refs{/sha}","trees_url":"https://api.github.com/repos/schuster/rayon/git/trees{/sha}","statuses_url":"https://api.github.com/repos/schuster/rayon/statuses/{sha}","languages_url":"https://api.github.com/repos/schuster/rayon/languages","stargazers_url":"https://api.github.com/repos/schuster/rayon/stargazers","contributors_url":"https://api.github.com/repos/schuster/rayon/contributors","subscribers_url":"https://api.github.com/repos/schuster/rayon/subscribers","subscription_url":"https://api.github.com/repos/schuster/rayon/subscription","commits_url":"https://api.github.com/repos/schuster/rayon/commits{/sha}","git_commits_url":"https://api.github.com/repos/schuster/rayon/git/commits{/sha}","comments_url":"https://api.github.com/repos/schuster/rayon/comments{/number}","issue_comment_url":"https://api.github.com/repos/schuster/rayon/issues/comments{/number}","contents_url":"https://api.github.com/repos/schuster/rayon/contents/{+path}","compare_url":"https://api.github.com/repos/schuster/rayon/compare/{base}...{head}","merges_url":"https://api.github.com/repos/schuster/rayon/merges","archive_url":"https://api.github.com/repos/schuster/rayon/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/schuster/rayon/downloads","issues_url":"https://api.github.com/repos/schuster/rayon/issues{/number}","pulls_url":"https://api.github.com/repos/schuster/rayon/pulls{/number}","milestones_url":"https://api.github.com/repos/schuster/rayon/milestones{/number}","notifications_url":"https://api.github.com/repos/schuster/rayon/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/schuster/rayon/labels{/name}","releases_url":"https://api.github.com/repos/schuster/rayon/releases{/id}","deployments_url":"https://api.github.com/repos/schuster/rayon/deployments","created_at":"2016-12-02T01:12:07Z","updated_at":"2016-12-02T01:12:08Z","pushed_at":"2016-12-20T22:01:41Z","git_url":"git://github.com/schuster/rayon.git","ssh_url":"git@github.com:schuster/rayon.git","clone_url":"https://github.com/schuster/rayon.git","svn_url":"https://github.com/schuster/rayon","homepage":null,"size":1862,"stargazers_count":0,"watchers_count":0,"language":"Rust","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"nikomatsakis:master","ref":"master","sha":"e3289104903e3abc8b16e0b7effdd1368e3f1cf0","user":{"login":"nikomatsakis","id":155238,"avatar_url":"https://avatars.githubusercontent.com/u/155238?v=3","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"repo":{"id":24725038,"name":"rayon","full_name":"nikomatsakis/rayon","owner":{"login":"nikomatsakis","id":155238,"avatar_url":"https://avatars.githubusercontent.com/u/155238?v=3","gravatar_id":"","url":"https://api.github.com/users/nikomatsakis","html_url":"https://github.com/nikomatsakis","followers_url":"https://api.github.com/users/nikomatsakis/followers","following_url":"https://api.github.com/users/nikomatsakis/following{/other_user}","gists_url":"https://api.github.com/users/nikomatsakis/gists{/gist_id}","starred_url":"https://api.github.com/users/nikomatsakis/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nikomatsakis/subscriptions","organizations_url":"https://api.github.com/users/nikomatsakis/orgs","repos_url":"https://api.github.com/users/nikomatsakis/repos","events_url":"https://api.github.com/users/nikomatsakis/events{/privacy}","received_events_url":"https://api.github.com/users/nikomatsakis/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/nikomatsakis/rayon","description":"Rayon: A data parallelism library for Rust","fork":false,"url":"https://api.github.com/repos/nikomatsakis/rayon","forks_url":"https://api.github.com/repos/nikomatsakis/rayon/forks","keys_url":"https://api.github.com/repos/nikomatsakis/rayon/keys{/key_id}","collaborators_url":"https://api.github.com/repos/nikomatsakis/rayon/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/nikomatsakis/rayon/teams","hooks_url":"https://api.github.com/repos/nikomatsakis/rayon/hooks","issue_events_url":"https://api.github.com/repos/nikomatsakis/rayon/issues/events{/number}","events_url":"https://api.github.com/repos/nikomatsakis/rayon/events","assignees_url":"https://api.github.com/repos/nikomatsakis/rayon/assignees{/user}","branches_url":"https://api.github.com/repos/nikomatsakis/rayon/branches{/branch}","tags_url":"https://api.github.com/repos/nikomatsakis/rayon/tags","blobs_url":"https://api.github.com/repos/nikomatsakis/rayon/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/nikomatsakis/rayon/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/nikomatsakis/rayon/git/refs{/sha}","trees_url":"https://api.github.com/repos/nikomatsakis/rayon/git/trees{/sha}","statuses_url":"https://api.github.com/repos/nikomatsakis/rayon/statuses/{sha}","languages_url":"https://api.github.com/repos/nikomatsakis/rayon/languages","stargazers_url":"https://api.github.com/repos/nikomatsakis/rayon/stargazers","contributors_url":"https://api.github.com/repos/nikomatsakis/rayon/contributors","subscribers_url":"https://api.github.com/repos/nikomatsakis/rayon/subscribers","subscription_url":"https://api.github.com/repos/nikomatsakis/rayon/subscription","commits_url":"https://api.github.com/repos/nikomatsakis/rayon/commits{/sha}","git_commits_url":"https://api.github.com/repos/nikomatsakis/rayon/git/commits{/sha}","comments_url":"https://api.github.com/repos/nikomatsakis/rayon/comments{/number}","issue_comment_url":"https://api.github.com/repos/nikomatsakis/rayon/issues/comments{/number}","contents_url":"https://api.github.com/repos/nikomatsakis/rayon/contents/{+path}","compare_url":"https://api.github.com/repos/nikomatsakis/rayon/compare/{base}...{head}","merges_url":"https://api.github.com/repos/nikomatsakis/rayon/merges","archive_url":"https://api.github.com/repos/nikomatsakis/rayon/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/nikomatsakis/rayon/downloads","issues_url":"https://api.github.com/repos/nikomatsakis/rayon/issues{/number}","pulls_url":"https://api.github.com/repos/nikomatsakis/rayon/pulls{/number}","milestones_url":"https://api.github.com/repos/nikomatsakis/rayon/milestones{/number}","notifications_url":"https://api.github.com/repos/nikomatsakis/rayon/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/nikomatsakis/rayon/labels{/name}","releases_url":"https://api.github.com/repos/nikomatsakis/rayon/releases{/id}","deployments_url":"https://api.github.com/repos/nikomatsakis/rayon/deployments","created_at":"2014-10-02T15:38:05Z","updated_at":"2016-12-20T14:40:25Z","pushed_at":"2016-12-21T09:47:15Z","git_url":"git://github.com/nikomatsakis/rayon.git","ssh_url":"git@github.com:nikomatsakis/rayon.git","clone_url":"https://github.com/nikomatsakis/rayon.git","svn_url":"https://github.com/nikomatsakis/rayon","homepage":null,"size":1924,"stargazers_count":687,"watchers_count":687,"language":"Rust","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":true,"forks_count":56,"mirror_url":null,"open_issues_count":31,"forks":56,"open_issues":31,"watchers":687,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189"},"html":{"href":"https://github.com/nikomatsakis/rayon/pull/189"},"issue":{"href":"https://api.github.com/repos/nikomatsakis/rayon/issues/189"},"comments":{"href":"https://api.github.com/repos/nikomatsakis/rayon/issues/189/comments"},"review_comments":{"href":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189/comments"},"review_comment":{"href":"https://api.github.com/repos/nikomatsakis/rayon/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/nikomatsakis/rayon/pulls/189/commits"},"statuses":{"href":"https://api.github.com/repos/nikomatsakis/rayon/statuses/febc7ed7a688305cde4ac532760a3f27eeb84b69"}}}}
{"actor":{"display_login":"nikomatsakis"}}