Recent Features
| |||||||||||||
Rethinking optimization for sizeRethinking optimization for sizePosted Feb 10, 2013 11:34 UTC (Sun) by khim (subscriber, #9252)In reply to: Rethinking optimization for size by daglwn Parent article: Rethinking optimization for size
I can't think of any possible reason that converting array index operations into pointer arithmetic is ever a win. It may be a win because to access data using an index you need two variables (array address and index) but to access data using pointer you need one (just pointer is enough). When callbacks are involved it may replace code which uses just registers to pass information around with code which uses structure in memory - in this case wins can be substantial (speaking from experience). But of course such cases are rare. But you are saying that conversion to pointer arithmetic is somehow bad? In my experience it's usually net neutral. What kind of optimization compiler can apply if I'm using indexes? How often it can apply them? I'm not saying it never happens, I just don't see and a common occurrence.
(Log in to post comments)
Rethinking optimization for size Posted Feb 11, 2013 17:21 UTC (Mon) by daglwn (subscriber, #65432) [Link]
> It may be a win because to access data using an index you need two
> variables (array address and index) but to access data using pointer you > need one (just pointer is enough).
At code-generation time the compiler knows well enough how to convert from array notation to pointer arithmetic so no extra registers are used. Indeed it must do so for most architectures. By doing that too early, the compiler loses valuable information about array stride accesses and the like that are critical for transformations like vectorization.
In addition, pointer arithmetic has all sorts of nasty aliasing properties that hamper the compiler's ability to analyze the code.
"But arrays and pointers are the same in C!" some may cry. Well, that's not entirely true and even if it were there's nothing that prohibits the compiler from representing the two very differently in its internal data structures.
> When callbacks are involved it may replace code which uses just
This sounds like an ABI issue. Most sane ABIs pass small structs via registers.
> What kind of optimization compiler can apply if I'm using indexes?
Anything that involves analyzing loop inductions and stride patterns.
- Vectorization
and about a dozen other transformations. These are the "big improvement" optimizations. Petty things like CSE and copy propagation are important but are done more to enable these big-gain transformations than for their code improvement in and of themselves.
In rare cases the compiler can convert pointer arithmetic back to array indices but this often involves extra bit-twiddling or other arithmetic to recover the original indices and more likely than not aliasing rules get in the way and make it impossible to recover the critical information.
Pointer arithmetic is just generally bad for the compiler. Avoid it if possible.
Incidentally, this is also why it's a very *bad* idea to use unsigned as a loop counter. One is not "giving the compiler more information." On the contrary, by using unsigned one is moving the arithmetic away from normal algebraic rules to the realm of modulo arithmetic. The compiler must then make all kinds of pessimistic assumptions about loop termination and access patterns. This also kills many of the loop transformations listed above.
Of course I am speaking in generalities. One can always find a counter-example. However, the vast majority of codes behave as I describe.
Rethinking optimization for size Posted Feb 11, 2013 18:45 UTC (Mon) by Aliasundercover (subscriber, #69009) [Link]
In times past I often reviewed the code output from compilers I was working with. It was helpful to calibrate what idioms carried what costs and track how they changed with compilers.
I still get the itch to look now and then but mostly recoil in horror at how hard it is to relate the code GCC gives me to what I wrote. Typically I have some function I want to review but give up after 10 minutes of searching the listing without finding it. The listing is of course fabulously ugly but that is no change from any other compiler I ever used. I just don't find my code. Well, I do, but it is all in a huge block of raw C code without the corresponding output.
No doubt some cool optimization hoisted my code out of its place in the C code I wrote and dropped it some place which makes sense to the compiler. No doubt all this transformation is good for run time performance or size or something. Perhaps listing quality just isn't an interesting bit of work for compiler writers.
I used to know what those old Windows and SunOS compilers would do with my code but now I have no similar feeling for GCC. I can read what people write about indexing vs. pointers and signed vs. unsigned but I used to really know from first hand observation.
I wish the listing got more respect. It can be a powerful optimization tool.
Maybe I just do it wrong. My makefile has the following incantation for generating listings.
%.lst: %.c
Rethinking optimization for size Posted Feb 11, 2013 19:25 UTC (Mon) by daglwn (subscriber, #65432) [Link]
> The listing is of course fabulously ugly but that is no change from any
> other compiler I ever used.
This is actually a quality of implementation issue. There are compilers out there that give fantastic listings, even down to a mostly-readable highish-level decompliation even after very aggressive code transformations. This is not very easy to obtain and really has to be baked-in at the beginning of the compiler design.
But you're right in that a good compiler will make your code unrecognizable. :)
> I wish the listing got more respect. It can be a powerful optimization
Indeed. I don't think there's much one can do with gcc to get a decent listing. It just doesn't carry enough information. Neither does LLVM, unfortunately, at least AFAIK.
Rethinking optimization for size Posted Feb 11, 2013 21:09 UTC (Mon) by PaXTeam (subscriber, #24616) [Link]
maybe you want gcc -S -fverbose-asm for commented assembly output? also -fdump-tree-all and -fdump-rtl-all if you want to see what happens to your C and also relate the internal GIMPLE variable names to the comments in the verbose asm output.
Rethinking optimization for size Posted Feb 12, 2013 16:28 UTC (Tue) by Aliasundercover (subscriber, #69009) [Link]
Well, you got me there. I tried those dump options and got 151 spam files in my source directory.
-fverbose-asm seems useful. It doesn't help with finding where my code went but the comments are nice.
I wish compiler listings got more respect.
Rethinking optimization for size Posted Feb 11, 2013 19:54 UTC (Mon) by khim (subscriber, #9252) [Link] Anything that involves analyzing loop inductions and stride patterns. Which are not applicable at all if you have arrays of various complex objects. Sure, I can understand that in some tight loops where "vectorization", "loop interchange" and other cool things can be applied indexes may be beneficial. But for typical high-level code (that is: for 90% of code if not 99% of code in a given project) changes from indexes to pointers and back make absolutely no difference: any function call tend to break all these nice techniques - and there are a lot of them. Sure, for inner loop it may be interesting, but then they usually are faster when implemented in the appropriate CPU intrinsics (the change in data structures needed to use them efficiently are impossible for the compiler) anyway thus in practice I rarely see any observable difference. Of course nowadays it's often better to use CUDA or OpenCL to push all that to the GPU - where different rules are used altogether and where traditional pointers make no sense at all, but these are specialized applications. This sounds like an ABI issue. Most sane ABIs pass small structs via registers. Yup. Up to six registers for x86-64 case. And if you have couple of arrays plus some kind of "options" argument plus some callback_data... you've already used all of them. Add one additional argument - and spill is inevitable. You may say that code which calls a callback in a tight loop is hopeless in a first place, but that's the problem: quite often I can not afford doing anything else. It's just too expensive to have one function for buttons, another for lists and so on: code is pushed from from L1 (or sometimes even L2 cache) and all these benchmark-friendly optimizations actually slow the code down.
Rethinking optimization for size Posted Feb 11, 2013 21:41 UTC (Mon) by daglwn (subscriber, #65432) [Link]
> Which are not applicable at all if you have arrays of various complex
> objects.
How did you come to that conclusion? Sometimes it is not worth it but for smallish structs it can be a win. Complex numbers are a good example.
> any function call tend to break all these nice techniques
If the function call is still there and even then the compiler can sometimes accomplish the task, depending on how aggressive the developers were.
> Of course nowadays it's often better to use CUDA or OpenCL to push all
No. There is never a case where CUDA or OpenCL are a good idea. Only poor compilers have led us down that path. Look at what's being done with OpenACC. A good compiler can match CUDA performance pretty easily and can often dramatically outperform it.
> Add one additional argument - and spill is inevitable.
In the grand scheme of thing, one write to cache/read from cache isn't usually critical. Sure, there are cases where this kind of optimization is very important -- if the callback is called in a tight loop for example. But in that case a better solution is often to refactor the code and/or rework the data structures. It should not be necessary to hand-linearize array accesses to get performance.
> You may say that code which calls a callback in a tight loop is hopeless
Actually, I would say that's often good design for the reasons you give. But then this kind of code usually isn't dealing with numerical arrays or arrays of very small structs which might be well vectorized. I suppose that is what you were thinking of with your first statement.
If that's the kind of code you're concerned about then yes, hand-linearizing array accesses is probably not going to hurt much. But it won't really help either. I've no problem with a loop that iterates over such arrays using a single pointer. I am more concerned about people who take multidimensional arrays and translate accesses to complex pointer arithmetic.
Still, if the objects are small enough, vectorization targeting efficient load/store of the data can often be a win, even if the actual data manipulation isn't vectorized.
|
|||||||||||||