On 13/06/2012 4:15 PM, Niko Matsakis wrote:
*Implications for writing efficient Rust*
I figured I'd just start with the implications for writing Rust.
Currently, to build up a vector, we rely upon an idiom like:
let mut v = [];
for some loop { v += [elt]; }
Yeah. After we lost the one-element-append rule, this never really read
well anyway. Happy to see it go (at least in that form).
Now, often, such loops can (and should) be written using a higher-order
function (e.g., map, filter). But sometimes not. In such cases, under
the new regime, the recommended idiom would be:
let dv = dvec();
for some loop { v.push(elt); }
let v = dvec::unwrap(dv); // if necessary, convert to a vector
Actually the name `dvec()` (dynamic vector) will probably change—perhaps
to vecbuf? mvec? suggestions welcome—but you get the idea. The same
would eventually apply to building up strings.
It's funny, this is pretty clearly a stack (growth is optimized only at
one end), so I'm of half a mind to just call it a stack, but something
kinda balks at the notion. Not sure why.
What disappoints me about all this is that the language is now dependent
on unsafe library code in order to do asymptotically fast aggregate
types at all. The += optimization and vec doubling-allocation was the
"one primitive" related to aggregate types that the compiler was filling
in for us safely, before, for the sake of building more-efficient
containers on top. Now pretty much every primitive container that has a
doubling-store growth pattern is going to involve unsafe code. That's a
bitter pill, but I guess it was true before too, it was just unsafe code
with an interface curated by the compiler and runtime, not core library :(
Most of this exists today. The only
real thing that changes is that we take *away* the tricks the compiler
does for `+=`.
Not ok with the thrust of this. I mean, in terms of the API for dvec or
stack or whatever, that may be the right thing; the current += rule
actually requires a _companion_ compiler-written optimization in the
construction of single-element vectors on the RHS in order to append
them w/o allocation, in a type-symmetric way, which is totally over the
top and should go. So for now pushing a single element should probably,
yes, involve a .push method. At least until (or if) we address the
type-level question of doing operator overloading on mixed types.
But this general move feels like obscuring a pretty important bug, that
I'm inclined to point out: we need to expand operator overloading to
have op= forms, in general, such that a user could _define_ a version of
+= that does what the compiler currently does, when that's reasonable
(overload arg-type symmetry aside). Operator overloading is simply
incomplete here; likewise, fn [](...) needs to have a 3-arg lval form,
not try to "return a mutable ref" or something.
Stacks are by no means the only case in which there's a "fast" in-place
op= form that users _will_ want to write. Pretty much any nontrivial
data structure with operators on it has an "in-place" optimization
opportunity for several operations. There's no reason to deny them the
opportunity when it appears in a for appropriate for overloaded
operators; the operator is already named, reserved, parsed at right
precedence, etc. It just needs to dispatch like the others.
-Graydon
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
