Pass by value semantics

[jumpnbrownweasel]

Just for completeness, I think you’re referring to this issue:

eliminate hidden pass-by-reference footguns

[LucasSantos91]

@npc1054657282

I didn’t fully understand. If item itself is a type of data that requires a deep copy, this should be a logical issue; semantically, it is an error, not a parameter-passing optimization problem.

Look again. Item can be a u8, the issue still happens. item is semantically copied into the function stack. It should be semantically safe to move the data inside the list somewhere else. But if you surreptitiously changed the value to a pointer, that pointer will be dangling after the realloc, before you could copy it.
Search for “Attack of the Killer Features” on youtube, by SpexGuy.

[LucasSantos91]

Worst title ever for an issue. It should have been called “Hidden pass by reference miscompilation”. A footgun is when a feature is easy to misuse. This is correct code being broken by an optimization, that’s a miscompilation.

[npc1054657282]

@pzittlau

If you pass by pointer(reference) nothing will be copied onto the stack(except if you dereference it later onto a stack variable).

It may need to be reiterated that here, the ‘pass-by-reference’ is designed based on the Windows calling convention.

For these aggregate types passed as a pointer, including __m128 , the caller-allocated temporary memory must be 16-byte aligned.

Simply put, for passing larger structures, the Windows calling convention is: allocate a temporary copy on the stack, while passing the parameter by reference.

This allows the caller to optimize based on known information: the caller knows the mutability and aliasing of the parameter, and if the caller knows the parameter is immutable, the temporary copy can be omitted.

And based on Zig’s previous issues, I believe that Zig does not make a temporary copy for parameters that are not immutable either.

[pzittlau]

Oh my bad. I overread the windows part beforehand.

@npc1054657282

This allows the caller to optimize based on known information: the caller knows the mutability and aliasing of the parameter, and if the caller knows the parameter is immutable, the temporary copy can be omitted.

It’s late for me so excuse me if I’m wrong, but isn’t this still susceptible to this?

[npc1054657282]

@pzittlau

It’s late for me so excuse me if I’m wrong, but isn’t this still susceptible to this?

@pzittlau

pub fn main(init: std.process.Init) !void {
    var list: std.ArrayList(LargeItem) = .empty;
    defer list.deinit(init.gpa);

    try list.append(init.gpa, LargeItem{ .data = [_]u8{42} ** 128 });
    // Value semantics guarantee this should be a safe snapshot copy.
    try ownAppend(&list, init.gpa, list.items[0]);
}

My understanding is as follows:
list is mutable, and list.items[0] is mutable.
Therefore, semantic analysis cannot conclude that the temporary copy here should be eliminated, so it will still be temporary copied according to the usual pass-by-value semantics.

@LucasSantos91

Look again. Item can be a u8, the issue still happens. item is semantically copied into the function stack. It should be semantically safe to move the data inside the list somewhere else. But if you surreptitiously changed the value to a pointer, that pointer will be dangling after the realloc, before you could copy it.

Can this explaination helps?

[LucasSantos91]

@npc1054657282

list is mutable, and list.items[0] is mutable.
Therefore, semantic analysis cannot conclude that the temporary copy here should be eliminated, so it will still be temporary copied according to the usual pass-by-value semantics.

Yes, now find any example where this is safe, guaranteed, and can be proven programatically. There will be a minuscule amount of trivial cases, which are already optimized in every every compiler. Zig’ PRO was supposed to be the next step forward.

[npc1054657282]

@LucasSantos91

which are already optimized in every every compiler. Zig’ PRO was supposed to be the next step forward.

@npc1054657282

The reason I advocate for “optimization guaranteed by semantics” is precisely to ensure that even if optimizations are not enabled, certain large object copies are not expected to happen. However, always using noalias readonly pointers undermines the performance of non-optimized scenarios from another perspective.

My ambition is not that great; my idea is simply this: for those stateless immutable data, copy optimization for pass-by-value can be determined semantically, so that even users in scenarios where the optimization is not enabled can be assured that there is no additional overhead here.

This is especially useful for generics.

[matklad]

@LucasSantos91

This is correct code

The thing is, whether the code is correct depends on definition of the language. You could define a language such that this sort of aliasing is illegal behavior, ad we might still get something like that eventually: noalias on all parameters by default (with debug safety); ability to specify mayalias · Issue #1108 · ziglang/zig · GitHub.

My understanding is that, at the time the issue was written, this was literally undefined behavior, in a sense that the language didn’t conclusively rule one way or another whether this sort of code is valid.

[gwenzek]

copy optimization for pass-by-value can be determined semantically

I like the idea. Though I always hated the “will copy elision trigger” C++ game.
But maybe that’s a UX problem. Like if there is a way to ask ZIg compiler, is there a copy ellision here ? it’s way better.

[LucasSantos91]

With PRO, some types

@matklad

@LucasSantos91

This is correct code

The thing is, whether the code is correct depends on definition of the language.

Defining it this way would make some kinds of code impossible (literally) to write correctly. Which was exactly the case when PRO existed.

Take a look at this beautiful example. I doubt anyone will disagree with PRO being removed after seeing it.
In the example, the functions involved had no pointer arguments, and in fact, there’s not a single pointer to be seen, other than a discarded one (_ = &b), which happens after the function call. That user even explicitly created an unnecessary copy on the stack, even though the argument itself was passed by value and should be, semantically, copied. The copy explicitly eliminates aliasing.
PRO attacked anyways.
The compiler eliminated the explicit copy and passed a one-byte struct by reference, creating aliasing, even though semantically the user did everything to avoid aliasing.

[LucasSantos91]

@npc1054657282

My ambition is not that great; my idea is simply this: for those stateless immutable data, copy optimization for pass-by-value can be determined semantically, so that even users in scenarios where the optimization is not enabled can be assured that there is no additional overhead here.

I don’t think it’s possible to determine these conditions hold without analyzing the code, that is, enabling optimizations. And I’m pretty sure your small ambition is what LLVM already does, with optimizations enabled.

[gwenzek]

I feel the discussion is a bit too much all or nothing.
I would love some reliable optimization that currently LLVM don’t do.

The main issue with PRO is a pointer may alias with one of the argument magic pointer.

But there can be no alias if nobody knows the magic pointer.
Which is true if you just created the value on the stack and you didn’t give the pointer to anyone.
It means taking a pointer to an argument or a stack variable requires making a new copy for further pass by reference call.

• in the array list example, items[0] isn’t on the stack, so it need to be copied to it before being passed by reference

The other big footgun with naive PRO

fn merge(a: *A, b: A) { ... }

fn shootfoot() void {
  var a: A = .init;
  merge(&a, a);
}

• here shootfoot needs two copies of a because of the reference.

[gwenzek]

This example is baffling,
but it seems to be due to a poorly implemented PRO, rather than PRO in general.
Why would const b = a; not materialize a copy of the global variable a on the stack ?

[npc1054657282]

@LucasSantos91

I don’t think it’s possible to determine these conditions hold without analyzing the code, that is, enabling optimizations. And I’m pretty sure your small ambition is what LLVM already does, with optimizations enabled.

If we want to infer aliasing situations, I think it requires relatively complex semantic analysis. However, I believe that in most cases the demands we face are very simple: when we pass stateless data through the abstraction of a function, we do not want the parameter passing to incur an extra meaningless expensive copy in an unoptimized scenario. To explicitly ensure this, one would have to manually write noalias *const T in the function signature, which is usually not what we want.

The cost for users to achieve this guarantee is very simple: cultivate the good habit of avoiding var when using stateless data. Doing so makes it easy to determine through semantics that optimization is possible.

[matklad]

@LucasSantos91

Defining it this way would make some kinds of code impossible (literally) to write correctly.

I wouldn’t be so categorical! I think there is a coherent language where passing parameters and const bindings in general is specified as creating an aliases for data, where the aliased data is considered “borrowed” (so, mutating it while such a binding is active is illegal behavior), and where there’s an explicit operator to force a copy.

I can clearly see two ways to look at this whole design space:

You can see it as extremely weird that function parameter isn’t an independent copy of memory, and can alias something else.

But, equally, you could see it as extremely weird that compiler silently duplicates or moves values behind your back.

[gwenzek]

I feel one thing that would help the compiler detect aliases is to prevent pointers from being copied by default.
Like fn (x: *Foo) void is not allowed to store x pointer anywhere. Only fn (x: *free-for-all Foo) can.

[gwenzek]

@LucasSantos91

I’m pretty sure your small ambition is what LLVM already does, with optimizations enabled.

LLVM is actually quite bad at removing copies, unless it inlines.

Compiler Explorer - Zig

In this examples I would expect exactly one copy, when receiving data from outer world.

[LucasSantos91]

Maybe. I would hope so. My biggest wish for Zig is for PRO to come back correctly. I don’t know if it’s impossible, but the evidence does point in that direction. Like I said earlier, if we use C’s semantics for parameter passing, then we benefit from C’s optimizations in LLVM. And those guys have been optimizing C for a very long time, and they’ve done amazing things, but they have failed to implement this. Then Andrew and the core team came, stubbornly insisted on it for so long, and also failed. If it is possible, it will certainly take a genius with some kind of breakthrough. We’d have a better shot at this if we changed the semantics of parameter passing to something different from C, like the in/out parameters that some languages are trying.

[LucasSantos91]

That code is unoptimized. On ReleaseFast the behavior is what you expected.