Single-Assignment C(sac-home.org)
sac-home.org
Single-Assignment C
http://www.sac-home.org/doku.php
43 コメント
That's what I thought, too.
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.
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.
Single assignment style has structural similarities to continuation-passing style in FP iirc.
i recall a micro language built around the infamous brainfuck that has a non destructive read for function arguments. seems like a bigger concept exists. let the caller determine what the called can modify.
Agreed, I'm currently taking a similar approach, but forgoing pointers as much as possible as well. This leads to structs being passed by value, and const abuse.
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.
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.
> I've sedded openempires to replace occurrences of _Type name_ with C++'s _Type& name_ for all functions arguments
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?
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?
> This leads to structs being passed by value
do compilers generally optimize this away on -O3, or do you just accept the performance hit in exchange for prettier code?
do compilers generally optimize this away on -O3, or do you just accept the performance hit in exchange for prettier code?
If it's a static method (or in an anonymous namespace in C++), it should get fixed at any optimisation level. However if it's a global method, you'll need to pass -flto to defer optimisations to link time to make it work.
>I was interested because I've started adopting the single assignment style in my own code
What benefit have you seen from doing this? Genuinely curious.
What benefit have you seen from doing this? Genuinely curious.
It does have some positive consequences for optimization. For example, if you "recycle" local variables by using them again for different purposes, you might think you're saving stack space by sharing the space. You're not. Optimizers are pretty good at storing multiple variables in the same stack slot when their usages (i.e. "live ranges") are disjoint.
On the other hand, if you write:
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,
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;
> Optimizers are pretty good at storing multiple variables in the same stack slot when their usages (i.e. "live ranges") are disjoint.
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". :-)
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". :-)
Are there production compilers who don't do SSA nowadays?
Go apparently didn't do SSA until 1.7. Then again it's not exactly an optimising compiler.
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
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
It's easier for compilers to optimize. https://en.wikipedia.org/wiki/Static_single_assignment_form
It actually is not. The compiler has no problems turning your imperative code into SSA on its own, and PHI functions are no problem for optimizers.
I guess it's just for readability and easier reasoning about the code.
I guess it's just for readability and easier reasoning about the code.
Any MFA code is trivially converted to SSA and that's pretty much the first thing your compiler will do.
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.
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.
You're not the OP of the comment, who is a compiler writer (C, C++, D). I hope he'll weigh in with his rationale.
This is interesting; I just investigated SAC for the first time about seven hours ago (I actually posted a license-fragment from it on my social media account: https://blob.cat/notice/9qMowPTjR9F7fjid3Q), finding it technically impressive but unfortunately proprietary.
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.
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;
As an aside,
[1]: https://en.wikipedia.org/wiki/Euler_method [2]: https://en.wikipedia.org/wiki/Semi-implicit_Euler_method
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
It's not C, but a new language with similar syntax. Based on reading the docs at [1], the assignment is sugar for generating a new binding for the result of that expression that shadows the previous one.
[1]: http://www.sac-home.org/doku.php?id=about:core
[1]: http://www.sac-home.org/doku.php?id=about:core
I don't understand.
What does the "single assignment" bit get you that a compiler with an SSA pass doesn't?
What does the "single assignment" bit get you that a compiler with an SSA pass doesn't?
An SSA pass is an implementation detail that can't change language semantics, so, as I understand, it either doesn't transform or applies only to pointers when values have externally (to the block in which they are defined) visible mutation based on the language semantics; having single assignment semantics and thereby lacking mutability is a significant property for, particularly, parallel code with shared references. If no one can mutate a reference, you don't need Rust- or Pony-like tracking of who can see or mutate it, it's safe for everyone to see it.
I assume the removal of pointer aliasing?
Probably that the original binding of p is immutable, as it would be in a functional language: you can create a new binding, but you can't actually change the value of the existing binding.
Unless there's something I don't understand, that's what the single static assignment pass does in a compiler.
New bindings live at different addresses (if you pass a pointer to one binding, and then make a new binding with a new value, the existing pointer will point to the old value and not the new binding's value) and bindings made in a loop iteration won't live to the next iteration.
This sounds like an implementation detail. What does the language spec say about the outcome.
The (C) language spec says that:
x = 5;
int* p = &x;
x = 6; // new binding of x
printf("%i\n",*p);
Different bindings are like entirely different variables that just coincidentally share the same name.
When the SSA pass happens in the compiler it's already too late to have guaranteed certain behaviours from the source stage...
E.g. you can turn a C program into SSA, but if you have aliasing issues, it's not gonna fix them...
E.g. you can turn a C program into SSA, but if you have aliasing issues, it's not gonna fix them...
Maybe it’s short for:
p[t+dt] = p[t]+v[t]*dt
v[t+dt] = v[t]+a[t]*dt
?The home page is fairly free of any details about SaC, though I do now know an awfully lot about who is involved. Also, there's no reference manual.
Where can I find a tutorial, examples, or any concrete details?
Where can I find a tutorial, examples, or any concrete details?
There's a docs page linked from the home page with a tutorial and various other docs:
http://www.sac-home.org/doku.php?id=docs:main
http://www.sac-home.org/doku.php?id=docs:main
Related from 2013: https://news.ycombinator.com/item?id=6949525
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).