Java – Why Use Bit Hacks Over Readable Non-Bitwise Techniques

bitwise-operatorscode-qualityjavaperformancereadability

Is there any legitimate use for bit manipulation hacks in higher-level languages such as Java?

I can see them being useful in speed-sensitive low-level and computation-intensive programs, e.g. graphics processing or crypto functions. I guess that's why all collections of them are in C. However, getting to think about them in terms of higher-level design I cannot think of any point where I would, for example, write the following in a Java program:

r = y ^ ((x ^ y) & -(x < y));

rather than:

r = (x < y) ? x : y;

The first line looks more like an obfuscation than an improvement. And most applications have different kinds of bottlenecks – most commonly networks or disc access, so much so that any potential improvement gained by using a bitwise hack would be so tiny that it is completely ignorable.

This line of thought was provoked by a recent SO question in which someone was asked about a bitwise hack in Java during a interview.

I agree as much as anyone that it's always better to write faster code, but considering that it becomes much less readable, especially by someone not familiar with bit hacks, is there any kind of application in which it is legitimately worth it?

This question is not about bitwise operators in general, but more specifically about bitwise hacks, and even more specifically about bitwise hacks in Java.

By bitwise hack I mean a manipulation that has a trivial and/or obvious implementation, but which can be done slightly faster/better with some clever bitwise manipulation — which in most cases makes it near-unreadable to someone not used to bitwise hacks.

There are similar looking questions: Importance of bitwise thinking and What are bit operators good for? The answers in these questions talk about bit manipulations in general, which yes, have a lot of clear and useful applications; especially in other languages like C. While this may seem similar, my question was about having them versus using the non-bitwise technique in Java. In the other questions this is not addressed at all.

Best Answer

Sometimes, the specification of an algorithm is based on bit operations. This is especially true in crypto work.

Crypto has another attribute to it that is important - that the operation takes exactly the same amount of time no matter what the parameters are. This is to try to avoid leaking any data with timing attacks (there are even attacks based on the sounds the computer makes while doing cryptography).

Thus, for cryptography, it is of paramount importance that the code takes exactly the same amount of time and does the same things. Bitwise operations can play a significant role in that area in that they are not often or easily optimized by the compiler. With things were you can short circuit the expression or decide to follow one branch or another that has a different timing these are avenues of timing attacks.

The code

if(x < y) {
  r = x;
} else {
  r = y;
}

Can take different amounts of time based on the branch prediction and branching itself. While

r = y ^ ((x ^ y) & -(x < y));

takes exactly the same amount of time each time through the code. Branch prediction doesn't play a role because there are no branches in there.

With graphics work, there are similar areas of concern. Some systems (especially older ones) had the CRT refresh tied with the clock cycle (for example the Amiga had 4 clock cycles per refresh line). This meant that when you wrote code that was specifically tailored to the graphics of the system you knew exactly where the screen refresh was and could improve the appearance of the system. This isn't quite as much of an issue now (the GForce GTX 780 can do 40,0000 operations per pixel per frame refresh), but it is something to be considered.

Secondly, there's also deep magic within fitting things into various caches on various systems. Doing as much as possible with the cache can improve that. This often means doing bitwise work rather than trying to load and store things or send them off to the ALU.

In Java, this can be difficult to know for certain, but again, maintaining a consistent frame rate based on the scene is something that is often very important with graphics.

Related Solutions

Scala vs Java – Performance Comparison

There's one thing that you can do concisely and efficiently in Java that you can't in Scala: enumerations. For everything else, even for constructs that are slow in Scala's library, you can get efficient versions working in Scala.

So, for the most part, you don't need to add Java to your code. Even for code that uses enumeration in Java, there's often a solution in Scala that is adequate or good -- I place the exception on enumerations that have extra methods and whose int constant values are used.

As for what to watch out for, here are some things.

If you use the enrich my library pattern, always convert to a class. For example:

// WRONG -- the implementation uses reflection when calling "isWord"
implicit def toIsWord(s: String) = new { def isWord = s matches "[A-Za-z]+" }

// RIGHT
class IsWord(s: String) { def isWord = s matches "[A-Za-z]+" }
implicit def toIsWord(s: String): IsWord = new IsWord(s)

Be wary of collection methods -- because they are polymorphic for the most part, JVM does not optimize them. You need not avoid them, but pay attention to it on critical sections. Be aware that for in Scala is implemented through method calls and anonymous classes.
If using a Java class, such as String, Array or AnyVal classes that correspond to Java primitives, prefer the methods provided by Java when alternatives exist. For example, use length on String and Array instead of size.
Avoid careless use of implicit conversions, as you can find yourself using conversions by mistake instead of by design.
Extend classes instead of traits. For example, if you are extending Function1, extend AbstractFunction1 instead.
Use -optimise and specialization to get most of Scala.
Understand what is happening: javap is your friend, and so are a bunch of Scala flags that show what's going on.
Scala idioms are designed to improve correctness and make the code more concise and maintainable. They are not designed for speed, so if you need to use null instead of Option in a critical path, do so! There's a reason why Scala is multi-paradigm.
Remember that the true measure of performance is running code. See this question for an example of what may happen if you ignore that rule.

C++ – Using scoped enums for bit flags in C++

The simplest way is to provide the operator overloads yourself. I am thinking of creating a macro to expand the basic overloads per type.

#include <type_traits>

enum class SBJFrameDrag
{
    None = 0x00,
    Top = 0x01,
    Left = 0x02,
    Bottom = 0x04,
    Right = 0x08,
};

inline SBJFrameDrag operator | (SBJFrameDrag lhs, SBJFrameDrag rhs)
{
    using T = std::underlying_type_t <SBJFrameDrag>;
    return static_cast<SBJFrameDrag>(static_cast<T>(lhs) | static_cast<T>(rhs));
}
    
inline SBJFrameDrag& operator |= (SBJFrameDrag& lhs, SBJFrameDrag rhs)
{
    lhs = lhs | rhs;
    return lhs;
}

(Note that type_traits is a C++11 header and std::underlying_type_t is a C++14 feature.)

Best Answer

Related Solutions

Scala vs Java – Performance Comparison

C++ – Using scoped enums for bit flags in C++

Related Topic