Re: [rust-dev] Tagged integral floating-point types
Okay. But first I'd like to get some input on for what types T should the language guarantee this suggested optimization for OptionT. Because the optimization could be done for any type T from which at least one or more of these new primitive data types is accessible. But it's not clear whether or not it should be done if accessing one of those has to go through one or more indirections. I assume that if at least one of these new primitive data types can be accessed through T without any indirections, then it always makes sense to do this optimization. On 2014-04-04, at 03:37, Corey Richardson co...@octayn.net wrote: Language suggestions should go through our new RFC process: https://github.com/rust-lang/rfcs/blob/master/active/0001-rfc-process.md On Thu, Apr 3, 2014 at 8:26 PM, Tommi rusty.ga...@icloud.com wrote: I forgot to mention that this same space-optimization could be done for Optionbool already. On 2014-04-04, at 03:18, Tommi rusty.ga...@icloud.com wrote: I have a suggestion. Let's add new primitive data types: i7, i15, i31, i63, u7, u15, u31, u63, f31 and f63 Those would behave exactly like the integral data and floating-point data types: i8, i16, i32, i64, u8, u16, u32, u64, f32 and f64 ...except that the new data types would come with the (unchecked) promise that the high-order bit of each of those new data types' representations would never be set to 1 (with the floating-point types it would be the high-order bit of the exponent). That would reduce the range of values the user is supposed to represent with those types. But the new types would give rise to an optimization for OptionX, where X is one of the new primitive data types: OptionX wouldn't need to use extra memory for a separate tag, but could simply use the high-order bit as a tag to indicate the None case. If a user assigns a value which sets the high-order bit of those data types, then it would be considered a logical overflow (even though the actually representation hasn't overflown) and Some(x) where x is such a logical overflown value would be None (which, to me, kind of makes sense). ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev -- http://octayn.net/ ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] A More Detailed Tour of the Rust Compiler
Hey folks, I took the slides from my talk at last week's PDX-Rust meetup slapped together a blog post that covers some of the innards of the Rust compiler in a little more detail: http://tomlee.co/2014/04/03/a-more-detailed-tour-of-the-rust-compiler/ It kind of reads somewhere between a high level overview and a detailed look at compiler innards, but hopefully it's useful to somebody out there. Cheers, Tom -- *Tom Lee */ http://tomlee.co / @tglee http://twitter.com/tglee ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Tagged integral floating-point types
Regarding the original idea: Why use a whole bit, when you only need one
value out of all possible type's values? For example, for floats, one of
the NaNs could be used for this purpose without any issues with overflow as
would happen in your proposal.
Regarding which types?: Perhaps this should be controlled via another
built-in trait, such as the following:
trait Invalid {
fn invalid() - Self;
}
The compiler could then perform option space optimization for any type
implementing 'Invalid'.
On Fri, Apr 4, 2014 at 12:13 AM, Tommi rusty.ga...@icloud.com wrote:
Okay. But first I'd like to get some input on for what types T should the
language guarantee this suggested optimization for OptionT. Because the
optimization could be done for any type T from which at least one or more
of these new primitive data types is accessible. But it's not clear whether
or not it should be done if accessing one of those has to go through one or
more indirections. I assume that if at least one of these new primitive
data types can be accessed through T without any indirections, then it
always makes sense to do this optimization.
On 2014-04-04, at 03:37, Corey Richardson co...@octayn.net wrote:
Language suggestions should go through our new RFC process:
https://github.com/rust-lang/rfcs/blob/master/active/0001-rfc-process.md
On Thu, Apr 3, 2014 at 8:26 PM, Tommi rusty.ga...@icloud.com wrote:
I forgot to mention that this same space-optimization could be done for
Optionbool already.
On 2014-04-04, at 03:18, Tommi rusty.ga...@icloud.com wrote:
I have a suggestion. Let's add new primitive data types:
i7, i15, i31, i63, u7, u15, u31, u63, f31 and f63
Those would behave exactly like the integral data and floating-point
data types:
i8, i16, i32, i64, u8, u16, u32, u64, f32 and f64
...except that the new data types would come with the (unchecked)
promise that the high-order bit of each of those new data types'
representations would never be set to 1 (with the floating-point types it
would be the high-order bit of the exponent). That would reduce the range
of values the user is supposed to represent with those types. But the new
types would give rise to an optimization for OptionX, where X is one of
the new primitive data types: OptionX wouldn't need to use extra memory
for a separate tag, but could simply use the high-order bit as a tag to
indicate the None case. If a user assigns a value which sets the high-order
bit of those data types, then it would be considered a logical overflow
(even though the actually representation hasn't overflown) and Some(x)
where x is such a logical overflown value would be None (which, to me, kind
of makes sense).
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
--
http://octayn.net/
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] matching on a few bits in int
I've submitted an RFC for this one:
https://github.com/rust-lang/rfcs/pull/29
On Sat, Mar 29, 2014 at 6:14 PM, Bill Myers bill_my...@outlook.com wrote:
I think the best solution is to add uN and sN types where N is not a power
of two, which LLVM should already support.
Then you can write your match like this:
match (val 6) as u2
{
...
}
And it will work as desired.
Biggest issue is that to make it work nicely you'd need to add some way to
generalize over the bit-length and integers, and that's going to require
generics with int parameters and work to add those.
--
Sincerely,
Vladimir Farcaller Pouzanov
http://farcaller.net/
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
On 03/04/14 11:48 PM, Nathan Myers wrote: Perhaps the best thing is to wait a month (or two or three) until DST is more of a reality and then see how we feel. Are you thinking we should also wait before converting the current uses of ~[T] to VecT? Doing the migration gives us the performance[1] and zero-length-zero-alloc benefits, but there were some concerns about additional library churn if we end up converting back to DST's ~[T]. I can't speak about how a usage choice affects the standard library, but it seems worth mentioning that vector capacity doesn't have to be in the base object; it can live in the secondary storage, prepended before the elements. Needing to use a header seriously hurts the performance. The new vector is 7x faster at pushing elements when space isn't reserved compared to the old one, all due to leaving off the length/capacity header. The overhead would be less if it stored the capacity inside *and* outside the vector, but it's still overhead. It's an extra overflow check branch along with needing to calculate padding for alignment in the future, extra space in the memory allocation and more pointer aliasing issues. A zero-length VecT might be null for the case of zero capacity, or non-null when it has room to grow. It's going to be forbidden from actually being null in the future when the Option-like enum optimization is applied to it via an attribute. This work has already landed - calling exchange_free on a zero-size allocation is *forbidden*. signature.asc Description: OpenPGP digital signature ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Tagged integral floating-point types
On 04 Apr 2014, at 12:30, Vadim Chugunov vadi...@gmail.com wrote:
Regarding the original idea: Why use a whole bit, when you only need one
value out of all possible type's values? For example, for floats, one of
the NaNs could be used for this purpose without any issues with overflow as
would happen in your proposal.
Yes, you're quite right.
Regarding which types?: Perhaps this should be controlled via another
built-in trait, such as the following:
trait Invalid {
fn invalid() - Self;
}
The compiler could then perform option space optimization for any type
implementing 'Invalid'.
Again, that makes more sense than my proposal. But I do wonder if it would be
necessary to make the restriction that only a compile-time constant would be
allowed for the 'invalid' sentinel value. That would require type associated
constants and also that traits would be able to require such a constant be
defined by its implementor type. But I think those features are bound to land
at some point.
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
Needing to use a header seriously hurts the performance. The new vector is 7x faster at pushing elements when space isn't reserved compared to the old one, all due to leaving off the length/capacity header. The overhead would be less if it stored the capacity inside *and* outside the vector, but it's still overhead. It's an extra overflow check branch along with needing to calculate padding for alignment in the future, extra space in the memory allocation and more pointer aliasing issues. Perhaps I am not understanding you correctly. Assuming that the capacity is stored inside and outside Vec, the only overhead I see is during allocation/deallocation. Otherwise the code will be identical. If you are worried about space, there is a cost of passing around Vecs ( vs ~[T]), which consumes and extra register for the capacity. It's going to be forbidden from actually being null in the future when the Option-like enum optimization is applied to it via an attribute. This work has already landed - calling exchange_free on a zero-size allocation is *forbidden*. As mentioned elsewhere on this thread, we can use another invalid pointer value to represent either Option-None or 0 capacity depending on which is more efficient. Manu ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
On 04/04/14 10:51 AM, Manu Thambi wrote: Needing to use a header seriously hurts the performance. The new vector is 7x faster at pushing elements when space isn't reserved compared to the old one, all due to leaving off the length/capacity header. The overhead would be less if it stored the capacity inside *and* outside the vector, but it's still overhead. It's an extra overflow check branch along with needing to calculate padding for alignment in the future, extra space in the memory allocation and more pointer aliasing issues. Perhaps I am not understanding you correctly. Assuming that the capacity is stored inside and outside Vec, the only overhead I see is during allocation/deallocation. Otherwise the code will be identical. It bloats the code size by requiring extra overflow checks in functions like `push`, which impacts performance. Unwinding prevents many LLVM passes from doing their job, since it adds significant complexity to the control flow. In addition to this, there is even an impact on the performance of immutable operations like indexing. There's a need to calculate the offset to the first element in the vector, which includes compensating for alignment because there can be padding in between the capacity and the first element in the vector. You can deny that this has performance implications, but the fact is that I have looked at the performance and code size impact in depth and and have hard numbers from benchmarks proving that there is a enormous performance overhead for this choice. If you are worried about space, there is a cost of passing around Vecs ( vs ~[T]), which consumes and extra register for the capacity. 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 VecT` 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. It's going to be forbidden from actually being null in the future when the Option-like enum optimization is applied to it via an attribute. This work has already landed - calling exchange_free on a zero-size allocation is *forbidden*. As mentioned elsewhere on this thread, we can use another invalid pointer value to represent either Option-None or 0 capacity depending on which is more efficient. 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 `VecT` - `~[T]` is not a no-op, which is what I am saying. Commits: 1778b6361627c5894bf75ffecf427573af02d390 898669c4e203ae91e2048fb6c0f8591c867bccc6 signature.asc Description: OpenPGP digital signature ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
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 VecT` 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 VecT - ~[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 `VecT` - `~[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 VecT - ~[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 VecT as well, even though it is not needed. This will keep VecT - ~[T] a no-op. This will add a branch to every deallocation call. c) Conversion between VecT - ~[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 `VecT` - `~[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 Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] Building a static array of pointers
Is it possible to port the following C code to rust?
__attribute__ ((section(.isr_vector)))
void (* const isr_vector_table[])(void) = {
_stack_base,
main, // Reset
isr_nmi, // NMI
isr_hardfault,// Hard Fault
0,// CM3 Memory Management Fault
0,// CM3 Bus Fault
0,// CM3 Usage Fault
_boot_checksum, // NXP Checksum code
0,// Reserved
0,// Reserved
0,// Reserved
isr_svcall, // SVCall
0,// Reserved for debug
0,// Reserved
isr_pendsv, // PendSV
isr_systick, // SysTick
};
here main and isr_* are rust external functions, and _stack_base is defined
as
extern void _stack_base()
and gets loaded from linker script.
Also, is it possible to make a weak symbol in rust or somehow emulate it?
Weak symbols are used in C code to provide the following functionality:
isr_* functions are stubs with default implementation (morse out id code
with led, loop forever), but if any of those requires actual code, than it
is overrides the weak morse-blinking function symbol.
--
Sincerely,
Vladimir Farcaller Pouzanov
http://farcaller.net/
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Building a static array of pointers
As you've discovered in bug #13325, dealing with external constants in
static expressions is sometimes a little tricky. I would avoid casting
for now (as happens in the bug) in favor of stronger types. For
example, this compiles and runs for me:
extern {
fn foo();
fn bar();
}
static table: 'static [extern unsafe fn()] = [foo, bar];
pub mod test {
#[no_mangle] pub extern fn foo() { println!(foo); }
#[no_mangle] pub extern fn bar() { println!(bar); }
}
fn main() {
for f in table.iter() {
unsafe { (*f)(); }
}
}
Note that in rust, a value of type `extern fn()` cannot be null, but
`Optionextern fn()` can indeed be null. You'll probably want
something along the lines of:
#[link_section = .isr_vector]
pub static ISR_VECTOR_TABLE: [Optionextern unsafe fn(), ..N] =
[Some(...), None, Some(...), ...];
On Fri, Apr 4, 2014 at 12:53 PM, Vladimir Pouzanov farcal...@gmail.com wrote:
Is it possible to port the following C code to rust?
__attribute__ ((section(.isr_vector)))
void (* const isr_vector_table[])(void) = {
_stack_base,
main, // Reset
isr_nmi, // NMI
isr_hardfault,// Hard Fault
0,// CM3 Memory Management Fault
0,// CM3 Bus Fault
0,// CM3 Usage Fault
_boot_checksum, // NXP Checksum code
0,// Reserved
0,// Reserved
0,// Reserved
isr_svcall, // SVCall
0,// Reserved for debug
0,// Reserved
isr_pendsv, // PendSV
isr_systick, // SysTick
};
here main and isr_* are rust external functions, and _stack_base is defined
as
extern void _stack_base()
and gets loaded from linker script.
Also, is it possible to make a weak symbol in rust or somehow emulate it?
Weak symbols are used in C code to provide the following functionality:
isr_* functions are stubs with default implementation (morse out id code
with led, loop forever), but if any of those requires actual code, than it
is overrides the weak morse-blinking function symbol.
--
Sincerely,
Vladimir Farcaller Pouzanov
http://farcaller.net/
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
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 VecT as well, even though it is not needed. This will keep VecT - ~[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 VecT - ~[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 `VecT` - `~[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 VecT would contain the same amount info. The only difference is that in ~[T], the capacity is stored at a negative index. In VecT, 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
[rust-dev] Some help needed in Vector of enum conversion
Hello,
I've some problem to find a solution for something I want to do with a
vector of enum. This is an example of what I want to do:
trait Base{
fn set_something(mut self);
}
struct FirstThink;
impl Base for FirstThink{
fn set_something(mut self){}
}
struct SecondThink;
impl Base for SecondThink{
fn set_something(mut self){}
}
enum BaseImpl{
FirstThinkImpl(~FirstThink),
SecondThinkImpl(~SecondThink),
}
fn some_process(list: mut Vecmut ~Base){
for think in list.mut_iter() {
think.set_something();
}
}
struct Container{
nodeList: Vec~BaseImpl,
}
impl Container{
fn add_FirstThink(mut self, think: ~FirstThink){
self.nodeList.push(~FirstThinkImpl(think));
}
fn add_SecondThink(mut self, think: ~SecondThink){
self.nodeList.push(~SecondThinkImpl(think));
}
fn do_some_process(mut self, fct: fn(mut Vecmut ~Base)){
I didn't find a simple way to convert the Vec~BaseImpl to a
mut Vecmut ~Base
to do the call
fct(self.nodeList);
}
}
I use the enum pattern to have only one collection of object that impl
Base but sometime I have to do specific processing depending if the Base
is a FirstThink or SecondThink (not in the example). I use the match as
follow
match think {
FirstThinkImpl(first) = do specific first,
SecondThinkImpl(second)= do specific second,
});
Perhaps there is a better way to do. Any suggestions would be appreciated.
Philippe
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
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 `VecT` 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 `VecT` 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 VecT as well, even though it is not needed. This will keep VecT - ~[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 `VecT` 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 Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Reminder: ~[T] is not going away
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 `VecT` 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 `VecT` 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 VecT as well, even though it is not needed. This will keep VecT - ~[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 `VecT` 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
