Velocity Reviews > statistic of integer values

# statistic of integer values

Stefan Wallentowitz
Guest
Posts: n/a

 12-10-2005
Hello together!

I'm searching for a statistic about the value ranges of integers in a set
of "standard" c-programs.
I'm specifically interested in the avarage ratio of assignments etc. of
integers where the value is either of (un)signed 16 bit or 32 bit size.
Has anybody ever been in contact with something similar?

Bye,
Stefan

Malcolm
Guest
Posts: n/a

 12-10-2005

"Stefan Wallentowitz" <(E-Mail Removed)> wrote
>
> I'm searching for a statistic about the value ranges of integers in a set
> of "standard" c-programs.
> I'm specifically interested in the avarage ratio of assignments etc. of
> integers where the value is either of (un)signed 16 bit or 32 bit size.
> Has anybody ever been in contact with something similar?
>

No. It will be rather tricky to define exactly what you mean.

For instance, a loop in which a variable, i, takes range between 0 and N-1,
is an extremely common construct. However the counting variable usually
isn't held for more than a few machine cycles. N, on the other hand, may
well keep its value for the life of the program.

However if the loop is in a subroutine, variable N may be passed to that
routine, copied from a "Nemployees" member of a data structure. So does N
now count as one or two integers?

Also, because of C semantics, i will actually be set to N at the end of the
for loop. Probably, however, i will never be accessed outside of the loop.
So has i taken the value N, or not?

Stefan Wallentowitz
Guest
Posts: n/a

 12-10-2005
Am Sat, 10 Dec 2005 21:25:38 +0000 schrieb Malcolm:

Hi!

> No. It will be rather tricky to define exactly what you mean.

Ok, I thought it might be a bit unexact.

> Also, because of C semantics, i will actually be set to N at the end of
> the for loop. Probably, however, i will never be accessed outside of the
> loop. So has i taken the value N, or not?

Yes, N is one of it. But the initialisation of i also. In fact I'm
interested in the ratio of common integer ranges being loaded in
registers. Several examples:
a=1, a=b+4, a=0x0feff0c4 etc.
It is related to a compiler optimization and it is interesting how much
instructions are in average saved, e.g. when theres a high occurence-rate
of 16 bit signed integers, the optimization brings more success. But some
measurement data would be great.
I also know that there is a machine dependency, but I envision some
overall data from a more abstract view on c-code.

Greets,
Stefan

Guest
Posts: n/a

 12-10-2005
Stefan Wallentowitz wrote:

> I'm searching for a statistic about the value ranges of integers in a set
> of "standard" c-programs.

You will probably have to generate your own.

> I'm specifically interested in the avarage ratio of assignments etc. of
> integers where the value is either of (un)signed 16 bit or 32 bit size.

You need to be more precise about what you need.
"ratio of assignments etc. of integers where the value is either of
(un)signed 16 bit or 32 bit size."

Does that mean you want to count the number of integer assignments
executed in which the value has exactly 16 sigificant bits and exactly
32 significant bits and compute their ratio?

Do you want to know how many assignment statements are made to 16-bit
vs. 32-bit integer types without regard to value and without regard to
the number of times executed? Or something else?

--

slebetman@yahoo.com
Guest
Posts: n/a

 12-11-2005
Stefan Wallentowitz wrote:
> It is related to a compiler optimization and it is interesting how much
> instructions are in average saved, e.g. when theres a high occurence-rate
> of 16 bit signed integers, the optimization brings more success.
>

Not a good idea. The compiler should be consistent or the programmer
will be surprised later on if the run-time code suddenly overflows on
65536. If the compiler implements 16bit ints, then that's fine. If it
is 32bit ints, then that's fine also. But if it is sometimes 32 and
sometimes 16 that's not a good thing. An example of a compiler where
this is configurable is the HITECH C compiler for PIC microcontrollers.
The programmer gets to decide via compiler options or #pragma
statements weather ints are 16 or 32 bits.

Walter Roberson
Guest
Posts: n/a

 12-11-2005
In article <(E-Mail Removed) .com>,
http://www.velocityreviews.com/forums/(E-Mail Removed) <(E-Mail Removed)> wrote:
>Stefan Wallentowitz wrote:
>> It is related to a compiler optimization and it is interesting how much
>> instructions are in average saved, e.g. when theres a high occurence-rate
>> of 16 bit signed integers, the optimization brings more success.

>Not a good idea. The compiler should be consistent or the programmer
>will be surprised later on if the run-time code suddenly overflows on
>65536. If the compiler implements 16bit ints, then that's fine. If it
>is 32bit ints, then that's fine also. But if it is sometimes 32 and
>sometimes 16 that's not a good thing.

Ummm, it looked to me like that OP wasn't trying to say anything like
that.

If I understand correctly, the question is about integral literals
appearing in source code -- though it should probably instead be about
integral literals appearing after pre-processing and constant folding.

The question is about the relative rates at which 16 bit literals
appear, compared to 32 bit literals. The point, if I understand
the instructions involved in coding the literals into the machine
code.

the same literal.

For example, there are architectures which have (say) "Add Quick", an
instruction which operates on registers of whatever size is specified
in other parts of the instruction (e.g., ADDQ.W, ADDQ.L) -- but no
matter what the register size, the value being added is restricted to a
particular range, such as -128 to +127 . For example, ADDQ.L A3,#16
might be used to increment address register A3 by 16. Such instructions
could hypothetically crop up quite a bit in loops over arrays.

constant to a 16 bit register; add a 16 bit constant to a 32 bit
register) and might have a regular ADD instruction in which
one of the source operand modes was "immediate 32 bit constant".

When these instructions are available, they can result in smaller
machine language, which is a benefit for fitting more into
cache; they may also end up operating faster because of the
reduced number of cycles required to read the constant from
memory. There may also turn out to be interesting tradeoffs
in such architectures, such as it potentially being faster to
load a byte value in one instruction and sign-extending it to 32
bits in a second instruction, rather than using a single
instruction to load a 32 bit constant -- the dual instruction
version might, for example, hypothetically pipeline better,
or the "sign extend" instruction might be only a two byte-long
instruction, with the "load quick" being 4 bytes long, for
a total of 6 bytes where the architecture would need 8 bytes
(4 for the instruction, 4 for the constant) to load a 32 bit
constant.

Suppose one is working on a compiler for an architecture
that offers different instructions for the same basic task,
with some of the variations being shorter or faster for particular
ranges of literal constants, If one were doing that, then one
might wonder whether it is worth the effort to put in a bunch
of compiler optimization work to get the absolute best possible
memory fit or absolute best possible instruction speed. Such work
could get particularily messy if the less-memory variations
turn out to take longer, as one would then have to analyze to see
whether the surrounding code is such that it is better to
optimize for space or time. In a tight loop that was likely to
stay in cache for a while, the answer could depend on the exact
size of the loop...

If this is what the OP is trying to talk about, then I would
make some suggestions:

1) That possibly this kind of study was undertaken back when RISC
theory was being developed;

2) That not just the explicitly coded (or constant folded) literals
are important, since there can be many implicit literals for

3) That it matters not only how often various sizes of literals appear,
but also what kind of circumstances they appear in. There might
be (hypothetically) several 32 bit constants per "for" loop
(initialization, termination test, increment), but those would tend
to get loaded into registers, and the literal that might be
most crucial to the speed of the loop might be (say) the 4 in
"add #4, %eax" where %eax is being used to index arrays. Or
depending on the architecture and generated code, it might be the 2
in the sequence INC R3; MOV R3, R2; SHL R2, #2; LOAD R4, \$1BE00C(R2)
i.e., increment, shift-level to get a byte offset, load from that
byte offset relative to the contant location of a static array...
--
I was very young in those days, but I was also rather dim.
-- Christopher Priest

slebetman@yahoo.com
Guest
Posts: n/a

 12-11-2005
Walter Roberson wrote:
> In article <(E-Mail Removed) .com>,
> (E-Mail Removed) <(E-Mail Removed)> wrote:
> >Stefan Wallentowitz wrote:
> >> It is related to a compiler optimization and it is interesting how much
> >> instructions are in average saved, e.g. when theres a high occurence-rate
> >> of 16 bit signed integers, the optimization brings more success.

>
>
> >Not a good idea. The compiler should be consistent or the programmer
> >will be surprised later on if the run-time code suddenly overflows on
> >65536. If the compiler implements 16bit ints, then that's fine. If it
> >is 32bit ints, then that's fine also. But if it is sometimes 32 and
> >sometimes 16 that's not a good thing.

>
> Ummm, it looked to me like that OP wasn't trying to say anything like
> that.
>
> If I understand correctly, the question is about integral literals
> appearing in source code -- though it should probably instead be about
> integral literals appearing after pre-processing and constant folding.
>

In this case there would be no need to ask about statistics. It is
always safe to do this because the compiler know there is ONLY one
value for each literal - not a range. This is implemented by almost all
modern compilers. Not only that, if for example on a RISC machine you
use the literal 1 or 0 the compiler would simply generate code to read
the one and zero registers.

Walter Roberson
Guest
Posts: n/a

 12-11-2005
In article <(E-Mail Removed) .com>,
(E-Mail Removed) <(E-Mail Removed)> wrote:
>Walter Roberson wrote:
>> If I understand correctly, the question is about integral literals
>> appearing in source code -- though it should probably instead be about
>> integral literals appearing after pre-processing and constant folding.

>In this case there would be no need to ask about statistics. It is
>always safe to do this because the compiler know there is ONLY one
>value for each literal - not a range.

There is more than one meaning of "safe" that might apply here.

There is the "safe" of "Is there a certainty that I can find
a valid instruction to use for this particular literal, that the
literal will not overflow the range allowed for the instruction?".
I suspect that's the meaning of "safe" that you are using.

There is another meaning, though, when it comes to generating
instructions: "Is there a certainty that if I chose to generate
this particular one of the instruction sequences that I could
generate, that this choice will not result in worse performance
than could be obtained with a different sequence?" And the answer
to that is "It depends on the instruction set, upon the
internal details of multiple dispatch or pipelining, and upon
the cache characteristics of the surrounding code."

Also, as I indicated earlier, the point might not be "can it
safely be done", but rather, "Is it worth putting in the programming
effort to do this potential optimization? Do small literals occur
often enough that the savings would be appreciable? Is it worth
the time to find good algorithms for the boundary cases such as
the short load taking longer to execute but the extra cost being worth
it if it allows a tight loop to fit in cache when it would not otherwise
fit?" And that's where the statistics come in.

You know the usual refrain about "premature optimization" -- well,
it looks to me as if the OP is trying to get a feel for whether
this kind of optimization is premature, or is worth while.
--
"law -- it's a commodity"
-- Andrew Ryan (The Globe and Mail, 2005/11/26)

Stefan Wallentowitz
Guest
Posts: n/a

 12-11-2005
Am Sun, 11 Dec 2005 03:31:09 +0000 schrieb Walter Roberson:

Hi Walter!

Many thanks, you got what I was trying to point out.
> If this is what the OP is trying to talk about, then I would
> make some suggestions:

Yes, thats what I had in mind. In fact it's dealing about designing a
requires two instructions, but when having 16bit-fitting value it is
possible utilizing only one instruction. It is quite a simple
"optimization", but in a small presentation I wanted to describe its
possible impact with such a study.

> 1) That possibly this kind of study was undertaken back when RISC theory
> was being developed;
>
> 2) That not just the explicitly coded (or constant folded) literals
> are important, since there can be many implicit literals for

In general this is true, but in my case, it is only literals being
interested because addresses/pointers are not handled in this way.
>
> 3) That it matters not only how often various sizes of literals appear,
> but also what kind of circumstances they appear in. There might be
> (hypothetically) several 32 bit constants per "for" loop
> (initialization, termination test, increment), but those would tend to
> get loaded into registers, and the literal that might be most crucial to
> the speed of the loop might be (say) the 4 in "add #4, %eax" where %eax
> is being used to index arrays. Or depending on the architecture and
> generated code, it might be the 2 in the sequence INC R3; MOV R3, R2;
> SHL R2, #2; LOAD R4, \$1BE00C(R2) i.e., increment, shift-level to get a
> byte offset, load from that byte offset relative to the contant location
> of a static array...

Yes, I was thinking about some equivalent issues. In total perhaps someone
did some work like profiling somewhat "reference code" with exact values
(or ranges) of values being loaded. Doing it on my own for just a small
chart doesn't make sense. But perhaps someone reading has ever been in
contact with some related studies ans knows a source for raw data.

Thanks so far,
Stefan

Stefan Wallentowitz
Guest
Posts: n/a

 12-11-2005
Am Sat, 10 Dec 2005 23:35:03 -0800 schrieb (E-Mail Removed):

> In this case there would be no need to ask about statistics. It is
> always safe to do this because the compiler know there is ONLY one
> value for each literal - not a range. This is implemented by almost all
> modern compilers. Not only that, if for example on a RISC machine you
> use the literal 1 or 0 the compiler would simply generate code to read
> the one and zero registers.

Yes, but creating an own compiler leads me to this question regarding the
impact of a quite simple optimization.
I am searching for a statistic of how often a loaded integer (either in
register or as part of an immediate instruction etc.) in whatever general
is:
- in 16-bit domain
- above
(might be extended to is zero, 8-bit and so on)

Bye, Stefan