Single-Assignment C
sac-home.org
sac-home.org
I was interested because I've started adopting the single assignment style in my own code, and like the results (the code is easier to comprehend).
Ray h_cast(const Hero hero, const Hit hit, const Sheer sheer, const int yres, const int xres)
{
const Point end = p_sub(hit.where, hero.where);
const Point corrected = p_turn(end, -hero.yaw);
const Line trace = { hero.where, hit.where };
const Projection projection = p_project(yres, xres, hero.fov.a.x, hero.pitch, corrected, hero.height);
const Ray ray = { trace, corrected, p_sheer(projection, sheer), hit.surface, hit.offset, hero.torch };
return ray;
}
As for performance I am heavily relying on LTO. I seem to get a 50% performance boost with pass by values on structs - as I've sedded openempires to replace occurrences of _Type name_ with C++'s _Type& name_ for all functions arguments - and the added pointer aliasing and de-references bogged the engine down in heavily forested areas.
Compilers love singly assigned const values, and seem to suffer under heavy pointer aliasing.
This isn’t a valid transformation :/
> Compilers love singly assigned const values
I mean, they’re going to convert to SSA for you anyways.
> and seem to suffer under heavy pointer aliasing
Have you tried restrict?
do compilers generally optimize this away on -O3, or do you just accept the performance hit in exchange for prettier code?
What benefit have you seen from doing this? Genuinely curious.
I guess it's just for readability and easier reasoning about the code.
So doing SSA by hand makes no real difference to the compiler unless your compiler is so trivial it doesn't start by converting its input to SSA.
On the other hand, if you write:
int i = value;
... use i ...
... lots of code ...
i = another value;
... use i ...
But just for code comprehension, it is better to use different variables for disjoint uses. A related point is to "shrink wrap" a variable into the smallest scope you can. The less you have to look over the rest of the function for uses, the better.
And lastly,
int x = value;
if (condition) x = another;
const int x = condition ? value : another;
It's also somewhat common for functional language implementations to use CPS rather than SSA e.g. ghc does CPS conversion rather than SSA, and apparently didn't even used to do that: https://stackoverflow.com/a/8031177/8182118
Exactly. Also the true lifetime of the variable might be way longer than what the programmer thinks due to compiler reordering the code to help CPU with dependency chain latency. (I've also seen plenty of cases where CPU out-of-order engine apparently completely fails, but (Intel) compiler saves the day.)
> int x = value;
> if (condition) x = another;
> is just better written as:
> const int x = condition ? value : another;
> It reads better, and it enables x to be const, which is always better.
While const sure is safer, the generated code should be same in both cases.
In this case I agree with you. But not if the ternary operator has any more complexity, because it quickly becomes hard to read. In my experience complicated ternary operators are rather bug prone, especially with large teams.
That said, I guess you agree with me your benchmark being "reads better". :-)
There's a lot to be said for real single-assignment programming. It provides many of the advantages of functional programming. The code is more readable, because the intermediate variables have names. When you need to do something imperative, you don't have to jump through hoops to do it. Go and Rust both encourage that style - the default is to create a new variable, not assign to an old one. (The semantics of multiple := assignment in Go, where some variables are assigned and others are created, though...)
One of the historical headaches of C is that function parameters are non-const by-value by default. That's backwards. The default should be const ref. If you need a local mutable copy, or the parameter is an "in-out", as Ada calls it, you should have to specify that. Those are the less likely cases and the ones that cause trouble if missed. Passing small const ref values by value is a compiler optimization; the programmer shouldn't have to worry about it, especially since whether it's a win varies with the target machine.
The language in the article seems more like a variant of Matlab, not C.
Was there news about it, or something? It came to mind because something I was wanting to try depended on it, and it doesn't get posted to HN very often, so I'm really curious as to how you found it.
p = p + v * dt;
v = v + a * dt;
What does the "single assignment" bit get you that a compiler with an SSA pass doesn't?
x = 5;
int* p = &x;
x = 6; // new binding of x
printf("%i\n",*p);
E.g. you can turn a C program into SSA, but if you have aliasing issues, it's not gonna fix them...
p[t+dt] = p[t]+v[t]*dt
v[t+dt] = v[t]+a[t]*dt
? v = v + a * dt;
p = p + v * dt;
[1]: https://en.wikipedia.org/wiki/Euler_method [2]: https://en.wikipedia.org/wiki/Semi-implicit_Euler_method
Where can I find a tutorial, examples, or any concrete details?