Sunday, March 8, 2020

Java Lambda vs method performance is 2x slower

Going over algorithms exercises I found that inline functions with access to outer scope variables make code way cleaner.  In Java 8+ I know two ways of doing so:

  1. wrap an outer scope variables in object and define a method
  2. use Lambda functions
Surprisingly 1st method became almost 2x more performant:
member
    final public class
BinaryGap
{
    public BinaryGap( long value ){ val = value; }

        public final static int
    maxGapCount( final long value )
    {
        final BinaryGap vo = new BinaryGap(value);
        vo.skipBits(0 );

        for( int max0 = 0; vo.val !=0 ; )
        {
            vo.skipBits(1 );
            int z = vo.skipBits(0 );
            if( z == 0 )
                return max0;
            if( z > max0 )
                max0 = z;
        }
        return 0;
    }
    long val;

    final int skipBits( final int bit0 )
    {   int ret = 0;
        do
        {   if( val == 0 || (val&1) != bit0  )
                return ret;
            val = val >> 1;
            ret++;
        }while( val != 0 );
        return ret;
    }
}
Lambda
        public final static int
    maxGapCountLambda(  long value )
    {   class Wrap{ long v; }
        final Wrap w = new Wrap(); w.v = value;
        IntSupplier skip0 = ()->
        {   int count=0;
            long L = w.v;
            for( ; L!=0 && (L&1) == 0; count++ ) // skip 0
                L = L>>1;
            w.v = L;
            return count;
        };
        IntSupplier skip1 = ()->
        {   long L = w.v;
            while( L!=0 && (L&1) == 1 ) // skip 1
                L = L>>1;
            w.v = L;
            return 0;
        };

        skip0.getAsInt();
        int maxCount =0;
        while( w.v != 0 )
        {
            skip1.getAsInt();
            int count =skip0.getAsInt();
            if( count > maxCount )
                maxCount = count;
        }
        return maxCount;
    }

Tests

Test Duration Result
maxGapCount 0s passed
maxGapCountInlineLoad 0.126s
Of course inline is fastest, but not as much readable.
passed
maxGapCountLambdaLoad 0.226s passed
maxGapCountLoad 0.141s passed
skipBits 0s passed
Full sources
BinaryGap.java
package codily.lesson1;

import java.util.function.IntSupplier;
import java.util.function.LongPredicate;
import java.util.function.LongToIntFunction;

/**
 * https://app.codility.com/programmers/lessons/1-iterations/binary_gap/
 */
    final public class
BinaryGap
{
    long val;
    public BinaryGap( long value ){ val = value; }

        public final static int
    maxGapCount( final long value )
    {
        final BinaryGap vo = new BinaryGap(value);
        vo.skipBits(0 );

        for( int max0 = 0; vo.val !=0 ; )
        {
            vo.skipBits(1 );
            int z = vo.skipBits(0 );
            if( z == 0 )
                return max0;
            if( z > max0 )
                max0 = z;
        }
        return 0;
    }
        public final static int
    maxGapCountInline(  long value )
    {
        while( value!=0 && (value&1) == 0 ) // skip 0
            value = value>>1;
        int maxCount =0;

        while( value !=0 )
        {
            while( value!=0 && (value&1) == 1 ) // skip 1
                value = value>>1;

            int count =0;
            while( value!=0 && (value&1) == 0 ) // skip 0
            {   count ++;
                value = value >> 1;
            }
            if( count > maxCount )
                maxCount = count;
        }
        return maxCount;
    }
        public final static int
    maxGapCountLambda(  long value )
    {   class Wrap{ long v; }
        final Wrap w = new Wrap(); w.v = value;
        IntSupplier skip0 = ()->
        {   int count=0;
            long L = w.v;
            for( ; L!=0 && (L&1) == 0; count++ ) // skip 0
                L = L>>1;
            w.v = L;
            return count;
        };
        IntSupplier skip1 = ()->
        {   long L = w.v;
            while( L!=0 && (L&1) == 1 ) // skip 1
                L = L>>1;
            w.v = L;
            return 0;
        };

        skip0.getAsInt();
        int maxCount =0;
        while( w.v != 0 )
        {
            skip1.getAsInt();
            int count =skip0.getAsInt();
            if( count > maxCount )
                maxCount = count;
        }
        return maxCount;
    }


        final int
    skipBits( final int bit0 )
    {   int ret = 0;
        do
        {   if( val == 0 || (val&1) != bit0  )
                return ret;
            val = val >> 1;
            ret++;
        }while( val != 0 );
        return ret;
    }
}
BinaryGapTest.java
package codily.lesson1;

import org.junit.Test;
import static org.junit.Assert.*;

    public class
BinaryGapTest
{
    public final long [] exp =  { 00, 00, 00, 00, 00, 00, 01, 02, 03, 30 };
    public final long [] inp =  { 0b0000_0000_0000_0000_0000_0000_0000_0000L
                                , 0b1111_1111_1111_1111_1111_1111_1111_1111L
                                , 0b0000_0000_0000_0000_0000_0000_0000_0001L
                                , 0b0000_0000_0000_0000_0000_0000_0000_0011L
                                , 0b0000_0000_0000_0000_0000_0000_0000_0010L
                                , 0b0000_0000_0000_0000_0000_0000_0000_0100L
                                , 0b0000_0000_0000_0000_0000_0000_0000_0101L
                                , 0b0000_0000_0000_0000_0000_0000_0000_1001L
                                , 0b0000_0000_0000_0000_0000_0000_1000_1001L
                                , 0b1000_0000_0000_0000_0000_0000_0000_0001L
                                };
    long [] act= new long[inp.length];

        @Test public void
    maxGapCount()
    {
        assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0000L ) );
        assertEquals(00, BinaryGap.maxGapCount( 0b1111_1111_1111_1111_1111_1111_1111_1111L ) );
        assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0001L ) );
        assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0011L ) );
        assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0010L ) );
        assertEquals(00, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0100L ) );

        assertEquals(01, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_0101L ) );
        assertEquals(02, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_0000_1001L ) );
        assertEquals(03, BinaryGap.maxGapCount( 0b0000_0000_0000_0000_0000_0000_1000_1001L ) );
        assertEquals(30, BinaryGap.maxGapCount( 0b1000_0000_0000_0000_0000_0000_0000_0001L ) );
    }
    final int REPEAT_COUNT = 1000_000;

    @Test public void
    maxGapCountLoad()
    {
        for( int k=0; k < REPEAT_COUNT; k++ ) // timer count
            for( int i=0; i<exp.length; i++ )
                act[i] = BinaryGap.maxGapCount( inp[i] );
        assertArrayEquals( act, exp );
    }
        @Test public void
    maxGapCountInlineLoad()
    {
        for( int k=0; k < REPEAT_COUNT; k++ ) // timer count
            for( int i=0; i<exp.length; i++ )
                act[i] = BinaryGap.maxGapCountInline( inp[i] );
        assertArrayEquals( act, exp );
    }
        @Test public void
    maxGapCountLambdaLoad()
    {
        for( int k=0; k < REPEAT_COUNT; k++ ) // timer count
            for( int i=0; i<exp.length; i++ )
                act[i] = BinaryGap.maxGapCountLambda( inp[i] );
        assertArrayEquals( act, exp );
    }

        @Test public void
    skipBits()
    {
        BinaryGap bg = new BinaryGap( 0L );
        assertEquals( "zero", bg.skipBits(0), 0 );
        assertEquals( "zero", bg.skipBits(0), 0 );
        assertEquals( "zero", bg.skipBits(1), 0 );

        bg = new BinaryGap( 0b1111_1111_1111_1111_1111_1111_1111_1111L );
        assertEquals( "zero", bg.skipBits(0), 0 );
        assertEquals( "zero", bg.skipBits(1), 32 );
        assertEquals( "zero", bg.skipBits(1), 0 );
        assertEquals( "zero", bg.skipBits(0), 0 );
    }
}

No comments:

Post a Comment