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 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.
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.
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?
Just to clear, the "negative index scheme", will allow free() to take
the size argument.
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.
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`.
We "negative index scheme" does not require you to drop excess capacity.
With this scheme,
~[T] and Vec<T> would contain the same amount info. The only difference
is that in ~[T], the
capacity is stored at a negative index. In Vec<T>, capacity is stored,
both inline and at the negative
index.
The only overhead would be a couple of checks/additions during
allocation/deallocation. Everything
else would perform exactly as it does now.
Manu
_______________________________________________
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
