Skip to content

treemap's lazy iterator needs to be optimized #4763

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

Closed
thestinger opened this issue Feb 2, 2013 · 1 comment
Closed

treemap's lazy iterator needs to be optimized #4763

thestinger opened this issue Feb 2, 2013 · 1 comment

Comments

@thestinger
Copy link
Contributor

Going back to the old way isn't currently possible (without multiple lifetime parameters), but it's currently doing implicit copies of the pointer stack with every iteration which should be fixable.

@nikomatsakis
Copy link
Contributor

Strictly speaking multiple lifetime parameters are not required to use a more traditional iterator. However, the current handling of the self region is problematic. Here is a proof of concept that I got to compile, but it doesn't work with impls because they always conflate the self region with the lifetime parameter. This is actually a known issue I plan to address, I will open a bug describing it.

The key point is that the next() function does not use the same lifetime for the &mut Iterator pointer as for its contents:

fn next<T>(iter: &mut Iterator/&a<T>) -> bool {
    iter.index += 1; // Relies on rollover
    iter.index < iter.vector.len()
}

Note: I changed the iterator protocol here to use a bool return on next() rather than returning an Option from get. This is not necessary, it was to see which style I preferred. Probably best, ultimately, would be to offer two methods or something like that.

extern mod std;

use std::treemap;

struct Iterator<T> {
    vector: &[T],
    index: uint
}

fn iter<T>(v: &v/[T]) -> Iterator/&v<T> {
    Iterator {vector: v, index: uint::max_value}
}

fn next<T>(iter: &mut Iterator/&a<T>) -> bool {
    iter.index += 1; // Relies on rollover
    iter.index < iter.vector.len()
}

fn get<T>(iter: &v/Iterator<T>) -> &v/T {
    &iter.vector[iter.index]
}

fn is_disjoint(t1: &[int], t2: &[int]) -> bool {
    let mut x = iter(t1);
    let mut y = iter(t2);

    if !next(&mut x) { return true; }
    if !next(&mut y) { return true; }

    loop {
        let advance_x = {
            let a = get(&x);
            let b = get(&y);
            if *a < *b {
                true
            } else if *b < *a {
                false
            } else {
                return false;
            }
        };

        if advance_x {
            if !next(&mut x) {
                return true;
            }
        } else if !next(&mut y) {
            return true;
        }
    }
}

fn main() {
    assert is_disjoint([1, 3, 5], [2, 4, 6]);
    assert !is_disjoint([1, 3, 5], [2, 4, 5]);
    assert is_disjoint([], []);
    assert is_disjoint([1, 2], []);
    assert is_disjoint([], [1, 2]);
}

bors added a commit that referenced this issue Feb 7, 2013
5283a8b reworks the TreeMap lazy iterator to use `&mut` again, which closes #4763. It gets the performance of the set methods back in the same ballpark that it was pre-INHTWAMA which is nice. These can be turned back into methods eventually.

e5b6334 removes the transitional smallintmap attributes which closes #4737.
@graydon graydon closed this as completed in 37e9986 Feb 7, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants