DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Newsletter
Log In / Join
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Related

  • Building an AI-Powered Code Review Assistant in Java
  • Modernizing a Legacy Java Application With OpenRewrite: What We Automated and What We Didn't
  • From Database Changes to Real-Time Actions at Scale: Oracle GoldenGate and Java
  • Java 27 Makes G1 the Default Everywhere: How to Test Your Small Containers Before You Upgrade

Trending

  • Build Production-Ready AI Phone Agents: Infrastructure, Models, and Telephony
  • Designing a Polling Pipeline for Rate-Limited APIs Without Losing Data
  • Engineering Data Observability: Detecting Schema Drift, Data Drift, and Silent Pipeline Failures
  • Spring Security JWT Validation Best Practices

Draft This article hasn't been published, so readers can't see it.

In moderation This article is waiting for review, so readers can't see it yet.

Deleted This article has been deleted, so readers can't see it.

  1. DZone
  2. Testing, Deployment, and Maintenance
  3. Deployment
  4. Java and Branch Prediction

Java and Branch Prediction

Get your microprocessing performance hat on because we're going to talk about branch prediction in Java and how it affects your code.

By 
Artem Rukavytsia
·
Aug. 28, 17 · Tutorial
Post on X (opens in a new tab) Share on LinkedIn (opens in a new tab)
13.5K Views

Join the DZone community Save articles, join the discussion, and download Refcards and Trend Reports with a free account.

Join for free Already a member? Log in

A branch prediction unit is a device that is part of microprocessors that have a pipeline architecture that predicts a conditional jump in an executable program. Branch prediction allows you to reduce the pipeline downtime by preloading and executing instructions that must be executed after the conditional branch instruction is executed. Forecasting branching plays a critical role (the accuracy of the prediction of transitions in modern processors exceeds 90%) because it allows you to optimally use the computing resources of the processor.  

Let's consider this situation: There are two arrays with the same length. The first array is sorted and the other array is unsorted. Processing of one of them is faster than the other. As you could guess from the topic, processing the sorted array is faster than the unsorted array. In fact, branch prediction for the unsorted array will fail.

To understand branch prediction, one must first understand instruction pipelining: A processor with an implementation of branch prediction that usually makes correct predictions can minimize the performance penalty from branching. However, if branches are predicted poorly, it may create more work for the processor, such as flushing the incorrect code path from the pipeline that has begun execution before resuming execution at the correct location.

In case the of the sorted array, the branch predictor always takes the true branch, since historically, all its predictions are correct. But with the random unsorted array, the prediction will need to discard the partially executed instructions and start over with the correct branch.

It can be shown using JMH:

package samples.branch_prediction;

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(5)
@State(Scope.Benchmark)
public class BranchPredictionBenchmark {

    private static final int COUNT = 1024 * 1024;

    private byte[] sorted;
    private byte[] unsorted;

    @Setup
    public void setup() {
        sorted = new byte[COUNT];
        unsorted = new byte[COUNT];
        Random random = new Random(1234);
        random.nextBytes(sorted);
        random.nextBytes(unsorted);
        Arrays.sort(sorted);
    }

    @Benchmark
    @OperationsPerInvocation(COUNT)
    public void sorted(Blackhole bh1, Blackhole bh2) {
        for (byte v : sorted) {
            if (v > 0) {
                bh1.consume(v);
            } else {
                bh2.consume(v);
            }
        }
    }

    @Benchmark
    @OperationsPerInvocation(COUNT)
    public void unsorted(Blackhole bh1, Blackhole bh2) {
        for (byte v : unsorted) {
            if (v > 0) {
                bh1.consume(v);
            } else {
                bh2.consume(v);
            }
        }
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + BranchPredictionBenchmark.class.getSimpleName() + ".*")
                .build();

        new Runner(opt).run();
    }

}


The output of benchmark is next:

# Run complete. Total time: 00:01:48

Benchmark                           Mode  Cnt  Score   Error  Units
BranchPredictionBenchmark.sorted    avgt   25  4.289 ± 0.754  ns/op
BranchPredictionBenchmark.unsorted  avgt   25  9.742 ± 0.466  ns/op


For this benchmark, we used AverageTime BenchmarkMode (see 14 line of the code snapshot). It means that the lower score value is better, and as you see, BranchPredictionBenchmark.sorted is more than two times faster. The full listing of source code is on my GitHub repository.

Branch (computer science) Java (programming language)

Opinions expressed by DZone contributors are their own.

Related

  • Building an AI-Powered Code Review Assistant in Java
  • Modernizing a Legacy Java Application With OpenRewrite: What We Automated and What We Didn't
  • From Database Changes to Real-Time Actions at Scale: Oracle GoldenGate and Java
  • Java 27 Makes G1 the Default Everywhere: How to Test Your Small Containers Before You Upgrade

Partner Resources

×

Comments

Loading comments

The comments didn't load

Please try again in a moment.

Likes

Loading

The next likes didn't load. Please try again.

The likes didn't load

Please try again in a moment.

See who liked this

Log in or join DZone for free to see who liked this article.

Log in Join for free
  • RSS
  • X
  • Facebook

ABOUT US

  • About DZone
  • Support and feedback
  • Community research

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 215
  • Nashville, TN 37211
  • [email protected]

Let's be friends:

  • RSS
  • X
  • Facebook