4

I read this, that and a few others already.

Annoyingly, in Java, it takes more than a byte to store a boolean, which should be one bit. Boolean arrays cheat and only use one byte per boolean, but that's still 8x the amount of space they need.

I thought perhaps theoretically at least I could treat them as bits and encode them in a larger primitive. An int would work fine for most cases. Sure, when I wanted to use it I would have to convert it back but at least I would be nearly optimally using memory. One boolean isn't a lot, but a lot of them add up. Besides, it's a simple optimization that would have a significant impact.

I hadn't seen any ways to read a single bit as a boolean or write a boolean as a bit to some value (stored as byte, short, int or long). Not in Java at least.

Using BitSet is an option, but in a data class I should probably write code specific to it to be as efficient as possible.

Probably optimized versions of the methods I came up with for both:

Read, probably the best already

public boolean read(int encoded,int index){
    return (encoded << index) < 0;
}

Alt read, probably marginally slower

public boolean read(int encoded,int index){
    return (encoded << index >>> 31) == 1;
}

Alt read, used in BitSet*

public boolean read(int encoded,int index){
    return (encoded & (1 << index)) != 0;
}

Write, if it isn't optimal blame the compiler for not making it

public int write(int encoded,int index,boolean bit){
    int bits = 1 << (31-index);
    if(bit){
        return encoded | bits;
    }else{
        return encoded & (~bits);
    }
}

Alt write, written by someone else and adapted by me, probably less efficient

public int write(int encoded,int index,boolean bit){
    return encoded ^ (((bit?-1:0) ^ encoded) & (1 << index));
}

Surely there is a better way?

*Update

Looked at the source code for BitSet. The only one that's different other than all the safety and the long array is the one I pointed out, their read. If the Java devs working on the official util library can't figure out a better solution then it's probably optimal. Also means there's sadly no secret bytecode instruction to do this.

Community
  • 1
  • 1
  • 3
    Why are you optimizing the storage of bits (or `boolean`s) in the first place? What problem do you really want to solve? – Elliott Frisch Jan 06 '17 at 02:30
  • Unless you're sending the data over a network, I don't really any point of these micro-optimizations. – Jacob G. Jan 06 '17 at 02:35
  • _"Surely there is a better way?"_ - Well, yes. Use `BitSet` which you dismiss for what sounds to me like a very sketchy reason. – Ted Hopp Jan 06 '17 at 02:42
  • Yep, I really overestimated the amount of extra data BitSet uses to wrap the raw bits, which are encoded in longs. BitSet is very minimal already so I wouldn't be gaining much performance either by writing my own micro-optimized methods. –  Jan 06 '17 at 03:10
  • How do you come to the claim “it takes more than a byte to store a boolean”? The way, boolean values are represented by the JVM is entirely up to the JVM. HotSpot/openJDK may use a byte per boolean for arrays, but they typically run on machines, where that isn’t an issue. Other JVMs for platforms with less memory can do it entirely different. – Holger Jan 06 '17 at 15:42

0 Answers0