On 04/04/14 01:50 PM, Manu Thambi wrote: > > As Nathan mentioned, the capacity is stored at a negative offset to the > pointer to the heap.
Storing at a negative index removes the cost at indexing, but not elsewhere. It still consumes more memory and makes `push` slower, especially since it has to do more than more offset based on alignment with at least one overflow check. > So the Vec code should be identical, except that during > allocation/re-allocation, we need > to compute the heap pointer by adding sizeof(uint) to the value returned > by malloc(). > (and the opposite computation on free()) > > indexing, etc, will not change, from how it is done now. It has to check for overflow on any addition like this. The inability to pass a size to `dealloc` is not going to be free either. Teaching LLVM to understand the pointer gymnastics here means trying to make it simpler rather than allowing it to become more complicated. >> Passing vectors around by-value isn't a common operation. In the >> common case, functions operate on mutable or immutable borrowed >> slices. In uncommon cases, they operator on `&mut Vec<T>` in order to >> change the length in place. There are rare cases when ownership needs >> to be moved, but it's rare for it not to correspond by a constant >> factor to the number of allocations. > > I agree that passing around Vec by value is uncommon. But you seem to be > concerned about > Vec<T> -> ~[T] performance, which should also be a rare transfer of > ownership. I'm not at all concerned about it. I think it would be a huge mistake to use `~[T]` frequently at all, and I'm simply pointing out that this is not going to be a no-op because that claim was made several times. >> I've already implemented support for this in the compiler some time ago >> and the library portion is now in master. This means it's invalid to >> call exchange_free on an allocation with a zero size capacity, so slices >> need to track whether the allocation is zero size. A zero size length >> does not imply a zero size capacity unless `Vec<T>` -> `~[T]` is not a >> no-op, which is what I am saying. Commits: >> >> 1778b6361627c5894bf75ffecf427573af02d390 >> 898669c4e203ae91e2048fb6c0f8591c867bccc6 > > I understand that we cannot call free with a zero size/capacity. > > There are three possibilities: > > a) Use the special pointer value to represent Option::None. The Vec<T> > -> ~[T] would be a no-op. An empty vector is not the same as `None`. Reserving an address is also not possible in all environments Rust is going to be used in as a language, and I think it should be up to the allocator implementation rather than hard-coded knowledge in the compiler. At the moment, the `Some(~())` problem is fixed with no overhead anywhere, and allocators have the choice between a sentinel and clamping zero-size allocations to 1. > b) If that makes implementation of Option complicated, then use the > special pointer value to represent > a zero capacity. We can use that special value in Vec<T> as well, even > though it is not needed. This > will keep Vec<T> -> ~[T] a no-op. This will add a branch to every deallocation call. > c) Conversion between Vec<T> -> ~[T] is not likely to be common. So, > doing an additional check is okay? It's not about there being an additional check. It's about it having to drop excess capacity, which will make conversions to and from `~[T]` hurt. This can easily result in higher time complexity rather than just a constant factor slowdown. I don't think conversion from `Vec<T>` -> `~[T]` is important, and I just want to make it clear that there's no way it is going to be free. The cost can not simply be hand-waved away by moving it elsewhere, such as requiring new branches and losing the ability to pass a size to `dealloc`.
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
