Rfcs: should struct fields and array elements be dropped in reverse declaration order (a la C++)

[steveklabnik]

Issue by pnkfelix
_Thursday Aug 21, 2014 at 23:34 GMT_

_For earlier discussion, see https://github.com/rust-lang/rust/issues/16661_

_This issue was labelled with: in the Rust repository_

---

should struct fields and array elements be dropped in reverse declaration order (a la C++) ?

https://github.com/rust-lang/rust/pull/16493 made us internally consistent with respect to struct fields, but chose to make the drops follow declaration order.

Note struct construction follows the order of the fields given at the construction site, so there's no way to ensure that the drop order is the reverse of the order used at the construction site.

But we should still think about whether we should change that. That is, if local variables are dropped in reverse declaration order (even though they can be initialized in any order), then it seems like it would make sense to do the same thing for struct fields.

[pnkfelix]

(If we're going to do this, we probably need to do it for 1.0. And thus I suspect we just will not do it. Which I am fine with.)

[pnkfelix]

Although, today I did run into this fun case:

use std::thread;

struct D(u8);

impl Drop for D {
    fn drop(&mut self) {
        println!("Dropping {}", self.0);
    }
}

fn main() {
    fn die() -> D { panic!("Oh no"); }
    let g = thread::spawn(|| {
        let _nested = vec![vec![D( 1), D( 2), D( 3), D( 4)],
                           vec![D( 5), D( 6), die(), D( 7)],
                           vec![D( 8), D( 9), D(10), D(11)]];
    });
    assert!(g.join().is_err());
}

The above prints:

Dropping 6
Dropping 5
Dropping 1
Dropping 2
Dropping 3
Dropping 4

So ... when we panic in the middle of the vec! construction, we drop in reverse order ... but then we drop fully constructed vecs in normal order (?) Does this _really_ make sense?

[pnkfelix]

A recent discussion with @nikomatsakis pointed out tuple structs as a case bordering the issues here.

http://is.gd/4mxF0Z

Namely, let a = ...; let b = ...; _must_ drop "b, then a".

For consistency, we then dictate that let (a, b) = ...; also drops "b, then a". (This seems to me like it is _not_ subject to debate nor change.)

The oddity is that then let p = (A, B); will drop the left component of the struct before the right component when it eventually drops p itself. I.e. that looks like dropping "a, then b"; which _seems_ inconsistent with the two cases above.

[nikomatsakis]

I feel pretty strongly that we ought to drop everything back-to-front. It seems to be overall most consistent. My mental model is that everything in life is a stack, and things in stacks get popped, and that's how it is. :P Now, it may be that for backwards compatibility reasons we don't want to change this though.

[nikomatsakis]

I feel pretty strongly that we ought to drop everything back-to-front.

To clarify, I mean "as much as possible". I'm sure there are weird corner cases I'm not thinking about. But I would like to be as consistent with C++ as possible (I understand Swift took a different order, but I'm stuck in my ways.)

[steveklabnik]

It seems to be overall most consistent

:+1:

[nagisa]

I personally don’t care as long as it drops most of the time. Is there any code that would break due to non-specified order?

[glaebhoerl]

I have the same stack intuition as @nikomatsakis, fwiw.

[nikomatsakis]

@nagisa it's very hard to know whether changing the current behavior of the compiler would affect the correctness of code.

[nagisa]

@nikomatsakis I’m more interested in use cases that would get fixed going from the current behaviour to any new one. That is, is there any case where current behaviour is not correct? If not, there’s moderately less incentive to do anything IMO.

[nikomatsakis]

@nagisa I don't there is anything that is fundamentally "enabled" by any particular order; you could always reorder your fields under any rules. The appeal of changing is that the current rules were not particularly "designed" and are sort of a patchwork of conventions, making it hard to predict what will happen in any scenario without actually just trying it.

[glaebhoerl]

Doesn't this all interact with dropck somewhere, even if only on the theoretical-hypothetical plane?

[pnkfelix]

@glaebhoerl are you anticipating some world with safe interior pointers within a struct by having dropck know that the fields are dropped in some order?

That seems like such a far off extension to the language that it need not influence decisions here. (Plus my gut tells me that it's an orthogonal issue)

[glaebhoerl]

Yeah, probably.

[nikomatsakis]

@glaebhoerl @pnkfelix yes to everything you guys just said :)

[aidancully]

If there isn't a use case for this (and I don't see why there would be, yet, besides "surprise"?), I'd think leaving the order unspecified is the most forward-compatible approach? It's conceivable that a scenario we come up with in the future would be incompatible with whatever order gets decided on today...

For what it's worth, I'm worried about assigning unrelated meanings to the field declaration order. In a systems-programming context, one might worry about locality-of-reference in structure definitions: at the least, it affects cache performance. By using #[repr(C)], you can explicitly control locality-of-reference in a structure, but locality-of-reference is an orthogonal concern to field destruction order... so I'd think we'd want to use a different mechanism to control each concern independently?

[aidancully]

One other point, is that I suspect that in-memory-order for calling destructors may perform somewhat better, as cache controllers expect forward-memory-accesses... So

struct MyStruct {
  a: Foo,
  b: Bar,
  c: Baz,
}
fn profile_1(m: &MyStruct) {
  m.a; m.b; m.c;
}
fn profile_2(m: &MyStruct) {
  m.c; m.b; m.a;
}

profile_1 may perform better than profile_2. This could easily be tested by profiling Vec, and a changed Vec that drops in reverse order, though I haven't tried to do so yet.

[nagisa]

The suspection is not valid. In the past, for some implementations of x86,
backwards memcpy used to perform even better than a forward one.

I can't exactly give more info at the moment though; on mobile.
On Aug 21, 2015 12:21 AM, "Aidan Cully" [email protected] wrote:

One other point, is that I suspect that in-memory-order for calling
destructors may perform somewhat better, as cache controllers expect
forward-memory-accesses... So

struct MyStruct {
a: Foo,
b: Bar,
c: Baz,
}fn profile_1(m: &MyStruct) {
m.a; m.b; m.c;
}fn profile_2(m: &MyStruct) {
m.c; m.b; m.a;
}

profile_1 may perform better than profile_2. This could easily be tested
by profiling Vec, and a changed Vec that drops in reverse order, though I
haven't tried to do so yet.

—
Reply to this email directly or view it on GitHub
https://github.com/rust-lang/rfcs/issues/744#issuecomment-133179381.

[aidancully]

@nagisa I think that has to do with the specific memcpy operation. See section 2.2.5.4 of Intel's optimization manual... Quoting:

Two hardware prefetchers load data to the L1 DCache:

• Data cache unit (DCU) prefetcher. This prefetcher, also known as the streaming prefetcher, is
  triggered by an ascending access to very recently loaded data. The processor assumes that this
  access is part of a streaming algorithm and automatically fetches the next line.
• Instruction pointer (IP)-based stride prefetcher. This prefetcher keeps track of individual load
  instructions. If a load instruction is detected to have a regular stride, then a prefetch is sent to the
  next address which is the sum of the current address and the stride. This prefetcher can prefetch
  forward or backward and can detect strides of up to 2K bytes.

It's highly likely that memcpy could use the stride prefetcher, and would work just as well forwards and backwards. OTOH, a heterogenous structure may not use the stride prefetcher for backwards-oriented reads, but forward-looking reads should be able to use the streaming prefetcher. (This also means that my suggestion of testing performance with Vec wouldn't have worked to demonstrate the performance issue I mentioned.)

[aidancully]

I spent more time than I wanted on this, but I wrote a quick-n-dirty C++ test program (I know it's ugly and unidiomatic, sorry for that, I don't have much spare time) that (I think) shows that reverse order may actually be the least efficient order in which to clean up fields. When I run it, compiled with -O3, I get the following:

...some results not shown...
size: 2048; time: 631000 ns => 308.105469 (Reverse)
size: 2048; time: 565000 ns => 275.878906 (Random)
size: 2048; time: 533000 ns => 260.253906 (Forward)
size: 4096; time: 1577000 ns => 385.009766 (Reverse)
size: 4096; time: 1293000 ns => 315.673828 (Random)
size: 4096; time: 1101000 ns => 268.798828 (Forward)
size: 8192; time: 2932000 ns => 357.910156 (Reverse)
size: 8192; time: 2698000 ns => 329.345703 (Random)
size: 8192; time: 2257000 ns => 275.512695 (Forward)
size: 16384; time: 6782000 ns => 413.940430 (Reverse)
size: 16384; time: 6177000 ns => 377.014160 (Random)
size: 16384; time: 3852000 ns => 235.107422 (Forward)
size: 32768; time: 13016000 ns => 397.216797 (Reverse)
size: 32768; time: 10411000 ns => 317.718506 (Random)
size: 32768; time: 10884000 ns => 332.153320 (Forward)
size: 65536; time: 25647000 ns => 391.342163 (Reverse)
size: 65536; time: 23366000 ns => 356.536865 (Random)
size: 65536; time: 17553000 ns => 267.837524 (Forward)
size: 131072; time: 53949000 ns => 411.598206 (Reverse)
size: 131072; time: 46924000 ns => 358.001709 (Random)
size: 131072; time: 35042000 ns => 267.349243 (Forward)
size: 262144; time: 108725000 ns => 414.752960 (Reverse)
size: 262144; time: 94490000 ns => 360.450745 (Random)
size: 262144; time: 71401000 ns => 272.373199 (Forward)
size: 524288; time: 216911000 ns => 413.724899 (Reverse)
size: 524288; time: 188521000 ns => 359.575272 (Random)
size: 524288; time: 142849000 ns => 272.462845 (Forward)

Basically, in the test I allocate an array of a number of large structures, then read them in different orders - the "read" operation for an element in the array always works the same way, reading the array from front to back, but I select which element to read using different strategies: sequential order, reverse order, and pseudo-random order. (This is intended to be similar to how Vec would operate on Drop, if Vec implemented different element order access strategies.) The last number in each row is the amount of time we spent per element in the array on the read operation. My results _seem_ to indicate that dropping back-to-front is actually the worst-case in terms of performance - iterating in reverse order is 1.5x as slow as iterating in forward order. (There are some results I can't immediately explain, but I've spent too long on it anyway, and the overall pattern seems reasonably clear, and in line with my expectations. Though I'm not 100% sure of the test program.)

[nagisa]

One of the very important things to be noted here: the language gives up almost full control over the drop order. The only two you can’t quite control are primitive types (most relevant: arrays) and stack (already in reverse).

This might be both a pro and a con for this issue. Namely “anybody who wants a different behaviour than the default can pretty trivially implement it most of the time” and “why bother with it, if anybody who cares can make it (most of the time) be in reverse anyway” respectively.

Finally, the drop order can never be a guarantee; only a guideline – anybody can drop things in whatever order they want anyway.

---

EDIT: rereading my post I think I might have implied that it is impossible to drop elements from array in reverse order. That is not true; you can do that with a wrapper type.

[aidancully]

It probably won't be a surprise, but I'm :-1: on this issue: the drop-order should be left unspecified. There are a few reasons I say so:

1. Leaving it unspecified allows the compiler to optimize the strategy to the target platform. While I suspect all platforms of interest will either behave identically with forward-and-reverse drop strategies (if they don't have a good prefetcher), or will be more efficient in the forward direction, cache prefetcher behavior is clearly platform specific, and it's conceivable that different drop orders might perform better on different platforms. Optimizing these memory accesses is only possible if the order is unspecified. (If it must be specified, forward order will ~always be as fast or faster.)
2. Leaving it unspecified now is forward compatible with specifying the strategy in the future, if it's determined we need to do so.
3. There's a general design principle that we should try to represent user intent as clearly as possible. Users usually won't care what order we drop fields in, and if they _do_ care, they will probably want to make their intention explicit. This is most compatible with the language not specifying drop order, but allowing mechanisms for users to define an order for cases in which they care. (That is, I find @nagisa's "con" argument significantly more compelling than the "pro" argument.)

But those are just my opinions.

[petrochenkov]

@aidancully

One other point, is that I suspect that in-memory-order for calling destructors may perform somewhat better, as cache controllers expect forward-memory-accesses...

After layout optimization (field reordering) declaration order may be different from order in memory, this may be one more argument in favor of leaving the destruction order unspecified at least for structs and tuples.

Otherwise,

I have the same stack intuition as @nikomatsakis, fwiw.

[nikomatsakis]

@petrochenkov

After layout optimization (field reordering) declaration order may be different from order in memory, this may be one more argument in favor of leaving the destruction order unspecified at least for structs and tuples.

I don't think it really matters how things are lald out in memory. The whole stack thing is really just a metaphor.

[aidancully]

@nikomatsakis I think you misunderstood? The memory access pattern is important to performance. I think I've shown that the CPU will perform better when memory accesses on contiguous data structures are always in the forward direction. If we want drop to perform as efficiently as possible, then it should also go in memory forward order. If we have field re-ordering, and we don't specify drop order, then the compiler is free to drop fields in memory order, as opposed to declaration order, or reverse declaration order. This will be faster: in my earlier results, it looks like 140ns blocking on a cache fill (that's hit _every time_ in my analogue of memory-reverse drop order), for an operation that usually takes 270ns to read almost 2KB of data (when using the analogue of memory-forward drop order). That's about 1.5x slower. And when I still don't see what problem is solved by defining the drop order to users, I struggle to understand the motivation.

_Edit_ Actually, let me put it differently. The argument from performance, in current Rust, suggests that we should drop in forward declaration order, since that corresponds to memory order. As @petrochenkov points out, in future Rust, with field re-ordering, the argument from performance still suggests that we drop in memory order, but since the mapping from memory order to declaration order isn't controlled by users, that implies that the optimally-performing drop also won't be known to users. We get best performance by declaring that the drop order is unspecified.

[glaebhoerl]

Given that field order is also undefined for structs, having the drop order be undefined as well does make sense. Would it be that unexpected for real-world programs to grow a behavioral dependence on the drop order used for arrays, though?

[sfackler]

There are some unsafe constructs that depend on drop order. For example, say you have a type Foo which produces a borrowed type Bar<'a>. You want to be able to pass the Bar and Foo around together with a static lifetime, so you can define something like

struct FooWithBar {
    bar: Bar<'static>
    foo: Box<Foo>,
}

and transmute the Bar's lifetime when reading it out. This does depend on destructors running in the right order though. For example, crates.io has this kind of struct to pass a Postgres Transaction<'a> object around along with the Connection that it has a reference to.

You can avoid depending on destructor ordering with some extra work, but if we want to mess with destructor order, we may want to add a type to the stdlib that helps with this kind of thing.

[pnkfelix]

Following up on what @sfackler put quite nicely, I think of Rust, at least when one doesn't say "unsafe" anywhere, as being safe, predictable, fast (in that order).

In particular, while I appreciate @aidancully 's point about an unspecified drop order yielding the highest performance in theory, I think that a struct/enum definition should have to opt into an unspecified order (e.g. via an attribute), in the name of predictability.

Otherwise it becomes much more arduous to reason about cases like the one described by @sfackler , and IMO, predictability of such cases should trump hypothetical optimize-ability.

---

Update: This is different from the lack of specification of layout order, because (I think), in the absence of unsafe, one should not be able to observe the struct layout order -- until one is actually transmuting and/or passing values via FFI, the struct layout order is an implementation detail. But on the flip side, one can certainly observe the Drop order of a struct!

[aidancully]

So the thing that bothers me about @sfackler's case is that

struct FooWithBar {
    bar: Bar<'static>,
    foo: Box<Foo>,
}

is not obviously different than

struct FooWithBar {
    foo: Box<Foo>,
    bar: Bar<'static>,
}

to most readers of the code, and yet the first version will work correctly under forward drop order (which is current behavior), while the second will work correctly with reverse drop order (which is what this issue suggests using, instead). So, one thing is that accepting this issue as stated will break current code, and it won't be at all obvious that it's done so. (Or else we could specify that drop order is forward declaration order, but reverse order seems breaking, to me.) In either event, the concern can be partially addressed by putting comments in the code, describing why the field order is what it is... Or it can be addressed by adding explicit control over the drop order to the destructor:

impl DropValue for FooWithBar {
  fn drop_value(this: Interior<Self>) {
    drop(this.foo);
    drop(this.bar);
  }
}

(assuming #1180 gets accepted, though the same effect could be had with #197). I think the last option is much more robust against accidental bug insertion during maintenance.

[nagisa]

@sfackler I don’t quite understand how drop order of struct fields is relevant in your example, can you explain it in simpler way/more throughout-ly?

The way I see it, the only thing that matters here is the inter-field references, and these cannot go wrong and are pretty hard to do in general in safe code.

---

I looked at the crates.io example and here’s my comments on it:

I assume dropping pg::Connection without dropping a pg::Transaction you started on the pg::Connection cannot be done “safely”. In that case pg::Transaction with a lifetime of 'static is obviously not “safe”: the lifetime should be less than the lifetime of associated pg::Connection. The way we specify drop order will not help reasoning about this kind of case at all.

[sfackler]

@nagisa Dropping the Connection without dropping the Transaction is fine, but Transaction's destructor uses its Connection, so if the Connection has already been destroyed, bad things will happen.

[pnkfelix]

@aidancully

one thing is that accepting this issue as stated will break current code, and it won't be at all obvious that it's done so

Note by the way that this issue is not a formal RFC. The language team would not just "accept" it as written.

Namely, I suspect any real RFC addressing this issue would need to define one or more mitigation strategies to deal with potential breakage associated with changing the drop order for structs+enums.

I'm not sure what form such mitigiation measures would take; the fact that no "obviously correct" mitigation measure has come to mind is probably one big reason why I have allowed inertia to trump all else here

[nikomatsakis]

I see. My priority here was basically just making things as
predictable for end users as possible.

Performance is another interesting consideration. Sorry if I missed
out on a lot of earlier conversation in this respect; do you have a
link to the results you gathered? I am unclear on how important the
order of drops are for performance in an absolute sense, but I can
imagine it might make a difference in some cases. If it's rare enough,
of course, one can always drop the vector explicitly using into_iter
or something like that.

On Mon, Aug 24, 2015 at 06:54:55AM -0700, Aidan Cully wrote:

@nikomatsakis I think you misunderstood? The memory access pattern is important to performance. I think I've shown that the CPU will perform better when memory accesses on contiguous data structures are always in the forward direction. If we want drop to perform as efficiently as possible, then it should also go in memory forward order. If we have field re-ordering, and we don't specify drop order, then the compiler is free to drop fields in memory order, as opposed to declaration order, or reverse declaration order. This will be faster: in my earlier results, it looks like 140ns blocking on a cache fill (that's hit _every time_ in my analogue of memory-reverse drop order), for an operation that usually takes 270ns to read almost 2KB of data (when using the analogue of memory-forward drop order). That's about 1.5x slower. And when I still don't see what problem is solved by defining the drop order to users, I struggle to understand the motivation.

---

Reply to this email directly or view it on GitHub:
https://github.com/rust-lang/rfcs/issues/744#issuecomment-134211923

[aidancully]

@nikomatsakis regarding the link to my performance investigation, there _is_ this message from earlier in the thread, where I link to the test program I wrote, and show some of the output from running the program on my hardware. The program is not very clean (it took me a few tries to demonstrate the effect I expected, and I didn't bother cleaning it up as I experimented) but on my hardware, something like reverse drop order for a large array (in which each element is ~2KB) takes ~410ns, while forward takes ~270, or about 1.5x the time to drop in reverse order compared to forward. I interpret this as a cache miss having a penalty of ~140ns, and since cache line size is likely much smaller than 2KB, I think I could get a much worse multiplier by tweaking the size of each array element.

As a side point, both you and @pnkfelix argue that predictability is important for end users... I doubt I'll change any minds, but I'd like to argue against that point of view, and argue that expressivity is sometimes more important than predictability? As I tried to say earlier, @sfackler's example works for his use case because Rust is predictable here (well, sort of - I actually think it's a bug to rely on drop order in today's Rust, albeit one that won't bite unless/until the compiler changes its drop strategy)... But even given that this code can be made to work, I think it's vulnerable to bug introduction under maintenance: A maintainer is likely not to understand that the field order is intentional, and may change the order because she prefers the ordering to be alphabetical, or to follow top-down layering, or bottom-up layering (whichever is wronger). Her experience in the rest of the language (where drop-order hardly ever matters) will not prepare her to expect the bug she introduces by changing the field order here. There are no robust solutions for this problem, besides building in explicit constructs to control drop order when a developer considers the drop order important - that is, I think we should make the uncommon case (where drop order is a design consideration) explicit in the code. (I call this an "expressivity" concern because I think that the best code maps directly between from developer intention to language syntax: "I don't care about drop order" is the overwhelmingly more common case, and in any case it'd be annoying to need a syntax that makes "I don't care" explicit in code.)

[main--]

As I tried to say earlier, @sfackler's example works for his use case because Rust is predictable here (well, sort of - I actually think it's a bug to rely on drop order in today's Rust, albeit one that won't bite unless/until the compiler changes its drop strategy)...

As @nagisa noted above, Bar<'static> is still _wrong_ in that what it references really doesn't live forever (contradicting the 'static) - the unsafe code _creating_ it simply promises that there won't ever be an observable difference. As @sfackler mentioned, a defined drop order is not a critical requirement but merely a convenience here: When wrapped in an Option, a custom destructor could ensure that bar is dropped first, similar to the DropValue solution.

AFAICS Rust generally doesn't allow intra-struct borrowing for two reasons:

• Borrows are pointers, but structs are moveable. This would change their memory address and break all borrows.

Note how the example circumvents this by keeping the referenced struct inside of a Box. It lives on the heap, so borrows into it are fine even if the box is moved around.

• It's impossible to remember the fields that were borrowed. (e.g. in struct Thing(u64, u64, &u64), which one is borrowed?)

The unsafe code that transmutes the lifetime away simply promises that it will honor the borrow anyways - even though the compiler is no longer checking it.

After this analysis, it's clear that a much nicer solution (for this particular case) would be provided by a language feature that allows the programmer to tell the compiler about intra-struct borrows (and whether they are boxed and therefore moveable; this could apply not only to Box<T> but also types like Rc<T> and even Vec<T> ... although it would be much more complicated there). The compiler could then enforce all necessary safety, including drop order.

(I got this crazy idea because it would improve an RFC I'm working on)

---

To summarize: Drop order being observable from safe code anyways is a very strong point in favor of clearly defining it, but it would be nice if one could leverage this for more than just unsafe conveniency and side effects - namely: Safe intra-struct borrowing.

[glaebhoerl]

Drop order being observable from safe code anyways is a very strong point in favor of clearly defining it

Right... why would we go to pains to make sure that e.g. the results of shifts and of overflow in release builds are always defined and consistent, and then intentionally do the opposite for drop order? (Though perhaps a closer analogy is evaluation order - how precisely do we define that?) It seems like either we should desire a well-defined implementation-independent semantics for (the safe subset of) the language, or we should not, and either way we should at least know it.

[aidancully]

@main--:

To summarize: Drop order being observable from safe code anyways is a very strong point in favor of clearly defining it, but it would be nice if one could leverage this for more than just unsafe conveniency and side effects - namely: Safe intra-struct borrowing.

FWIW, I'd also like to see safe intra-struct borrowing, but if we went there, I figured we'd want to use an explicit mechanism to control the lifetime of fields, something like:

// note that Foo will be immovable due to the self-reference.
// though perhaps it could be made movable with &in and &out pointers,
// and an ops::Move trait.
struct Foo {
  // lifetime of Bar field is named 'a.
  'a: bar: Bar,
  // BarRef is defined such that 'a strictly outlives BarRef.
  bar_ref: BarRef<'a>,
}

This is compatible with my argument: it's an explicit mechanism saying that bar should outlive bar_ref. Even better, it adds another input to the field layout optimization: perhaps with -O time, the optimizer could enforce that bar_ref precedes bar in memory, allowing the prefetcher to work better when dropping the fields of Foo. (It's possible that -O space would want a different field layout.)

@glaebhoerl:

why would we go to pains to make sure that e.g. the results of shifts and of overflow in release builds are always defined and consistent, and then intentionally do the opposite for drop order?

That doesn't bother me, because a) overflows are usually bugs, while different drop orders are usually not bugs (that is, a developer should be immediately penalized for an overflowing arithmetic operation, but usually will not be penalized for changing the drop order: it makes sense for the language to enforce the former and not the latter), and b) I think release builds are compiled such that we don't actually include overflow checks, so they do not necessarily incur overhead?

It seems like either we should desire a well-defined implementation-independent semantics for (the safe subset of) the language, or we should not, and either way we should at least know it.

My position regarding this issue is that it is forward-compatible with any future drop scheme to leave drop order unspecified now: a defined drop order is a subset of the possible drop orders when the order is unspecified, so code written to work with unspecified drop order will necessarily work with any future-defined drop ordering. On the other hand, it is not backwards-compatible to specify a drop order now should we decide to change that order in the future. And it's likely that we haven't considered the design space fully enough to actually know what the "best" drop order is, yet: I think it's likely that memory-forward order will usually be best, but adding lifetime annotations to structure fields would probably change the equation somewhat, and there may be other considerations we haven't encountered yet, as well...

[glaebhoerl]

@aidancully In the original overflow RFC, I had overflow return an unspecified result, out of a desire to avoid people disabling overflow checks as a means to get two's-complement arithmetic (i.e., to avoid them depending on any particular result). There was a big debate about this, and in the followup RFC by @nikomatsakis this was changed to "always panics in debug builds, always returns the two's-complement result if checks are disabled", out of concern about the difficulty, or even feasibility, of precisely defining the difference between "unspecified result" and "undefined behavior", and what "the compiler shouldn't optimize based on it" _really_ means.

So I think there's a resemblance between that debate and this one.

My position regarding this issue is that it is forward-compatible with any future drop scheme to leave drop order unspecified now

The snag is that leaving the order formally unspecified doesn't imply that programs won't depend on whatever order the implementation uses in practice. There's no enforcement mechanism. You can say that these programs are invalid and don't merit consideration, but either way, changing the drop order later on _will_ break them. If we were really serious about wanting to leave our options open, we would have to do something like intentionally randomizing the drop order in each build, for now - that might be sufficient discouragement.

[oberien]

IMHO rust is about perfect safety for programmers. Every undefined behavior contradicts this safety. Especially Drops and it's orders can play a very important role (as seen in many examples above). Therefore I'd like to have the drop-order defined, but with the possibility to also handle it on your own.

[main--]

We're talking about two separate cases here and we need to be careful about not mixing them up:

• Drop order within a struct.
• Drop order within containers (Vec<T> and arrays being the classic examples but this affects things like B-Trees or hashmaps as well, right?)

Structs rarely contain hundreds of fields (or more), so performance considerations are probably less important there. It's also much more likely for users to depend on drop order for correctness in this case (no data on this, just a general feeling).

The story is dramatically different for containers: They often contain _LOTS_ of elements (millions) and drop order may have a substantial performance impact. Note how an abstract container (a set) is unordered (e.g. hashset with linear probing). Without a (defined) internal ordering, there's nothing a defined drop order could be based on (ignoring totally insane approaches like requiring elements to be Ord and sorting them before dropping). So now that the order is undefined anyways, we can at least optimize for performance (to get _something_ out of it).

Naturally, some containers may choose to offer additional guarantees beyond that, especially when they get an ordering for free (arrays, vectors).

So there seems to be only one question left: Should the standard library's ordered containers guarantee the potentially faster forward drop or the (for some users) potentially expected backward drop order? (While "neither" is a third option, it doesn't make sense to me as I'm unable to see any advantage)

---

@Blackhole16 Please note that an undefined drop order is not fully blown (unsafe) undefined behavior.

Consider a program with structs A, B, C. When dropped, A and B print (respectively) "A down" and "B down". C contains A and B. main() creates a C and drops it.

• With a defined drop order, the program's output could be either "A down; B down" or "B down; A down" but consistently. The output would not change across recompiled unless the order of C's fields is changed.
• With an undefined drop order, the program could still only output one of these two options. This time however, the compiler is free to pick one and change its choice when the program is recompiled (even if the source code wasn't changed at all!). While unpredictable, all of this is still perfectly safe. The example above that depends on drop order for safety uses unsafe code and is therefore irrelevant regarding safety concerns (beyond backwards compatibility).
• If relying on drop order (somehow making it observable) were full C-style undefined behavior, the program could also output "Compiler is mad". Or do _anything_, including memory unsafe things.

So while I agree with you that having a defined drop order is nice, I don't think safety is an issue.

[pnkfelix]

I see an unspecified drop order as similar to an unspecified order of evaluation for function call arguments.

One can (and some do) argue that leaving the order of evaluation unspecified helps C/C++ produce better code. See for example blog post (and you can find others with some searches).

Nonetheless, Rust _does_ define the evaluation order for function call arguments to be left-to-right.

• (Caveat: I cannot find an explicit statement of this in the manual. But I am pretty sure that the intention of the language designers has always been for function call argument evaluation to be left-to-right.)
• There is some related discussion of this point on stackoverflow
• There is also some discussion at this rust-lang issue: https://github.com/rust-lang/rust/issues/15300

There was a trade-off here:

• Do we follow in C/C++'s footsteps in the name of giving the compiler the freedom to produce the best code possible?
• Or do we ensure that in foo(A, B), that the side-effects of A will always take place before the side-effects of B, and more generally, that the order of evaluation should not be platform dependent.

Rust decided on the latter.

---

My gut feeling is that we should make a similar stance with respect to drop order: We should probably define it to be _something_.

Having said that, it would certainly be a good idea to take observations such as those yielded by @aidancully 's experiments into account.

• For example, while I still think that dropping struct fields and tuples in reverse order makes a fair amount of sense, I would not object to dropping the elements of arrays (and vectors) in ascending index order.
• I think we can justify this on the basis that it is probably reasonable to expect a LIFO behavior for structs and tuples, but not for arrays.

[nikomatsakis]

So I had started a response and then failed to finish it yesterday, but it seems that @pnkfelix and @glaebhoerl said what I wanted to say, and then some. Basically that leaving the order unspecified is perhaps a false choice (in that we will not be able to change it) and that it has oft been said that all programs are _wildly_ overspecified when it comes to ordering (which is clearly true) -- and yet autoparallelization remains largely unrealized, because it's hard to figure out _just which_ semicolons are not needed.

That said, the argument for struct fields is perhaps the weakest of all, given that we traditionally permit struct fields to be reordered at will, which means that e.g. if you have a struct with fields a, b, and c:

let x = Struct { a: ..., b: ..., c: ... };
panic!() // drops `x` as a whole, and hence (let's say) `c`, then `b`, then `a`

let x = Struct { a: ..., b: ..., c: panic!() };
// drops `b` then `a`, no matter what semantics we choose here, since `x` is not yet fully built

let x = Struct { b: ..., a: ..., c: panic!() };
// drops `a` then `b`, no matter what semantics we choose here, since `x` is not yet fully built

let Struct { b, a, c } = x;
// drops c, a, then b

[aidancully]

@glaebhoerl:

If we were really serious about wanting to leave our options open, we would have to do something like intentionally randomizing the drop order in each build, for now - that might be sufficient discouragement.

I think it's easier than that: have a compiler option to choose the drop order you want, either forward, or reverse, or "whatever the compiler thinks is best". cargo test could be made to run tests twice, once with forward drop order, once with reverse. If the code is robust under both forward and reverse orders, then it does not have a dependency on drop order, and "whatever the compiler thinks is best" will almost certainly work. (I could be wrong about this, but can't think of a counter-example... The test mechanism has established that struct Foo { ... } is robust under both a outlives b and b outlives a, for any pair of fields (a, b).) But this is complexity I was hoping to avoid, and don't want to advocate strongly for this approach.

@main--:

Structs rarely contain hundreds of fields (or more), so performance considerations are probably less important there.

For what it's worth, I think we should be careful here... A given struct may only contain a few fields, but each of those fields may contain a few fields, and each of those fields may contain a few fields, so that by the end the top-level struct might easily contain hundreds of leaves. In my last project, we had a context structure defined in this way that was several hundred kilobytes large (it was the context structure for the main part of the system).

@pnkfelix:

There was a trade-off here:

• Do we follow in C/C++'s footsteps in the name of giving the compiler the freedom to produce the best code possible?
• Or do we ensure that in foo(A, B), that the side-effects of A will always take place before the side-effects of B, and more generally, that the order of evaluation should not be platform dependent.

Rust decided on the latter.

I agree with the analogy to function argument evaluation order, and I find this argument compelling...

[pnkfelix]

@nikomatsakis of course the cases you describe only arise either 1. in the struct's own module or 2. when all of the struct's fields are public.

I.e., it would still be quite possible for a struct designer to _enforce_ a drop order via the order of field definition in the struct, if the language were to actually provide a defined drop order. (Because the struct designer can simply make the fields private, and then audit their own code to make sure the construction orders all make sense.)

---

Update: but of course when we are at the point where someone is using private fields and fn new(..) constructors to build struct instances, etc, then we have sort of left the realm of "you can reify your stack frame as a struct definition and things behave the same", which was the sort of argument I was seeking when I was arguing for reverse drop order.

[nikomatsakis]

Yes, good point. 

Niko

-------- Original message --------

From: Felix S Klock II [email protected]

Date:09/01/2015 17:27 (GMT-05:00)

To: rust-lang/rfcs [email protected]

Cc: Niko Matsakis [email protected]

Subject: Re: [rfcs] should struct fields and array elements be dropped in
reverse declaration order (a la C++) (#744)

@nikomatsakis of course the cases you describe only arise either 1. in the struct's own module or 2. when the struct's fields are all public.

I.e., it is certainly still quite possible for a struct designer to enforce a drop order via the order of field definition in the struct, if the language were to actually provide a defined drop order. (Because the struct designer can simply make the fields private, and then audit their own code to make sure the construction orders all make sense.)

—
Reply to this email directly or view it on GitHub.

[sgrif]

Landed here because I have some code which needs to ensure that the struct fields are dropped in a specific order, and I'm unsure if I'm able to rely on the current behavior. Is the current behavior considered stable? If not, is this change something that can still be considered post-1.0? I'm sure there is a good bit of code out there that is relying on drop order at this point.

[nikomatsakis]

We have traditionally said that the behavior is unstable and reserved
the right to change it. And I do feel that the current behavior is not
ideal.

That said, I too am skeptical that we can get away with changing this
after such a long delay. It suspect we should just stabilize it
roughly as is.

On Sun, Apr 17, 2016 at 02:07:44PM -0700, Sean Griffin wrote:

Landed here because I have some code which needs to ensure that the struct fields are dropped in a specific order, and I'm unsure if I'm able to rely on the current behavior. Is the current behavior considered stable? If not, is this change something that can still be considered post-1.0? I'm sure there is a good bit of code out there that is relying on drop order at this point.

---

You are receiving this because you were mentioned.
Reply to this email directly or view it on GitHub:
https://github.com/rust-lang/rfcs/issues/744#issuecomment-211116774

[nikomatsakis]

Nominating for lang team discussion.

[strega-nil]

@nikomatsakis Can we please just change this and specify? It's really weird and unexpected that

struct Dropper(u32);
impl Drop for Dropper {
  fn drop(&mut self) { println!("{}", self.0); }
}

{
  let x0 = Dropper(0);
  let x1 = Dropper(1);
  let x2 = Dropper(2);
}
// 2
// 1
// 0
{
  let x = (
    Dropper(0),
    Dropper(1),
    Dropper(2)
  );
}
// 0
// 1
// 2

will result in opposite drop orders; and unsafe code needs to be able to, imo, rely on drop ordering to be memory-safe.

[strega-nil]

I've seen too many people asking about drop order to think it's okay to not specify it anymore.

[juhanoi]

Please, at least consider implementing some workaround way to force Drop order, if a default order cannot be established.
I find it difficult to many C libraries, because you cannot store instances of their wrapper structures in struct as their cleanup functions may get executed in wrong order causing memory leaks etc.

[strega-nil]

Just an example:

struct ReadsOnDrop<'a>(&'a u32);
impl<'a> Drop for ReadsOnDrop<'a> {
  fn drop(&mut self) { println!("{}", self.0); }
}

// for this to be safe, you must order it like this
fn test0 () {
  let x = Box::new(0);
  let y = ReadsOnDrop(&*x);
}

// for *this* to be safe, you must order it like this
struct InternalRef {
  y: ReadsOnDrop<'static>, // always valid as long as InternalRef is alive
  x: Box<u32>, // is a Box so that the address stays the same
}

fn test1 () {
  let x = Box::new(1);
  let y = &*x as *const _;
  let ref_ = InternalRef { x: x, y: &*y };
}

// Now it's the same ordering as test0, what a normal person might expect to do
struct InternalRefUnsafe {
  x: Box<u32>,
  y: ReadsOnDrop<'static>,
}

fn test2 () {
  let x = Box::new(2);
  let y = &*x as *const _;
  let ref_ = InternalRef { x: x, y: &*y };
}

fn main () {
  test0 ();
  test1 ();
  test2 ();
}
// 0
// 1
// segfault!

This is weird and confusing.

[nikomatsakis]

I agree we should specify a drop order. I don't know that we should change the current one, though I would. Also, it seems that this nomination tag from April got overlooked due to the lack of a T-lang tag. :(

I'm not sure what's the best way to test if we could change this. We could certainly attempt a "crater-like" run that also runs tests, but I don't have a lot of confidence in that.

[strega-nil]

@nikomatsakis We don't specify it now, therefore we can break it. We should run it through nightlies, but any code that relies on it now is broken. Specifying it the "wrong" way just because of a trick of the implementation would hurt rust forever with confusing semantics, instead of in the short term with a change that breaks code which was relying on something we specifically didn't specify _so_ we could change it.

[strega-nil]

Specifically, we should advertise this change _hard_, but it shouldn't harm the long-term goodness of the language.

[sfackler]

There was a window to make this change, and it passed a year ago. It seems astonishingly irresponsible to change drop order a _year_ into Rust being a stable language that people should use for real things. Is there something I'm missing or is this purely an aesthetic concern?

Real code in the wild does rely on the current drop order, including rust-openssl, and _there is no upgrade path_ if we reverse it. Old versions of the libraries will be subtly broken when compiled with new rustc, and new versions of the libraries will be broken when compiled with old rustc.

Unless I am misremembering, our stability guarantee was not "we will make arbitrary changes as long as we post about them on reddit and users.rust-lang.org first".

[strega-nil]

@sfackler We have made no promises about drop order. Specifically, we have promised that there is _no guarantee_ about drop order. That is different from stability. That is a promise of instability. If someone were relying on box patterns, it would not be a problem to break their code because we have said that box patterns are unstable. It is the same situation here. We can fix the code if need be; we can make the transition as easy as possible. I don't agree we have any promise to stability in this area.

[arielb1]

Quoting RFC #1122:

Order of dtor execution within a data structure is somewhat inconsistent (see #744).

[pnkfelix]

This issue is ready for _some_ RFC.

One such potential RFC would be to specify and stabilize the drop order as currently implemented.

Another such RFC would state a different drop order, and just state that we plan to change it overnight at some point. (I believe this is an example of an approach that @sfackler stated would be irresponsible.)

Another one would be an RFC that specifies a forward path to _change_ the drop order, in a _slow_, _controlled_ way.

• For example (sort of off the top of my head), we could add an struct attribute that specifies to use the current drop order for the fields of that struct, and then also add a lint that warns for any struct without that attribute that has >1 field that has associated destruction effects.

In any case, this issue has been discussed for some time, so it seems like a good time for us to finally take action.

[nrc]

Further to @pnkfelix's comment (which, to clarify, was because we discussed this issue at the lang team meeting this week), the team felt that this is an important issue and one where we would like to make progress sooner rather than later. We felt that an RFC is the best way to make further progress here.

The team felt that simply changing the drop order without a migration plan, or with only advertising was not an option due to silent and subtle nature of failures.

That leaves either:

• an RFC to stabilise the current behaviour,
• an RFC to change the current behaviour by a well-defined process.

At this stage the lang team does not have a consensus over which direction to move in. In particular, we feel that making a call on the trade-off in any approach would require specifics about the details of that approach. (Personally, I would prefer change, if an acceptable plan can be formulated).

If anyone involved in this thread would like to write either RFC, we'd be very happy! If you would like to write one and need any help or advice please ping someone from the lang team and we'd be happy to help.

[carllerche]

I have already written code that relies on the current drop order for correctness. It would be nice if it stays as is :)

[aochagavia]

I think a possibility would be to:

• Add something like #[drop_order(legacy)] struct Foo { ... }, in order to opt-in for the current unstable behavior.
• Add something like #[drop_order(stack)] struct Foo { ... }, in order to opt-in for the new behavior (which still needs to be specified, so we may end up choosing a different name than stack).
• Add a warning lint for drop implementations that appear in modules where unsafe is used, in case they don't opt-in to any drop ordering. It seems reasonable to assume that modules are the limit of the scope of unsafe code, as explained here.
• Post a PSA indicating that the drop order is going to change in the future and that you are required to update your code in case you rely on the current (unspecified) one.

IMO the combination of a lint and a PSA is a great way to raise awareness for all people affected by the change.

Note that #[drop_order(legacy)] and #[drop_order(stack)] seem non-trivial to implement, since structs are not the only place where the drop order matters (eg what happens if you create a tuple in a function and rely on its destructor order at the end of the scope? You don't actually store it in the struct, but you still want to choose the drop order). Alternatives include specifying drop order at a higher level (module or crate), or allowing using it at a function level (though the semantics could be confusing in this case).

[burdges]

Just a question : Is the order specified as reverse in C++ to help reduce use after free? If so, would it be less important for Rust code which way the drop order gets standardized? I'd kinda think code that might care would needs Arcs everywhere anyways. Interacting with C++ code might become an issue of course.

[Amanieu]

@burdges In C++, fields in a struct are always initialized in the order they are declared in the struct definition. Field destruction is therefore done in the reverse order since destructors should be called in the reverse of the order that objects were constructed in.

This doesn't apply to us since in Rust the programmer has direct control over the order that fields are initialized in (left-to-right expression evaluation order).

[aochagavia]

@nrc I have summarized my thoughts on the subject in a blog post. Please let me know if you would like me to write an RFC based on it.

[mpartel]

Perhaps this is a naive and impractical suggestion, but a possible refinement of the create attribute idea in @aochagavia's blog might be the following: Any new crate must declare (in Cargo.toml) a language version. The drop behaviour for a struct would then depend on the language version of the crate that defines the struct.

Advantages:

• New crates would default to the new behaviour. Older crates would start getting compiler warnings to set a language version.
• The new drop order, and a mechanism for introducing other breaking changes in the future.

Disadvantages:

• A codebase can now have mixed drop order: new language version crates can depend on old language version crates and vice versa.
• Language semantics depending on a config setting adds complexity and can get out of hand if we're not careful.

[ahmedcharles]

@Amanieu In C++, you don't get to control the expression evaluation order, in the general case. In Rust, you get to control the expression evaluation order, but since Rust doesn't have constructors, it doesn't have an analogue to initialization order in C++, since C++ only defines the order in which constructors run, not the expressions used when passed to constructors as arguments.

[jan-hudec]

@ahmedcharles, in C++ you don't control evaluation order of arguments in one argument list, but between the members, arguments to the next member or base constructor are not evaluated before the previous constructor completes.

The Rust constructor expression is analogue of the C++ initialiser list. But due to the difference in initialisation order, Rust can't build a static drop order for the type (unlike C++ that does).

[aochagavia]

This issue can be closed now, as the drop order has been specified by RFC 1857