On 04/04/14 04:12 PM, Manu Thambi wrote: > > On 04/04/2014 02:51 PM, Daniel Micay wrote: >> >> 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. > > In the "negative index scheme", the length and capacity in the Vec would > be identical > to what is it in the current implementation. Hence the code will be > identical, except > for while allocating/deallocatiing. (ie, push() would have the same > performance)
It won't have the same performance, because the performance hit comes from the code size increase needed to handle offsetting and overflow checking along with aliasing issues. It was slow because a header involves offsets and overflow checks. It also screws up the alias analysis. The negative index solution suffers from this almost as much as the old vector representation. I feel I've made the reasons why it's slower clear and you simply don't believe what I said. The performance gains from removing the header from vectors weren't imaginary. Even a better implementation than the one in `std::slice` is still slower. >> 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. > I don't understand what addition you mean? The only time you need the > size stored in the negative index > is to call dealloc. > > You absolutely can pass size into dealloc while destructing ~[T]. Just > use the size, stored in the negative index. You can pass it for the negative index proposal, but not the other proposals. The negative index proposal involves bloating the `Vec<T>` type to micro-optimize what is going to be an incredibly rare conversion, while the other proposals lose the ability to pass the length. I don't see a valid reason to change the status quo. >> 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 will be a no-op, if you use null (0) to indicate 0-capacity, and > special value(1?) to indicate > Option::None. You can't use a special value to indicate None without adding a lang item, no other pointer values are specified by Rust or LLVM as being invalid. >> 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. > Can you name one architecture, where we are not able to find a single > extra invalid virtual address > other than 0? Whether or not *I* can name such an architecture doesn't matter. Rust is meant to be a portable language, even to platforms this specific contributor is not familiar with. This would add a dependency on global variables for unique pointers, even though you could implement them on in an environment with only a stack using a fixed-size pool. > Just to clear, the "negative index scheme", will allow free() to take > the size argument. I'm talking about all of the proposed solutions such as the ones at the end of your message in isolation from the proposal to require `Vec<T>` to have a header (not going to happen). >>> 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. > > No it wouldn't. Vec, doesn't have to check the pointer. Just check the > capacity. Checking the capacity is a branch. > The only overhead would be a couple of checks/additions during > allocation/deallocation. Everything > else would perform exactly as it does now. It will cause `push` to perform worse than it does now and it will cause `Vec<T>` to allocate more memory. All to micro-optimize a conversion to a nearly useless type. I've made it clear why adding headers to vectors decreases the performance. You clearly don't believe me and I won't be wasting my time on this thread anymore.
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
