port from ~[T] to Vec<T>

[thestinger]

Annoying issues, but not hard blockers:

• split Index into Index, IndexMut and IndexAssign
• make Vec implement the slice methods
• Constructing an iterator from a slice doesn't optimise completely

This is a significant performance improvement for any vectors that are grown, and will reduce heap allocation since zero-length vectors do not allocate and it does not have a header.

test bench::old_push              ... bench:     43200 ns/iter (+/- 804)
test bench::old_push_preallocated ... bench:     42948 ns/iter (+/- 4043)
test bench::push                  ... bench:      7190 ns/iter (+/- 245)
test bench::push_preallocated     ... bench:      6606 ns/iter (+/- 170)

#[cfg(test)]
extern mod extra;

#[cfg(test)]
mod bench {
    use std;
    use std::vec_ng::Vec;
    use extra::test::BenchHarness;

    static size: uint = 10000;

    #[bench]
    fn push(bh: &mut BenchHarness) {
        bh.iter(|| {
            let mut xs = Vec::with_capacity(16);
            for i in range(0, size) {
                xs.push(i);
            }
        });
    }

    #[bench]
    fn old_push(bh: &mut BenchHarness) {
        bh.iter(|| {
            let mut xs = std::vec::with_capacity(16);
            for i in range(0, size) {
                xs.push(i);
            }
        });
    }

    #[bench]
    fn push_preallocated(bh: &mut BenchHarness) {
        bh.iter(|| {
            let mut xs = Vec::with_capacity(size);
            for i in range(0, size) {
                xs.push(i);
            }
        });
    }

    #[bench]
    fn old_push_preallocated(bh: &mut BenchHarness) {
        bh.iter(|| {
            let mut xs = std::vec::with_capacity(size);
            for i in range(0, size) {
                xs.push(i);
            }
        });
    }
}

I moved the priority tag here from the old issue, as this is the same core issue but without the distractions of past issues and discussions that are no longer relevant.

[pnkfelix]

cc me

[alexcrichton]

The P- tags need to be added through the triage meeting, not manually, removing for now.

[alexcrichton]

(also nominating)

[thestinger]

@alexcrichton: The P- tag was already on this issue. I just closed the old one instead of heavily editing it and making the comments there irrelevant. If it's going to have to go through a meeting again, I'll just close this and edit the old one.

[alexcrichton]

Oh sorry, I should have read the issue more closely!

[nikomatsakis]

cc me

[aturon]

cc me

[thestinger]

Keeping this metabug around no longer makes sense, since the blockers didn't actually end up blocking it.