Java-Gaming.org Java4K winners: [ by our judges | by the community ]         
Featured games (67)
games approved by the League of Dukes 		Games in Showcase (∞)
games submitted by our members



News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Java-Gaming.org > Game Development > Performance Tuning > Bit Twiddle & Branch Removal
Pages: [1]
  Print  
  Bit Twiddle & Branch Removal  (Read 1864 times)
0 Members and 2 Guests are viewing this topic.
Offline Roquen

JGO Strike Force
***

Posts: 823
Medals: 25
« on: 2009-10-27 06:25:20 »
These are more interesting for other languages since the JDK does not do a good job of inline/reg-alloc & schedule.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
public static final int clampPositive(int a)
{
  // return (a >= 0) ? a : 0;
  return a & ~(a >> 31); 
}

public static final int abs(int a)
{
  // return (a >= 0) ? a : -a;
  int s = a >> 31;
  a ^= s;
  a -= s;
  return a;
}

public static final int min(int a, int b)
{
  // return (a <= b) ? a : b;
  a -= b;
  a &= (a >> 31);
  a += b;

  return a;
}

public static final int max(int a, int b)
{
  // return (a >= b) ? a : b;
  a -= b;    
  a &= ~(a >> 31);
  a += b;    

  return a;
}

public static final int select(int a, int b, int c, int d)
{
  // return (a<b) ?c : d
  return (((a-b)>>31) & (c^d))^d;
}

public static final int sgn(int a)
{
  // return (a > 0) ? 1 : (a < 0) ? -1 : 0;
  return (-a >>> 31) | (a >> 31);
}
Online Abuse

JGO Kernel
*****

Posts: 1866
Medals: 5


falling into the abyss of reality
« Reply #1 on: 2009-10-27 07:09:44 »
I especially like sgn(..)  Grin
Surely that must be faster than the 1.5 branches needed ordinarily?
Offline Stranger

JGO n00b
*

Posts: 42
Medals: 1
« Reply #2 on: 2009-10-27 09:40:24 »
AFAIK, the shifts are some expensive for Java ...
Anton
Games published by our own members! Go get 'em!
Offline Roquen

JGO Strike Force
***

Posts: 823
Medals: 25
« Reply #3 on: 2009-10-27 09:45:51 »
The shifts are JVM opcodes and the cost will be strongly related to the hardware cost of performing a shift.
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5866
Medals: 255


Hand over your head.
« Reply #4 on: 2009-10-27 09:53:50 »
At that level of execution, it's more about what (surrounding) native code the JIT generates, not so much the cost of the single instruction.
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline Roquen

JGO Strike Force
***

Posts: 823
Medals: 25
« Reply #5 on: 2009-10-27 11:29:45 »
This is a different issue related to the execution of a sequence of instructions and is what my opening comment was attempting to say.  As individual operations, shifts are very fast. 
Offline pjt33

JGO Strike Force
***

Posts: 913
Medals: 17
« Reply #6 on: 2009-10-27 12:16:22 »
Quote from: Roquen on 2009-10-27 06:25:20
1  
2  
3  
4  
5  
public static final int sgn(int a)
{
  // return (a > 0) ? 1 : (a < 0) ? -1 : 0;
  return (a >> 31) | (a >>> 31);
}

Huh That's equivalent to
1  
return (a >= 0) ? 0 : -1;
Online Abuse

JGO Kernel
*****

Posts: 1866
Medals: 5


falling into the abyss of reality
« Reply #7 on: 2009-10-27 12:28:47 »
Quote from: pjt33 on 2009-10-27 12:16:22
Huh That's equivalent to
1  
return (a >= 0) ? 0 : -1;


Indeed; classic case of TGTBT =)

Also, clampPositive is doing more work than it needs to.

1  
2  
3  
4  
5  
public static final int clampPositive(int a)
{
  // return (a >= 0) ? a : 0;
  return a & ~(a >> 31); 
}
Offline Roquen

JGO Strike Force
***

Posts: 823
Medals: 25
« Reply #8 on: 2009-10-27 12:46:04 »
Classic case of screwing up when deleting a cast from C.  Nuked the negate.  And yeah, the &= should just be and.

(edit: I update the original code to reflect these changes)
Offline Jono

Full Member
**

Posts: 143
Medals: 1
« Reply #9 on: 2009-10-27 16:13:13 »
Quote from: pjt33 on 2009-10-27 12:16:22
Huh That's equivalent to
1  
return (a >= 0) ? 0 : -1;


Can't that one just be:

1  
return (a >>> 31) ^ 1


Edit: that was for sgn(a), incase it wasn't clear
Games published by our own members! Go get 'em!
Offline Riven
« League of Dukes »

JGO Kernel
*****

Posts: 5866
Medals: 255


Hand over your head.
« Reply #10 on: 2009-10-27 17:30:28 »
Quote from: Jono on 2009-10-27 16:13:13
Can't that one just be:

1  
return (a >>> 31) ^ 1


Edit: that was for sgn(a), incase it wasn't clear


sgn(int) => [-1, 0, +1]

Your code returns either a 0 or 1, never -1
Hi, appreciate more people! Σ ♥ = ¾

Learn how to award medals... and work your way up the social rankings
Offline Jono

Full Member
**

Posts: 143
Medals: 1
« Reply #11 on: 2009-10-27 18:52:52 »
Quote from: Riven on 2009-10-27 17:30:28

sgn(int) => [-1, 0, +1]

Your code returns either a 0 or 1, never -1
I blame it on the early morning. First I thought sgn returned 1 or -1 only, then I was working in 1's complement instead of 2's complement. Duh.
Pages: [1]
  Print  
 
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.16 | SMF © 2011, Simple Machines Valid XHTML 1.0! Valid CSS!
Page created in 0.102 seconds with 19 queries.