Skip to content
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

Implement missing specializations on the PutBack adaptor and on the MergeJoinBy Iterator #372

Merged

Conversation

Ten0
Copy link
Contributor

@Ten0 Ten0 commented Sep 28, 2019

Resolves #371

count, last and nth of the MergeJoinBy iterator are made faster when one of the iterators is completely consumed by directly calling the methods of the underlying only iterator left (there is benefit if the underlying iterator also specialized these methods).

This is in particular useful when you want to count the number of different elements in the union of two sorted known-size iterators (count).

Those methods are also specialized on the PutBack adaptor for the same performance reasons.
The nth specialization on the MergeJoinBy iterator depends on the nth specialization on the PutBack adaptor working.

@Ten0 Ten0 changed the title Implement missing specializations on the MergeJoinBy Iterator Implement missing specializations on the MergeJoinBy Iterator & PutBack adaptor Sep 28, 2019
@Ten0 Ten0 changed the title Implement missing specializations on the MergeJoinBy Iterator & PutBack adaptor Implement missing specializations on the PutBack adaptor and on the MergeJoinBy Iterator Sep 28, 2019
src/adaptors/mod.rs Outdated Show resolved Hide resolved
@Ten0 Ten0 force-pushed the merge_join_by_missing_specializations branch 2 times, most recently from cb71c58 to c6a2ce1 Compare September 28, 2019 19:32
@jswrenn
Copy link
Member

jswrenn commented Sep 30, 2019

@Ten0 Could you add some quickcheck tests to ensure the specializations match the unspecialized behavior exactly? An unspecialized wrapper iterator is useful for these sorts of tests:

struct Unspecialized<I>(I);
impl<I> Iterator for Unspecialized<I>
where I: Iterator
{
type Item = I::Item;
#[inline(always)]
fn next(&mut self) -> Option<I::Item> {
self.0.next()
}
#[inline(always)]
fn size_hint(&self) -> (usize, Option<usize>) {
self.0.size_hint()
}
}

They were missing and did hurt the MergeJoinBy performance improvement on the `nth` method because we couldn't borrow iter without exposing new interfaces or using something like the `take_mut` crate.
@Ten0 Ten0 force-pushed the merge_join_by_missing_specializations branch 5 times, most recently from b670bb6 to d62e946 Compare November 1, 2019 01:32
@Ten0
Copy link
Contributor Author

Ten0 commented Nov 1, 2019

Well it did take quite some time to implement these, especially with Rust 1.24 compatibility, but at least now we've got a pretty reusable framework for testing any other specialization set we'd want to test on any Iterator.

This is also rebased on master.

@Ten0 Ten0 force-pushed the merge_join_by_missing_specializations branch from d62e946 to b13e35f Compare November 1, 2019 01:40
@Ten0
Copy link
Contributor Author

Ten0 commented Nov 8, 2019

Hello,
I'm still waiting for a merge here now that I have spent the time to implement the tests.

@jswrenn
Copy link
Member

jswrenn commented Nov 8, 2019

Thank you for your contribution and patience! Unfortunately, I'm tied up with preparing for my dissertation proposal for the next couple weeks and can't thoroughly review this yet. I'll review as soon as possible.

tests/specializations.rs Outdated Show resolved Hide resolved
tests/specializations.rs Outdated Show resolved Hide resolved
@Ten0 Ten0 requested a review from jswrenn December 26, 2019 13:39
@jswrenn
Copy link
Member

jswrenn commented Jan 1, 2020

Thanks!

bors r+

@jswrenn jswrenn added this to the next milestone Jan 1, 2020
@bors
Copy link
Contributor

bors bot commented Jan 1, 2020

Merge conflict

…sing_specializations

# Conflicts:
#	src/merge_join.rs
@jswrenn
Copy link
Member

jswrenn commented Jan 31, 2020

bors r+

bors bot added a commit that referenced this pull request Jan 31, 2020
372: Implement missing specializations on the PutBack adaptor and on the MergeJoinBy Iterator r=jswrenn a=Ten0

Resolves #371

`count`, `last` and `nth` of the `MergeJoinBy` iterator are made faster when one of the iterators is completely consumed by directly calling the methods of the underlying only iterator left (there is benefit if the underlying iterator also specialized these methods).

This is in particular useful when you want to count the number of different elements in the union of two sorted known-size iterators (`count`).

Those methods are also specialized on the `PutBack` adaptor for the same performance reasons.
The `nth` specialization on the `MergeJoinBy` iterator depends on the `nth` specialization on the `PutBack` adaptor working.

Co-authored-by: Thomas BESSOU <thomas.bessou@hotmail.fr>
@bors
Copy link
Contributor

bors bot commented Jan 31, 2020

Build failed

@jswrenn
Copy link
Member

jswrenn commented Jan 31, 2020

@orium Any idea what's going on with this build failure: https://travis-ci.org/rust-itertools/itertools/builds/644492455

It appears to be related to a criterion dependency.

@Ten0
Copy link
Contributor Author

Ten0 commented Feb 21, 2020

Maybe we can try this again?

@jswrenn
Copy link
Member

jswrenn commented Feb 21, 2020

bors r+

@bors
Copy link
Contributor

bors bot commented Feb 22, 2020

Build succeeded

@bors bors bot merged commit e7ebc13 into rust-itertools:master Feb 22, 2020
@Ten0 Ten0 deleted the merge_join_by_missing_specializations branch December 2, 2020 17:40
@Ten0 Ten0 restored the merge_join_by_missing_specializations branch December 2, 2020 17:44
@Ten0 Ten0 deleted the merge_join_by_missing_specializations branch December 2, 2020 17:46
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

MergeJoinBy should specialize more of Iterator
3 participants