5
\$\begingroup\$

How can I optimize the following class?

prepareSharing packs bits on left and prepareMask counts the required bits for encoding integers between zero and max.

public class KeyFactory
{      
  public static short[] prepareSharing( short[] sharing, int mask )
  {
    // Ensure mask is unsigned short
    //
    mask &= 0xFFFF;

    // Search first zero bits
    //
    // BE CAREFUL : raise java.lang.ArrayIndexOutOfBoundsException if there aren't enough bits available
    //
    int i = 0;
    while( ( sharing[i] & 0xFFFF ) == 0xFFFF )
      i++;

    // Handle masks larger than available free bits
    //
    int remaining = ~( sharing[i] & 0xFFFF ) & 0x0000FFFF;

    if( remaining < mask )
    {
      for( ;remaining > 0; remaining >>= 1, mask >>= 1 );      
      sharing[i++] |= 0xFFFF;
    }

    // Pack bits
    //
    int temporary, current = sharing[i];
    for( temporary = ( current | mask ) & 0xFFFF; ( ( current | ( mask << 1 ) ) & 0xFFFF ) > temporary; mask <<= 1, temporary = ( current | mask ) & 0xFFFF );

    sharing[i] = 0;
    sharing[i] |= temporary;

    return sharing;
  }

  public static int prepareMask( int maxCount )
  {
    int mask = 0;

    for( int i = 0; i < 16; i++ )
      if( maxCount >> i > 0 )
        mask |= 1 << i;

    return mask;
  }
}

Tests:

import org.junit.Assert;
import org.junit.Test;

import fr.meuns.render.KeyFactory;

public class TestKeyFactory
{
  @Test
  public void testPrepareMask()
  {
    Assert.assertEquals( 0b0001 ,KeyFactory.prepareMask( 1 ) );
    Assert.assertEquals( 0b0011 ,KeyFactory.prepareMask( 2 ) );
    Assert.assertEquals( 0b0011 ,KeyFactory.prepareMask( 3 ) );
    Assert.assertEquals( 0b0111 ,KeyFactory.prepareMask( 4 ) );
    Assert.assertEquals( 0b0111 ,KeyFactory.prepareMask( 5 ) );
    Assert.assertEquals( 0b0111 ,KeyFactory.prepareMask( 6 ) );
    Assert.assertEquals( 0b0111 ,KeyFactory.prepareMask( 7 ) );

    for( int i = 8; i < 16; i++ )
      Assert.assertEquals( 0b001111 ,KeyFactory.prepareMask( i ) );

    for( int i = 16; i < 32; i++ )
      Assert.assertEquals( 0b011111 ,KeyFactory.prepareMask( i ) );

    for( int i = 32; i < 64; i++ )
      Assert.assertEquals( 0b111111 ,KeyFactory.prepareMask( i ) );
  }

  @Test
  public void testPackSharing_0x0007()
  {
    short[] sharing = new short[] {
      0x0000, 0x0000
    };

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xE000, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFC00, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFF80, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFF0, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFFE, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xC000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xF800, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xFF00, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xFFE0, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x0007 );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xFFFC, sharing[1] & 0xFFFF );
  }

  @Test
  public void testPackSharing_0x003F()
  {
    short[] sharing = new short[] {
      0x0000, 0x0000
    };

    sharing = KeyFactory.prepareSharing( sharing, (short)0x003F );    
    Assert.assertEquals( 0xFC00, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x003F );    
    Assert.assertEquals( 0xFFF0, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0x0000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x003F );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xC000, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x003F );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xFF00, sharing[1] & 0xFFFF );

    sharing = KeyFactory.prepareSharing( sharing, (short)0x003F );    
    Assert.assertEquals( 0xFFFF, sharing[0] & 0xFFFF );
    Assert.assertEquals( 0xFFFC, sharing[1] & 0xFFFF );
  }
}
\$\endgroup\$
  • \$\begingroup\$ What's wrong with good old BitSet? \$\endgroup\$ – Landei Aug 16 '13 at 14:12
  • \$\begingroup\$ BitSet uses JNI, does a lot of checking and stocks bits in long words. JNI and checking wastes performances. Longs are painful for comparing resulting keys (see posts about signed and unsigned int java mess). Converting long words to short words is bad for performance too. \$\endgroup\$ – sylvain Aug 16 '13 at 15:24
  • 2
    \$\begingroup\$ BitSet does not use JNI. Just look at the source. \$\endgroup\$ – Rafael Winterhalter Dec 28 '13 at 0:17
3
\$\begingroup\$

The very first thing I miss, in both your question and the code, is a description of what it does. You should make a habit out of documenting your code with JavaDoc. After some time it will go easy while writing code and will improve the readability tremendously. It's also a nice way to do a quick check if the class is supposed to do what you expect it to do.


Java normally uses a modified K&R style for braces and indentation:

public function void test() {
    if (condition) {
        // Code
    } else {
        // Code
    }
}

Just in case: You're not supposed to use Bitmasks in Java, the EnumSet is supposed to take it's place.


public class KeyFactory

Helper classes should be declared public final with a private constructor like this:

/**
  * Static helper class for dealing with Bitmasks.
  */
public final class KeyHelper {
    private KeyHelper() {}

  public static short[] prepareSharing( short[] sharing, int mask )
  {
    // Ensure mask is unsigned short
    //
    mask &= 0xFFFF;

Yet it is declared as int. Is that by design? if you want an unsigned short, shouldn't you only take an unsigned short? Especially as you cast the ints in the tests to shorts?


// Search first zero bits
//
// BE CAREFUL : raise java.lang.ArrayIndexOutOfBoundsException if there aren't enough bits available
//
int i = 0;
while( ( sharing[i] & 0xFFFF ) == 0xFFFF )
  i++;

That's an information that should go into the JavaDoc of the method.


int i = 0;

The only time i is a valid variable name is within a for-loop. You use it as a reusable and important variable throughout the function, that means that it should have a better, even if longer, name.


You're not using curly braces for one-line loops or ifs. You should start using them as it makes your code easier to read.


Your use of for loops is valid, from a syntactical point of view, but is far from readable.

Turning them into longer, more verbose variants is advised.


I did no review of the logic itself as, to be honest, it is very hard to follow and I have a hard time figuring out what it is supposed to do in the first place (missing documentation and description).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.