Problems converting Float to Integer efficiently

Problems converting Float to Integer efficiently

[Dr. Adrian Wrigley]

Hi all!

I have been having problems getting decent code out of GNAT 3.15p (Intel architecture)

All I want to do is get the integer part of a Float variable (without checks).
I don't want rounding to nearest like I get with "Integer (Y)"

In C, a function to do this might look like:
int x (float y)  {  return y; }

Which generates code like:
	pushl %ebp
	movl %esp,%ebp
	subl $12,%esp
	flds 8(%ebp)
	fnstcw -4(%ebp)
	movl -4(%ebp),%edx
	movb $12,%dh
	movl %edx,-12(%ebp)
	fldcw -12(%ebp)
	fistpl -12(%ebp)
	movl -12(%ebp),%eax
	fldcw -4(%ebp)
	movl %ebp,%esp
	popl %ebp
	ret

In Ada you could try something like:

pragma Suppress (All_Checks);
function X (A : Float) return Integer is
begin
    return Integer (Float'Floor (A));
end X;

which generates twice as much code, and a call to system__fat_flt__fat_float__floor
I have also seen "Integer (A - 0.5)" used, but the core of the code for this is still *much* more
verbose than the core of the C function.

No matter what I try, I get *at least* twice as much code to execute out of the Ada.
My application is generating indexes for a multi-dimensional array structure from
floating point values.  If I get a major performance penalty from Ada (>20%), I will be tempted
to code this in C or assembly :(   Could I get the right code in my application using
a Machine Operation in an pragama Inlined function?

This should be so simple!  What is the expression for getting the right code?
Shouldn't there be an attribute to an integer out of a float, rounding up/down/nearest/etc??
--
Adrian Wrigley, Cambridge, UK

Re: Problems converting Float to Integer efficiently

[Jeffrey Carter]

Dr. Adrian Wrigley wrote:
> 
> pragma Suppress (All_Checks);
> function X (A : Float) return Integer is
> begin
>    return Integer (Float'Floor (A));
> end X;

If 'Floor works for you (A is >= 0.0), then 'Truncation should also 
work. I have no idea what kind of object code it produces.

As always, if you want specific object code, you should use a machine 
code insertion.

-- 
Jeff Carter
"My brain hurts!"
Monty Python's Flying Circus
21

Re: Problems converting Float to Integer efficiently

[Jeff C,]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
news:KD1hb.8538$RU4.82065@newsfep4-glfd.server.ntli.net...
> Hi all!
>
> I have been having problems getting decent code out of GNAT 3.15p (Intel
architecture)
>
> All I want to do is get the integer part of a Float variable (without
checks).
> I don't want rounding to nearest like I get with "Integer (Y)"
>
> In C, a function to do this might look like:
> int x (float y)  {  return y; }
>
> Which generates code like:
> pushl %ebp
> movl %esp,%ebp
> subl $12,%esp
> flds 8(%ebp)
> fnstcw -4(%ebp)
> movl -4(%ebp),%edx
> movb $12,%dh
> movl %edx,-12(%ebp)
> fldcw -12(%ebp)
> fistpl -12(%ebp)
> movl -12(%ebp),%eax
> fldcw -4(%ebp)
> movl %ebp,%esp
> popl %ebp
> ret
>
> In Ada you could try something like:
>
> pragma Suppress (All_Checks);
> function X (A : Float) return Integer is
> begin
>     return Integer (Float'Floor (A));
> end X;
>
> which generates twice as much code, and a call to
system__fat_flt__fat_float__floor
> I have also seen "Integer (A - 0.5)" used, but the core of the code for
this is still *much* more
> verbose than the core of the C function.
>
> No matter what I try, I get *at least* twice as much code to execute out
of the Ada.
> My application is generating indexes for a multi-dimensional array
structure from
> floating point values.  If I get a major performance penalty from Ada
(>20%), I will be tempted
> to code this in C or assembly :(   Could I get the right code in my
application using
> a Machine Operation in an pragama Inlined function?
>
> This should be so simple!  What is the expression for getting the right
code?
> Shouldn't there be an attribute to an integer out of a float, rounding
up/down/nearest/etc??
> --
> Adrian Wrigley, Cambridge, UK
>


Kind of yucky, although the C version that wants rounding ends up being a
little
ugly and calling a builtin to do a round...It does seem to be a shame that
the compiler does not do something better here.

If you can use a more up to date gcc (a 3.X series) and have a pentium 4
(maybe ok on III)
then you can try this little thing I made

contents of a file called truncate.ads

function truncate(y : in float) return Integer;
pragma inline(truncate);

contents of a file called truncate.adb

with Machine_Code;
use Machine_Code;

function truncate(y : in float) return Integer is

temp : integer;
begin
  Asm ("cvttss2si %1, %0",inputs  => float'asm_input("m", y),
                          Outputs => integer'asm_output("=r",temp));
  return temp;
end truncate;

and a little test driver

with Text_IO;
with Truncate;

procedure TestX is

I : Integer;
begin
  I := Truncate(100.8);
  Text_IO.Put_Line(Integer'image(I));
end TestX;


This prints 100 when it runs...Beyond that I can not promise anything :)


In terms of the code, it looks like
gcc -S -O2 -gnatp -fomit-frame-pointer truncate.adb

C:\msys\1.0\home\jcreem>type truncate.s
        .file   "truncate.adb"
.globl _truncate_E
        .data
_truncate_E:
        .byte   0
        .text
        .p2align 4,,15
.globl __ada_truncate
        .def    __ada_truncate; .scl    2;      .type   32;     .endef
__ada_truncate:
/APP
        cvttss2si 4(%esp), %eax
/NO_APP
        ret


Or in other words, it is a single instruction. I can confirm that when
compiled with -O2 -gnatn it does indeed
inline this and you essentially end up with the single instruction.

Re: Problems converting Float to Integer efficiently

[Dr. Adrian Wrigley]

Jeff C, wrote:
...
> begin
>   Asm ("cvttss2si %1, %0",inputs  => float'asm_input("m", y),
>                           Outputs => integer'asm_output("=r",temp));
>   return temp;
> end truncate;
...

This looks like the kind of thing I was wanting the compiler to produce.
I'm not a whizz at Intel Assember (nor package Machine_Code), so it might have
taken a long time to for me to figure out exactly what I needed.

It's a bit disappointing that the compiler does not produce code like this for
some "obvious" source code.  I dislike Ada's default of rounding to nearest, and
it seems that a series of Float=>Integer attributes might help the compiler.

I have Athlons and GNAT 3.15, so I may have to experiment with this approach.
But it is now past my bedtime...

Thanks for a speedy response on this problem!
--
Adrian Wrigley, Cambridge, England.

Re: Problems converting Float to Integer efficiently

[Jeff C,]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
news:Ku4hb.8589$RU4.82535@newsfep4-glfd.server.ntli.net...
> Jeff C, wrote:
> ...
> > begin
> >   Asm ("cvttss2si %1, %0",inputs  => float'asm_input("m", y),
> >                           Outputs => integer'asm_output("=r",temp));
> >   return temp;
> > end truncate;
> ...
>
> This looks like the kind of thing I was wanting the compiler to produce.
> I'm not a whizz at Intel Assember (nor package Machine_Code), so it might
have
> taken a long time to for me to figure out exactly what I needed.
>
> It's a bit disappointing that the compiler does not produce code like this
for
> some "obvious" source code.  I dislike Ada's default of rounding to
nearest, and
> it seems that a series of Float=>Integer attributes might help the
compiler.
>
> I have Athlons and GNAT 3.15, so I may have to experiment with this
approach.
> But it is now past my bedtime...
>
> Thanks for a speedy response on this problem!
> --
> Adrian Wrigley, Cambridge, England.
>


I don't really know what  I am doing with assembly lang inserts with GNAT
either. If I did I am
sure it would be pretty simple to make a 6-7 instruction insertion for this
that would
work with 3.15. The big problem of course is not so much the compiler as the
binutils needing
to know this instruction......

What OS are you running on?

Re: Problems converting Float to Integer efficiently

[Robert I. Eachus]

Dr. Adrian Wrigley wrote:

> This should be so simple!  What is the expression for getting the right 
> code?
> Shouldn't there be an attribute to an integer out of a float, rounding 
> up/down/nearest/etc??

Two things to keep in mind.  First, there is no right way to do this on 
an x86 architecture chip.  There are best ways for particular models of 
x86 chips, and there are best ways for x86 chips that are in particular 
rounding modes.  Here is more than you will ever want to know about the 
issue: http://www.stereopsis.com/FPU.html and 
http://www.df.lth.se/~john_e/gems/gem0042.html

And finally, my comment on the mess: The real (ouch!) problem is that 
you can't convert to integer and get the result in a register.  Add to 
that all the fun you can have getting a floating-point value into a 
register, and you start to wonder why you are using the floating-point 
registers at all.  Worse, on a Pentium 4 you don't even want to use the 
FP (st(n)) registers for floating-point, you want to use the SSE2 registers!

But I did have one case where I needed to do about the same thing as you 
are doing realtively fast (the code was in an interrupt handler).  I was 
calculating a floating-point distance and needed to truncate to an 
integer.  I knew the value was in the range 0..2^31-1, so I did the 
magic add, stored the value, and used an overlay to reference the 
low-order 32-bits as an integer.  Worked fine, but I felt very guilty 
afterwards.  As I said to start, there is no right way to do this, just 
best ways for particular processors and situations.

-- 
                                                     Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Problems converting Float to Integer efficiently

[Dr. Adrian Wrigley]

Jeff C, wrote:
> If you can use a more up to date gcc (a 3.X series) and have a pentium 4
> (maybe ok on III)
> then you can try this little thing I made
...
 > Asm ("cvttss2si %1, %0",inputs  => float'asm_input("m", y),
 >                          Outputs => integer'asm_output("=r",temp));

This works great!

I have had no problems on my Athlon (1100MHz clock speed) and GNAT 3.15p

My experiments show the following:
-- X is integer, Y is float
X := X + Truncate(Y);               -- 0.029us    1x
X := X + Integer (Y);               -- 0.360us   12x
X := X + Integer (Float'Floor (Y)); -- 1.196us   41x

This is timed in a  tight loop.  Optimisation "-O3", Checks suppressed, inlined where possible.
I checked carefully that the "right" code was being generated, and the test was fair.
These lines are not exactly equivalent in function - I wanted "floor", but "Truncate" is OK

As you can see, the "obvious" Ada code for converting to integer is at least 12x slower
than Jeff's version. This has the potential to be quite significant in my code which
implements interpolation of five dimensional arrays for function approximation.

I also had a look at the "stereopsis" and "gems" web site.  It seems the deficiency of compiler in
getting integers from floats has caused other people difficulties too.  I'm slightly worried that
the "Truncate" function will fail if the FPU/SSE mode is changed.  I'll try to cross that hurdle
if I encounter it.

Quoting the stereopsis site : "I've seen quite well-written code get 8 TIMES FASTER after
fixing conversion problems. Fix yours! And here's how.."

This whole situation illustrates one of the things which frustrates me about coding in Ada/GNAT:
performance and reliability of Ada code is often very good, but you need to be eternally
vigilant that you are getting out the code that you think you should be getting.  The speed
of the compiled code is sometimes critically dependent on apparently inocuous choices.
Things like enumerated types, use of generics under certain circumstances etc. can cause
apparently good source code to crawl.  Is this a necessary price for ditching low-level HLLs
like 'C'?  Perhaps someone should create a web site highlighting the problem areas and
explaining the solutions? Volunteers anybody?

Thanks guys for the help on this!
--
Adrian Wrigley, Cambridge, England.

Re: Problems converting Float to Integer efficiently

[Jeff C,]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
news:Oplhb.9211$RU4.88029@newsfep4-glfd.server.ntli.net...
> Jeff C, wrote:
> >
> This whole situation illustrates one of the things which frustrates me
about coding in Ada/GNAT:
> performance and reliability of Ada code is often very good, but you need
to be eternally
> vigilant that you are getting out the code that you think you should be
getting.  The speed
> of the compiled code is sometimes critically dependent on apparently
inocuous choices.
> Things like enumerated types, use of generics under certain circumstances
etc. can cause
> apparently good source code to crawl.  Is this a necessary price for
ditching low-level HLLs
> like 'C'?  Perhaps someone should create a web site highlighting the
problem areas and
> explaining the solutions? Volunteers anybody?
>
> Thanks guys for the help on this!


No problem... The problem is not really unique to Ada.  Even with C if you
are writing performance
critical code you often run into areas where you have to do "something" to
make the code run better.
This can be an assembly language insertion or just a restructing of the code
to help the compiler figure
out what you wanted better. I have ended up having to create my own
memcpy/bcopy serveral times
because the "optimized" one from the compiler ended up doing something
really bad for a specific (but
potentially common) situation.

The problem with any website or list I have ever seen that tries to tell you
things to "look out for" is that
they all tend to be full of misleading information that is either based on
someone not understanding the tool
or language or based on some specific compiler, version, bug, os, etc.

My best advice is to run a profiler and see what you can see. Of course this
is one of those things
that people always say but there are plenty of ways for profilers to get
somewhat confused too so even
using a profiler can be somewhat of an art form.

I have personally used generics to actually make some code faster in the
past (and had
no problems with performance critical code with enumeration types as long as
you stay away from 'image 'value in performace critical code and avoid
rep-specing them when you don't need to).

Now even my last statement is full of half-truths and misleading info. I can
just see someone going ah-ha I won't use a 'image I'll build a lookup table
of pointers to strings and return that...and of course the code would be
just as slow..(probably).....

Re: Problems converting Float to Integer efficiently

[Robert I. Eachus]

Dr. Adrian Wrigley wrote:
> Jeff C, wrote:
> 
>> If you can use a more up to date gcc (a 3.X series) and have a pentium 4
>> (maybe ok on III)
>> then you can try this little thing I made
> 
> ...
>  > Asm ("cvttss2si %1, %0",inputs  => float'asm_input("m", y),
>  >                          Outputs => integer'asm_output("=r",temp));
> 
> This works great!
> 
> I have had no problems on my Athlon (1100MHz clock speed) and GNAT 3.15p
> 
> My experiments show the following:
> -- X is integer, Y is float
> X := X + Truncate(Y);               -- 0.029us    1x
> X := X + Integer (Y);               -- 0.360us   12x
> X := X + Integer (Float'Floor (Y)); -- 1.196us   41x
> 
> This is timed in a  tight loop.  Optimisation "-O3", Checks suppressed, 
> inlined where possible.
> I checked carefully that the "right" code was being generated, and the 
> test was fair.
> These lines are not exactly equivalent in function - I wanted "floor", 
> but "Truncate" is OK
> 
> As you can see, the "obvious" Ada code for converting to integer is at 
> least 12x slower
> than Jeff's version. This has the potential to be quite significant in 
> my code which
> implements interpolation of five dimensional arrays for function 
> approximation.
> 
> I also had a look at the "stereopsis" and "gems" web site.  It seems the 
> deficiency of compiler in
> getting integers from floats has caused other people difficulties too.  
> I'm slightly worried that
> the "Truncate" function will fail if the FPU/SSE mode is changed.  I'll 
> try to cross that hurdle
> if I encounter it.
> 
> Quoting the stereopsis site : "I've seen quite well-written code get 8 
> TIMES FASTER after
> fixing conversion problems. Fix yours! And here's how.."
> 
> This whole situation illustrates one of the things which frustrates me 
> about coding in Ada/GNAT: performance and reliability of Ada code 
> is often very good, but you need to be eternally
> vigilant that you are getting out the code that you think you should be 
> getting.  The speed of the compiled code is sometimes critically 
> dependent on apparently inocuous choices.

> Things like enumerated types, use of generics under certain
> circumstances etc. can cause apparently good source code to crawl.
> Is this a necessary price for ditching low-level HLLs > like 'C'?  Perhaps someone should create a web site highlighting the 
> problem areas and explaining the solutions? Volunteers anybody?
> 
> Thanks guys for the help on this!

I think that is just the nature of designing, building, and using 
high-level languages (including in this case C) and compilers.  If the 
hardware architecture is well designed for what you want to do, fine. 
If it isn't, you run into issues like this.  The compiler has to deal 
with choosing the correct implementation in for every different case, 
and since the program space is infinite, you can't exhaustively test the 
compiler.  All you can do--and it is well worth doing--is ensure that 
efficient code is generated in most cases, and correct code in all cases.

The discussion of square root functions going on in another thread is a 
case in point.  The Newton-Rhapson approach has all kinds of nice 
mathematical properties, but it uses divide, and on many modern 
processors divide is painfully slow.  There are ways to take advantage 
of the convergence properties of the algorithm.  For example use 
single-precision divide for all but the last two iterations.  However, 
on most hardware a square root routine that uses add, subtract compare 
and shifts is much faster.  Of course the best solution is to use the 
hardware square root that is part of the IEEE math library--if it is 
present.

And that gets back to the original problem.  Using compiler flags to 
tell the compiler which particular CPU chip you are targetting is very 
worthwhile.  For example, you should see almost a  factor of two speedup 
in floating-point code on a Pentium 4 if you tell the compiler to use 
SSE2.  But on the new Athlon64 from AMD, you can use SSE2 code if you 
want in 32-bit mode, but it will be no faster--and no slower--than x87 
code.

Incidently, the 64-bit long mode on the Athlon64 allows SSE2 floating 
point code only.  Since long mode programs on the Athlon64 can call 
32-bit mode dlls, and these can use the x87 IEEE floating-point 
arithmetic, you can see that this has created a whole new bunch of fun 
for compiler optimizers--and it has nothing to do with HLLs as such.

-- 
                                          Robert I. Eachus

"Quality is the Buddha. Quality is scientific reality. Quality is the 
goal of Art. It remains to work these concepts into a practical, 
down-to-earth context, and for this there is nothing more practical or 
down-to-earth than what I have been talking about all along...the repair 
of an old motorcycle."  -- from Zen and the Art of Motorcycle 
Maintenance by Robert Pirsig

Re: Problems converting Float to Integer efficiently

[Waldek Hebisch]

Dr. Adrian Wrigley (amtw@linuxchip.demon.co.uk.uk.uk) wrote:
: I have had no problems on my Athlon (1100MHz clock speed) and GNAT 3.15p

: My experiments show the following:
: -- X is integer, Y is float
: X := X + Truncate(Y);               -- 0.029us    1x
: X := X + Integer (Y);               -- 0.360us   12x
: X := X + Integer (Float'Floor (Y)); -- 1.196us   41x
The times seem way too high, you should be able to do such calculation 
in 2-3 clocks and you get more then 30 (the relative timings however
look reasonable).

: apparently good source code to crawl.  Is this a necessary price for ditching low-level HLLs
: like 'C'?  Perhaps someone should create a web site highlighting the problem areas and
: explaining the solutions? Volunteers anybody?

Rounding/truncating is a well known problem for many years. I had very
similar problem -- just in C. I wanted rounding, gcc introduced 
truncation. So I added bias and called floor first. When profiling
it turned out that my program spent 70% time roundind and I made about
10 FLOPS per rounding. 

So the problem really has nothing to do with Ada, but just Intel folks
probably forget about HLLs when designing 8087 -- they choose to save
two bits in instructions and used rounding mode stored in proccesor
state word. So to exexute a single instruction using different 
rounding mode you need to store old mode, set new one, do the work
and restore old mode -- that is many instructions (and state change
used to be very slow one). Surely, gcc could do better job, but
if you want really fast rouding/truncation usually you can do faster.

If processor is set to rounding (usual for normal calculation) then
a single (1 clock) assembly instruction will round a number to 
integer. If your number have limited range and you know the precision
setting of the processor then you can truncate adding and substracting
apropriate constant. 

All this is really much below C level (not to mention Ada). And only
programmer knows if assumptions are satisfied, no compiler can check that.


--
                              Waldek Hebisch
hebisch@math.uni.wroc.pl 

Re: Problems converting Float to Integer efficiently

[Randy Brukardt]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> wrote in message
news:Ku4hb.8589$RU4.82535@newsfep4-glfd.server.ntli.net...
> It's a bit disappointing that the compiler does not produce code like this
for
> some "obvious" source code.  I dislike Ada's default of rounding to
nearest, and
> it seems that a series of Float=>Integer attributes might help the
compiler.

Not really, and they would be messy to define. When we discussed this in the
ARG, we concluded that compilers ought to recognize the pattern
Integer(Float'Truncation(Foo)), etc. if that will generate better code (it
usually will). In particular, the code needed to round the float as part of
the conversion to Integer should be omitted (it is already an integer
value). That actually will be in the AARM as a note to implementors (see
AI-267).

So, if you are not getting good code from this, you should complain to your
implementor. This is not a language issue, just a quality of implementation
one.

                 Randy.