www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - fast floor

reply Spacen Jasset <spacenjasset yahoo.co.uk> writes:
Hello,

I am after a fast floor function; In fact a fast truncation and 
conversion to integer. I see that std.math takes a real, and that 
std.c.math takes a double.

Is there a quicker function, and what might cast(int)1.5f do?

Regards,

Spacen.
Oct 10 2013
next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
On 11/10/13 00:27, Spacen Jasset wrote:

 I am after a fast floor function; In fact a fast truncation and conversion to
 integer. I see that std.math takes a real, and that std.c.math takes a double.

 Is there a quicker function, and what might cast(int)1.5f do?


What's wrong with

     to!int(floor(x));

... which you could also write as

     x.floor.to!int;

Have you tried it?  Is it empirically to slow for your purposes, or are you
just 
assuming it won't work?
Oct 10 2013
prev sibling next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
On Thursday, 10 October 2013 at 22:27:14 UTC, Spacen Jasset wrote:

 Hello,

 I am after a fast floor function; In fact a fast truncation and 
 conversion to integer. I see that std.math takes a real, and 
 that std.c.math takes a double.

 Is there a quicker function, and what might cast(int)1.5f do?

 Regards,

 Spacen.


casting to int does't "floor" a floating type. It truncates it
towards 0. eg:
cast(int)-2.5 => 2.

Keep that in mind, and ask yourself which you require (in
particular, do you even care about negatives at all)?

AFAIK, the "point" of floor is to have a double "end to end": if
you use:
double df = cast(int)mydouble;
Then:
a) You'll lose performance by transforming to int, when floor is
smart enough not to.
b) if mydouble doesn't fit in an int, it'll fail (in this case,
floor does nothing, but it doesn't clobber your mydouble either.

So, if you don't need a double at the end, I *think* using
cast(int) is probably faster.

To protecte yourself from overflow/underflow problems, you can
also use "to", eg:
int myInt = to!int(myDouble);

As long as you are in positive space, this is probably what you
want, and probably as fast as it gets.

If you have to take into account negative numbers, things get
more hairy. I'd use either of:
to!int(foor(x)); //As suggested by JRW
or
(x < 0) ? -to!int(-x) : to!int(x)

However, you'd have to bench to *really* know which is fastest.

Honestly, at the end of the day, I'd just use
to!int(foor(x));

THEN I'd profile, and then I'd see if it's worth trying to throw
optimizations at it.
Oct 10 2013
parent reply Spacen Jasset <spacenjasset yahoo.co.uk> writes:
On 11/10/2013 07:25, monarch_dodra wrote:> On Thursday, 10 October 2013 
at 22:27:14 UTC, Spacen Jasset wrote:

 Hello,

 I am after a fast floor function; In fact a fast truncation and
 conversion to integer. I see that std.math takes a real, and that
 std.c.math takes a double.

 Is there a quicker function, and what might cast(int)1.5f do?

 Regards,

 Spacen.


 casting to int does't "floor" a floating type. It truncates it
 towards 0. eg:
 cast(int)-2.5 => 2.

 Keep that in mind, and ask yourself which you require (in
 particular, do you even care about negatives at all)?

 AFAIK, the "point" of floor is to have a double "end to end": if
 you use:
 double df = cast(int)mydouble;
 Then:
 a) You'll lose performance by transforming to int, when floor is
 smart enough not to.
 b) if mydouble doesn't fit in an int, it'll fail (in this case,
 floor does nothing, but it doesn't clobber your mydouble either.

 So, if you don't need a double at the end, I *think* using
 cast(int) is probably faster.

 To protecte yourself from overflow/underflow problems, you can
 also use "to", eg:
 int myInt = to!int(myDouble);

 As long as you are in positive space, this is probably what you
 want, and probably as fast as it gets.

 If you have to take into account negative numbers, things get
 more hairy. I'd use either of:
 to!int(foor(x)); //As suggested by JRW
 or
 (x < 0) ? -to!int(-x) : to!int(x)

 However, you'd have to bench to *really* know which is fastest.

 Honestly, at the end of the day, I'd just use
 to!int(foor(x));

 THEN I'd profile, and then I'd see if it's worth trying to throw
 optimizations at it.


I will have to learn about what "to" does exactly. It wasn't around when 
I looked at D x years ago.

My rounding-truncation is for a graphical demo, nothing serious or 
accurate, but it's important it be fast. I've found that for my purposes 
cast(int) some_float causes the program to run 47% faster, which is what 
I was looking for. I am just reading up on the D floating point pages 
which I have discovered to see how this works. It is, incidentally a 
similar story for C++.
Oct 11 2013
parent "Joseph Rushton Wakeling" <joseph.wakeling webdrake.net> writes:
On Friday, 11 October 2013 at 20:31:50 UTC, Spacen Jasset wrote:

 I will have to learn about what "to" does exactly. It wasn't 
 around when I looked at D x years ago.




Its principal benefit is that it can do overflow checks, so it's 
worth using unless there is a very extreme speed requirement.  
That's why I suggest trying it first (in combination with 
floor()) and then perhaps replacing to!int with a cast only if it 
turns out to be unacceptably slow.
Oct 13 2013
prev sibling next sibling parent =?ISO-8859-1?Q?S=F6nke_Ludwig?= <sludwig outerproduct.org> writes:
Am 11.10.2013 00:27, schrieb Spacen Jasset:

 Hello,

 I am after a fast floor function; In fact a fast truncation and
 conversion to integer. I see that std.math takes a real, and that
 std.c.math takes a double.

 Is there a quicker function, and what might cast(int)1.5f do?

 Regards,

 Spacen.


For a noise generator I wrote some little assembler routines for that 
some years ago. It's main speed advantage comes from the fact that it 
allows to set the rounding mode once (ftoi_init) instead of for every 
conversion (as a cast(int) does for example). However, it requires great 
care that the rounding mode isn't accidentally changed during the 
computation by some function.

Today I would use core.simd instead, though (using XMM.CVTSS2SI), but 
that requires that the whole algorithm is in SIMD for optimal performance.

This is the old code:

	void ftoi_init() {
		fesetround(FE_DOWNWARD);
	}
	void ftoi_toint2(int* dst, float src) {
		asm {
			mov EAX, dst;
			fld src;
			fistp [EAX];
		}
	}
	void ftio_fracint(int* int_part, float* frac_part, float src) {
		asm {
			mov EAX, int_part;
			mov EBX, frac_part;
			fld src;
			frndint;
			fist [EAX];
			fld src;
			fsubr;
			fstp [EBX];
		}
	}
	void ftoi_round(float* dst, float src) {
		asm {
			mov EAX, dst;
			fld src;
			frndint;
			fstp [EAX];
		}
	}
Oct 11 2013
prev sibling parent "ponce" <contact gam3sfrommars.fr> writes:
On Thursday, 10 October 2013 at 22:27:14 UTC, Spacen Jasset wrote:

 Hello,

 I am after a fast floor function; In fact a fast truncation and 
 conversion to integer. I see that std.math takes a real, and 
 that std.c.math takes a double.

 Is there a quicker function, and what might cast(int)1.5f do?

 Regards,

 Spacen.


If you don't need to handle negatives, I suggest you simply use a 
cast(int) since truncation has both a x87 instruction (FISTTP) 
and a SSE instruction (CVTTSS2SI).
Oct 13 2013