Most of your comments below do not apply to a properly implemented
negative index scheme.
So, it seems clear to me, that I haven't been able to get it across to you.
I guess we can both agree that spending more time on this thread is
unproductive, especially
since the real question is whether we would *want* to have ~[T] used.
Thank you for your time.
Manu
On 04/04/2014 05:09 PM, Daniel Micay wrote:
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.
--
Manu Thambi
Mesh Capital, LLC
201-918-4202
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
