[rust-dev] iterate over pairs and why no multiple mutable references

Discussion:

silvio

2014-09-19 07:39:53 UTC

Hi Rust,

I've recently tried to investigate rust's claim of being fast and had a
look at debian shootout.

A particular program I took a looked at is the n-body problem in which
you have to loop over pairs of bodies to calculate their gravitational
attraction. What struck me as strange was the number of indexing operations.

bodies[i]
bodies[j]
bodies[i]
bodies[j]
...

Now I don't know if the compiler is smart enough to optimize this away.
However, it seems generally impossible to make references.

let mut body_i = bodies.someMethod(i)
let mut body_j = bodies.someMethod(j)

So how is this usually done?

Why are multiple mutable references to the same object not allowed. To
achieve safe memory you only need to guarantee that different threads
don't write/read from/to the same memory location at the same time and
that is handled via ownership. (borrowed) references & don't have
ownership. Additionally, you need to ensure that all references not only
mut are not usable anymore until you can transfer ownership. So, I don't
understand why mut and not mut are treated differently.

An other small thing. I read that you should always return a type directly.

fn foo(args) -> big_struct

Does this mean that all return values are secretly pointers passed to
the function except for things that fit into registers?

regards

silvio

Jan Klesnil

2014-09-19 08:13:43 UTC

Permalink

Hi,

indexing operations check boundaries. Compiler (LLVM backend) is capable
of removing some of them, sometimes, but generally indexed accesses
tends to be slower in comparison to iteration using the Iterator<T>.

Multiple mutable references are not only bad for multithreading and data
races but also they create more aliases that prevent optimizations.
Moreover, single-threaded code can be turned into multi-threaded easily
if you follow stricter rules from the start.
http://doc.rust-lang.org/guide.html#ownership,-borrowing,-and-lifetimes

Multiple mutable borrows from a same vector is currently one of the
biggest weaknesses of Rust. There are some proposals to cope with it but
I personally do not know what is the current state of the matter.

Large return values are placed in preallocated space, the same way as
RVO works in C++.
http://doc.rust-lang.org/guide-pointers.html#returning-pointers

JK

Post by silvio
Hi Rust,
I've recently tried to investigate rust's claim of being fast and had a
look at debian shootout.
A particular program I took a looked at is the n-body problem in which
you have to loop over pairs of bodies to calculate their gravitational
attraction. What struck me as strange was the number of indexing operations.
bodies[i]
bodies[j]
bodies[i]
bodies[j]
...
Now I don't know if the compiler is smart enough to optimize this away.
However, it seems generally impossible to make references.
let mut body_i = bodies.someMethod(i)
let mut body_j = bodies.someMethod(j)
So how is this usually done?
Why are multiple mutable references to the same object not allowed. To
achieve safe memory you only need to guarantee that different threads
don't write/read from/to the same memory location at the same time and
that is handled via ownership. (borrowed) references & don't have
ownership. Additionally, you need to ensure that all references not only
mut are not usable anymore until you can transfer ownership. So, I don't
understand why mut and not mut are treated differently.
An other small thing. I read that you should always return a type directly.
fn foo(args) -> big_struct
Does this mean that all return values are secretly pointers passed to
the function except for things that fit into registers?
regards
silvio
_______________________________________________
Rust-dev mailing list
Rust-dev at mozilla.org
https://mail.mozilla.org/listinfo/rust-dev

Manish Goregaokar

2014-09-19 08:13:57 UTC

Permalink

Iterator invalidation is a common memory safety issue where you have two
references being simultaneously used -- one mutable, one immutable. With
multiple mutable references worse errors can happen.

-Manish Goregaokar

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140919/b7d4ca8b/attachment.html>

Clark Gaebel

2014-09-19 15:32:09 UTC

Permalink

You can use a Vec> for this.?
Sent from Mailbox

On Fri, Sep 19, 2014 at 1:14 AM, Manish Goregaokar <manishsmail at gmail.com>

Post by Manish Goregaokar
Iterator invalidation is a common memory safety issue where you have two
references being simultaneously used -- one mutable, one immutable. With
multiple mutable references worse errors can happen.
-Manish Goregaokar

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140919/6cc3f303/attachment.html>

Viktor Dahl

2014-09-21 17:24:47 UTC

Permalink

You can break memory safety in a single thread if you allow multiple
mutable references to the same object. Consider an enum like this:

enum Foo {
Pointer(Box<T>),
Integer(i32)
}

Take one reference to the boxed `T` inside a `Foo` of the `Pointer`
variant. It doesn't even have to be mutable. Then use a mutable reference
to the enum object itself to change the variant to `Integer`. Reading from
the first reference now is a use-after-free, since the boxed T was freed
when the variant changed. If you'd taken a reference to the box instead,
you'd be trying to follow a garbage pointer.

Post by Clark Gaebel
You can use a Vec> for this.
?
Sent from Mailbox <https://www.dropbox.com/mailbox>
On Fri, Sep 19, 2014 at 1:14 AM, Manish Goregaokar <manishsmail at gmail.com>

_______________________________________________
Rust-dev mailing list
Rust-dev at mozilla.org
https://mail.mozilla.org/listinfo/rust-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/rust-dev/attachments/20140921/1bb97e6a/attachment.html>

silvio

2014-09-21 20:00:08 UTC

Permalink

Thanks that was a very illuminating example.

As for iterating over pairs would it be possible to have an iterator
that gives both:

1. A mutable reference to the next element
2. An iterator over the rest of the elements

the idea would be to be able to write

for (ele_i, rest) in list.iterator() {
for ele_j in rest {
do stuff
}
}

silvio