Order of operations when initializing from a compound literal

[geoffromer]

Summary of issue:

When a tuple or struct literal is used as an initializer, how do we order operations within vs. across elements?

Details:

Consider the following code, written in terms of #5389 form generics:

fn MakeA() -> var A;
fn MakeB() -> var B;

// var A -> val C and var B -> val D
impl form(var A) as Core.ImplicitAsPrimitive(C) where .ResultForm = Form(val C);
impl form(var B) as Core.ImplicitAsPrimitive(D) where .ResultForm = Form(val D);

var cd: (C, D) = (MakeA(), MakeB());

Evaluation of that last line requires 6 separate function calls: for each tuple element, we have to call a Make function, an implementation of Core.ImplicitAsPrimitive.Convert type conversion, and an implementation of Core.Copy.Op (which can't be elided because in this example, the conversions happen to be value expressions, not initializing expressions).

What order should these function calls happen in?

I assume that we want to go left-to-right, don't want to have different rules for different elements, and don't want to violate causality, but that still leaves several possible orders. The two extremes are:

• Breadth-first: evaluate both the factory calls, then both type conversions, and then both copies.
• Depth-first: evaluate all operations involving the first element, then all operations involving the second.

There are also a couple of hybrid options, where we combine some steps depth-first within an overall breadth-first order.

Depth-first traversal has the appealing property that it doesn't need any temporaries to remain live across a function call: the result of each call is immediately consumed by the next call, or written directly to a durable variable. This may enable us to generate more efficient machine code. However, it poses some substantial challenges:

The implementation of pattern matching seems like it will require major architectural changes to support interleaving scrutinee evaluation with pattern matching. We can avoid this problem by evaluating the scrutinee breadth-first, and limiting the depth-first order to conversion and pattern matching, but it's not clear if that's meaningfully better than fully breadth-first.

It seems like we would need major changes to #5389 and/or other parts of the language design if we want to model a tuple-to-tuple type conversion in terms of a call to Core.ImplicitAsPrimitive.Convert while retaining depth-first evaluation. Note that there are at least two separate problems here: interleaving the Convert call with its arguments, and with the code that uses its outcome.

Finally, this question applies to structs as well as tuples, and in that context a depth-first order reopens the question of how to handle cases where the field order differs:

var cd: {.c: C, .d: D} = {.d = MakeB(), .c = MakeA()};

We had previously decided to evaluate the initializer in the order it's written, and then evaluate the conversions and copies in the order specified by the destination type, but that only works if the order of operations is at least partially breadth-first. In a fully depth-first world, we have to choose a single field order for the entire initialization.

Any other information that you want to share?

This question came up here during the review of #5545, and there was some preliminary discussion at the 12-02 open discussion.

[tkoeppe]

Would it be an option to leave the order of evaluation unspecified, like in C++ (with similar non-interleaving constraints)?

That might improve the maintainability of code: WIth a specified order, a superficially simple seeming refactoring from f1(x(), y()) to f2(y(), x()) becomes suspect since the original code may have depended on the evaluation order, and would need to be refactored to something like var tmp = x(); f2(y(), tmp);.

[geoffromer]

Keep in mind that this issue isn't about the order of evaluation of function arguments, it's about the order of operations when initializing from a tuple or struct literal. In that context even C++ doesn't leave the order unspecified. For example, C++ requires designated initializers to be written in the same order as the field declarations, despite the substantial ergonomic and interop burden that imposes, in order to ensure that fields are initialized in the reverse of the order they'll be destroyed in. The whole problem in the last paragraph of the issue report is that Carbon chose to drop that restriction, and one of the open questions here is to what extent we can relax C++'s "destruction order is the reverse of initialization order" principle.

Also, I would argue that from a maintainability point of view, an unspecified but stable evaluation order isn't much different from an explicitly specified evaluation order. Even if developers are aware that the order isn't specified, it's too easy for order-dependence to sneak in by accident, so Hyrum's Law applies pretty strongly. I don't expect the toolchain to be able to prevent that by making the evaluation order unstable, because abstracting it away is likely to impose a substantial performance overhead in the compiler (not to mention the concern that different orders may have substantially different run-time performance).

[tkoeppe]

Keep in mind that this issue isn't about the order of evaluation of function arguments [...]

Ah yes, of course. Never mind then.

Also, I would argue that from a maintainability point of view, an unspecified but stable evaluation order isn't much different from an explicitly specified evaluation order. [...]

Yes, people might inappropriately depend on it, but at least it would allow pointing out a mistake, and not be something one has to assume everywhere. Also, if the unspecified-but-stable order were sufficiently surprising, it might at least make people take notice.

But from a practical point of view regarding the question, this would simply allow you to not have to come up with a specific answer :-)

[chandlerc]

I'd like us, to the extent possible, to really push to not have unspecified order of evaluation. I'd rather instead provide tools (potentially meta-programming tools) to allow authors of code in corner cases where they need to toggle order in complex ways to do so explicitly.

---

Getting at the original question of whether there is a fundamental performance concern when thinking about layer-wise evaluation vs. element-wise evaluation, I think I have a demonstration that confirms this does matter and results in a very significant efficiency difference:

https://cpp.compiler-explorer.com/z/Pxaar4edb

In short, element-wise is categorically less work and requires less storage... So I suspect we should be working hard to adapt the design in that direction.

This shifts me to wanting to always do element-wise evaluation when we can.

I think this even makes me suggest we should change our decision around re-ordering initializations to say they are element-wise evaluated in the order the expressions are written, even if that initializes members in an order different from the declaration order in the destination type. And opting into the capability to have member reordering initialization the way struct types do (and possible other types will if we develop a way to enable that) inherently involves accepting the initialization of members in any possible order. For initializing class types from a reordered struct type, if we want to be able to disallow that we should add a facility to the language that forces the order to be consistent in the initialization rather than hiding the difference with layer-wise initialization.

[geoffromer]

It seems like the same reasoning would apply to assignment as well as initialization. Should tuple and struct assignment also be evaluated element-wise?

[chandlerc]

It seems like the same reasoning would apply to assignment as well as initialization. Should tuple and struct assignment also be evaluated element-wise?

Possibly... but maybe that is a separable step here?

There are some differences -- you can unroll and manually write element-wise assignment for both tuples and structs, but you don't have that flexibility with initialization (I think)...

[geoffromer]

Another question: it sounds like we want this to proceed element-wise:

var cd: (C, D) = (MakeA(), MakeB());

But what about this?

let (var c: C, var d: D) = MakeAB();

Or even this?

var cd: (C, D) = MakeAB();

I assume we don't want to interleave the body of MakeAB with the conversion and pattern matching in the caller, so in those cases we can't avoid having live temporaries that persist across the Convert and Copy.Op calls. Does that mean we might as well do the whole thing layer-wise, or should we still proceed element-wise after the initial function call? Does the answer depend on whether MakeAB returns val (A, B) or (val A, val B)?

The answer I'm leaning toward is that we proceed element-wise at the smallest possible granularity. In other words, we never observably perform an operation at one layer if there's an operation that we could perform at a lower layer. That means the two new examples proceed in the order:

1. Evaluate MakeAB()
2. Convert A -> C.
3. Copy C to final destination.
4. Convert B -> D.
5. Copy D to final destination.

This order seems to be the most stable in the face of code evolution: it's hard to come up with a plausible refactoring that changes the relative order of the operations. Also, I can't tell if there's a meaningful efficiency difference among the options here, but if so, it seems likely to favor this approach.

However, it's possible that other orders would be more intuitive, and I suspect that other orders may be easier to implement. For example, suppose A and C are compatible types, as are B and D, and MakeAB() returns ref (A, B):

let ref cd: (C, D) = MakeAB();

From a type-checking perspective, matching a tuple ref binding can't be decomposed into element-wise sub-matching operations, the way matching a var or value binding can, so this must proceed layer-wise. This doesn't matter from the user's point of view, because none of the conversions here have observable side effects, but it may complicate the structure of the implementation.

It seems like the same reasoning would apply to assignment as well as initialization. Should tuple and struct assignment also be evaluated element-wise?

Possibly... but maybe that is a separable step here?

Yes, I'm pretty sure it's separable, I'm just wondering if we want to separate it. The two are closely coupled enough that treating them the same might be easier to specify, and maybe easier to implement.

There are some differences -- you can unroll and manually write element-wise assignment for both tuples and structs, but you don't have that flexibility with initialization (I think)...

I think that's right, but enabling that sort of unrolling seems like it might be within reach if we wanted to go that route, at least for objects, because unformed state gives us a way to talk about objects that haven't been fully initialized. I don't think #5913 quite gets us there, but the discussion of raw storage seems like it points the way. The ergonomics and safety of that probably wouldn't be great, though, and I don't think it really helps with values, especially since value acquisition isn't cheap for tuple and struct types.

[chandlerc]

I think I agree about using the smallest granularity we can. In particular:

fn MakeAB() -> (A, B);
fn MakeABRef() -> (ref A, ref B);
var ab: (A, B) = MakeAB();

// Call, convert, and copy element wise:
var x1: (C, D) = (MakeA(), MakeB());

// Convert and copy element wise for all of:
let x2a: (var C, var D) = MakeAB();
var x2b: (C, D) = MakeAB();
var x3: (C, D) = MakeABRef();
var x4: (C, D) = ab;

I think having inconsistent element-wise-ness for x2-x4 would be more surprising than the fact that ref bindings can't work this way.

But if we can't find a reasonable implementation strategy, we should revisit.