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.

Sign up for GitHub

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

Jump to bottom

make the vector iterator use GEP, not ptrtoint + add + inttoptr #8212

Closed
thestinger opened this issue Aug 2, 2013 · 0 comments
Closed

make the vector iterator use GEP, not ptrtoint + add + inttoptr #8212

thestinger opened this issue Aug 2, 2013 · 0 comments
Labels
I-slow Issue: Problems and improvements with respect to performance of generated code.

Comments

@thestinger
Copy link
Contributor

LLVM is currently incapable of analysing the alias implications of these conversions despite a set of rules being defined for them, so they're an opaque wall blocking optimizations. I fixed the offset family of functions in the ptr module but vectors are a bit problematic.

Vector iterators use a pointer to the start and a pointer one byte past the end, so an iteration of the loop is just an increment (or decrement, in reverse) of a pointer and a comparison between the start and end.

Since zero-size types can be stored in vectors, it currently uses nonzero_size_of to increment the pointer instead of the optimized offset functions - otherwise iterating of a vector of 11 zero-size types would stop immediately instead of looping 11 times. This can likely be fixed by special-casing the iterator for zero-size types.
@huonw huonw mentioned this issue Aug 2, 2013
Closed
huonw added a commit to huonw/rust that referenced this issue Aug 2, 2013
@huonw
std: use ptr.offset where possible in the vec iterator.
076468f 
Closes rust-lang#8212.
bors added a commit that referenced this issue Aug 2, 2013
@bors
auto merge of #8225 : huonw/rust/vec-iter, r=graydon
a461776 
Closes #8212.

Before:

```llvm
%sum.028 = phi i64 [ %23, %match_else ], [ 0, %"normal return" ]
%.sroa.0.027 = phi i64* [ %21, %match_else ], [ %12, %"normal return" ]
%19 = ptrtoint i64* %.sroa.0.027 to i64
%20 = add i64 %19, 8
%21 = inttoptr i64 %20 to i64*
%22 = load i64* %.sroa.0.027, align 8
%23 = add i64 %22, %sum.028
%24 = inttoptr i64 %20 to %"enum.std::libc::types::common::c95::c_void[#1]"*
%25 = icmp eq %"enum.std::libc::types::common::c95::c_void[#1]"* %24, %16
%26 = icmp eq i64 %20, 0
%or.cond = or i1 %25, %26
```

```
test vec::bench::iterator ... bench: 87 ns/iter (+/- 7)
test vec::bench::mut_iterator ... bench: 87 ns/iter (+/- 10)
```

After:

```llvm
%sum.028 = phi i64 [ %21, %match_else ], [ 0, %"normal return" ]
%.sroa.0.027 = phi i64* [ %19, %match_else ], [ %12, %"normal return" ]
%19 = getelementptr i64* %.sroa.0.027, i64 1
%20 = load i64* %.sroa.0.027, align 8
%21 = add i64 %20, %sum.028
%22 = bitcast i64* %19 to %"enum.std::libc::types::common::c95::c_void[#1]"*
%23 = icmp eq %"enum.std::libc::types::common::c95::c_void[#1]"* %22, %16
%24 = icmp eq i64* %19, null
%or.cond = or i1 %23, %24
```

```
test vec::bench::iterator ... bench: 79 ns/iter (+/- 8)
test vec::bench::mut_iterator ... bench: 78 ns/iter (+/- 2)
```

(NB. I'm not 100% sure the benchmarks were set-up correctly, so take them with a grain of salt.)
huonw added a commit to huonw/rust that referenced this issue Aug 3, 2013
@huonw
std: use ptr.offset where possible in the vec iterator.
590c892 
Closes rust-lang#8212.
@huonw huonw closed this as completed in fbb7cd3 Aug 3, 2013
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
I-slow Issue: Problems and improvements with respect to performance of generated code.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

std: use ptr.offset where possible in the vec iterator. huonw/rust
1 participant
@thestinger