Java integer flag and bitwise operations for memory reduction

Question

Is using an integer flag and bitwise operations an effective way of reducing the memory footprint of high volume Objects?

• Memory Footprint

  It is my understanding that commonly a boolean is stored as an int in a JVM implementation. Is this correct? In which case surely the 32 flags represent a large memory footprint reduction.

  Although of course the JVM implementations vary, so this may not always be the case.

• Performance

  It is my understanding that CPUs are very number driven and bitwise operations are about as efficient as things come in computing.

  Is there a performance penalty - or even gain - to using bitwise operations over boolean operations?

• Alternatives

  Is there a better way of accomplishing the same thing? Does an Enum allow the combination of flags i.e. FLAGX = FLAG1 | FLAG2?

---

Example Code

Note the last method propogateMove() is recursive and may be called many hundreds of times per second and has a direct effect on the responsiveness of our application, hence the usage of flags to avoid logic bits and calling other methods.

// FLAGS helper functions
private final void setclear(int mask, boolean set) { if (set) set(mask); else clear(mask); }
private final void set(int mask) { flags |= mask; }
private final void clear(int mask) { flags &= ~mask; }
private final boolean test(int mask) { return ((flags & mask) == mask); }



// Flags //////////////////////////////////////////////////////////////////////

private static final boolean HORIZONTAL          = true;
private static final boolean VERTICAL            = false;

private static final int ORIENT                  = 0x00000001;
private static final int DISPLAY                 = 0x00000002;
private static final int HSHRINK                 = 0x00000004;
private static final int VSHRINK                 = 0x00000008;
private static final int SHRINK = HSHRINK | VSHRINK;

private static final int TILE_IMAGE              = 0x00000010;
private static final int CURSOR                  = 0x00000020;
private static final int MOUSEINSIDE             = 0x00000040;
private static final int MOUSEINSIDE_BLOCKED     = 0x00000080;

private static final int CONSTRAIN               = 0x00000100;
private static final int CONSTRAIN_DESCENDENT    = 0x00000200;
private static final int PLACE                   = 0x00000400;
private static final int PLACE_DESCENDENT        = 0x00000800;
private static final int REFLOW = CONSTRAIN | CONSTRAIN_DESCENDENT | PLACE | PLACE_DESCENDENT;

private static final int PACK                    = 0x00001000;
private static final int CLIP                    = 0x00002000;
private static final int HAS_WIDTH_SLACK         = 0x00004000;
private static final int HAS_HEIGHT_SLACK        = 0x00008000;

private static final int ALIGN_TOP               = 0x00010000;
private static final int ALIGN_BOTTOM            = 0x00020000;
private static final int ALIGN_LEFT              = 0x00040000;
private static final int ALIGN_RIGHT             = 0x00080000;
private static final int ALIGNS = ALIGN_TOP | ALIGN_BOTTOM | ALIGN_LEFT | ALIGN_RIGHT;
private static final int ALIGN_TOPLEFT = ALIGN_TOP | ALIGN_LEFT;
private static final int ALIGN_TOPRIGHT = ALIGN_TOP | ALIGN_RIGHT;
private static final int ALIGN_BOTTOMLEFT = ALIGN_BOTTOM | ALIGN_LEFT;
private static final int ALIGN_BOTTOMRIGHT = ALIGN_BOTTOM | ALIGN_RIGHT;

private static final int ENTER_TRAP              = 0x00100000;
private static final int LEAVE_TRAP              = 0x00200000;
private static final int _MOVE_TRAP              = 0x00400000;
private static final int MOVE_TRAP               = 0x00800000;

private static final int CHILDREN_READ_TRAP      = 0x01000000;
private static final int CHILDREN_TRAP           = 0x02000000;
private static final int PLACE_CLEAN             = 0x03000000;

private static final int SHRINK_TRAP             = 0x04000000;
private static final int HSHRINK_TRAP            = 0x10000000;
private static final int VSHRINK_TRAP            = 0x20000000;

//private static final int UNUSED                = 0x40000000;
//private static final int UNUSED                = 0x80000000;




// Flags in switch ////////////////////////////////////////////////////////////

/** get align value as a string from align flags */
private JS alignToJS() {
    switch(flags & ALIGNS) {
        case (ALIGN_TOPLEFT):
            return SC_align_topleft;
        case (ALIGN_BOTTOMLEFT):
            return SC_align_bottomleft;
        case (ALIGN_TOPRIGHT):
            return SC_align_topright;
        case (ALIGN_BOTTOMRIGHT):
            return SC_align_bottomright;
        case ALIGN_TOP:
            return SC_align_top;
        case ALIGN_BOTTOM:
            return SC_align_bottom;
        case ALIGN_LEFT:
            return SC_align_left;
        case ALIGN_RIGHT:
            return SC_align_right;
        case 0: // CENTER
            return SC_align_center;
        default:
            throw new Error("This should never happen; invalid alignment flags: " + (flags & ALIGNS));
    }
}




// Flags in logic /////////////////////////////////////////////////////////////

private final boolean propagateMove(int mousex, int mousey) throws JSExn {
    // start with pre-event _Move which preceeds Enter/Leave
    if (test(_MOVE_TRAP)) {
        if (Interpreter.CASCADE_PREVENTED == justTriggerTraps(SC__Move, JSU.T)) {
            // _Move cascade prevention induces Leave
            propagateLeave();
            // propagate cascade prevention
            return true;
        }
    }

    // REMARK: anything from here on in is a partial interruption relative
    // to this box so we can not call propagateLeave() directly upon it
    int i;
    boolean interrupted = false;

    if (!test(PACK)) {
        // absolute layout - allows for interruption by overlaying siblings
        for (Box b = getChild(i=treeSize()-1); b != null; b = getChild(--i)) {
            if (!b.test(DISPLAY)) {
                continue;
            }
            if (interrupted) {
                b.propagateLeave();
                continue;
            }
            int b_mx = mousex-getXInParent(b);
            int b_my = mousey-getYInParent(b);
            if (b.inside(b_mx, b_my)) {
                if (b.propagateMove(b_mx, b_my)) {
                    interrupted = true;
                }
            } else {
                b.propagateLeave();
            }
        }
    } else {
        // packed layout - interrupted still applies, plus packedhit shortcut
        boolean packedhit = false;
        for (Box b = getChild(i=treeSize()-1); b != null; b = getChild(--i)) {
            if (!b.test(DISPLAY)) {
                continue;
            }
            if (packedhit) {
                b.propagateLeave();
                continue;
            }
            int b_mx = mousex-getXInParent(b);
            int b_my = mousey-getYInParent(b);
            if (b.inside(b_mx, b_my)) {
                packedhit = true;
                if (b.propagateMove(b_mx, b_my)) {
                    interrupted = true;
                }
            } else {
                b.propagateLeave();
            }
        }
    }

    // child prevented cascade during _Move/Move which blocks
    // Enter on this box - invoking Leave if necessary
    if (interrupted) {
        if (test(MOUSEINSIDE)) {
            if (!test(MOUSEINSIDE_BLOCKED)) {
                // mouse previously inside, now blocked so invoke Leave
                set(MOUSEINSIDE_BLOCKED);
                if (test(LEAVE_TRAP)) {
                    justTriggerTraps(SC_Leave, JSU.T);
                }
            }
        } else {
            // mouse not previously inside, Enter not yet triggered, so
            // do not invoke Leave
            set(MOUSEINSIDE);
            set(MOUSEINSIDE_BLOCKED);
        }
        // propagate cascade prevention 
        return true;
    }

    // set cursor if applicable to this box
    if (test(CURSOR)) {
        Surface s = getSurface();
        if (s!=null && !s.cursorset) {
            s.cursor = JSU.toString(getAndTriggerTraps(SC_cursor));
            s.cursorset = true;
        }
    }

    // fire Enter traps
    if (!test(MOUSEINSIDE)) {
        set(MOUSEINSIDE);
        if (test(ENTER_TRAP)) {
            justTriggerTraps(SC_Enter, JSU.T);
        }
    }

    // finish post-event Move which follows Enter/Leave
    if (test(MOVE_TRAP)) {
        if (Interpreter.CASCADE_PREVENTED == justTriggerTraps(SC_Move, JSU.T)) {
            // propagate cascade prevention
            return true;
        }
    }

    // propagation uninterrupted
    return false;
}

Filings

I would say the answer is highly context dependent. Typically I favour enums and constructs such as EnumSet. However, for wire protocol implementations or examples such as the one above related to display code bitwise operations offer a clear advantage. – Birdiebirdlike

Answer 1

It is my understanding that commonly a boolean is stored as an int in a JVM implementation. Is this correct?

It depends on the JVM implementation of course, but is probably true for implementations on mainstream CPUs.

In which case surely the 32 flags represent a large memory footprint reduction.

If you actually have 32 flags in a class, and a large number of instances of that class, yes. If you never have more than a few hundred instances, it's not worth worrying about.

It is my understanding that CPUs are very number driven and bitwise operations are about as efficient as things come in computing.

This is true.

Is there a performance penalty - or even gain - to using bitwise operations over boolean operations?

That depends also on the memory usage. If you work very intensively with only a few objects, the bitwise operations may slow things down. If you have lots of objects, the reduced memory will probably improve performance a lot due to better caching behaviour.

Is there a better way of accomplishing the same thing? Does an Enum allow the combination of flags i.e. FLAGX = FLAG1 | FLAG2?

Instead of doing the bitwise operations yourself, you can (and should) use a BitSet. And yes, it would be even cleaner if you could work with Enums and an EnumSet, but if you have a number of enums with a few elements each, it would probably not yield the desired memory savings, due to the overhead for multiple EnumSet instances.

Thereinto

The JVM byte codes do not distinguish between ints and booleans, so I doubt it depends on the CPU. Method signatures and fields include the distinction to allow proper type checking. – Letterperfect

@Mathias: But the question is basically about boolean fields. – Thereinto

Aren't multiple boolean fields combined into a larger value (e. g. int) by the VMs? I thought I heard something about that. – Robles

@soc: not to my knowledge. But I'd certainly be interested to hear about any concrete counterexamples. – Thereinto

Answer 2

Yes, a boolean is stored as a 32 bit int. Method signatures distinguish between booleans and ints but otherwise they are treated the same. This is part of the JVM byte code specification.

The bitwise operations on Java map directly to a single instruction on the CPU which does the same bitwise operation, so it is indeed pretty fast. Of course it is faster to keep each value in its own 32 bit word (then you do not need to do any bitwise operations at all). You will save memory and spend more CPU cycles using your approach.

Java has no operator for combining enum, and I do not see how that would make any sense anyway...

Letterperfect

re: "Java has no operator for combining enum" take a look at EnumSet – Mccarter

EnumSet will not combine two enums to give a new Enum. – Letterperfect

Answer 3

Is using an integer flag and bitwise operations an effective way of reducing the memory footprint of high volume Objects?

If an object has a large number of these flags AND there are huge numbers of these objects (or reducing heap usage is a critical issue) then this may be a worthwhile micro-optimization. Otherwise no (IMO).

The problem with this is that it makes your code harder to read and more fragile. So you really should only contemplate it if memory usage is a critical issue.

Richers

Answer 4

As you can't trust booleans are stored as bits or integers (I think the latter is the actual implementation), yes I think bit masks and flags do improve performance.

I have used them on some projects. They are less readable, but I never minded about that since my opinion is that every programmer should understand binary notation and arithmetic.

Just a recommendation: as for java 7, we can define the numeric literals like this:

   private static final int ENTER_TRAP = 0b00000000000100000000000000000000;

And even like this:

   private static final int ENTER_TRAP = 0b0000_0000_0001_0000_0000_0000_0000_0000;

Bromeosin