Dear Delphi compiler - are you kidding?!
Dear Delphi compiler - are you kidding?!
Yes, following code it compiled with optimizations on and the method is inlined.
Project48.dpr.28: FastDefaults.TComparer.Default.Compare(1, 2);
004CDF65 C745F801000000 mov [ebp-$08],$00000001
004CDF6C C745F402000000 mov [ebp-$0c],$00000002
004CDF73 8D55F4 lea edx,[ebp-$0c]
004CDF76 8B12 mov edx,[edx]
004CDF78 8D45F8 lea eax,[ebp-$08]
004CDF7B 8B00 mov eax,[eax]
004CDF7D 3BD0 cmp edx,eax
Johan Bontes I found out the cause:
The Compare method has this code:
Result:= integer(PInteger(@Left)^> PInteger(@Right)^)-
integer(PInteger(@Left)^< PInteger(@Right)^)
If I just call this function then it inlines the code better:
function CompareInt(const left, right): Integer; inline;
begin
Result := Integer(left) - Integer(right);
end;
and generates this asm:
Project48.dpr.28: FastDefaults.TComparer.Default.Compare(1, 2);
004CDF65 C745F801000000 mov [ebp-$08],$00000001
004CDF6C C745F402000000 mov [ebp-$0c],$00000002
004CDF73 8B45F8 mov eax,[ebp-$08]
004CDF76 2B45F4 sub eax,[ebp-$0c]
Still stupid stack juggling but a little less horrible.
Yes, following code it compiled with optimizations on and the method is inlined.
Project48.dpr.28: FastDefaults.TComparer
004CDF65 C745F801000000 mov [ebp-$08],$00000001
004CDF6C C745F402000000 mov [ebp-$0c],$00000002
004CDF73 8D55F4 lea edx,[ebp-$0c]
004CDF76 8B12 mov edx,[edx]
004CDF78 8D45F8 lea eax,[ebp-$08]
004CDF7B 8B00 mov eax,[eax]
004CDF7D 3BD0 cmp edx,eax
Johan Bontes I found out the cause:
The Compare method has this code:
Result:= integer(PInteger(@Left)^> PInteger(@Right)^)-
integer(PInteger(@Left)^< PInteger(@Right)^)
If I just call this function then it inlines the code better:
function CompareInt(const left, right): Integer; inline;
begin
Result := Integer(left) - Integer(right);
end;
and generates this asm:
Project48.dpr.28: FastDefaults.TComparer
004CDF65 C745F801000000 mov [ebp-$08],$00000001
004CDF6C C745F402000000 mov [ebp-$0c],$00000002
004CDF73 8B45F8 mov eax,[ebp-$08]
004CDF76 2B45F4 sub eax,[ebp-$0c]
Still stupid stack juggling but a little less horrible.
Stefan Glienke Just curiosity, in the second method why the parameters are typeless? Thanks :D
ReplyDeleteHorácio Filho Because then you can pass values to it from the generic Compare method without typecast voodoo.
ReplyDeleteFor an untyped const parameter, the compiler must pass by reference in all instances. This means even if the value is in a register, it has to be placed onto the stack so that it becomes addressable. You cannot pass a reference to a register.
ReplyDeleteHow, exactly, would the compiler be able to make this code any better? Given the information the compiler has been given, it has no other choice. The compiler's primary task is to translate the code into a sequence of instructions that perform the task as the source code describes.
Allen Bauer I am a compiler noob but I once learned that the 2 instructions "put value on stack" and "load stack value into register" can be reduced to "load value into register", or am I wrong here?
ReplyDeleteI was in the impression that this is what optimizations do. Also since the method is inlined does it matter how the values would have been passed?
Also the untyped const arguments function is only a crutch because there is no better way to optimize the generated code - I would be happy if you disprove that.
Allen Bauer It should have noticed that after inlining, there is no need for stuffing things on the stack. And yes this would mean it has to look at the code after inlining, either through a (lagged) pass or similar.
ReplyDeleteWhen I compared my Tiger hash implementations between VC++ and Delphi, the ~2x performance difference between them as far as I could see was mostly because VC++ tries hard to avoid stack juggling while Delphi doesn't.
Ok, let's look at your assumption closer. When the compiler builds the body of the Compare method, all it knows is how the parameters are declared. They're untyped "const" parameters. The compiler doesn't know how large the data being passed in actually is. You can pass a large 1K structure or a single byte. The compiler just doesn't know this. Of course the code the user writes in the body of the method can make assumptions about the data... the compiler simply cannot. The only way to pass arbitrarily size data to the method is to pass in a reference.
ReplyDeleteNow look at the callers; the compiler is generating machine code for method, and all it knows is how the code is declared (iow, the untyped "const" parameters). Because the call-site doesn't know what the method body is trying to do, it cannot "load the value into a register"... That isn't how the call is described, which is "call me with a reference to your parameter's data"
Asbjørn Heid Yes, of course the compiler could work much harder at trying to figure out what the inlined code is doing and try and eliminate the extra stack juggling. That is, however, going to take more time and effort during the compile process, thus slowing it down. How much of a slow-down? I cannot say... I just know that it has ho choice but to take longer because it is simply doing more work. That seems axiomatic, no?
ReplyDeleteIn this instance, when inlining a function which takes an untyped "const" parameter, I do agree that it would be great if the compiler could collapse and eliminate the stack juggling... at least as long as the inlined method body never needs the actual address of the value.
Allen Bauer Are you really saying that the compiler should produce non optimal code because the compilation needs to be fast?
ReplyDeleteI wonder if anyone cares if a release config build takes a bit longer if it produces optimized code.
Also you are still commenting on the second case with the untyped arguments. What about the original code that was even worse? Because of typecast limitations on generics we have to use that ref/deref "trick" to cast values - if that would generate better code that would be fine as well.
Allen Bauer I realize it is difficult to do this ahead of the inlining, which is why I said it should take another look after inlining.
ReplyDeleteI haven't done compiler work in a decade, but from what I can see it has the required information for a peephole pass to notice the stack juggling as unnecessary.
Stefan Glienke That's a strawman argument. There are many other factors here. The primary one is what the effort vs. the benefit. When you take into account all that we have to do, it's much easier see and to make those determinations. When you hyper-focus on one small test case and ignore the rest of the outside world, it's easy to build such a strawman.
ReplyDeleteI've already agreed that the compiler could generate better code here. In fact, I've discussed this very issue with the primary compiler developer. However, we also have lots of other target platforms that are absorbing time.
Asbjørn Heid It's a little more involved than a simple peephole pass, but yes, you are on the right track. The optimization would also need to eliminate the reserved stack space (this affects the surrounding function's prologue and epilogue). What if the inlined code needs the address of the value? That means it needs to remain on the stack anyway. What if another non-inlined call needs to pass by reference?
ReplyDeleteThe point is that there needs to be a deeper analysis of the inlined code in order to make sure it isn't just making a local one or two-instruction assumption.
FTR, the compiler does do a fairly decent job of optimizing inlined code in many other instances already.
Allen Bauer I am not a micro optimize fetishist but even I noticed that this code was not good. And I am not hyper focusing on a small test case. I have seen cases where cascaded inlined calls resulted in multiple sequences of stack juggling which slowed the entire thing down (RTL code!).
ReplyDeleteMissing RVO for managed types is another case where stack juggling goes completely out of control.
Allen Bauer Of course I realize there's a trade-off. However as far as I can see, eliminating this stack juggling should be the primary focus when it comes to compiler optimization for you guys, as it's only going to hurt more and more for each year.
ReplyDeleteCompiler speed when optimizations are turned on should be expected to be slower. The rendering project I've worked on (300kloc C++) took about a minute to rebuild in debug mode in VC++, but closer to ten minutes in release mode. This is entirely acceptable.
Stefan Glienke This is a whole class of cases. I do also agree that the code generated could (should) be better. When developing a compiler, the first order of business is to get it correct. Only then can you begin to tune it. I remember a time when compilers tried to be so aggressive in their optimizations that many times the developer had to turn it off just to get their program to work properly. Earlier versions of the Borland C++ compiler would generate crashing code when optimizations were cranked up.
ReplyDeleteAsbjørn Heid We're focusing on inlining untyped const parameters... this is a specific case... and a not very common case. I can see why Stefan, who is steeped in working on lots of low-level generics twiddling, feels this is highly critical.
ReplyDeleteI've explained what is happening, and why it's happening. I've also agreed that it is less than optimal. I'm convinced. I've encountered the same exact issue and have as well lamented the fact that it could be better. So, is this now about trying to get a firm commitment that it will be fixed at some point? I simply cannot provide such assurances.
I hope there is a request in the Quality Portal that highlights this issue. It is, of course, a feature request.
Allen Bauer The original code did not have untyped const parameter.
ReplyDeleteSee this code:
type
TComparer = class
class function Compare(const x, y: T): Integer; static; inline;
end;
class function TComparer.Compare(const x, y: T): Integer;
begin
case GetTypeKind(T) of
tkInteger: Result := PInteger(@x)^- PInteger(@y)^;
end;
end;
var
x:Integer;
begin
x := TComparer.Compare(1,2);
end.
This produces exactly the asm I originally posted. I guess this again is because it accesses the address of the value (which it just done because you cannot properly hardcast T to Integer).
Stefan Glienke The @x and @y is taking the address of the parameter. The compiler has no choice but to move the value to the stack so it has an address.
ReplyDeleteAllen Bauer So is there a way to get this code generate the same as a Compare(const x, y: Integer) would?
ReplyDeleteStefan Glienke In this instance, I'm not aware of any.
ReplyDeleteStefan Glienke Allow me to clarify; I cannot think of any way without doing some rather heinous hacks or requiring more language/compiler work.
ReplyDeleteAllen Bauer I guessed so - I found the original issue while looking into Johan Bontes https://github.com/JBontes/FastCode
ReplyDeleteIt seems you cannot get any faster than keeping the IComparer reference somewhere and then calling Compare on it without losing the benefit of having generic code in the first place.
I think this problem can get solved with the introduction of a rooted type-system.
ReplyDeleteHorácio Filho No, I guess you have a wrong understanding of how a rooted type system works.
ReplyDeleteStefan Glienke Generics are always going to be somewhat more inefficient and impractical for that sort of tasks (requiring ugly casts, interfaces and generally much plumbing both in the code, compiler and runtime).
ReplyDeleteTemplates on the other hand would have no trouble with the simple/obvious form.
Eric Grange Templates are whole different beast. They have some advantages, but also have a lot of disadvantages. Templates are, essentially, a glorified text-based "macro" substitution mechanism... in fact, they were originally implemented by a pre-processor. This is why you could get some really weird errors because a template could generate code that simply cannot compile properly with certain types.
ReplyDeleteOn the C# side there is a similar related debate (http://stackoverflow.com/questions/32664/is-there-a-constraint-that-restricts-my-generic-method-to-numeric-types) about allowing arithmetic when T has the required operators. The compiler can benefit of knowing more about T, regarding optimizations.
ReplyDeleteStefan Glienke
ReplyDeleteAllen Bauer
The problem with changing the signature of the compare function to using untyped parameters is that it is no longer guaranteed that TypeInfo(A) = TypeInfo(B). There is an alternative solution though, which is to look for the offending code and replace it with more efficient code using a peephole optimizer. I'm working on one for the fastcode project (My PHD subject is compiler optimization). This will replace the stack jugling with direct register access. Some code in the initialization section of fastcode does code analysis, a partial disassembly and replaces code.
Right now it only allows outputs code that is shorter than the original.
Johan Bontes I never said that you should change the public compare method to untyped parameters but internally use those to avoid the ref/deref nightmare.
ReplyDeleteStefan Glienke
ReplyDeleteAh, yes that makes sense. The inlining should take care of the rest.
I've written lots of compilers and translators over the years, but nothing at the level of detail that we're talking about here. So this may be a rather naive question. Take it for what it's worth.
ReplyDeleteMy skills with generics in Delphi ave not very good b/c it seems you have to develop some kind of "x-ray vision" so you're examining a bunch of invisible stuff at the same time you're writing (visible) code. I've read a lot of code for generics and it typically seems overly convoluted and ugly, and this thread highlights why. (I tend to be good with abstractions, but templates and generics have always been somewhat of a challenge for me to grasp what they're doing very quickly.)
There's a whole "meta-language" you have to understand in order to get to this level of writing generics that, while ugly and convoluted, are more amenable to forcing the compiler to grasp the intent you're trying to get at.
What about defining some kind of simple meta-language (tags, descriptors, casts, whatever) that can be used to surround pieces of expressions that define / guide / constrain low-level interface choices, and assumptions that the compiler can make while it's analyzing this sort of code?
I get that part of the problem with generics is that they ARE typeless; but this puts a considerable burden on the compiler to come up with optimal code b/c it really needs to make multiple passes over the code where the generic expressions are utilized in order to get the best results. It needs to take context into account much more acutely than otherwise.
One alternative being you need to give some "type hints" in the generics, like "if this is an integer, treat it this way; if it's an array, treat it another way" and so on, which seems to compromise the whole purpose of having generics in the first place.
Another alternative is being able to tell the compiler, "if this is an integral type, do this; if it's a structured type, do that", where you're speaking to the compiler on its own terms in a way that's still type-independent, but tacitly knows about the underlying structures the compiler is dealing with.
What seems needed is a way to give the compiler hints about how to thread a needle very simply when it's default approach is to construct something that resembles a Rube Goldberg type of mechanism because it has to take every possible consideration into account (what we've got right now).
That's what meta-languages are for.
As I mentioned earlier, such a language already SEEMS to exist -- the problem is, it's invisible to humans, and inferred by the compiler.
It seems sensible to try to make this meta-language more explicit so both a human reading the code and the compiler itself can be dealing with the same (now explicit) information. At least, it would help explain some of the ugly convoluted expressions that are present in a lot of generic code that only exists the way it does in order to convince the compiler to TRY a certain way of generating optimal code as opposed to some alternative.
David Schwartz Many words to discuss a problem that only exists because another problem was not properly solved without actually saying much. The compiler knows just fine how to handle different types (as it knows that an assignment of an integer is different from an interface or string when creating a generic type).
ReplyDeleteThe only convolution happens when doing more complex operations on the generic type argument that is not common to all of them because then you need to treat integers different from say strings or interfaces.
The problem is the architecture of the compiler is not capable of handling several things properly.
Stefan Glienke I understand this. But what's the solution? I'm suggesting some kind of meta-language or ability to tell the compiler what to do. I somehow think that would be easier than re-architecting the compiler.
ReplyDeleteAllen Bauer Generics do have an awful lot of disadvantages, mostly in terms of added development complexity and plumbing they involve. You cannot really do anything significant beyond basic collections with generics that is still "simple".
ReplyDeleteTemplates can become hideously complex as well, but they can also be far more straightforward and simple than generics, they can handle far more than collections without involving complexity.
The error situation is not so dire, C++ errors can be arcane even without involving templates, and the Delphi compiler has its own issues with generic-related errors (internal or not).
Also most of the benefits of generics are lost in a statically compiled language, runtime is what generics were designed for.
The plumbing required for generics (interfaces) drastically reduces the ability for the compiler to perform optimizations or static analysis, especially when you throw the need for proper RTTI in the mix. So Delphi is limited in ways C# is not, and just cannot compete with C++ either.
Eric Grange So, is your solution to not have them at all? I think you're way, way over the top in your criticism. Yes, there are some things that could (should) be done better, however the benefits clearly outweigh any negatives.
ReplyDeleteStefan Glienke
ReplyDeleteI think the optimization issues have to do with the number of iterations the register allocator/graph coloring algorithm makes over the data. Because graph coloring is a NP-hard problem the optimizer only makes a limited number of iterations to speed up the compilation. If the inlining gets too deep the iterations allocated are not enough to resolve to that level of nesting and the variables get spilled to the stack.
IMO Delphi currently leans to much toward speed of compilation and should ideally bent more towards better code generation.
The solution would be for Delphi to make more iterations (i.e. slow down the compilation) in the graph coloring code so that better register usage and faster code can be generated. If we could somehow set the number of iterations that would be cool (something like the -O1/2/3 switch in C (I know Ox only enables/disables certain optimizations, but I hope you get the point)).
The naive me thinks this is a simple point mutation in the compiler source.
Inc(MaxNumberOfIterationsInGraphColoring,x)
Allen Bauer I've decided to try and include a post-optimizer into the fastcode project. One that will run at unit-initialisation and redoes the graph-recoloring and than injects the updated code. For now only in the fastcode unit itself, but I'm hoping to get it to be general enough.
ReplyDeleteThis will eliminate the stack-trashing problem in this part of the code.
Allen Bauer Well dumping the current generics and replacing them with templates in a new Delphi would not be a bad decision. You could keep the constraint syntax and get the both of both worlds.
ReplyDeleteSince generics are capability-wise a subset of such templates, backward compatibility of source code would exist outside of low level hackery.
As for current solution, well yes, "my solution" is to use generics/templates quite heavily in "other languages", but not so much in Delphi. ICEs had me backtrack there actually: I have less generics "variety" in Delphi these days than in the years after they came out, which is both a pity and a major annoyance.
Eric Grange
ReplyDeleteTo be fair a lot of bugs with generics have been fixed in recent releases.
I think it's a pipe dream to expect Emba to rip out the existing generics and replace them with templates.
I think it's much more productive to come up with suggestions that actually have a chance of being implemented. Something useful like better constraints.
Johan Bontes well, I see your point, but that would just be an encouragement to digging a deeper hole from my PoV.
ReplyDeleteWithout a Delphi architectural overhaul, chasing the tails of .Net generics or Boost with Delphi generics will remain a chase.
I'm afraid the most productive suggestion right now is to use more competitive languages/frameworks. Yes, Emba may be dug-in deep on this, but more shovels is not the answer.