Tag Archives: bitwise

Performance pattern: Modulo and powers of two

The modulo operator is rare but does occur in certain vital use-cases in Java programming. I’ve been seeing it a lot in striping, segmenting, pipelining and circularity use cases lately. The normal and naive implementation is as below.

    public static int modulo(int x, int y) {
        return x % y;
    }

Recently I saw the following pipelining logic in quite a few places in the codebase on a fast runtime path. This essentially takes an incoming message and uses the following to resolve a queue to enqueue the message onto for later dequeuing by the next stage of the workflow.

int chosenPipeline = input.hashCode() % numberOfPipelines

It is little known, however, that on most hardware the division operation and as a result the modulo operation can actually be quite expensive. You’ll notice that for example modulo is never used in hash functions for example. Have you ever asked why? The reason is that there is a far quicker alternative: bitwise AND. This does involve making a small compromise however in the inputs to the original problem. If we are willing to always supply y in the above method as a power of two we can do the following instead.

    public static int moduloPowerOfTwo(int x, int powerOfTwoY) {
        return x & (powerOfTwoY - 1);
    }

This is dramatically quicker. To give you some stats which you should be asking for at this point see the table below.

Iterations Modulo (ms) PowerOfTwoModulo (ms)
10*4*32 5 1
10*5*32 24 4
10*6*32 237 54
10*7*32 2348 549
10*8*32 30829 5504
10*9*32 320755 54947

You might be thinking at this point – if I’m expecting a power of two I should validate the input to make sure it is so. Well, that’s one viewpoint. The other is, if you’re supplying y or if it is statically configured at startup then you can make sure it is a power of two without taking the performance hit of a runtime check. But if you really want to check here’s how to do so.

    public static boolean isPowerOfTwo(int i) {
        return (i & (i - 1)) == 0;
    }

So the next time you’re writing something that falls into one of the above use cases or any other for the modulo operator and your method needs to be fast at runtime for one reason or another consider the faster alternative. Certainly for price streaming (which is what I’m doing) latency matters! It would be interesting to check whether the java compiler actually makes this optimisation by substitution for you automatically. If so one can stick with the slower alternative for better readability.

The intelligent reader might say that in any such typical modulo use case the use of a bounded data structure and the resulting contention will far outweigh the costs of the modulo operation and the reader would be right in saying so but that’s another problem space entirely that I intend to explore separately. In short – there’s no need to be limited by a bounded data structure 🙂

Effective Java Item 32: Use EnumSet instead of bit fields

A small tidbit of information which I came across in Effective Java Item 32 that I thought was worth a mention due to the fact that it is a little new in Java and less commonly found in use.

The Old Way – Int enum pattern

In the olden days one might have implemented enumeration sets using integers representing binary patterns and bitwise operations on those patterns. This was relatively easy and very efficient but it required reinventing the wheel and boilerplate code to some degree with every use case. It was also not type safe. An example follows.

Bitwise operations

In this particular case I couldn’t help but abstract the bitwise operations out of the main class requiring them but the normal pattern of use is that the bit operations are coupled with the class containing the integer constants.

package resolver;

public class IntEnumPatternResolver {

    private int current = 0;

    public boolean isEnabled(final int flag) {
        return (current & flag) == flag;
    }

    public int current() {
        return current;
    }

    public void enable(final int flag) {
        current |= flag;
    }

    public void disable(final int flag) {
        current &= ~flag;
    }

    public void toggle(final int flag) {
        current ^= flag;
    }

    /*
     * bulk operations
     */

    public void enableAll(final int... flags) {
        for (final int flag : flags) {
            enable(flag);
        }
    }


}
Integer based constants
package resolver;

public class IntEnumPatternExample {

    public static final int STYLE_BOLD          = 1 << 0; // 1
    public static final int STYLE_ITALIC        = 1 << 1; // 2
    public static final int STYLE_UNDERLINE     = 1 << 2; // 4
    public static final int STYLE_STRIKETHROUGH = 1 << 3; // 8

    public static void main(String[] args) {
        final IntEnumPatternResolver resolver = new IntEnumPatternResolver();
        resolver.enableAll(STYLE_BOLD, STYLE_ITALIC, STYLE_STRIKETHROUGH, STYLE_UNDERLINE);
        resolver.disable(STYLE_STRIKETHROUGH);
        resolver.toggle(STYLE_UNDERLINE);
        print(resolver);
    }

    private static void print(IntEnumPatternResolver resolver) {
        assert resolver.isEnabled(STYLE_BOLD) == true;
        assert resolver.isEnabled(STYLE_ITALIC) == true;
        assert resolver.isEnabled(STYLE_UNDERLINE) == false;
        assert resolver.isEnabled(STYLE_STRIKETHROUGH) == false;

        System.out.println("STYLE_BOLD: " + resolver.isEnabled(STYLE_BOLD));
        System.out.println("STYLE_ITALIC: " + resolver.isEnabled(STYLE_ITALIC));
        System.out.println("STYLE_UNDERLINE: " + resolver.isEnabled(STYLE_UNDERLINE));
        System.out.println("STYLE_STRIKETHROUGH: " + resolver.isEnabled(STYLE_STRIKETHROUGH));
    }

}

The New Way – EnumSet<E>

package resolver;

import java.util.EnumSet;

public class EnumPatternExample {

    public enum Style {
        BOLD, ITALIC, UNDERLINE, STRIKETHROUGH
    }

    public static void main(String[] args) {
        final EnumSet<Style> styles = EnumSet.noneOf(Style.class);
        styles.addAll(EnumSet.range(Style.BOLD, Style.STRIKETHROUGH)); // enable all constants
        styles.removeAll(EnumSet.of(Style.UNDERLINE, Style.STRIKETHROUGH)); // disable a couple
        assert EnumSet.of(Style.BOLD, Style.ITALIC).equals(styles); // check set contents are correct
        System.out.println(styles);
    }

}

Discussion

As you can see the new way has far less boilerplate code and the complex and error prone bitwise logic is nicely encapsulated in the EnumSet type as opposed to being in IntEnumPatternResolver (above). As the API docs say EnumSets are represented internally as bit vectors and are extremely compact and efficient and bulk operations are also very quick as long as you pass an EnumSet where the expect argument type is Set.

Update [02/07/2011]: Nice to see this featured on StackOverflow as the top voted answer to that question.