vec::from_elem with primitives should be as fast as calloc

[erickt]

While @cmr landed a nice optimization of vec::from_elem in #6876, he said that it's still not performing as fast as doing a malloc and a ptr::set_memory. We should figure out why it is not performing as well as it should be and fix it in order to remove the temptation of using the faster unsafe functions.

[erickt]

It turns out this is substantially slower than I expected. With this test benchmark:

extern mod extra;

use std::vec;
use std::ptr;

#[bench]
fn bench_from_elem(b: &mut extra::test::BenchHarness) {
    do b.iter {
        let v: ~[u8] = vec::from_elem(1024, 0u8);
    }
}

#[bench]
fn bench_set_memory(b: &mut extra::test::BenchHarness) {
    do b.iter {
        let mut v: ~[u8] = vec::with_capacity(1024);
        unsafe {
            let vp = vec::raw::to_mut_ptr(v);
            ptr::set_memory(vp, 0, 1024);
            vec::raw::set_len(&mut v, 1024);
        }
    }
}

fn main() {}

I'm getting these results:

running 2 tests
test bench_from_elem ... bench: 16351 ns/iter (+/- 192)
test bench_set_memory ... bench: 384 ns/iter (+/- 6)

This is related to #6623 and #7137.

[erickt]

@huonw mentioned in irc that with -O the difference is:

test bench_from_elem ... bench: 799 ns/iter (+/- 0)
test bench_set_memory ... bench: 200 ns/iter (+/- 0)

Which is much better, but still not great.

[emberian]

memset "cheats" with sse. from_elem spends a lot of time in move_val_init without optimizations so there's a bunch of unnecessary function calls. With optimizations, the thing that's killing it is the copies.

[thestinger]

LLVM knows how to optimize loops to the same code as memcpy/memmove/memset though, as long as you generate good IR.

http://llvm.org/docs/doxygen/html/LoopIdiomRecognize_8cpp_source.html

[luqmana]

I added a bench for the literal vec repeat syntax as well:

#[bench]
fn bench_vec_repeat(b: &mut extra::test::BenchHarness) {
    do b.iter {
        let v: ~[u8] = ~[0u8, ..1024];
    }
}

Without optimizations:

running 3 tests
test bench_from_elem ... bench: 21803 ns/iter (+/- 597)
test bench_set_memory ... bench: 381 ns/iter (+/- 6)
test bench_vec_repeat ... bench: 2125 ns/iter (+/- 12)

With optimizations (-O):

running 3 tests
test bench_from_elem ... bench: 752 ns/iter (+/- 0)
test bench_set_memory ... bench: 183 ns/iter (+/- 0)
test bench_vec_repeat ... bench: 90 ns/iter (+/- 3)

Looking at the optimized IR, both set_memory and vec_repeat become a memset but set_memory seems to have a lot more overhead. from_elem does not become a memset hence the bad results.

[thestinger]

@erickt: this gets a lot better with the optimization passes from #7466, from ~3x as slow to ~2x as slow

Before (opt-level=2):

test bench_from_elem ... bench: 986 ns/iter (+/- 3)
test bench_set_memory ... bench: 343 ns/iter (+/- 3)
test bench_vec_repeat ... bench: 175 ns/iter (+/- 3)

After (opt-level=2)

test bench_from_elem ... bench: 667 ns/iter (+/- 0)
test bench_set_memory ... bench: 343 ns/iter (+/- 0)
test bench_vec_repeat ... bench: 178 ns/iter (+/- 0)

[thestinger]

@luqmana: the problem is with the code bloat from the surrounding code, rather than set_memory itself - I think we actually produce some IR there with undefined behaviour

[thestinger]

#7682 greatly speeds up with_capacity, fixing half of the issue

Before:

test bench_from_elem ... bench: 683 ns/iter (+/- 3)
test bench_set_memory ... bench: 334 ns/iter (+/- 3)
test bench_vec_repeat ... bench: 176 ns/iter (+/- 0)

After:

test bench_from_elem ... bench: 461 ns/iter (+/- 0)
test bench_set_memory ... bench: 143 ns/iter (+/- 0)
test bench_vec_repeat ... bench: 148 ns/iter (+/- 0)

[thestinger]

The performance of all 3 has improved, but from_elem got slower relative to the others:

test bench_from_elem ... bench: 409 ns/iter (+/- 4)
test bench_set_memory ... bench: 83 ns/iter (+/- 1)
test bench_vec_repeat ... bench: 84 ns/iter (+/- 3)

[thestinger]

It looks like the remaining issue is our pointer arithmetic being slow. The offset and mut_offset functions compile to conversions to and from integers, rather than actual pointer arithmetic with the stricter semantics. I think we need to make the + and - implementations for pointers a compiler feature.

[thestinger]

Fixed by #8121.

test bench_from_elem ... bench: 84 ns/iter (+/- 1)
test bench_set_memory ... bench: 84 ns/iter (+/- 3)
test bench_vec_repeat ... bench: 84 ns/iter (+/- 2)