automatic compiler flag optimization

[srepmub]

hi guys,

there are several interesting tools, acovea and milepost gcc (?), that
can automatically optimize gcc compiler flags (it literally has
hundreds of flags..)

so the obvious thought is, wouldn't it be nice if we could combine
these with shedskin, or implement a simple (genetic?) algorithm that
does the same thing..? shedskin is dog slow anyway, especially for
larger programs (my estimate is that if the C64 emulator example grows
to 5,000 lines, it will currently take 2 hours to compile on a fast
CPU), so that would certainly fit in with the philosophy.. :-)

thoughts or experencies, anyone..?

btw, I was reminded by private mail of the -Ofast option in GCC 4.6.
apparently it turns on -ffast-math, and possibly some other goodies.

btw2, I love the idea of -fprofile-generate and -fprofile-use, and
also get some minor gains from it now and then.

thanks,
mark.

[Ian Ozsvald]

Back around 2004 I was senior programmer in an AI research firm using
MS VC 6 to write logistic system optimisers (basically a more-complex
traveling salesman problem). I did a lot of work with flag
optimisation, the bottom line being that most flags have a tiny
effect.

Generally speaking using -O2 gave the best improvements (10% better
or so than plain old Release mode), after that nothing really helped
(but sometimes the numeric evolution was different, leading to
different execution paths, which led to faster 'runs' but with the
wrong results...many an unhappy hour was spent here trying to figure
out if I'd done something clever or stupid!). I'm curious about Mark's
result though, a 5* speed-up is really significant. It is odd that I
couldn't replicate it here.

At the risk of being boring you might want to look at these few paragraphs:
http://research.microsoft.com/en-us/um/people/toddpro/papers/law.htm

I do know that the Intel compiler is generally better than GCC (and
MSVC beats GCC too), that was true at least a year back when I worked
on a cell-based flood modeling system (OpenMP, 8 cores, big PCs,
running on Linux and Windows).

Personally I'm interested in finding a good openmp example and trying
to wire that together to use >1 core :-)

i.

> --
> You received this message because you are subscribed to the Google Groups "shedskin-discuss" group.
> To post to this group, send email to shedskin...@googlegroups.com.
> To unsubscribe from this group, send email to shedskin-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/shedskin-discuss?hl=en.
>
>

--
Ian Ozsvald (A.I. researcher, screencaster)
i...@IanOzsvald.com

http://IanOzsvald.com
http://SocialTiesApp.com/
http://MorConsulting.com/
http://blog.AICookbook.com/
http://TheScreencastingHandbook.com
http://FivePoundApp.com/
http://twitter.com/IanOzsvald

[Fahrzin Hemmati]

On 6/2/2011 2:01 AM, srepmub wrote:
> hi guys,
>
> there are several interesting tools, acovea and milepost gcc (?), that
> can automatically optimize gcc compiler flags (it literally has
> hundreds of flags..)
>
> so the obvious thought is, wouldn't it be nice if we could combine
> these with shedskin, or implement a simple (genetic?) algorithm that
> does the same thing..? shedskin is dog slow anyway, especially for
> larger programs (my estimate is that if the C64 emulator example grows
> to 5,000 lines, it will currently take 2 hours to compile on a fast
> CPU), so that would certainly fit in with the philosophy.. :-)
>
> thoughts or experencies, anyone..?

I don't have experience, but having seen the difference made by
-march=native (when gcc supports it), using one of those tools might be
even better.

If they depend on running the output, it'll require more specific
documentation on the 'if __name__=="__main__":' section of the code.
Currently it only needs to call the functions with the right types, so
my extension modules are filled with "foo()" and "bar([0])". If the
resulting binary is run for timing, it'll need real inputs like
bar(range(1000))

> btw, I was reminded by private mail of the -Ofast option in GCC 4.6.
> apparently it turns on -ffast-math, and possibly some other goodies.

This, along with -march=native, needs a GCC version check. I have three
versions of GCC installed from the past few years, and the latest I have
is 4.4.5. Distributions update at different speeds, usually skipping a
version or two of tools, so a quick "gcc --version" parsing would be
very useful.

import subprocess
data =
subprocess.Popen(['gcc','--version'],stdout=subprocess.PIPE).communicate()[0]
version = tuple(map(int,data.splitlines()[0].rsplit(' ',1)[-1].split('.')))

version results in (4,4,5) for me

--fahhem

[Ian Ozsvald]

I would suggest a bit of googling first - lots of people in lots of
numeric projects have had similar ideas. As best I know it generally
doesn't get too far as you end up with specific flags for specific
compiler versions on specific architectures, so cross-platform support
is an absolute pain. Also, the overall gains are generally not that
great (but I also agree that Mark's native+ffast-math flag observation
is definitely interesting - can anyone replicate his timings? Maybe
that is a gcc version thing?).
i.

[Enzo Erbano]

Hi Ian,

I just saw your post (I follow the posts of the group by email), and I could not 

restrain myself to reply this. :-)

(by the C++ and Windows perspective.... sorry if my perspective dont help you,

but, if it helps, I would like to know!)

The only reason Intel is better [only for intel CPUs, obviously], is because Intel 

compiler generates many versions of the very same code, each one for each

Intel CPU model. It is also obviously that each of these versions only can be

run in their specific CPU model. Intel compiler also could generate generic 

codes with a good average performance. For now, the best Intel C++ Compiler

is the version 10. The version 9 is not good for optimization as version 10, and

the version 11 was degraded in optimization for some reason.

By the way, for what I know, by doing many tests and tries, all compiled versions

done by Intel compiler have almost an average good speed, but, there still have 

room for more optimization. I mean, there are a possibility to get more speed

from the code, because the compiler dont fully optimize the code.

For generic codes, MSVC 2008 is the best, also because it inline many runtime 

functions together your code. Also, today, MSVC 2008 is the best compiler for

optimizations, for Windows, sure.

The best thing to do, related to optimizing codes, would be identify the optimization

groups that gives the greatest boosts. It means, optimization is a game of "know your

enemy" :-) . Inside each group, there are a lot of techniques, I will comment on it 

later. In my opinion, they are:

- Vectorization

- Parallelization

I am also aware that are a bunch of other optimization types, that dont join 

in any specific optimization group I know, but the ones I mentioned is the ones I

think that worth wasting some time to work... because, they are the basis

of the CPU operations. The other optimizations are almost tricky.

- The vectorization is nothing more than joining variables of the same type and 

operation to be all done together in a fixed size "package" with the size of the intended

CPU register [for example, 64bits of size for MMX, 128bits of size for SSE, 256bits for

AVX extension]. By the way, you would need to do a proper codification to make

your compiler take advantage of these more easier, for example, loop unrolling, loop collapsing,

loop splitting, loop fusion, etc, and constraining multiples of 4 operations at each loop,

and certifying that the operation you are doing is available at the intended CPU instruction

set. If the operation you are doing is not available in your CPU instruction set, you will

need to simplify the operations done in your code. Basically it means that you will need

to take a good look in the CPU manual. Or, you could try simple checking the output

assembly code generated by the compilers. :-)

- For parallelization, you need mostly to do branchless codes, because:

  1- Branch prediction analysis is very expensive, and the compiler could not always 

   figure out how to fully optimize your code, and it not even will take advantage of 

   parallelization nor vectorization because dependencies created by branch 

   instructions is very limiter.

   2- Branchless instructions offer good opportunities for optimization, since the code

   will not have dependencies from one code to another, making it more easier to be

   run in many CPU cores at once.

   3- When you do branchless codes, the compiler could identify it more easier,

   and the optimizations related to parallelization is done automatically, yet, it does

   not means that the optimizations the compiler done will take the same advantage

   in a dual core the same way in a quad core CPU, there are variations, but, you 

   could control the scalability better if you do a proper code.

Also, in the case of a loop, there is the possibility of splitting it in a half, to be run

in many cores, for example:

- normal loop

for (i = 0; i < 64; i++ )

{

 vect1[i] = vect2[i] + vect2[i+1]

}

- loop unrolling x4   

for (i = 0; i < 64; i += 4 )  // it helps in vectorization

{

 vect1[i] = vect2[i] + vect2[i+1]

 vect1[i+1] = vect2[i+2] + vect2[i+3]

 vect1[i+2] = vect2[i+4] + vect2[i+5]

 vect1[i+3] = vect2[i+6] + vect2[i+7]

}

- loop unrolling x4 + parallelization by loop splitting

for (i = 0; i < 32; i += 4 ) // first half

{

 vect1[i] = vect2[i] + vect2[i+1]

 vect1[i+1] = vect2[i+2] + vect2[i+3]

 vect1[i+2] = vect2[i+4] + vect2[i+5]

 vect1[i+3] = vect2[i+6] + vect2[i+7]

}

for (i = 32; i < 64; i += 4 ) // second half

{

 vect1[i] = vect2[i] + vect2[i+1]

 vect1[i+1] = vect2[i+2] + vect2[i+3]

 vect1[i+2] = vect2[i+4] + vect2[i+5]

 vect1[i+3] = vect2[i+6] + vect2[i+7]

}

-  loop unrolling x4 + parallelization by loop splitting + loop reversal

for (i = 32; i > 0; i -= 4 ) // first half  - comparing to zero is more cheaper

{

 vect1[i] = vect2[i] + vect2[i+1]

 vect1[i+1] = vect2[i+2] + vect2[i+3]

 vect1[i+2] = vect2[i+4] + vect2[i+5]

 vect1[i+3] = vect2[i+6] + vect2[i+7]

}

for (i = 64; i > 32; i -= 4 ) // second half

{

 vect1[i] = vect2[i] + vect2[i+1]

 vect1[i+1] = vect2[i+2] + vect2[i+3]

 vect1[i+2] = vect2[i+4] + vect2[i+5]

 vect1[i+3] = vect2[i+6] + vect2[i+7]

}

Well, these are just a few examples of optimizations, but, there still a lot

optimizations that still can be done in these loops.

What I really wanted to mean is that if you change your code properly

it will solve your problem much better than using simple compiler flags.

2011/6/2 Ian Ozsvald <i...@ianozsvald.com>

[Ian Ozsvald]

Hi Enzo. You're totally right, I was just thinking of compiler flag
optimisation rather than code layout. The downside is that changing
the code layout can be quite a lot of work though (I confess to having
tried it only on occasion though).

Over the last year I've done a lot of work with pyCUDA and C-based
CUDA (mostly working directly on the .cu C file). Most of the gains
there come from figuring out how to vectorise code, reduce memory
accesses and then tweak things (e.g. obtaining the magical 'coalesced
memory access speedups'). Your code examples remind me of a bunch of
this work :-)

I guess there's an interesting question (Mark?) asking whether
ShedSkin can do some of these conversions automatically?

i.

[Thomas Spura]

On Fri, 3 Jun 2011 09:17:10 +0100
Ian Ozsvald wrote:

> Hi Enzo. You're totally right, I was just thinking of compiler flag
> optimisation rather than code layout. The downside is that changing
> the code layout can be quite a lot of work though (I confess to having
> tried it only on occasion though).
>
> Over the last year I've done a lot of work with pyCUDA and C-based
> CUDA (mostly working directly on the .cu C file). Most of the gains
> there come from figuring out how to vectorise code, reduce memory
> accesses and then tweak things (e.g. obtaining the magical 'coalesced
> memory access speedups'). Your code examples remind me of a bunch of
> this work :-)
>
> I guess there's an interesting question (Mark?) asking whether
> ShedSkin can do some of these conversions automatically?

That could work, but thinks like loop unrolling and similar stuff is
automatically done with recent gcc's. There are plenty of optimizing
flags available and many of them are enabled with -O3.

Most of the time I use -ftree-vectorize and
-ftree-vectorizer-verbose=8, so I know where I can change code
efficently, so gcc can parallelize the loop on it's own.

But that doesn't work well with shedskin atm, because it uses to fancy
objects (all the garbage collected stuff). It's on my TODO list to kill
all usage of "units" everywhere, so we could switch the internal
representation, so gcc can further optimize things...

Thomas

[Mark Dufour]

I guess there's an interesting question (Mark?) asking whetherShedSkin can do some of these conversions automatically?

uhm.. some, probably :-) but I think it's better for shedskin to try and not be too smart, and just try to act as a "thin layer" between python and C++. I tried a few higher-level optimizations in the past, and usually ended up pulling my hair out and reverting them because of the added complexity.

I don't mind if people have to modify their python code a bit to get better performance with GCC. I actually seem to like this tweaking aspect of using shedskin.. ;-) perhaps it would be more interesting to see if we can slightly alter the generated C++/shedskin data structures so it becomes easier for GCC to apply its optimizations.

an escape analysis seems much harder for GCC (as even 'new' can and is overloaded by the boehm GC), which is also why I'd be more open to adding this to shedskin. but of course if there's a way to help GCC do this, that would be even better imo. I'm afraid it's not a focus of the GCC developers, because usually programmers will manually allocate on the stack.

but in any case, we're talking serious investments of time here. I'd be happy to support anyone looking into higher-level optimizations of course, but I think it's better for me to focus on the core type inference still.. that's more than enough researchy type stuff already than I can handle to my satisfaction.. ;-)

thanks,
mark.
--
http://www.youtube.com/watch?v=E6LsfnBmdnk

[Enzo Erbano]

Hi Ian,

Have you tried to use OpenCL? I think it is much more portable and also productive

way of programming, I also believe it is efficient.... 

OpenCL creators claim it is capable of auto-parallelize your code scaling and load 

balancing it perfectly through many CPU types, including GPUs [Nvidia or ATI], 

CELL CPU, Intel or AMD CPU and possible some others, like mobile ones....

It seems to be an unbelievable solution... but, for what I know, it seems to be possible,

but you will need to have a C/C++ compatible, and pre-otimized, code to convert it to 

OpenCL latter.

I know it is a massive work [both, hand optimizing or converting it to OpenCL],

but both solutions still better than relying on Compiler Flags that is not reliable for many

reasons, for example:

- Compiler flags does not offer stable efficiency from one to another compiler type or version.

- Compiler flags some times break your code without even notify you about this.

- In the case of O3 flag, yes it indeed offer loop unrolling and some other good optimizations, but,

it also indeed offer too some aggressive optimizations that will break your code harshly. Also,

if I remember well, O3 flag does not behave equally on different CPU architectures.

- Some optimizations like loop unrolling [and brothers] also benefit your code when you compile 

the code for generic CPU instructions set, but, loop unrolling is only available on GCC with O3 

flag, right, that it means that you cant use loop unrolling without aggressive and dangerous 

optimizations.

I also have many reasons to adopt hand optimized codes than only relying on the compiler

but I think what I said is enough. 

My opinion about implementing it on shedskin is... well, would be wonderful to have some 

safe and best optimizations available directly from shedskin, but I need to agree to Mark,

it adds some more complexity to shedskin code, and also, it cant be done in one week or two.

It would be better to implement it as post-processing tool to process output C++ code 

generated by shedskin.

Here, I will share to you a list of optimizations that worth wasting some time. The calcs

is only an "average" of how much each type of optimization can benefit your code

[it is only to C/C++ perspective for a single-core CPU, and I am not going to enter in 

details, take it as-is]:

Optimization
Function Inlining	x1.27
Loop Fusion	x1.33
Loop Interchange	x1.37
Induction Variable Elimination	x1.39
Common Subexpression Elimination	x1.41
Loop Unrolling	x1.43
Loop Splitting	x1.46
Loop Nest Optimization	x1.47
Hoisting	x1.49
Loop Skewing	x1.50
Loop Unswitching	x1.51
Bitfield Optimization	x1.52
Instruction Combining	x1.60
Loop Reversal	x1.62
If Optimization	x1.63
Loop-Invariant Code Motion	x1.70
Loop Collapsing	x1.71
Block Merging	x1.73
Loop Inversion	x1.78
Expression Simplification	x1.82
Integer Modulus Optimization	x1.84
Forward Store	x1.84
Integer Multiply Optimization	x1.95
Integer Divide Optimization	x1.96
Branch Elimination	x1.99

Also, if you take a better look about each optimization, you will notice that most

of them eliminates dependencies over the code, and it could give a bigger boost

when using multi-core CPUs!

I am also sure that GCC could not give you all the same boost if you implement 

these by hand. But these optimizations could make a lot easier to GCC parallelize

your code.

Best regards.

2011/6/3 Ian Ozsvald <i...@ianozsvald.com>