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
