Perfomance Issue in java core between literal operation and Integer operation

Question

I have PowerSet Util class that calculate All possible sub sets of set:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Created by ngrigoriev on 5/19/14.
 */
public class PowerSet {
    /**
     * Returns the power set from the given set by using a binary counter ordered by size Example: S = {a,b,c} P(S) = {[], [c], [b], [b, c], [a],
     * [a, c], [a, b], [a, b, c]}
     * @param superSet - Typed Set {@see Set}
     * @return LinkedHashSet @{see LinkedHashSet} with all possible Sub sets of @param superSet
     */
    public static <E> List<Set<E>> getAllCombinationsOfSubsets(final Set<E> superSet) {
        final List<E> listSet = new ArrayList<>(superSet);
        // create the empty power set
        final List<Set<E>> power = new LinkedList<>();

        // get the number of elements in the set
        final int elements = listSet.size();

        // the number of members of a power set is 2^n
        final int powerElements = (int) Math.pow(2, elements +1) - 1;

        // run a binary counter for the number of power elements
        for (int i = 0; i <= powerElements; i++) {
            // create a new set
            final Set<E> innerSet = new HashSet<>();

            // convert each digit in the current binary number to the
            // corresponding element
            // in the given set
            int tmp = i;
            for (int j = 0; j < elements; j++) {
                if (tmp % 2 == 1) {
                    innerSet.add(listSet.get(j));
                }

                tmp = tmp >> 1;
                if (tmp <= 0) {
                    break;
                }
            }

            // add the new set to the power set
            power.add(innerSet);
        }

        return power;
    }

    public static <E> List<Set<E>> powerset(final Set<E> superSet) {
        final List<E> listSet = new ArrayList<>(superSet);
        // create the empty power set
        final List<Set<E>> power = new LinkedList<>();

        // get the number of elements in the set
        final int elements = listSet.size();

        // the number of members of a power set is 2^n
        final int powerElements = (int) Math.pow(2, elements);

        // run a binary counter for the number of power elements
        for (int i = 0; i < powerElements; i++) {

            // convert the binary number to a String containing n digits
            final String binary = intToBinary(i, elements);

            // create a new set
            final LinkedHashSet<E> innerSet = new LinkedHashSet<>();

            // convert each digit in the current binary number to the
            // corresponding element
            // in the given set
            for (int j = 0; j < binary.length(); j++) {
                if (binary.charAt(j) == '1') {
                    innerSet.add(listSet.get(j));
                }
            }

            // add the new set to the power set
            power.add(innerSet);

        }

        return power;
    }


    /**
     * Converts the given integer to a String representing a binary number with
     * the specified number of digits For example when using 4 digits the binary
     * 1 is 0001
     *
     * @param binary
     * int
     * @param digits
     * int
     * @return String
     */
    private static String intToBinary(final int binary, final int digits) {

        final String temp = Integer.toBinaryString(binary);
        final int foundDigits = temp.length();
        String returner = temp;
        for (int i = foundDigits; i < digits; i++) {
            returner = "0" + returner;
        }

        return returner;
    }
}

And here is a UnitTest

import java.util.HashSet;
import java.util.Set;

import junitparams.JUnitParamsRunner;

import org.junit.Test;
import org.junit.runner.RunWith;

/**
 * Created by ngrigoriev on 5/19/14.
 */
@RunWith(JUnitParamsRunner.class)
public class TestPowerSet {

    public static final int CONST = 1000;

    @Test
    public void testOnInteger() {
        final Set<Integer> set = new HashSet<>();
        for (int i = 0; i < 10; i++) {
            set.add(i);
        }
        final long time = System.currentTimeMillis();

        for (int lll = 1; lll < CONST; lll++) {
            PowerSet.getAllCombinationsOfSubsets(set);
        }

        System.out.println("Time: " + (System.currentTimeMillis() - time));
        System.out.println("total  " + Runtime.getRuntime().totalMemory() / 1024);

        final long time2 = System.currentTimeMillis();

        for (int lll = 1; lll < CONST; lll++) {
            PowerSet.powerset(set);
        }

        System.out.println("Time: " + (System.currentTimeMillis() - time2));
        System.out.println("total  " + Runtime.getRuntime().totalMemory() / 1024);
    }
}

The Question Why powerset method work faster. and some times take less memory??? I already try look on byteCode but i do not find big difference. may be some one can explain me what happened.

I must admit I don't use JUnit for performance tests; does JUnit do the warm up phase for you? — Richard Tingle, May 21 '14 at 10:03
@RichardTingle From what I know, JUnit doesn't do warmups. I'd imagine this is because the user would be more interested in getting the tests done fast rather than relying on them for timing... If memory serves there are some plugins that add benchmarking-related things like warmups to JUnit tests though. — awksp, May 21 '14 at 10:18
Given what @user3580294 has said the most likely issue here is that you are microbenchmarking incorrectly. Java initially runs by interpreting bytecode (moderate speed), then if appropropriate it will compile that bytecode to native code (fast). This means that any shared methods will be slower in the first test because they are (at least initially) being interpreted; worse still the compilation may happen during the test which can further skew results. As a bare minimum always include a warmup phase in any microbenchmark — Richard Tingle, May 21 '14 at 10:22
See [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) for more details — Richard Tingle, May 21 '14 at 10:24
i add a perfomance test here only as example of difference in algoritm. I know how to make a good banch mark but in this case i do not need them — Grigoriev Nick, May 21 '14 at 13:38

score 3 · Accepted Answer · answered May 21 '14 at 10:39

The reason here is quite simple: The slower method is wrong. It returns a list that contains twice as many elements as the faster one.

Run, for example,

public class TestPowerSet2
{
    public static void main(String[] args)
    {
        Set<Integer> set = new LinkedHashSet<Integer>(Arrays.asList(0,1,2));

        List<Set<Integer>> resultA = PowerSet.getAllCombinationsOfSubsets(set);
        System.out.println("Result A:");
        for (Set<Integer> s : resultA)
        {
            System.out.println("    "+s);
        }

        List<Set<Integer>> resultB = PowerSet.powerset(set);
        System.out.println("Result B:");
        for (Set<Integer> s : resultB)
        {
            System.out.println("    "+s);
        }
    }
}

The computation and loop of the number of elements in getAllCombinationsOfSubsets should be the same as in the powerset method, namely

// the number of members of a power set is 2^n
final int powerElements = (int) Math.pow(2, elements);

// run a binary counter for the number of power elements
for (int i = 0; i < powerElements; i++) {

Then, the first method is faster (as expected).

By the way: Powers of 2 can also be computed with a bit shift:

final int powerElements = 1 << elements;

Perfomance Issue in java core between literal operation and Integer operation

1 Answers1