General profiling approaches - Compilers

> [People have been profiling C code for 30 years quite successfully.
> Perhaps this would be a good time to go find out how they've done so.
> -John]

The best way i know of that a C or any other code can be profiled is to
translate the code into assembly, marking begining and the end of the
assembly code coresponding to each line of code / statement in C and
then inserting time tracking code into this generated assembly code.
This method will allow minimal effect of profiler code on the profiled
code. Now, if i was to insert a C profiler code into C profiled code
and then compile the result, the resulting assembly code will look
nothing like the compiled profiled code without the profiler code.

My initial question in this thread was mostly intended to reveal the
profile limitation using a single language, that is profiling C using
C, not profile C using asm.

In physics the unsertanty principle poses limitation on measuring of
events, since the process of measuring in itself intoduces
perturbation, and therefore the measurement of an event is limited to a
given acuracy. 2*pi*p*x=h x is position p is momentum h is planks
constant.

Insertion of the profiler code also introduces perturbation of the
profiled code, the limiting case, which would be using assembly
language to profile assembly language, introduces perturbations such as
instruction que being different than in original code, plus the use of
cpu cache would also be probably altered.

I am a physisssist, not a computer engineer, hence i can not attach
any numbers to the above formulated limitation, but i was hoping
someone here may be able to.

it seems to me that there are 2 issues which are not accounted for in
todays top of the line profilers:
1) Error introduced by introduction of profiler code in assembly code
of the profiled code. This results in small error
2) Error introduced by introduction of profiler code of the same level
of abstraction as the profiled code. This introduces larger error than
in case 1 since the resulting assembly code looks very different than
the assembly of profiled code alone.

The second issue only exists for compilers which try to optimize the
code. Case 2 will be the same as case 1 if the compiler blindly
translates the input language into asm 1 statement at the time, hence
the compilation process is not altered by existance of profiler code.

Any thought about this?

[These are all techniques that have been used many, many, many times
over the past 40 years or so, and they're not the only ones. Unix
systems use a statistical method that doesn't change the object code
at all, for example. -John]

"fermineutron" <free4trample@yahoo.com> writes:

> The best way i know of that a C or any other code can be profiled is
> to translate the code into assembly, marking begining and the end of
> the assembly code coresponding to each line of code / statement in C
> and then inserting time tracking code into this generated assembly
> code.

Well, that's not the best way, not even close. You don't need to
measure that much if you have a good model of the hardware (see
below). You only need to know which paths through the code are taken.
Much of the ****ysis can be done off-line. Even if you have hardware
level out-of-order execution that might affect your speed, it is
likely that the hardware has counters that can tell you which
instructions used which hardware features (or were ordered in which
way), so that you can determine how the code was executed even without
inserting measurements that will perturb the result.

Thus, unlike physics, one isn't close to running into the Planck limit
when profiling code, because you can measure things without perturbing
them.

Below: When I worked on the ATOM profiling tools (at DEC), it used
compiler techniques to pre-compute when certain actions would have no
effect and thus did not need to be measured. We often reduced the
number of "probes" inserted into the code by more than one order (and
often nearly two orders) of magnitude.

Other people have done other things to resolve the problem. For
example, (if I understood it correctly) the SHADE tool developed at
Sun, modeled the whole architecture in software, allowing them to
measure any attribute they wanted. At Intel, we have a very similar
tool called VMOD, which models the hardware at the gate level. Now,
both of these tools take significant effort to get the measurements
they need--you can't get this accuracy of measurement for free. (If I
recall correctly again, it takes literally days to simulate the entire
BOOT process that brings up Windows.) However, you can make it as
accurate as you want.

However, even without such techniques, even simple C profiling by
inserting C statements into the source can be done without permuting
the execution too much. My recollection is that the INSIGHT tool from
Parasoft did just that. Again, I don't believe they put start/stop
blocks around each statement, but you don't need to. When you are
profiling a program, you don't care about the relative cost of the two
statements "a = 1; b = 2;", you care about how decision logic (if and
loop statements) and routine calls affect the execution. Therefore,
you only need measurements at the "branches" and the "calls".
Everything else you can compute off-line, if you need to compute it at
all.

Hope this helps,
-Chris

*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

Chris F Clark <cfc@shell01.TheWorld.com> schreibt:

> "fermineutron" <free4trample@yahoo.com> writes:
>
>> The best way i know of that a C or any other code can be profiled is
>> to translate the code into assembly, marking begining and the end of
>> the assembly code coresponding to each line of code / statement in C
>> and then inserting time tracking code into this generated assembly
>> code.
>
> Well, that's not the best way, not even close. You don't need to
> measure that much if you have a good model of the hardware (see
> below). You only need to know which paths through the code are taken.

[...]

> However, even without such techniques, even simple C profiling by
> inserting C statements into the source can be done without permuting
> the execution too much. My recollection is that the INSIGHT tool from
> Parasoft did just that. Again, I don't believe they put start/stop
> blocks around each statement, but you don't need to. When you are
> profiling a program, you don't care about the relative cost of the two
> statements "a = 1; b = 2;", you care about how decision logic (if and
> loop statements) and routine calls affect the execution. Therefore,
> you only need measurements at the "branches" and the "calls".
> Everything else you can compute off-line, if you need to compute it at
> all.

This is mostly what I wanted to say. AFAICT, measurements in physics
and profiling computer programs aren't done for the same reasons, at
least most of the time. In physics, or electrical engineering, which
I know a little more about, you are usually interested in the exact
value. It has to be correct because this affects how you design the
rest or your circuit or whatever. When you profile a computer
program, exactness doesn't really concern you. Usually you only want
to know what makes your program slow, where it spends most of its
time. You may find out that a certain function is called much more
often than you anticipated when you wrote it. So you optimize said
function and everything is well. Or you see that malloc and free are
called very often, so you try not to create as many temporary objects.
For these tasks, the measurements of the profiler just have to be in
the same ballpark as the actual values.

--
Wolfram Fenske