Re: [rust-dev] Scheduler and I/O work items for the summer
On Fri, May 31, 2013 at 3:45 PM, Brian Anderson bander...@mozilla.comwrote: With this problem in general I think the obvious solutions amount to taking one of two approaches: translate I/O events into pipe events; translate pipe events into I/O events. Solving the problem efficiently for either one is rather simpler than solving both. The example you show is promising model that looks like it could naively be implemented by buffering I/O into pipes. bblum and I talked about an implementation that would work well for this approach, but it has costs. I imagine it working like this. 1) The resolve_xxx function partitions the elements into pipesy types and I/O types. 3) For each of the I/O types it creates a new pipe, and registers a uv event. Note that because of I/O-scheduler affinity some of these may cause the task to migrate between threads. 4) Now we just wait on all the pipes. What if futures were treated as one-shot pipes with one element queue capacity, and real pipes were used only when there's a need for buffering? That would help to reduce per-operation costs (also see notes below about allocation). I think we would want to do this too for efficiency reasons. The above outline has two major costs: the first is the extra pipes and the second is the buffering of the I/O. For example, the synchronous read method looks like `read(buf: mut [u8])` where the buf is typically allocated on the stack. In the future scenario presumably it would be more like `read() - Future~[u8]`, forcing a heap allocation, but maybe `read(buf: mut [u8]) - Futuremut [u8]` is workable. Not necessarily. In fact, .NET's signature of the read method is something like this: fn read(buf: mut [u8]) - ~Futureint; It returns just the read bytes count. This is perfectly fine for simple usage because caller still has a reference to the buffer. Now, if you want to send it over to another task, this is indeed a problem, however composition of future comes to the rescue. Each .NET's future has a method that allows to attach a continuation that yields a new future of the type of continuation's result: trait FutureT { fn continue_withT1(self, cont: fn (T) - T1) - FutureT1; } let buf = ~[0,..1024]; let f1 = stream.read(buf); let f2 : Future(~[u8],int = f1.continue_with(|read| return (buf, read)); Now f2 contains all information needed to process received data in another task. 2. Each i/o operation now needs to allocate heap memory for the future object. This has been known to create GC performance problems for .NET web apps which process large numbers of small requests. If these can live on the stack, though, maybe this wouldn't be a problem for Rust. Haha, yep that's a concern. I know that Rust currently doesn't currently support this, but what if futures could use a custom allocator? Then it could work like this: 1. Futures use a custom free-list allocator for performance. 2. The I/O request allocates new future object, registers uv event, then returns unique pointer to the future to its' caller. However I/O manager retains internal reference to the future, so that it can be resolved once I/O completes. 3. The future object also has a flag indicating that there's an outstanding I/O, so if caller drops the reference to it, it won't be returned to the free list until I/O completes. 4. When I/O is complete, the future get resolved and all attached continuations are run. Vadim ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Question about lifetimes in type parameters
OK, I finally got a chance to take a look. Indeed, this is not a bug, I just misunderstood what was going on. The problem is that the key is `'b [u8]` but you can't supply precisely that type, because the key you are using to do th elookup has a shorter lifetime. This is true and the type checker is right to complain. What you want is to do in these situations is to use the `find_equiv` method, which demands a key that is not necessarily the *same* type as what is in the map but just one comparable to it. Unfortunately, we don't have an equivalence for two slices of unequal lifetimes right now (and we can't right one at the moment due to some limitations that I am supposed to be lifting). Annoyingly, we also don't have an equivalence from ~[u8] to [u8], only in the reverse direction. We should fix this, but usually people have ~[u8] as the key and [u8] as the equivalent lookup key, not the other way around. However, you can workaround this limitation using a new type struct. Here is a version that works. The main trick is to add a temporary type `MapKey` for which we can define the `Equiv` trait so that it can be compared to the slices that are in your table. ``` extern mod extra; use std::vec; use std::hashmap::*; use std::os; use std::str; use std::uint; use std::cmp::eq; #[deriving(IterBytes)] struct MapKey(~[u8]); impl'self Equiv'self [u8] for MapKey { fn equiv(self, other: 'self [u8]) - bool { let slice1: [u8] = **self; let slice2: [u8] = *other; slice1 == slice2 } } pub fn with_mmap_file_contentsU(filename : str, f : fn(v : [u8]) - U) - U { fail!() } pub fn each_combinationT:Copy(values : [T], r : uint, fun : fn(combo : [T]) - bool) - bool { fail!() } fn get_letters(s : str) - ~[u8] { let mut t = str::to_chars(s); extra::sort::quick_sort(t, |a,b| *a = *b); return vec::from_fn(t.len(), |i| t[i] as u8); } fn line_map'b(buffer : 'b [u8]) - ~HashMap'b [u8],'b [u8] { let length = buffer.len(); let mut map = ~HashMap::new(); let mut i = 0; while i length { let mut j = i; while j length buffer[j] != ' ' as u8 { j += 1; } let mut k = j+1; while k length buffer[k] != '\n' as u8 { k += 1; } map.insert(vec::slice(buffer, i, j), vec::slice(buffer, j+1, k)); i = k + 1; } return map; } fn search'b(letters : [u8], dictionary : 'b HashMap'b [u8],'b [u8]) - ~HashSet'b [u8] { let mut set = ~HashSet::new(); for uint::range(2, letters.len() + 1) |i| { let mut key = MapKey(vec::from_elem(i, 0)); // pub fn each_combinationT:Copy(values : [T], r : uint, fun : fn(combo : [T]) - bool) - bool for each_combination(letters,i) |combo| { for combo.eachi |j,ch| { key[j] = ch; } { match dictionary.find_equiv(key) { Some(val) = { set.insert(*val); } None = { } } } } } return set; } fn main() { let args = os::args(); if args.len() 2 { fail!(~Usage: anagrams letters); } let letters = get_letters(args[1]); do with_mmap_file_contents(anadict-rust.txt) |buf| { let map = line_map(buf); let set = search(letters, map); // Just count them for now... let mut count = 0; for set.each |ln| { count += 1 + vec::count(*ln, (' ' as u8)); } println(fmt!(%?, count)); } } ``` Niko On Thu, May 30, 2013 at 09:00:32AM -0500, Tommy M. McGuire wrote: On 05/30/2013 05:09 AM, Niko Matsakis wrote: On Wed, May 29, 2013 at 04:55:31PM -0500, Tommy M. McGuire wrote: The problem is that I want to use a completely unrelated vector as the argument to find() instead of an alias for part of the buffer or a pair of indices into the buffer. Currently, with my quick change to incoming, the code let kkey : [u8] = key; // key : ~[u8] match dictionary.find(kkey) { produces: 55:38 error: borrowed value does not live long enough let kkey : [u8] = key; ^~~ 67:1 note: borrowed pointer must be valid for the lifetime br_named({repr: 83, ctxt: 0}) as defined on the block at 48:0... ... 65:5 note: ...but borrowed value is only valid for the block at 50:46 The lifetime 'br_named(...)' stuff should be 'b, the lifetime parameter of the function (the block at 48:0) that is associated with the keys and values from the HashMap (was LinearMap) and the buffer. This seems like a bug (also, what a lousy error message! sorry.), I will further investigate. Thanks! (The error message changed when I updated incoming, so it's something recent.) I'm not sure it is a bug, though. I may not be understanding lifetimes well enough, but I think the interaction between that and generics is problematic. In this case,
Re: [rust-dev] Question about lifetimes in type parameters
Ah, one thouht, you may want to be more careful with the def'n of IterBytes on MapKey to be sure that the hashcodes are the same. Niko On Sat, Jun 01, 2013 at 06:46:00AM -0400, Niko Matsakis wrote: OK, I finally got a chance to take a look. Indeed, this is not a bug, I just misunderstood what was going on. The problem is that the key is `'b [u8]` but you can't supply precisely that type, because the key you are using to do th elookup has a shorter lifetime. This is true and the type checker is right to complain. What you want is to do in these situations is to use the `find_equiv` method, which demands a key that is not necessarily the *same* type as what is in the map but just one comparable to it. Unfortunately, we don't have an equivalence for two slices of unequal lifetimes right now (and we can't right one at the moment due to some limitations that I am supposed to be lifting). Annoyingly, we also don't have an equivalence from ~[u8] to [u8], only in the reverse direction. We should fix this, but usually people have ~[u8] as the key and [u8] as the equivalent lookup key, not the other way around. However, you can workaround this limitation using a new type struct. Here is a version that works. The main trick is to add a temporary type `MapKey` for which we can define the `Equiv` trait so that it can be compared to the slices that are in your table. ``` extern mod extra; use std::vec; use std::hashmap::*; use std::os; use std::str; use std::uint; use std::cmp::eq; #[deriving(IterBytes)] struct MapKey(~[u8]); impl'self Equiv'self [u8] for MapKey { fn equiv(self, other: 'self [u8]) - bool { let slice1: [u8] = **self; let slice2: [u8] = *other; slice1 == slice2 } } pub fn with_mmap_file_contentsU(filename : str, f : fn(v : [u8]) - U) - U { fail!() } pub fn each_combinationT:Copy(values : [T], r : uint, fun : fn(combo : [T]) - bool) - bool { fail!() } fn get_letters(s : str) - ~[u8] { let mut t = str::to_chars(s); extra::sort::quick_sort(t, |a,b| *a = *b); return vec::from_fn(t.len(), |i| t[i] as u8); } fn line_map'b(buffer : 'b [u8]) - ~HashMap'b [u8],'b [u8] { let length = buffer.len(); let mut map = ~HashMap::new(); let mut i = 0; while i length { let mut j = i; while j length buffer[j] != ' ' as u8 { j += 1; } let mut k = j+1; while k length buffer[k] != '\n' as u8 { k += 1; } map.insert(vec::slice(buffer, i, j), vec::slice(buffer, j+1, k)); i = k + 1; } return map; } fn search'b(letters : [u8], dictionary : 'b HashMap'b [u8],'b [u8]) - ~HashSet'b [u8] { let mut set = ~HashSet::new(); for uint::range(2, letters.len() + 1) |i| { let mut key = MapKey(vec::from_elem(i, 0)); // pub fn each_combinationT:Copy(values : [T], r : uint, fun : fn(combo : [T]) - bool) - bool for each_combination(letters,i) |combo| { for combo.eachi |j,ch| { key[j] = ch; } { match dictionary.find_equiv(key) { Some(val) = { set.insert(*val); } None = { } } } } } return set; } fn main() { let args = os::args(); if args.len() 2 { fail!(~Usage: anagrams letters); } let letters = get_letters(args[1]); do with_mmap_file_contents(anadict-rust.txt) |buf| { let map = line_map(buf); let set = search(letters, map); // Just count them for now... let mut count = 0; for set.each |ln| { count += 1 + vec::count(*ln, (' ' as u8)); } println(fmt!(%?, count)); } } ``` Niko On Thu, May 30, 2013 at 09:00:32AM -0500, Tommy M. McGuire wrote: On 05/30/2013 05:09 AM, Niko Matsakis wrote: On Wed, May 29, 2013 at 04:55:31PM -0500, Tommy M. McGuire wrote: The problem is that I want to use a completely unrelated vector as the argument to find() instead of an alias for part of the buffer or a pair of indices into the buffer. Currently, with my quick change to incoming, the code let kkey : [u8] = key; // key : ~[u8] match dictionary.find(kkey) { produces: 55:38 error: borrowed value does not live long enough let kkey : [u8] = key; ^~~ 67:1 note: borrowed pointer must be valid for the lifetime br_named({repr: 83, ctxt: 0}) as defined on the block at 48:0... ... 65:5 note: ...but borrowed value is only valid for the block at 50:46 The lifetime 'br_named(...)' stuff should be 'b, the lifetime parameter of the function (the block at 48:0) that is associated with the keys and values from the HashMap (was LinearMap) and the buffer. This seems like a
Re: [rust-dev] Scheduler and I/O work items for the summer
I know that Rust currently doesn't currently support this, but what if futures could use a custom allocator? Then it could work like this: 1. Futures use a custom free-list allocator for performance. 2. The I/O request allocates new future object, registers uv event, then returns unique pointer to the future to its' caller. However I/O manager retains internal reference to the future, so that it can be resolved once I/O completes. 3. The future object also has a flag indicating that there's an outstanding I/O, so if caller drops the reference to it, it won't be returned to the free list until I/O completes. 4. When I/O is complete, the future get resolved and all attached continuations are run. Vadim Brian, Vadim described the idea fairly well there with the meat of my idea being # 2. I was just trying to describe the scenario that # 4 be able to happen only when all the registered event(s) happen (not just 1 blocking step but perhaps many blocking steps). I would not know where to start mocking something like that with Rust yet... still beginning. -- -Thad http://www.freebase.com/view/en/thad_guidry ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Scheduler and I/O work items for the summer
On Sat, Jun 1, 2013 at 3:43 PM, Thad Guidry thadgui...@gmail.com wrote: I know that Rust currently doesn't currently support this, but what if futures could use a custom allocator? Then it could work like this: 1. Futures use a custom free-list allocator for performance. I don't see why Futures could not be allocated on the stack ? Since Rust is move aware and has value types, it seems to me this should be possible. -- Matthieu 2. The I/O request allocates new future object, registers uv event, then returns unique pointer to the future to its' caller. However I/O manager retains internal reference to the future, so that it can be resolved once I/O completes. 3. The future object also has a flag indicating that there's an outstanding I/O, so if caller drops the reference to it, it won't be returned to the free list until I/O completes. 4. When I/O is complete, the future get resolved and all attached continuations are run. Vadim Brian, Vadim described the idea fairly well there with the meat of my idea being # 2. I was just trying to describe the scenario that # 4 be able to happen only when all the registered event(s) happen (not just 1 blocking step but perhaps many blocking steps). I would not know where to start mocking something like that with Rust yet... still beginning. -- -Thad http://www.freebase.com/view/en/thad_guidry ___ 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] Scheduler and I/O work items for the summer
On Sat, Jun 1, 2013 at 7:47 AM, Matthieu Monrocq matthieu.monr...@gmail.com wrote: 1. Futures use a custom free-list allocator for performance. I don't see why Futures could not be allocated on the stack ? Since Rust is move aware and has value types, it seems to me this should be possible. Because I/O manager needs to know where that future is in order to fill in the result. Perhaps it's possible to have a stack-allocated future objects that consist of just a raw pointer to a block owned by the I/O manager. But these would need to have by-move semantics in order to emulate behavior of unique pointers. I am not entirely sure how by-move vs by-copy is decided, but according to thishttp://static.rust-lang.org/doc/rust.html#moved-and-copied-typesRust would choose by-copy. Vadim ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] Traits mod
Hey folks, A work colleague is trying to pick up some Rust we were both surprised by the following: // some_mod.rs pub trait SomeTrait { pub fn foo(self) - ~str; } pub struct SomeStruct { name: ~str } impl SomeTrait for SomeStruct { pub fn foo(self) - ~str { self.name.clone() } } impl SomeStruct { pub fn new(name: str) - SomeStruct { SomeStruct { name: name.to_owned() } } } // some_use.rs mod some_mod; fn main() { let inst = some_mod::SomeStruct::new(test); println(inst.foo()); } This fails with a compile error because the compiler can't see some_mod::SomeTrait in the scope of some_use.rs: some_use.rs:5:4: 6:1 error: type `some_mod::SomeStruct` does not implement any method in scope named `foo` some_use.rs:5 inst.foo() some_use.rs:6 } This is fixed by adding use some_mod::SomeTrait at the start of some_use.rs. It's as though traits need to be in the same scope as code that expects to make use of their behaviour (where I'd expect the behaviour would be associated with the implementation for the self type). My question is: is this intended behaviour? If not, what's the expected behaviour is there an outstanding issue for this? Appreciate any clarification! Cheers, Tom -- Tom Lee / http://tomlee.co / @tglee ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
[rust-dev] Mutability and borrowing
I have the following function: fn add_equal(x: mut Complex, y: Complex) { x.real += y.real; x.imag += y.imag; } Calling the function with the same variable being passed to both arguments (i.e. add_equal(mut c, c)), results in the compile error: error: cannot borrow `c` as immutable because it is also borrowed as mutable I am guessing this is to avoid aliasing issues? What is the way around this? Thanks -- Ziad ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Mutability and borrowing
Trying to concurrently borrow a value twice is never going to work. You could write a function like double for such a situation. -- Abhijeet Gaiha http://about.me/abhijeet.gaiha On Sunday, 2 June 2013 at 10:03 AM, Ziad Hatahet wrote: I have the following function: fn add_equal(x: mut Complex, y: Complex) { x.real += y.real; x.imag += y.imag; } Calling the function with the same variable being passed to both arguments (i.e. add_equal(mut c, c)), results in the compile error: error: cannot borrow `c` as immutable because it is also borrowed as mutable I am guessing this is to avoid aliasing issues? What is the way around this? Thanks -- Ziad ___ Rust-dev mailing list Rust-dev@mozilla.org (mailto: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] Mutability and borrowing
On Sat, Jun 1, 2013 at 9:33 PM, Ziad Hatahet hata...@gmail.com wrote: I have the following function: fn add_equal(x: mut Complex, y: Complex) { x.real += y.real; x.imag += y.imag; } Calling the function with the same variable being passed to both arguments (i.e. add_equal(mut c, c)), results in the compile error: error: cannot borrow `c` as immutable because it is also borrowed as mutable I am guessing this is to avoid aliasing issues? What is the way around this? You can copy y instead of passing a reference to it: fn add_equal(x: mut Complex, y: Complex) { ... Of course, that means that at the call site, you will have to write something like add_equal(mut c, copy c). Unless you want to write a function that just takes one argument and doubles it, like Abhijeet suggested, I don't know of another way around this. Cheers, Tim -- Tim Chevalier * http://catamorphism.org/ * Often in error, never in doubt Not a riot, it's a rebellion. -- Boots Riley Attention Bros and Trolls: When I call out your spew, I'm not angry, I'm defiant. -- Reg Braithwaite ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Mutability and borrowing
Thanks everyone. I actually thought about the two suggestions before posting. I thought there might be some common paradigm for this in the language though. So I take it that implementing a += operator overload function would not have a generic way to handle the case where the same parameter is passed on both sides? -- Ziad On Sat, Jun 1, 2013 at 9:42 PM, Tim Chevalier catamorph...@gmail.comwrote: On Sat, Jun 1, 2013 at 9:33 PM, Ziad Hatahet hata...@gmail.com wrote: I have the following function: fn add_equal(x: mut Complex, y: Complex) { x.real += y.real; x.imag += y.imag; } Calling the function with the same variable being passed to both arguments (i.e. add_equal(mut c, c)), results in the compile error: error: cannot borrow `c` as immutable because it is also borrowed as mutable I am guessing this is to avoid aliasing issues? What is the way around this? You can copy y instead of passing a reference to it: fn add_equal(x: mut Complex, y: Complex) { ... Of course, that means that at the call site, you will have to write something like add_equal(mut c, copy c). Unless you want to write a function that just takes one argument and doubles it, like Abhijeet suggested, I don't know of another way around this. Cheers, Tim -- Tim Chevalier * http://catamorphism.org/ * Often in error, never in doubt Not a riot, it's a rebellion. -- Boots Riley Attention Bros and Trolls: When I call out your spew, I'm not angry, I'm defiant. -- Reg Braithwaite ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev