OpenAI GPT-2 is amazing

OpenAI GPT-2 is amazing

This week I’ve finally gotten around to research (play with) OpenAI’s groundbreaking language model GPT-2 using talktotransformer.com.

What is OpenAI?

OpenAI is an AI research organization founded by Elon Musk in January 2016 to explore, develop, and deploy technology for the benefit of humanity. It’s headquartered in San Francisco, with headquarters in Mountain View, California.

And GPT-2?

OpenAI recently unveiled a language model called GPT-2 that, given some input text, predicts the coming sentences. GPT-2 also supports the idea of the “Grammar of Reasoning” (GRR), in which the model attempts to extract sentences that would make the most intuitive sense, in terms of human understanding. For example, if you input “the dog ate the cat” and the model predicts “dogs eat cats”, the GRR system would make that sentence as the most probable result. The problem is that even though GRR is very good at answering the question, its predictions are still highly contingent. For example, it is still possible to be a cat-eating dog, and then someone else who doesn’t eat cats can still eat your dog, but the GRR system would not make such a mistake for the second sentence.

GPT-2 uses an adaptive model to learn the most relevant concepts to solve complex problems. This is accomplished by using the most relevant words as words, rather than the least relevant words. The model is adaptive to the structure of the content being analyzed.

How does it work?

There are several components involved in GPT. GPT uses a deep learning based model to understand a large vocabulary.

The model consists of a neural network, which is composed of multiple layers. Each layer is a separate layer that processes a different input word. GPT uses two neural network layers for each of the following steps:

First, each layer learns to recognize a particular word. The layers for both input and target are trained together to improve the model’s performance over time.

Second, the neural networks are used to predict the target word for the current context. To do this, the first neural network is used to learn about the target word. The target is then used to select a second neural network layer, which is used to predict the word that is closest to the current context.

Is the model too powerful?

This is a good question to ask, but it should be taken with a grain of salt. In fact, the GPT-2 is actually quite limited in the way it learns the most relevant concepts. This is in part due to its learning model being a probabilistic algorithm that assumes a model of the world as a probabilistic system. This model is an attempt to describe all the possible states of the world, but the way it learns these states is by taking into account the best model for each state and comparing to that.

A GPT-2 surprise

Surprise!

This entire blogpost above has been generated by OpenAI’s GPT-2. I’ve only given the first sentence and the four headers as input. After that I’ve let GPT-2 fill in the blanks (of course I’ve cherry-picked here). The quality is amazing and I’m pretty sure there are people that made it this far… and had no clue that what they’ve been reading was 100% generated by a machine.

Be sure to play around with it at talktotransformer.com


Joggling4Trees

Joggling4Trees

Last week, during a code camp session at work, for some reason the subject of “joggling” came up.

What is Joggling?

So what is this ‘joggling’? The word joggling is a portmanteau of juggling and jogging (running).

This might sound very strange, but it is an actual sport. There are people joggling marathons (in under three hours!), they are faster while juggling 3 balls than most people (including me) are just running. I’m probably never running a marathon under three hours.

A man joggling (not me)

I’ve learned how to juggle when I was in my early teens, and it is a skill I’ll never forget, muscle memory. And a couple of years ago I had an annoying knee injury which prevented me from running too far or too fast.

This is when I learned about joggling. For me it was the perfect way to still enjoy running while not pushing my knees too much. Adding the juggling (3 balls) to my running prevented further injuries, it slowed me down and decreased the distance I was able to run.

And it is great: Almost everyone gets a smile on their face when I run past them when joggling.

The challenge: Bruggenloop 2019

When I mentioned joggling to my colleagues last week they encouraged me to try it once more.

We came up with the following challenge:

On sunday the 8th of december I’m going to joggle the Bruggenloop, a 15k race while juggling 3 balls. This will be the first time I’m joggling a race and it’ll be the first time I’ll joggle for over an hour. I’ve never done more than 10k, heck, I haven’t been running at all for the last 6 months. So there is quite some work to do now!

Me right now...

Update: I’ve received a decline email from the Bruggenloop organisers. So I’m going to have to come up with a plan B. This will likely be a 15k run… by myself, without anyone cheering me on, without providing all the onlookers with a smile.

Joggling for #TeamTrees

Because I’m doing this, my colleagues are donating money to #TeamTrees. This is a charity that, for each dollar, gets a new tree planted. Yes, all 100% of the donations will go towards planting new trees.

To encourage me not to give up I’ve created the following page Joggling4Trees where we can track the donations to my cause.

At the moment we’ve already collected almost 900 dollars, that means 900 new trees! Which is a freaking forest! I’m so happy with this, and encourages me to train even harder and make everyone proud!

But we can do even better… if you read this, please consider adding a few trees to this planet, every dollar helps!

FAQ

Some questions I’ve received about joggling:

  • Can you drop a ball?

Yes, this will probably happen a lot, you are not ‘disqualified’ for dropping a ball, just pick it up and continue from the point you’ve dropped. If a soccer player falls during a match they don’t automatically lose the game, it is part of the game.

  • What is the worst that can happen?

Losing one or more balls. I’ve had this happen during a training session, one of my balls is now at the bottom of a river. RIP.

  • What gear do you need to joggle?

Running shoes and 3 balls, that’s it.

And optionally:

Gloves (especially in december, it gets really cold/near freezing), it is hard to joggle when your hands are numb. Transparant glasses, during joggling you tend to not blink as much, and when you run in cold weather this causes a lot of tears to form. Glasses will fix this.

  • Why would anyone joggle….?

Here is an excellent explaination about why everyone should take up joggling as a sport:

One more time:

To support this, plant some trees: Joggling4Trees


The world of biased algorithms

The world of biased algorithms

The world is changing, more and more people are openly against racism, against gender discrimination, very much pro equality. People and companies are being called out when they do discriminate and there is a big movement against bias (in general).

One problematic thing though, for me as a programmer, is the backlash against ‘biased algorithms’.

Algorithms

What are algorithms?

If you look up the definition wikipedia you’ll find:

A sequence of instructions, typically to solve a class of problems or perform a computation. Algorithms are unambiguous specifications for performing calculation, data processing, automated reasoning, and other tasks.

In our case today, let’s define it is a set of instructions that a computer follows so it does a calculation and produces a result. People also do the same thing, they use sets of rules to come to certain conclusions.

Bias in algorithms

The problem here is bias. What is the problem with bias in algorithms?

Suppose we have an algorithm that determines if you do or don’t get a loan, and also determines the interest rate. This is great, before this system the bank had a human that was responsible for applying/declining loans, now a the computer can do this.

Now of course, it would be very bad if the programmer and product owners came up with the following rule:

if(applicant.isFemale()) {
   loan.addInterest(10); 
}

If is easy to state this rule is discriminating against a particular gender, we don’t want this discrimination.

But what if a certain car insurance charges 5% extra for male drivers under 25 with DUI charge? That kind of makes sense, it is still discrimination though, but we do allow this. It is a slippery slope.

The good thing though is: The rules are clear. Before there might have been a racist human doing the declines, now it is clear.

Bias in A.I./ML

The real problem though starts when you enter the world of AI, big data and machine learning. Now a programmer is no longer writing the readable rules. A machine is using a lot of data to make the best possible decision and find (invisible) correlations.

What is the ‘best decision’? Well, most of the time it is looking at the past, minimizing risk or cost, mimicking human behaviour. This is where a lot of bias comes from and it makes sense.

If you want everyone to be treated equally, there is no need for a complex algorithm in the first place. The sole purpose of these algorithms is to treat every individual differently based on certain traits. Sometimes we think these traits are obvious and valid, sometimes we think these traits racist and idiotic, but a computer/A.I. system doesn’t know the difference.

A reason A.I. declines a loan:

  • People with irregular income and a poor credit history > we’re okay with this.
  • Female from Easy Kentucky above 40 with a daughter > wait, what?

The algorithm is probably right though, it is minimizing risk. And while analyzing the given data it found some correlation. This might be because the humans that historically did the job before the algorithm had a certain bias and it was trained on that data, or there actually is a bigger risk for females from East Kentucky based on historic data.

Minimizing ‘bad’ bias

So there is good and bad bias, how can we use this? Well, if you are training the loan application, give it the ‘right’ data. Train the model with historic data that has income and credit history data, but not the fields for ‘race’ and ‘gender’.

There, problem solved.

Or not? It turns out those A.I. systems are very stubborn in finding correlations. If we don’t give the system any race information, but we do give the system an address and there is a current (or historic) correlation between race and loan declines… the A.I. might secretly group together people based on where they live. There are examples of this, where certain poorer black neighbourhoods are being discriminated against/biased without the system knowing anything about these neighbourhoods or the race of the people living there.

Algorithms are bias

The algorithmic bias problem isn’t going away, it will probably become much worse. Systems are getting more (and more) data and it will find many more correlations using this data.

It is impossible to have algorithms without bias because these decision-making algorithms are bias. The whole reason they exist is to add some bias into a neutral decision.

What’s your thought on this? Send me a tweet: @royvanrijn


SAT solving: Creating a solver in Java (part 2)

SAT solving: Creating a solver in Java (part 2)

This is the second blogpost in a series about SAT solving. Today we’re going to build a simple solver in Java. Before continuing, if you don’t know what a SAT solver is, read [part one][].

The algorithm we’re going to implement is called DPLL (Davis Putnam Logemann Loveland).

Input parsing

The input we’ll accept is in DIMACS format. For now we can just skip the p-line with all the settings and just parse all the numbers. Here is an example input:

p cnf 3 4
 1  2 -3  0
 2  3  0
-2  0
-1  3  0

In Java we can parse this entire file with almost a one liner (don’t do this in production code):

        // Read a DIMACS file and turn into a list of clauses:
        final List<List<Integer>> clauses = Files.lines(Paths.get(inputFile))
                // Trim the lines:
                .map(line -> line.trim().replaceAll("\\s+", " ").trim())
                // Only parse lines ending with a 0:
                .filter(line -> line.endsWith(" 0"))
                // Turn each line into a list of integers:
                .map(line -> Arrays.stream(line
                        .substring(0, line.length() - 2)
                        .trim().split("\\s+"))
                        .map(Integer::parseInt)
                        .collect(Collectors.toList())
                ).collect(Collectors.toList());

Unit propagation

The next step in creating a (slow) SAT solver is to implement the following pseudo code:

Step 1a: Find all the unit variables

Find all the unit variables (-4 0). These are clauses that have just a single (active) variable. If a clause has just a single variable, it has to be true. So in this case we mark 4 as false.

Step 1b: Process all unit variables

Now we go over all the other clauses that contain this variable -4 or the inverse (4).

If the clause has -4 (which we now know is true), we mark this entire clause as ‘satisfied’.

If the clause contains the inverse of the variable, in this case 4, we know that particular variable will never become true, so we remove it from the list.

Lets try step 1 with the following example:

 1  4  2 -3 -6 0
 2  3  0
-2  0
-1  3  5 0
-2 -4 -5 0
-1  6  0

We have a single unit variable, -2, so we mark this variable as true. Next we apply step 1b:

Known: -2

[1  4 2 -3 -6 0] becomes: [1 4 -3 -6 0]
[2  3  0] becomes: [3 0]
[-2  0] marked true (contains -2)
[-1  3  5 0] stays the same: [-1  3  5 0]
[-2 -4 -5 0] marked true (contains -2)
[-1  6  0] stays the same: [-1  6  0]

Now we have a new unit variable, 3 0. This again can be processed:

Known: -2, 3

[1 4 -3 -6 0] becomes: [1 4 -6 0]
[3  0] marked true (contains 3)
[-2  0] marked true (contains -2)
[-1  3  5 0] marked true (contains 3)
[-2 -4 -5 0] marked true (contains -2)
[-1  6  0] stays the same: [-1  6  0]

And now we are done with the unit propagation. We are now left with two clauses that both are not a unit clause.

Step 2: Gamble on a variable

First we repeat step 1 until there are no unit clauses left. Now we need to take a gamble. In this case we have unresolved: -1, 1, 4 and -6, 6. We need to pick one of these and try it.

Let’s pick 6.

Again, we process this, if a clause contains 6 we mark it as true. If a clause contains -6 we remove that variable as alive variable.

Known: -2, 3

 1  4  -6 0 becomes: 1 4 0
-1  6  0 is marked true (contains 6)

Now we go back to step 1 and repeat.

Conflict

There are two possible ways this loop will end.

1) There are no clauses left, everything it true. In this case we have reached SAT. 2) We run into a situation that we have a conflict (!)

A conflict happens when we have a situation that can’t happen. For example when we have the following situation:

-1  0
 1 -2  0
 1  2  0

In this case we have -1 as a unit clause, we assign this variable. Now we process the following lines and what happens? We are left with:

 -2  0
  2  0

This is a conflict, we can’t have -2 AND 2. It can’t be true and false at the same time.

In the case of a conflict we backtrack back to the last decision point where we gambled. Reset everything and try a different variable.

Nothing left to gamble? UNSAT

If, at a certain point, you’ve run out of options to gamble on, we are also done. We’ve proven there is no way to assign the variables to satisfy all the clauses. In this case we can return UNSAT.

Put this into code:

If you put the above algorithm into Java code you might end up with something like this:

package com.royvanrijn.boolish;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

public class DPLLSolver {

    public static void main(String[] args) throws Exception {
        new DPLLSolver().solve("dimacs/example.cnf");
    }

    private void solve(final String inputFile) throws Exception {

        // Read a DIMACS file and turn into a list of clauses:
        final List<Clause> clauses = Files.lines(Paths.get(inputFile))
                .map(line -> line.trim().replaceAll("\\s+", " ").trim())
                .filter(line -> line.endsWith(" 0"))
                .map(Clause::new).collect(Collectors.toList());

        List<Integer> literals = new ArrayList<>();

        processDPLL(clauses, literals);

        // If we get here, we are unable to assign SAT, so we are UNSAT:
        System.out.println("Got to the end, UNSAT");
    }

    private void processDPLL(List<Clause> clauses, List<Integer> literals) {

        // Check if we have no more clauses that are unsatisfied:
        if(!clauses.stream().filter(clause -> !clause.clauseSatisfied).findAny().isPresent()) {
            // We are done, SAT!
            exitWithSAT(literals);
        }

        List<Integer> newLiterals = new ArrayList<>();

        // Step 1a: Find unit clauses:
        List<Integer> unitPropagation = findUnitClauses(clauses);

        // Step 1b: Process the unit variables (new units can be created while processing):
        while(unitPropagation.size() > 0) {

            // Remove this unit from all clauses:
            for(Integer unit : unitPropagation) {
                // Detect conflicts: We can not have both unit and -unit in the set, if there is we've hit a conflict.
                if(unitPropagation.contains(-unit)) {
                    // Undo everything we've done and return.
                    for(Integer literal : newLiterals) {
                        System.out.println("Undo unit: " + literal);
                        undoStep(clauses, literal);
                    }
                    return;
                }
                newLiterals.add(unit);
                System.out.println("Applying unit: " + unit);
                applyStep(clauses, unit);
            }
            unitPropagation.removeAll(newLiterals);

            // Look if we've created new unit clauses:
            unitPropagation.addAll(findUnitClauses(clauses));
        }

        // Get all the unassignedLiterals from the alive clauses:
        Set<Integer> unassignedLiterals = clauses.stream()
                .filter(clause -> !clause.clauseSatisfied)
                .flatMap(clause -> clause.unassignedLiterals.stream()).collect(Collectors.toSet());

        for(Integer decisionLiteral : unassignedLiterals) {
            System.out.println("Gambling/deciding on: " + decisionLiteral);
            applyStep(clauses, decisionLiteral);

            // Go deeper with a fresh list:
            List<Integer> deeperAssignedLiterals = new ArrayList();
            deeperAssignedLiterals.addAll(literals);
            deeperAssignedLiterals.addAll(newLiterals);
            deeperAssignedLiterals.add(decisionLiteral);

            processDPLL(clauses, deeperAssignedLiterals);

            System.out.println("Undo gambling: " + decisionLiteral);
            undoStep(clauses, decisionLiteral);
        }

        // Undo all we've done this step:
        for(Integer literal : newLiterals) {
            System.out.println("Undo units: " + literal);
            undoStep(clauses, literal);
        }
    }

    /**
     * When applying a step, keep all the dead literals (variables) so we can undo.
     *
     * @param clauses
     * @param literal
     */
    private void applyStep(final List<Clause> clauses, final Integer literal) {
        for(Clause clause : clauses) {
            if(!clause.clauseSatisfied) {
                if(clause.unassignedLiterals.contains(literal)) {
                    clause.clauseSatisfied = true;
                } else if(clause.unassignedLiterals.contains(-literal)) {
                    clause.unassignedLiterals.remove((Integer) (-literal));
                    clause.deadLiterals.add(-literal);
                }
            }
        }
    }

    /**
     * Because we are backtracking we need to be able to undo all the steps in a clause, so we keep all the information
     *
     * @param clauses
     * @param literal
     */
    private void undoStep(final List<Clause> clauses, final Integer literal) {
        for(Clause clause : clauses) {
            if(clause.clauseSatisfied && clause.unassignedLiterals.contains(literal)) {
                clause.clauseSatisfied = false;
            }
            if(clause.deadLiterals.contains(-literal)) {
                clause.deadLiterals.remove((Integer) (-literal));
                clause.unassignedLiterals.add(-literal);
            }
        }
    }

    private List<Integer> findUnitClauses(final List<Clause> clauses) {
        List<Integer> unitPropagation = new ArrayList<>();
        // Check if there are unit clauses:
        for(Clause clause : clauses) {
            if(clause.isUnitClause()) {
                unitPropagation.add(clause.unassignedLiterals.get(0));
            }
        }
        return unitPropagation;
    }

    private void exitWithSAT(final List<Integer> literals) {
        // We are done:
        System.out.println("SAT");

        // Sort the output as absolute values.
        Collections.sort(literals, Comparator.comparingInt(Math::abs));

        // TODO: We might not list all the input variables here, some are not needed and can be + or -.

        // And print:
        System.out.println(literals.stream().map(n -> String.valueOf(n)).collect(Collectors.joining(" ")) + " 0");

        // Bye bye.
        System.exit(1);
    }

    public class Clause {

        private List<Integer> unassignedLiterals = new ArrayList<>();
        private List<Integer> deadLiterals = new ArrayList<>();
        private boolean clauseSatisfied = false;

        private Clause(String inputLine) {
            unassignedLiterals.addAll(
                    Arrays.stream(inputLine
                            .substring(0, inputLine.length() - 2)
                            .trim().split("\\s+"))
                            .map(Integer::parseInt)
                            .collect(Collectors.toList()));
        }

        boolean isUnitClause() {
            return !clauseSatisfied && unassignedLiterals.size() == 1;
        }
    }
}

This is all. This algorithm can solve any problem that can be turned into a SAT problem, which are a lot of mathematical problems.

DPPL isn’t the fastest algorithm, a lot of improvements can be made (part 3?). For example we can learn new clauses during analysis, and instead of backtracking to the last decision moment, sometimes you can backtrack to a much earlier decision moment, making the resolution much faster.

But the basic algorithm to solve SAT, is very simple indeed.

part one


SAT solving: Introduction to SAT (part 1)

SAT solving: Introduction to SAT (part 1)

Most software developers have never heard about SAT solvers, but they are amazingly powerful and the algorithms behind them are actually very easy to understand. The whole concept blew my mind when I learned about how they worked. This will be the first post in a series about SAT solving where we’ll end up building a simple solver in Java later on.

In this first part of the series we’ll cover:

  • Look at what SAT is
  • Explain the SAT DIMACS format
  • Solve a puzzle: Peaceable Queens

Peaceable Queen solution for N=8

What is SAT?

SAT is short for ‘satisfiability’, what people mean when they say SAT is: Boolean satisfiability problem.

It turns out you can write a lot of ‘problems’ in a specific way as a special boolean formula. These problems use boolean variables that can be either true or false. When a variable is assigned true or false, it is called a literal.

An example of a boolean expression:

(A or B or ~C) and (B or C) and (~B) and (~A or C)

Conjunctive normal form (CNF)

The statement above is written in a particular way, it is called the conjunctive normal form (or CNF). All boolean statements can be rewritten/transformed into this form.

First we’ll need to learn some more terminology. The variables have a label here, for example A. There is also the option to have a NOT A, this is written as ~A.

The line above can be broken up into four pieces:

(A OR B OR ~C)  AND
(B OR C)        AND
(~B)            AND
(~A OR C)

Each line is called a ‘clause’. Those clauses are connected together using AND statements. A clause can only contain variables (or negated variables) joined together by OR.

Because each clause will have OR between the variables and the end of the clause is always an AND statement, those things can be removed from the statement, turning it into:

 A    B   ~C
 B    C
~B
~A    C

DIMACS format

If we do one more step you’ll end up with a format called DIMACS, which is supported by almost all SAT solvers. The last step is to replace the name of variable A with 1 and B becomes 2 etc. The NOT statement is just writing the number negative, so ~C becomes -3.

Now add a 0 to the end of each line (as separator) and add a header which explains the amount of variables (= 3) and the amount of clauses (= 4) and you get:

p cnf 3 4
 1  2 -3  0
 2  3  0
-2  0
-1  3  0

This is a valid input file for almost all SAT solvers. You can run this for example in minisat:

$ minisat input.cnf output.cnf
============================[ Problem Statistics ]=============================
|                                                                             |
|  Number of variables:             3                                         |
|  Number of clauses:               2                                         |
|  Parse time:                   0.00 s                                       |
|  Simplification time:          0.00 s                                       |
|                                                                             |
============================[ Search Statistics ]==============================
| Conflicts |          ORIGINAL         |          LEARNT          | Progress |
|           |    Vars  Clauses Literals |    Limit  Clauses Lit/Cl |          |
===============================================================================
===============================================================================
restarts              : 1
conflicts             : 0              (0 /sec)
decisions             : 1              (0.00 % random) (405 /sec)
propagations          : 3              (1214 /sec)
conflict literals     : 0              ( nan % deleted)
Memory used           : 0.17 MB
CPU time              : 0.002471 s

SATISFIABLE

And print the output:

$ cat output.cnf
SAT
1 -2 3 0

Now we can see what a SAT solver actually does. It takes a boolean expression and tries to find a ‘solution’. It tries to find a particular combination of literals so all the clauses are true. If it is able to find one, it stops and returns SAT. When it is unable to find a valid assignment it returns UNSAT, the problem can’t be solved.

Most modern SAT solvers will not only return UNSAT, they will also return “proof” of the UNSAT, a listing of all the clauses that conflict with eachother and cause the UNSAT. This is very powerful and can be used to verify the correctness of the solvers.

In our case we have a valid SAT result: 1 -2 -3.

When we assign A=true, B=false, C=false we satisfy our entire boolean expression.

How can we use this?

The example above is very abstract with A’s and B’s. Lets look at some other problems that can be solved by SAT solvers.

A lot of ‘problems’ can be turned into big CNF statements which means a lot of problems can be solved by a general SAT solver! Which is kind of amazing to me, translate a hard problem into SAT/CNF and a (rather simple) general purpose solver can solve it!

Calling SAT solvers ‘rather simple’ isn’t a mistake. Sure, some implementations are very complicated pieces of finely tuned optimized software. But the algorithms and general ideas behind SAT solving are surprisingly simple. In the next coming blogpost(s), once I write them, I’ll show you how to make one in Java.

Most tutorials use a SAT solver to solve Sudoku puzzles. It is an easy problem to understand and it shows the power of SAT. It involves translating a Sudoku puzzle and all its rules into one big CNF file. Next the SAT solver will calculate a solution.

Some other (random) things SAT solvers can be used for:

  • Sudoku
  • N-queens
  • Hardware/software verification
  • Scheduling (sport events)
  • Cryptanalysis
  • Routing/planning problems

Peaceable queens problem

Instead of doing what most tutorials do (writing a boolean expression for Sudoku’s) I want to do something different.

The challenge: Find solutions for a puzzle from a recent Numberphile video: Peaceable queens.

The problem is:

Given a N x N chess board, what is the highest amount of black and white queens you can place so they don’t attack each other?

How can we encode such a problem into one big DIMACS file?

A chess board

First we need a way to describe our board. It is a chess board and can hold queens either white or black. So I decided to encode this using a variable for each square, first NxN white queens, next NxN black queens.

WHITE:
 1  2  3
 4  5  6
 7  8  9

BLACK:
 10 11 12
 13 14 15
 16 17 19

We don’t have to put anything in our DIMACS file yet, but the SAT output will contain these variables set to TRUE or FALSE.

White or black pieces

Now it is time to encode all the ‘rules’ of this puzzle. First a very simple rule: If a square has a white queen it CAN’T have a black queen.

Let’s take the first square, top left. If 1 is TRUE we have a white queen, if 10 is TRUE we have a black queen there. So we want either 1 or 10, not both. How do we encode a rule for this in our SAT input?

-1 -10 0

Simple right?

How does this work? For this clause to be TRUE we must have ‘NOT 1’ or ‘NOT 10’, so either one of them or both must be FALSE. Excellent!

Rows, columns, diagonals

To have a valid solution we must add a lot more rules, for example a row can only have either a white queen or black queen or none.

How do we do this? Let’s look at row 1,2,3 / 10,11,12 (the top row).

First we’re going to introduce two new variables, I’ll just continue using free numbers, 20 and 21. Those will represent the top row for white and black.

Encode white row as 20:
-1 20 0
-2 20 0
-3 20 0

Encode black row as 21:
-10 21 0
-11 21 0
-12 21 0

Let’s analyse this. The first clause says we must have NOT 1 or the white row 20 is TRUE. Next we state the same for NOT 2 and NOT 3. So if we have a white piece on row 1 2 3 means 20 will be TRUE. The same is done for black, if there is a black piece on the top row 21 will be TRUE.

Now we can encode the final rule for the top row just like we did with the white/black queen on the same square:

-20 -21 0

This can be done for each row, column and diagonal.

As you can imagine, this will quickly become too large to write manually. So to enumerate all possibilities I wrote a piece of Java code to generate a DIMACS file for me instead.

This happens a lot when using SAT solvers, most of the time you’ll want to create a piece of software to output all the rules in DIMACS for a solver to solve.

At least N-queens

If we run the SAT solver with the generated file above we encounter a small problem. It will solve very quickly by placing NO queens at all. Very ‘peaceable’ indeed, no queens are attacking.

We must tell the solver that we want to have a certain number of queens set to true. This turned out to be harder than I thought. There are algorithms online that do at most N booleans. I decided to implement the LTseq method from this scientific paper.

Having rules like this quickly explodes the amount of clauses needed. But LTseq seemed to be the best one.

This is what I’ve ended up with:

    /**
     * LTseq from: http://www.cs.toronto.edu/~fbacchus/csc2512/at_most_k.pdf
     */
    private int ltSeq(final int[] x, final int k, int nextFreeVariable, boolean state) {

        // Build registry table:
        final int[][] s = new int[x.length-1][k];
        for(int i = 0; i < x.length-1; i++) {
            for(int j = 0; j < k; j++) {
                s[i][j] = nextFreeVariable++;
            }
        }

        //(¬x1 ∨ s1,1)
        writer.println((state?-1:1)*x[0]+" "+s[0][0]+" 0");
        for(int j = 1; j<k;j++) {
            //(¬s1,j )
            writer.println(-s[0][j]+" 0");
        }
        for(int i = 1; i < x.length - 1; i++) {
            //(¬xi ∨ si,1)
            //(¬si−1,1 ∨ si,1)
            writer.println((state?-1:1)*x[i]+" "+s[i][0]+" 0");
            writer.println(-s[i-1][0]+" "+s[i][0]+" 0");
            for(int j = 1; j<k;j++) {
                //(¬xi ∨ ¬si−1,j−1 ∨ si,j )
                //(¬si−1,j ∨ si,j )
                writer.println((state?-1:1)*x[i]+" " + -s[i-1][j-1]+" "+s[i][j]+" 0");
                writer.println(-s[i-1][j]+" "+s[i][j]+" 0");
            }
            //¬xi ∨ ¬si−1,k)
            writer.println((state?-1:1)*x[i]+" "+-s[i-1][k-1]+" 0");
        }
        //(¬xn ∨ ¬sn−1,k)
        writer.println((state?-1:1)*x[x.length-1]+" "+-s[x.length-2][k-1]+" 0");
        return nextFreeVariable;
    }

How can we use at most N for this puzzle? Well in case of N=10 we want to have both white and black to have at least 14 queens. So I switched at least 14 of white and black squares TRUE to be at most (N*N - 14) of white and black squares FALSE.

This is still not very good because with (NxN - 14) we have a very large k, thus making a LOT of clauses. I have the feeling this can be done much better, but up to now I haven’t found a proper way. Perhaps forcing the sequential counter to overflow (instead of protecting it)? This didn’t seem to work for me. If you have SAT experience and know more about encoding problems, let me know!

I ended up doing the thing that works:

        // Make sure we have at least k pieces for white and black:
        int freeVariable = (N*N * 2) + 1;
        freeVar = ltSeq(whitePieces, N*N - k, freeVar, false);
        freeVar = ltSeq(blackPieces, N*N - k, freeVar, false);

        // ... encode rows, diagonals, columns ...

And it worked like a charm. I’m now able to ‘solve’ N=10 in under two seconds using modern SAT solver glucose. When I generate my ‘rules’ it comes down to about a staggering 17336 variables in 34518 clauses (far from optimal?).

But glucose is able to find a valid solution for N=10, k=14 in 1.2 seconds.

Below is the output where I’ve omitted most variables, we are only interested in the first 200 (10 x 10 x 2) that represent the board:

-1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 21 22 23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36 -37 -38 -39 -40 -41 -42 -43 -44 -45 -46 -47 -48 -49 -50 -51 -52 -53 -54 -55 -56 -57 -58 -59 -60 -61 -62 63 -64 -65 -66 -67 -68 -69 -70 -71 72 -73 74 -75 -76 -77 78 -79 -80 81 -82 83 84 -85 -86 -87 88 -89 -90 -91 92 93 -94 -95 -96 -97 98 -99 -100 -101 -102 -103 -104 -105 106 107 -108 -109 110 -111 -112 -113 -114 115 116 117 -118 119 -120 -121 -122 -123 -124 -125 -126 -127 -128 -129 -130 -131 -132 -133 -134 135 -136 137 -138 -139 140 -141 -142 -143 -144 -145 146 -147 -148 149 150 -151 -152 -153 -154 -155 -156 -157 -158 159 -160 -161 -162 -163 -164 -165 -166 -167 -168 -169 -170 -171 -172 -173 -174 -175 -176 -177 -178 -179 -180 -181 -182 -183 -184 -185 -186 -187 -188 -189 -190 -191 -192 -193 -194 -195 -196 -197 -198 -199 -200 ..... many more

And if you change this back into a chess board we can see valid solution for N=10 with 14 queens each!

. . W . . . . . W . 
. . W . . . . W . W 
. . W . . . W . W W 
. . . . . . . W W . 
. B . B . . . . . . 
B B . . B . . . . . 
B B . B . . . . . . 
. . . . . . . W W W 
. B . . B B . . . . 
B . . B B . . . . . 

I’ve uploaded all the code for this series to GitHub and called it: Boolshit

You can find the code to generate the Peaceable Queens puzzle here.

I hope this gives you an idea on how powerful SAT solvers are and how you can encode a problem into DIMACS format.

In the next blogpost we’ll write an actual SAT solver from scratch in Java! Although it won’t be a very fast one…


My worst public speaking experience...

My worst public speaking experience...

Last week I was invited to the Rabobank (a Dutch bank), where the bank and the Utrecht JUG hosted a small two day conference.

The first day was about clean code and the second day was about architecture.

The main attraction of this conference: Robert C. Martin, also known as Uncle Bob. He is one of the founders of the Agile manifesto and wrote numerous very good books on topics like ‘Clean Code’ and ‘Clean Architecture’. He’s also the main advocate for the SOLID design principles.

This presentation of mine… turned out to be my worst public speaking experience yet.

One thing I want to make clear though: I absolutely don’t want to discredit the Utrecht JUG or Rabobank in any way, they are doing awesome things for the community. I just want to share my personal experience. Also: Robert C. Martin (Uncle Bob) is a great speaker and writer, his talks are inspirational, entertaining and just very very good.

Breakout sessions

I was asked to present one of the breakout session. Those sessions had a rather unique form:

Two speakers are presenting at the same time on the same stage. The speakers and the entire audience had to wear a silent disco-headset. The audience could switch to whichever side they wanted to listen to. Technically this worked perfectly (kudos to the organisers), I have never seen this kind of setup work as well as it did.

The only other place I’ve seen headsets at a conference was in the overflow room of JavaZone. The overflow room there has a huge screen with all presentations and using a headset you can switch to whichever talk you want, great!

Initially this setup didn’t scare me, I’m not an anxious person, it sounded novel and quite frankly fun/entertaining! I did ask two fellow presenters whom presented the day before about the setup, they said it was a bit weird at first… but they got used to it.

Nobody prepared me for what followed though, my worst speaking experience to date (by far).

The fever

The first complication of the day: fever.

I woke up with a splitting headache. My kids had been ill for a couple of days and now it was my turn. Mucus filled sinuses and a bit of fever, I’ll spare the details.

Surely nothing a couple of painkillers couldn’t solve!

The censorship

When I was setting up my laptop before the presentation a colleague of mine made a joke. A joke about his height and the small wall which was being set up on stage. This wall divided the stage into the two parts for the breakout sessions.

One of the organisers (again: who did a great job, it isn’t easy to organize such an event, I love the Utrecht JUGs effort!) came to me and gave me a firm and surprising warning:

“Roy, one thing, I have to warn you: Don’t mention the wall. Don’t mention any wall, not this wall, not the Trump-wall. Don’t even say the word ‘wall’ in your presentation.

Don’t mention Trump or guns or anything political please. Just don’t joke about it. This was one of the requirements from Uncle Bob. He is very sensitive and clear about this, no mentions or jokes about his political views, we don’t want to upset him.

If you ignore this advice, we’ll switch all the headsets to the other presenter and you are done.”

This… was very suprising to me. Uncle Bob is one of the most outspoken people I have on my Twitter timeline. He often gets into public discussions making his views very clear, engaging in debate, for example:

And (surprisingly) this:

I actually wanted to start my talk with a small joke about the wall to break the ice, to point out the irony of having a wall on stage at a conference named after Uncle Bob. Because I’ve seen people attacking him, saying he’s a dumb Trump supporter.

It turns out other breakout-session presenters got a similar warning before their talk, it was not just me.

The bubble

Finally.

It was time…

I put on the headset and microphone and waited behind a closed door. The announcer called out my name and that of other presenter, we both made a grand entrance. Him entering the stage from the left, me from the right. We met in the middle for a friendly handshake and…

Ready to rumble!

… silence …

… just a deafening silence.

Normally you hear noise, people clap, cheer or laugh or… at least they breath. Now there was one big nothing. With the headset on I felt so alone, inside my little bubble. It was like recording a webinar or podcast, only my own voice, heavy breathing and my headache. Nothing else.

This was something I just couldn’t cope with. Whenever I made a joke, nothing, just the echo in my sinuses. 400+ people wearing headphones looking at me apathetically. Some of them (with blue-LED headphones) to the stage next to me, some (with green-LED headphones) looking directly at me… still hearing nothing. There was a complete disconnect with the audience…

My style of presenting is entirely based around the audience, around instant feedback and interaction. I want the audience to have a good time, to be entertained and learn something new at the same time. I’m not someone that (re-)plays a recording, throwing informantion into a void.

I just wanted to crawl into a corner and cry.

The hangover…

I’m still not sure what caused this horrible feeling, maybe it was the censorship, maybe it was the headphones/audience disconnect, maybe it was the fever, my exploding sinuses and the numbing painkillers… probably a combination of all those things.

It was a first for me in many ways:

I never did a headphone/silent disco-style presentation… and I’m not sure I want to do this again.

It was also the first time I experienced censorship at a meetup; being warned that some topics and/or jokes were off the table.

A couple of friends warned me: “Are you sure you want to connect your name to Uncle Bob, speaking at his conference”.

I thought about it back then and accepted the invite: Just because I’m speaking at an event bearing his (nick-) name doesn’t mean I agree with him or his political/world views. I’m free to have my own view and opinions.

Now that I know about the weird censorship, I’m not sure I was right.


Solving a word search puzzle

Solving a word search puzzle

In the previous post I showed a nice snippet/trick at the bottom of the post to find all the neighbors in a 2D array.

Last week I used this snippet to solve a word search puzzle a colleague created for us as a “Back to work in 2019”-challenge:

The word search puzzle

(Note: Some fellow developer colleagues think that solving the puzzle with code is unfair… heh. really?!)

Reading the lexicon

Here is the complete code:

First we’ll need to read in all the possible words we’re looking for. And using the new Java streams this is very easy. Just download one of the many online word-lists and do the following:

    public static void main(String[] args) throws Exception {

        // Store the words we find here:
        Set<String> foundWords = new HashSet<>();

        // Read in the lexicon, the list of possible words:
        Set<String> lexicon = Files.readAllLines(FileSystems.getDefault().getPath(("Lexicon.txt"))) 
                .stream()                        // Open the file as a stream
                .map(line -> line.toUpperCase()) // Convert all the lines (one word per line) to uppercase
                .collect(Collectors.toSet());    // Store this in a list.

It was never easier in Java to do File IO and manipulate collections. Next I embedded the entire puzzle and turned it into an array of Strings.

        // The puzzle: (yeah, hardcoded, sue me.)
        String[] lines = ("TZKRAMONHSMARIONRDBU\n" +
                          "ARNOSTIASSTUNODJEOFN\n" +
                          "FMAMLAPCNNTPIKETYKXA\n" +
                          "UDHBISMUHBALTIGLCCSK\n" +
                          "HKLANTGERICHTEBBOAER\n" +
                          "YCHAVFCONTEAMSHUFFLE\n" +
                          "MIPXRETHNWSLIISIAEIS\n" +
                          "ZRSEKANFEIEUWUTLBQGW\n" +
                          "RTNPCIHBNLBRDOEDRGAO\n" +
                          "UANRIANAEMLOKLFSIETR\n" +
                          "UPEDMDGCODZUWEATCWCB\n" +
                          "TMOISREKIURBEGNREKGX\n" +
                          "UASROCSRPDWIUNPADOXJ\n" +
                          "JGRFTKIXMLENJRMAGDRU\n" +
                          "CNLBLMRSAAKNYFATMGCS\n" +
                          "GEOOYBAVKNNETXCKXOPT\n" +
                          "ZTVRUNLPVOENIREVLOWU\n" +
                          "COHRDBONSRHVEUDMURCS\n" +
                          "QIBEOVPAPPFACTORYDJO\n" +
                          "MRRLNYTRAPNALGCARIJB\n" +
                          "DIUEGIPHYJEROENAGRUK\n" +
                          "KSCNADINEELTHRANABIK")
                .split("\n");

Finding all the words

Finally we need to traverse all the possible combinations a word can be made and check against the Set of target words. I’m doing this the dumbest way possible.

First I go over each possible start location by enumerating all x/y combinations:

        for(int y = 0; y < lines.length; y++) {
            for(int x = 0; x < lines[0].length(); x++) {

Next I check each direction using the neighbor algorithm from the previous post.

                for(int direction = 0; direction < 9; direction++) {
                    if(direction == 4) continue; // direction 4 is staying still, invalid.

Now we start building the possible word, using two new pointers (tx and ty):

                    int ty = y, tx = x;                      // Create two new pointers
                    String word = "" + lines[ty].charAt(tx); // Start with the initial character

While we are within the bounds of the puzzle we must travel in the current ‘direction’. This is done by adding the direction offset (from previous post) to the tx and ty pointers.

If the word in-progress matches one we’re searching for, add it to the found words list!

                    while(tx > 0 && tx < lines[ty].length() - 1 && ty > 0 &&  ty < lines.length - 1) {

                        // Move in the direction:
                        ty += ((direction%3) - 1);
                        tx += ((direction/3) - 1);

                        // Update the word:
                        word += lines[ty].charAt(tx));

                        // Check against the lexicon:
                        if(lexicon.contains(word)) {

                            // Store the words we found (for later reference):
                            foundWords.add(word);
                        }
                    }

Finally let’s close everything off, for developers with OCD like me:

                }
            }
        }
        // Print the words:
        foundWords.stream().sorted().forEach(System.out::println);
      }

This prints the words, sorted, just as we want. Q.E.D..

Improvements

The way we now iterate over all the possible word hiding places is very very dumb.

There are some obvious improvements to be made here, for example one could place the entire lexicon in a tree-like structure instead of a set of words and stop iterating if the certain branch doesn’t exist.

However, for this puzzle, this challenge, the speed it runs at is good enough!

Entire code:

You can download the complete listing here: PuzzleSolver.java


The longest maze/snake

The longest maze/snake

An amazing website I keep running into (especially through Hacker News) is: Red Blob Games.

It has a lot of amazing algorithms explained using interactive Javascript examples. For example take a look at how Amit explains Hexagonal grids and A* pathfinding. The interactive demo’s make it easy to grasp all these fun algorithms and implement them yourself.

Pathfinding for Tower Defense

Last week though I was reading this tutorial, Pathfinding for Tower Defense.

He explains a method for creating a single vector/flow field for game AI’s to follow. This allows a single calculation to be used by a lot of AI bots, which is great for a Tower Defense game.

A new game…

However, when I was playing with the bottom Javascript example (after pressing ‘Start animation’) I found myself playing a new little game of my own. There is a box, 20x10 where you can place walls, also you are able to drag/move the start position around.

The goal:

“What is the longest path possible? / What is the highest number I can reach?”

After I found out I can move the start position around, I came up with the following configuration:

A solution with score of 113

The maze is 113 long… but it turns out this is far from optimal. After coding up a little solver and playing around I found the following configuration:

A solution with score of 124

This is a solution that goes up to 124 (near the top left corner). I’ve also found one later with a score of 125.

It seems that diagonals are the best way to pack the longest maze into there, but the problem is, one diagonal cuts the field in two smaller parts. Zig-zagging works great, but there is no ‘easiest’ way to zig-zag.

It doesn’t seem to me that there is a trivial solution? I haven’t found one at least, is there? Are there simple optimal patterns for given boxes, NxN?

Searching for a solution seems to be NP-hard and even 20x10 is out of the question, the amount of possible configurations of walls and starting positions is huge and grows exponentially. Coding up a solver is pretty easy though, using some simple heuristics and some random searches I got my 125 solution.

Maybe this would be a fun puzzle for a future AZsPCs contest…?

Can you get a better configuration than 125? I’d love to know.

Neighbors algorithm

When I wrote a score checker for the puzzle above I needed a way to get the neighbors in an 2D array. I’ve gotten used to code 2D mazes/puzzles and I always use the following way to calculate all the neighbors.

I find this to be easier and more readable that the alternatives, going over all the -1/+1 combinations or having two nested loops.

// We have a 2D maze:
int[][] maze = new int[10][20];

// And a certain location, row and column:
int row = 8;
int col = 10;

// List all neighbors:
for(int direction = 0; direction < 9; direction++) {
    if(direction == 4) continue; // Skip 4, this is ourself.
    
    int n_row = row + ((direction%3) - 1); // Neighbor row
    int n_col = col + ((direction/3) - 1); // Neighbor column

    // Check the bounds:
    if(n_row >= 0 && n_row < maze.length && n_col >= 0 && n_col < maze[0].length) {
        
        // A valid neighbor:
        System.out.println("Neighbor: " + n_row + "," + n_col + ": " + maze[n_row][n_col]);
    }
}

How does this work?

First we list all directions with a single integer, 0 to 9, and we’ll need to skip the middle number four, this points to ourself.

List directions

From this single direction we’re able to easily calculate both the new row value (n_row) and the new col value (n_col). To do this we’ll need to divide by three and use modulo three.

Neighbor row value:

To find the new row value we start our by using modulo 3. The only thing left to do is to subtract 1 and we’ll get the new row value for each direction:

int n_row = row + ((direction%3) - 1);

row + (directions%3) - 1

Neighbor col value:

The same thing can be done for the col value. Instead of using modulo 3, we’ll be using divide by 3. And the same as with the row value, we’ll also need to subtract 1 to get the following new column values:

int n_col = col + ((direction/3) - 1);

col + (directions/3) - 1

And there you go, list all neighbors in a 2D array without using two nested loops and dirty checks.

Happy coding!


Happy New Year: 2019

Happy New Year: 2019

First of all, best wishes for 2019 from me.

Time for me to reflect on the last couple of months.

Public speaking

Last year has been a crazy busy year for me. I’ve been to and spoken at to J-Spring, J-Fall, Devoxx Belgium, Devoxx Poland and JavaOne… errr… Oracle CodeOne on various topics. From quantum computing to software architecture.

Here is a list of all my conference talks.

RotterdamJUG

I’m a big fan of sharing knowledge and getting people together to have fun. This is why I’ve decided to create a new JUG (Java User Group) this year in the city of Rotterdam, the RotterdamJUG. In November we had our first meeting and I’ve already got more meetups planned.

Java Champion

The biggest achievement this year is probably being named an Oracle Java Champion. There are no more than 300 Java Champions in the world and it is a great honor to be added to this group.

…. 2019

So what’s next for 2019? I’m going to continue with the RotterdamJUG, we’ve already got a Kotlin-workshop planned for this month and I’m looking for a venue for a February meetup (anyone?).

I’m also going to go back to math and puzzles, I’ve got some idea’s planned and some tricks/algorithms to explain, more on that in the coming days/weeks hopefully!


Part 2: Native microservice in GraalVM

Part 2: Native microservice in GraalVM

Last week I posted Part 1 of this series of blogposts about GraalVM.

We looked at GraalVM and what it can do. We dove into the native-image command and transformed a simple HelloWorld application into a native application (running in Docker).

This time I want to go beyond “Hello World” and build something useful (despite all the limitations listed below). A CRUD microservice with REST API and database access.

TLDR; If you’re just intersted in the end result, go right to the results

Limitations

So what are some of the limitations that GraalVM currently has? (using version 1.0.0 RC6 at time of writing)

Well, the Java VM is a very complete and dynamic system able to handle a lot of dynamic changes. This is something a native application can’t do as easily. GraalVM needs to analyse your application up front and discover all these things. Therefor, things like reflection and dynamic classloading are very hard to do (but not impossible).

To ‘emulate’ a dynamic running JVM the GraalVM project is shipped with Substrate VM.

Substrate VM is a framework that allows ahead-of-time (AOT) compilation of Java applications under closed-world assumption into executable images or shared objects (ELF-64 or 64-bit Mach-O).

The Java VM for example has a garbage collector, when you eliminate the JVM, you’ll still need to free your objects. This is something Substrate VM (written in Java!) does for you.

To read about the limitations of Substrate VM, look at this LIMITATIONS.md.

Spring Boot

We want to do more than just ‘HelloWorld’, how about an entire microservice?

If you talk about microservices in Java, most people will immediately say: Spring Boot. While you can certainly discuss the micro-part, it is by far the most popular way of writing (enterprise) Java applications at the moment. The problem is that most Spring Boot applications quickly grow, having Docker images of 600+ mb and runtime memory usage of 250+ mb is to be expected.

So it seems this is a perfect candidate to turn into a native application.

But there is some instant bad news: It won’t work

At least, at this moment in time. The developers of Spring Boot are working very hard with the developers of GraalVM to fix all the problems. A lot of work has already been done, you can check out the progress in this Spring issue.

Micronaut.io

A framework that also covers the entire spectrum and does work with GraalVM is micronaut.io. If you want something that works out of the box, check out their entire stack.

But I’d like to do it enirely myself, find the pitfalls and learn about the limitations of GraalVM at the moment. This is very useful to understand what you can and can’t do. I’m going to build my own GraalVM stack!

Web alternative: SparkJava

Instead of turning to Spring Boot or micronaut, let’s keep our application really micro and use something else. Spark Framework is a small web framework. And it works like a charm using native-image.

First I created a simple Maven project and to use the native-image command I needed all the Maven dependencies as a JAR file on the class path after compilation. To have this I added the following plugin to the pom.xml:

<!-- Make all the JAR files go into the output target/lib -->
<plugin>
   <groupId>org.apache.maven.plugins</groupId>
   <artifactId>maven-dependency-plugin</artifactId>
   <executions>
      <execution>
         <id>copy-dependencies</id>
         <phase>prepare-package</phase>
         <goals>
            <goal>copy-dependencies</goal>
         </goals>
         <configuration>
            <outputDirectory>${project.build.directory}/lib</outputDirectory>
            <overWriteReleases>false</overWriteReleases>
            <overWriteSnapshots>false</overWriteSnapshots>
            <overWriteIfNewer>true</overWriteIfNewer>
            </configuration>
         </execution>
    </executions>
</plugin>

Next I added the following dependency:

<dependency>
   <groupId>com.sparkjava</groupId>
   <artifactId>spark-core</artifactId>
   <version>2.7.2</version>
</dependency>

Now we can write our code and run the HelloWorld web application:

import static spark.Spark.*;

public class HelloWorld {
    public static void main(String[] args) {
        get("/hello", (req, res) -> "Hello World");
    }
}

Building everything is the same as in Part 1.

There are two differences though. The base image can no longer be FROM scratch because we need access to networking. Second, we need to expose the port of the web application to the outside using EXPOSE 4567.

Also we need to add the following option to native-image:

-H:+ReportUnsupportedElementsAtRuntime

This option eliminates some problems during the analysis phase out of the way.

Running this Dockerfile results in a “Hello World” in the browser at http://localhost:4567/hello. Using just 4 mb of runtime memory (!).

Dependency Injection: Google Guice

Another big problem at the moment using GraalVM is trying to use dependency injection. First I tried to use Google Guice. It is marketed as a ‘low overhead’ dependency injection framework. When I fired up the native-image command I got the following exception (amongst many others):

Exception in thread "main" java.lang.AssertionError: java.lang.NoSuchMethodException: java.lang.Integer.parseInt(java.lang.String)
  at java.lang.Throwable.<init>(Throwable.java:265)
  at java.lang.Error.<init>(Error.java:70)
  at java.lang.AssertionError.<init>(AssertionError.java:58)
  at java.lang.AssertionError.<init>(AssertionError.java:74)
  at com.google.inject.internal.TypeConverterBindingProcessor.convertToPrimitiveType(TypeConverterBindingProcessor.java:130)
  at com.google.inject.internal.TypeConverterBindingProcessor.prepareBuiltInConverters(TypeConverterBindingProcessor.java:46)
  at com.google.inject.internal.InjectorShell$Builder.build(InjectorShell.java:152)
  at com.google.inject.internal.InternalInjectorCreator.build(InternalInjectorCreator.java:104)
  at com.google.inject.Guice.createInjector(Guice.java:96)
  at com.google.inject.Guice.createInjector(Guice.java:73)
  at com.google.inject.Guice.createInjector(Guice.java:62)
  at com.royvanrijn.graal.Main.<init>(Main.java:39)
  at com.royvanrijn.graal.Main.main(Main.java:52)
  at com.oracle.svm.core.JavaMainWrapper.run(JavaMainWrapper.java:163)

It seems that Google Guice internally uses a way to call Integer.parseInt using reflection, but GraalVM doesn’t understand this. But luckely, we can help GraalVM a bit.

To fix this first problem I added the following file to my project:

[
  {
    "name" : "java.lang.Class",
    "allDeclaredConstructors" : true,
    "allPublicConstructors" : true,
    "allDeclaredMethods" : true,
    "allPublicMethods" : true
  },
  {
    "name" : "java.lang.Integer",
    "methods" : [
      { "name" : "parseInt", "parameterTypes" : ["java.lang.String"]}
    ]
  },
  {
    "name" : "java.lang.Long",
    "methods" : [
      { "name" : "parseLong", "parameterTypes" : ["java.lang.String"]}
    ]
  }
  ... etc ...

And during the build of native-image I pass the following option:

-H:ReflectionConfigurationFiles=src/main/resources/graal_config.json

Now we have instructed Substrate VM/GraalVM that our application will do a reflection lookup to Integer.parseInt (amongst other calls). It now understands this and loads everything.

For some reason though, for each dependency I kept getting the following exception:

Could not find a suitable constructor in com.royvanrijn.graal.domain.UserRepositoryImpl. Classes must have either one (and only one) constructor annotated with @Inject or a zero-argument constructor that is not private.
  at com.royvanrijn.graal.domain.UserRepositoryImpl.class(Unknown Source)
  at java.lang.Throwable.<init>(Throwable.java:250)

The application works great running it from java but not after using native-image. Time for something different!

Dependency Injection: Dagger 2

Instead of Google Guice or Spring I decided to go with another framework: Dagger 2

This framework has one big advantage over all the others: It works compile-time.

Sure, setting it up takes a little bit more time. You’ll need to include a Maven plugin that does all the magic during compilation. But it is a perfect solution (currently) for GraalVM’s native-image. All the injection-magic is done during compilation, so when running the application everything is already nicely wired up and static.

Database access (Hibernate/Oracle)

Finally, to complete my CRUD application I tried to access our Oracle database. GraalVM and the database are both created and maintained by Oracle so I hoped this would work out of the box…. but (spoiler): It didn’t.

The main problem here is the code in Oracle’s JDBC driver, this turned out to be a very hard thing to get working, this took about an entire day!

First off, there are a lot of static initializer blocks and some of those are starting Threads. This is something the SubstrateVM’s analyzer can’t handle (again: see LIMITATIONS.md).

It was throwing errors like:

Error: com.oracle.graal.pointsto.constraints.UnsupportedFeatureException: Detected a started Thread in the image heap. Threads running in the image generator are no longer running at image run time. The object was probably created by a class initializer and is reachable from a static field. By default, all class initialization is done during native image building.You can manually delay class initialization to image run time by using the option --delay-class-initialization-to-runtime=<class-name>. Or you can write your own initialization methods and call them explicitly from your main entry point.
Trace: 
  at parsing oracle.jdbc.driver.OracleTimeoutThreadPerVM.stopWatchdog(OracleTimeoutThreadPerVM.java:64)
Call path from entry point to oracle.jdbc.driver.OracleTimeoutThreadPerVM.stopWatchdog(): 
  at oracle.jdbc.driver.OracleTimeoutThreadPerVM.stopWatchdog(OracleTimeoutThreadPerVM.java:64)
  at oracle.jdbc.driver.OracleDriver.deregister(OracleDriver.java:517)
  at oracle.jdbc.driver.OracleDriver$$Lambda$443/1007825518.deregister(Unknown Source)
  at java.sql.DriverManager.deregisterDriver(DriverManager.java:414)

Again, like before, the exception itself does provide a solution. The issue here are static initializer blocks starting threads during analysis, but this can be countered by delaying the class initialization. This isn’t trivial here because I don’t have access to the code in Oracle’s JDBC driver. But in the end I managed to get it working by adding the following parameters to the native-image command:

--delay-class-initialization-to-runtime=oracle.jdbc.driver.OracleDriver,java.sql.DriverManager,org.hibernate.jpa.HibernatePersistenceProvider

The next problem was getting the persistence.xml file to load. Hibernate is using ClassLoader.getResources() for this during runtime and for some reason I couldn’t get this to work. I knew there was a way to add resources into the native image but I struggled to get it working, the flag is called -H:IncludeResources= and you can add a regex here.

It wasn’t until I browsed the Substrate VM source code and extracted the parsing from ResourcesFeature.java. Running this code locally showed me everything I tried was wrong.

Things I tried that didn’t work:

-H:IncludeResources=target/classes/*
-H:IncludeResources=target/classes/.*
-H:IncludeResources=target/classes/META-INF/persistence.xml
-H:IncludeResources=META-INF/persistence.xml
-H:IncludeResources=*/persistence.xml

... and more and more ...

This finally worked (including all XSD’s, properties and everything in META-INF):

-H:IncludeResources=.*.properties|.*META-INF/persistence.xml|.*.xsd

It turns out the listing goes through all the JAR files and directories and matches them against a relative path which in our case is:

  • /logging.properties
  • /META-INF/persistence.xml
  • etc

So having META-INF/persistence.xml or logging.properties isn’t enough. This cost me way more time than it should have. A nice feature to add to GraalVM would be to list all the resources being added because at some point I was convinced it should just work and the problem was in my code somewhere.

Next problem: Xerces

This library gave me nightmares before as a Java developer, but luckily this time the problems could be fixed easily by adding more reflection exceptions to our -H:ReflectionConfigurationFiles=reflection.json.

  ...
  {
    "name" : "com.sun.org.apache.xerces.internal.impl.dv.xs.SchemaDVFactoryImpl",
    "methods" : [
      {
        "name" : "<init>", "parameterTypes" : []
      }
    ]
  },
  {
    "name" : "com.sun.org.apache.xerces.internal.jaxp.DocumentBuilderFactoryImpl",
    "methods" : [
      {
        "name" : "<init>", "parameterTypes" : []
      }
    ]
  },
  (and some more, see GitHub for details)
  ...

Also xerces needed a resource bundle to load:

-H:IncludeResourceBundles=com.sun.org.apache.xerces.internal.impl.xpath.regex.message

Sigh, okay, still making progress.

Now again a problem with Hibernate and resources. I got the following StringIndexOutOfBoundsException running the application:

Caused by: java.lang.StringIndexOutOfBoundsException: String index out of range: -1
  at java.lang.Throwable.<init>(Throwable.java:265)
  at java.lang.Exception.<init>(Exception.java:66)
  at java.lang.RuntimeException.<init>(RuntimeException.java:62)
  at java.lang.IndexOutOfBoundsException.<init>(IndexOutOfBoundsException.java:56)
  at java.lang.StringIndexOutOfBoundsException.<init>(StringIndexOutOfBoundsException.java:69)
  at java.lang.String.substring(String.java:1967)
  at org.hibernate.boot.archive.internal.ArchiveHelper.getJarURLFromURLEntry(ArchiveHelper.java:45)
  at org.hibernate.jpa.boot.internal.PersistenceXmlParser.parsePersistenceXml(PersistenceXmlParser.java:256)
  at org.hibernate.jpa.boot.internal.PersistenceXmlParser.parsePersistenceXml(PersistenceXmlParser.java:240)

It turns out due to the way GraalVM labels its resources we get to a point where Hibernate is confused. It calls the following code with the wrong parameters:

Input:

  • url: “META-INF/persistence.xml”
  • entry: “/META-INF/persistence.xml”
public static URL getJarURLFromURLEntry(URL url, String entry) throws IllegalArgumentException {
   ...
   file = file.substring( 0, file.length() - entry.length());
   ...

With this input entry.length()=25 is bigger than url.length()=24 resulting in file.substring(0, -1), sigh.

To fix this I’ve created a so called shadowed class. This is a class with the exact same signature that I am compiling and adding to the classpath. Because my version of the class is loaded before the Hibernate version of the class, my version is used, I’m overriding the Hibernate version. This is obviously very ugly, but it does the job surprisingly well!

I used Math.max(0, file.length() - entry.length()) to fix getting a ‘-1’ in the substring:

public static URL getJarURLFromURLEntry(URL url, String entry) throws IllegalArgumentException {
   ...
   file = file.substring( 0, Math.max(0, file.length() - entry.length()));
   ...

And of course, a new problem pops up. Again with the resources, GraalVM seems to have put resource as a protocol of all the loaded resources. Opening the resource using an java.lang.URL caused more problems in ArchiveHelper because GraalVM doesn’t recognise ‘resource’ as a valid protocol (huh?). This meant I needed to make another small patch in the shadowed ArchiveHelper:

public static URL getJarURLFromURLEntry(URL url, String entry) throws IllegalArgumentException {
   ...
   } else if ( "resource".equals(protocol)) {
      // FIX: Added for GraalVM, just return the URL
      return url;
   }
   ...

The next big problem was getting oracle.jdbc.driver.OracleDriver to accept the fact that GraalVM doesn’t support JMX (and might never support it). The driver tried to load MXBeans and MBeans from a static initializer block, this caused major headaches…. but in the end I managed to solve this again by shadowing another class:

package oracle.as.jmx.framework;

import javax.management.MBeanServer;

/**
 * Shadowing class: oracle.as.jmx.framework.PortableMBeanFactory
 */
public class PortableMBeanFactory {

    /** Just return null, GraalVM doesn't support MBeans/JMX */
    public MBeanServer getMBeanServer() {
        return null; // Do nothing.
    }
}

Still the initial static initializer block in oracle.jdbc.driver.OracleDriver wouldn’t load and broke the native compilation. Browsing the decompiled code I noticed the following lines which might cause a problem:

...
try {
   new OraclePKIProvider();
} catch (Throwable var3) {
   ;
}
...

This class isn’t on the classpath oddly enough, so I decided to create a dummy/shadow class again, just in case:

package oracle.security.pki;

/** Another shadowing class... */
public class OraclePKIProvider {
   // Placeholder for GraalVM.
}

The next problem is Hibernate’s dynamic runtime proxies. This is something GraalVM can’t handle so we need to make sure Hibernate’s magic is done before we start our application. Luckily there is a Maven plugin which does just that:

<plugin>
   <groupId>org.hibernate.orm.tooling</groupId>
   <artifactId>hibernate-enhance-maven-plugin</artifactId>
   <version>5.3.6.Final</version>
   <executions>
      <execution>
         <configuration>
            <failOnError>true</failOnError>
            <enableLazyInitialization>true</enableLazyInitialization>
            <enableDirtyTracking>true</enableDirtyTracking>
            <enableAssociationManagement>true</enableAssociationManagement>
            <enableExtendedEnhancement>false</enableExtendedEnhancement>
         </configuration>
         <goals>
             <goal>enhance</goal>
         </goals>
      </execution>
   </executions>
</plugin>

Now we have everything in place and we can use the EntityManager to access our database and execute queries…. right?

Well it turns out, the application does start, and it comes a long way. But there is one thing I wasn’t able to fix, loading the definitions.

Hibernate has two ways of loading/mapping the actual class to the database:

  • Hbm files
  • Annotations

First I tried to use annotations, but this failed because at runtime the native (pre-loaded) classes don’t have any knowledge left of the annotations they once had.

The second method is using an HBM xml file, but this too failed. Reading the XML file again needs support for annotations and JAXB failed on me.

So we’ll have to stop here. The JDBC driver was working, so probably plain old SQL would work perfectly. Hibernate for now eludes me.

Update: Previously I mentioned Hibernate was working, this was a mistake on my part!

Docker: Multi-stage build

After Part 1 some people suggested my Dockerfiles could be made cleaner with a so called ‘multistage’ build. More information can be found here: Docker multistage

After some changes I now have a single Dockerfile with two FROM sections in it. The first section is the builder-part, the second part is the host-part. My docker build command now uses that first image to build, passes everything to the second image and builds our resulting Docker container. Really nice, I’m learning new techniques every day.

Compilation speed

One thing I noticed during this entire process, the analysis time used by native-image grew exponentially. The HelloWorld application from Part 1 took just a couple of seconds, but look at the following output:

[app:9]    classlist:  10,398.63 ms
[app:9]        (cap):   1,181.85 ms
[app:9]        setup:   2,329.11 ms
...
[app:9]   (typeflow): 477,904.73 ms
[app:9]    (objects): 2,641,498.60 ms
[app:9]   (features):  26,826.28 ms
[app:9]     analysis: 3,158,033.10 ms
[app:9]     universe: 221,809.62 ms
[app:9]      (parse):  29,723.95 ms
[app:9]     (inline):  49,021.78 ms
[app:9]    (compile): 104,756.90 ms
[app:9]      compile: 193,699.62 ms
[app:9]        image:  31,052.63 ms
[app:9]        write:   6,717.73 ms
[app:9]      [total]: 3,625,666.08 ms

It now took a whopping 60 minutes to compile to native! And during the creation of this project I needed to add a single line the reflecion.json and restart the entire build a lot of times. Transforming a project to work with native-image right now is a really time-consuming endeavour.

When compiling on my MacBook for MacOS, the compilation time is much shorter, just a couple of minutes. The problem here seems to be Docker and building for Ubuntu.

Final result: a working native microservice

I’m proud to say I now have a simple CRUD native microservice, written in Java, using Java libraries…. that is almost working. With a bit more work on the GraalVM/SubstrateVM side I’m pretty sure this could work in the near future.

It uses:

  • SparkJava
  • GSON
  • Dagger 2
  • SLF4J + java.util.logging
  • Hibernate/Oracle (almost working…)

This allows me to serve REST/JSON objects from the database with some Java code in between, what most microservices do.

All the sources are on GitHub: check it out

Check out all the code on GitHub and try it out for yourself. To get it up and running all you need it to set up a database and put the connection information in persistence.xml.

Start up time

The microservice has a very fast startup time:

Sep 25, 2018 7:22:54 PM org.eclipse.jetty.server.AbstractConnector doStart
INFO: Started ServerConnector@3650e607{HTTP/1.1,[http/1.1]}{0.0.0.0:4567}
Sep 25, 2018 7:22:54 PM org.eclipse.jetty.server.Server doStart
INFO: Started @486ms

Compare this to the Java 8 version (same code):

Sep 25, 2018 9:12:09 PM org.eclipse.jetty.server.AbstractConnector doStart
INFO: Started ServerConnector@6d5ff62e{HTTP/1.1,[http/1.1]}{0.0.0.0:4567}
Sep 25, 2018 9:12:09 PM org.eclipse.jetty.server.Server doStart
INFO: Started @3406ms

With 486ms compared to 3406ms the native version starts 7x faster.

Memory consumption

The Java version consumes 267mb of memory, while the native version takes just 20.7mb, so it is 13x smaller.

Conclusion

At the moment GraalVM is still in its infancy stage, there are still a lot of areas that can use some improvement. Most problems I’ve encountered have to do with resource loading or reflection. The build/analysis-cycle becomes pretty long when you add more and more classes and if you need to add reflection-configuration exceptions each build, this process is quite cumbersome.

Frameworks and libraries will start to notice GraalVM (once it gains more traction) and they will change their code to work better with Graal. For example the team behind Spring Boot is already actively working together with the GraalVM team to get their framework working.

Now some people are shouting to their laptops:

Why not just use Go/Rust/some other language that compiles to native by default!?

That is a very good point. If you want to use Go or Rust, go ahead!

Java is the most popular programming language in the world (according to the tiobe index). It is the language with most libraries and frameworks (except for Javascript probably). Changing entire development teams to learn Go and/or Rust, changing companies to a new language is very hard to do. Using native-image might be a more accessible way of transitioning to native backends IMO.

I’ll for sure be keeping track of GraalVM, not just because of the native-image capabilities, but also because the amazing speed of their VM.

Did you know the Oracle Database has GraalVM support? You can create queries which use Javascript functions or Java methods!

Did you know there is a Graal AOT compiler inside your JDK right now? (see: JEP-295)

Sources: All the code from this blogpost can be found here on GitHub.


Part 1: Java to native using GraalVM

Part 1: Java to native using GraalVM

One of the most amazing projects I’ve learned about this year is GraalVM.

I’ve learned about this project during Devoxx Poland (a Polish developer conference) at a talk by Oleg Šelajev. If you’re curious about everything GraalVM has to offer, not just the native Java compilation, please watch his video.

GraalVM is a universal/polyglot virtual machine. This means GraalVM can run programs written in:

  • Javascript
  • Ruby
  • Python 3
  • R
  • JVM-based languages (such as Java, Scala, Kotlin)
  • LLVM-based languages (such as C, C++).

In short: Graal is very powerful.

There is also the possibility to mix-and-match languages using Graal, do you want to make a nice graph in R from your Java code? No problem. Do you want to call some fast C code from Python, go ahead.

Installing GraalVM

In this blogpost though we’ll look at another powerful thing Graal can do: native-image compilation

Instead of explaining what it is, let’s just go ahead, install GraalVM and try it out.

To install GraalVM, download and unpack, update PATH parameters and you’re ready to go. When you look in the /bin directory of Graal you’ll see the following programs:

Here we recognise some usual commands, such as ‘javac’ and ‘java’. And if everything is setup correctly you’ll see:

$ java -version
openjdk version "1.8.0_172"
OpenJDK Runtime Environment (build 1.8.0_172-20180626105433.graaluser.jdk8u-src-tar-g-b11)
GraalVM 1.0.0-rc6 (build 25.71-b01-internal-jvmci-0.48, mixed mode)

Hello World with native-image

Next up, let’s create a “Hello World” application in Java:

public class HelloWorld {
   public static void main(String... args) {
      System.out.println("Hello World");
   }
}

And just like your normal JDK, we can compile and run this code in the Graal virtual machine:

$ javac HelloWorld.java
$ java HelloWorld
Hello World

But the real power of Graal becomes clear when we use a third command: native-image

This command takes your Java class(es) and turns them into an actual program, a standalone binary executable, without any virtual machine! The commands you pass to native-image very similar to what you would pass to java. In this case we have the classpath and the Main class:

$ native-image -cp . HelloWorld
Build on Server(pid: 63941, port: 60051)*
[helloworld:63941]    classlist:   1,236.06 ms
[helloworld:63941]        (cap):   1,885.61 ms
[helloworld:63941]        setup:   2,758.47 ms
[helloworld:63941]   (typeflow):   3,031.39 ms
[helloworld:63941]    (objects):   2,136.63 ms
[helloworld:63941]   (features):      46.04 ms
[helloworld:63941]     analysis:   5,304.17 ms
[helloworld:63941]     universe:     205.46 ms
[helloworld:63941]      (parse):     640.12 ms
[helloworld:63941]     (inline):   1,155.06 ms
[helloworld:63941]    (compile):   3,436.76 ms
[helloworld:63941]      compile:   5,594.76 ms
[helloworld:63941]        image:     749.82 ms
[helloworld:63941]        write:     653.29 ms
[helloworld:63941]      [total]:  16,753.87 ms
$ ls -ltr
-rw-r--r--  1 royvanrijn  wheel  119 Sep 20 09:36 HelloWorld.java
-rw-r--r--  1 royvanrijn  wheel  425 Sep 20 09:38 HelloWorld.class
-rwxr-xr-x  1 royvanrijn  wheel  5596400 Sep 20 09:41 helloworld
$ ./helloworld 
Hello World

Now we have an executable that prints “Hello World”, without any JVM in between, just 5.6mb. Sure, for this example 5mb isn’t that small, but it is much smaller than having to package and install an entire JVM (400+mb)!

Docker and native-image

So what else can we do? Well, because the resulting program is a binary, we can put it into a Docker image without ANY overhead. To do this we’ll need two different Dockerfile’s, the first is used to compile the program against Linux (instead of MacOS or Windows), the second image is the ‘host’ Dockerfile, used to host our program.

Here is the first Dockerfile:

FROM ubuntu

RUN apt-get update && \
    apt-get -y install gcc libc6-dev zlib1g-dev curl bash && \
    rm -rf /var/lib/apt/lists/*

# Latest version of GraalVM (at the time of writing)
ENV GRAAL_VERSION 1.0.0-rc6
ENV GRAAL_FILENAME graalvm-ce-${GRAAL_VERSION}-linux-amd64.tar.gz

# Download GraalVM
RUN curl -4 -L https://github.com/oracle/graal/releases/download/vm-${GRAAL_VERSION}/${GRAAL_FILENAME} -o /tmp/${GRAAL_FILENAME}

# Untar and move the files we need:
RUN tar -zxvf /tmp/${GRAAL_FILENAME} -C /tmp \
    && mv /tmp/graalvm-ce-${GRAAL_VERSION} /usr/lib/graalvm

RUN rm -rf /tmp/*

# Create a volume to which we can mount to build:
VOLUME /project
WORKDIR /project

# And finally, run native-image
ENTRYPOINT ["/usr/lib/graalvm/bin/native-image"]

This image can be created as follows:

$ docker build -t royvanrijn/graal-native-image:latest .

Using this image we can create a different kind of executable. Let’s create our application using the just created docker image:

$ docker run -it \
  -v /Projects/graal-example/helloworld/:/project --rm \
  royvanrijn/graal-native-image:latest \
  --static -cp . HelloWorld -H:Name=app

Build on Server(pid: 11, port: 40905)*
[app:11]    classlist:   3,244.85 ms
[app:11]        (cap):   1,023.94 ms
[app:11]        setup:   1,986.81 ms
[app:11]   (typeflow):   4,285.18 ms
[app:11]    (objects):   2,008.19 ms
[app:11]   (features):      57.07 ms
[app:11]     analysis:   6,446.49 ms
[app:11]     universe:     255.45 ms
[app:11]      (parse):     926.85 ms
[app:11]     (inline):   1,496.69 ms
[app:11]    (compile):   4,953.85 ms
[app:11]      compile:   7,689.47 ms
[app:11]        image:     806.53 ms
[app:11]        write:     573.77 ms
[app:11]      [total]:  21,160.90 ms
$ ls -ltr app
-rwxr-xr-x  1 royvanrijn  wheel  6766144 Sep 20 10:11 app
$ ./app
-bash: ./app: cannot execute binary file

This results in an executable ‘app’, but this is one I can’t start on my MacBook, because it is a statically linked Ubuntu executable. So what do all these commands mean? We’ll let’s break it down:

The first part is just running Docker:
     docker run -it

Next we map my directory containing the class files to the volume /project in the Docker image:
     -v /Projects/graal-example/helloworld/:/project --rm

This is the Docker image we want to run, the one we just created:
     royvanrijn/graal-native-image:latest

And finally we have the commands we pass to native-image inside the Docker image
We start with --static, this causes the created binary to be a statically linked executable
     --static

We have the class path and Main class:
     -cp . HelloWorld

And finally we tell native-image to name the resulting executable 'app'
     -H:Name=app

But we can do something cool with it using the following, surprisingly empty, Dockerfile:

FROM scratch
COPY app /app
CMD ["/app"]

We start with the most empty Docker image you can have, scratch and we copy in our app executable and finally we run it. Now we can build our helloworld image:

$ docker build -t royvanrijn/graal-helloworld:latest .
Sending build context to Docker daemon  34.11MB
Step 1/3 : FROM scratch
 ---> 
Step 2/3 : COPY app /app
 ---> f0894b299e8f
Removing intermediate container 37182de1ef68
 ---> 49ff43413c7a
Step 3/3 : CMD ["/app"]
 ---> Running in ea69a913d243
Removing intermediate container ea69a913d243
 ---> ab33b4d59de3
Successfully built ab33b4d59de3
Successfully tagged royvanrijn/graal-helloworld:latest

$ docker images
REPOSITORY                                                  TAG                         IMAGE ID            CREATED             SIZE
royvanrijn/graal-helloworld                                 latest                      ab33b4d59de3        5 seconds ago       6.77MB

We’ve now turned our Java application into a very small Docker image with a size of just 6.77MB!

In the next blogpost Part 2 we’ll take a look at Java applications larger than just HelloWorld. How will GraalVM’s native-image handle those applications, and what are the limitations we’ll run into?


Part 2: OpenJ9 versus HotSpot

Part 2: OpenJ9 versus HotSpot

Intro

Yesterday I compared different JDK versions and OpenJ9 versus HotSpot on memory and speed. The memory part of the test was realistic if you ask me, an actual working Spring Boot application that served REST objects.

The speed/CPU test however was… lacking. Sorting some random arrays, just one specific test.

Today I decided to test OpenJ9 and HotSpot a bit more using an actual benchmark: SPECjvm2008.

SPECjvm2008

SPEC (Standard Performance Evaluation Corporation) has a couple of well defined benchmarks and tests, including an old JVM benchmark called SPECjvm2008. This is an elaborate benchmark testing things like compression, compiling, XML parsing and much more. I decided to download this and give it a spin versus OpenJ9 and HotSpot. This should be a much fairer comparison.

Initially I encountered some issues, some of the tests didn’t work against Java 8 and the tests wouldn’t even start against Java 9+. But eventually I got it working by excluding a couple of benchmarks with the following parameters:

java -jar SPECjvm2008.jar startup.helloworld startup.compiler.compiler  startup.compress startup.crypto.aes startup.crypto.rsa startup.crypto.signverify startup.mpegaudio startup.scimark.fft startup.scimark.lu startup.scimark.monte_carlo startup.scimark.sor startup.scimark.sparse startup.serial startup.sunflow startup.xml.validation compiler.compiler compress crypto.aes crypto.rsa crypto.signverify derby mpegaudio scimark.fft.large scimark.lu.large scimark.sor.large scimark.sparse.large scimark.fft.small scimark.lu.small scimark.sor.small scimark.sparse.small scimark.monte_carlo serial sunflow xml.validation

Testing

The Docker images used in these tests are both Java 8 with OpenJDK8, but one with HotSpot underneath, the other with OpenJ9:

  • adoptopenjdk/openjdk8
  • adoptopenjdk/openjdk8-openj9

Again I started the Docker image with a directory linked to the host containing the SPEC benchmark:

  • Start Docker:
docker run -it -v /Projects/SPECjvm2008:/app/SPECjvm2008 adoptopenjdk/openjdk8-openj9 /bin/bash
  • Go to the correct directory:
cd /app/SPECjvm2008
  • Run the (working) tests:
java -Xmx600m -jar SPECjvm2008.jar startup.helloworld startup.compiler.compiler  startup.compress startup.crypto.aes startup.crypto.rsa startup.crypto.signverify startup.mpegaudio startup.scimark.fft startup.scimark.lu startup.scimark.monte_carlo startup.scimark.sor startup.scimark.sparse startup.serial startup.sunflow startup.xml.validation compiler.compiler compress crypto.aes crypto.rsa crypto.signverify derby mpegaudio scimark.fft.large scimark.lu.large scimark.sor.large scimark.sparse.large scimark.fft.small scimark.lu.small scimark.sor.small scimark.sparse.small scimark.monte_carlo serial sunflow xml.validation

Results

After waiting a long time for the benchmark to finish, I’ve got the following results:

Chart with SPECjvm2008 results

The graph is measured in ops/m, higher is better. Results may vary of course depending on hardware.

In most cases HotSpot is faster than OpenJ9, and in two cases HotSpot is much faster, crypto and derby. It appears this is a case where HotSpot is doing something special that J9 isn’t doing (yet?). This might be important to know if you’re working on applications that do a lot of cryptology, for example high performance secured endpoints.

One place where OpenJ9 came out on top is XML validation. Parsing/validation is also an important part in most modern applications, so this could be a case where J9 makes up some lost ground in actual production code.

Conclusion

Is there a real conclusion from this? I don’t think so.

The real lesson here is: Experiment, measure and you’ll know. Never decided anything based on some online benchmark.

If there is anything else you’d love me to test, send me a tweet: royvanrijn


Part 1: OpenJ9 versus HotSpot

Part 1: OpenJ9 versus HotSpot

TLDR;

OpenJ9 and IBM J9 are a different JVM implementation from the default Oracle HotSpot JVM. With the modern adoptopenjdk pre-made Docker images it is easy to swap and test different combinations and pick the right JVM for you.

The rumours seem to be true, OpenJ9 seems to blow HotSpot away on memory usage. HotSpot seems to have the edge CPU-wise.

OpenJ9

In the Java world most people are familiar with OpenJDK. This is a complete JDK implementation including the HotSpot JVM engine. Not a lot of developers know or try alternatives to HotSpot. Asking around some colleagues remembered the name JRockit, nobody mentioned IBM J9 and/or Eclipse OpenJ9.

I’ve read that OpenJ9 is very good with memory management and is tailered for usage in the cloud/in containers. OpenJ9 is an independent implementation of the JVM. It’s origins are IBM’s Java SDK/IBM J9 which can trace its history back to OTI Technologies Envy Smalltalk (thanks Dan Heidinga!).

With the current rise in microservice usage (and most services are not so micro in Java). I recon this could become a hot topic again!

Testing

Before the Docker-era it was relatively hard to compare different JVMs, versions. You needed to download, install, script and run everything. But now a lot of pre-made images are available online.

Here is my idea on how to test the JVMs:

  1. Create a simple Spring Boot application
  2. Start the application in various Docker Images
  3. Measure memory usage after startup and GC
  4. Measure the time it takes to run a small CPU-intensive test

This is by no means a thorough test or benchmark, but it should give us a basic idea of what we can expect from the virtual machines.

Spring Boot application

The Spring Boot application I created contains the following endpoints:

  1. A REST endpoint that calls the GC (trying to make it fair)
  2. A REST endpoint that creates 1000 large random arrays and sorts them, returns the runtime (in ms)

Here is the listing of the CPU-test:

@RestController
public class LoadTestController {

    @RequestMapping("/loadtest")
    public LoadTestResult loadtest() {

        long before = System.currentTimeMillis();

        Random random = new Random();

        for(int i = 0; i < 1000; i++) {
            long[] data = new long[1000000];
            for(int l = 0; l < data.length; l++) {
                data[l] = random.nextLong();
            }
            Arrays.sort(data);
        }

        return new LoadTestResult(System.currentTimeMillis() - before);
    }
}

Again, we can argue endlessly about if this test makes sense and is even remotely relevant… but still it should give us some basic idea of what kind of performance we can expect. If the rumoured memory improvements are true, might there be a performance hit? Is there a performance trade-off?

JVM images

I’ve decided to test the following images.

First we have the (slim) openjdk images for 8/9/10/11:

  • openjdk:8-slim
  • openjdk:9-slim
  • openjdk:10-slim
  • openjdk:11-slim

Next there are the adoptopenjdk images for 8/9/10:

  • adoptopenjdk/openjdk8
  • adoptopenjdk/openjdk9
  • adoptopenjdk/openjdk10

Then we have OpenJ9, again provided by adoptopenjdk for 8, 9 and a nightly build of 9 (see my previous blogpost):

  • adoptopenjdk/openjdk8-openj9
  • adoptopenjdk/openjdk9-openj9
  • adoptopenjdk/openjdk9-openj9:nightly

And I decided to include IBM’s own J9 image as well:

  • ibmcom/ibmjava:8-jre

Testing with Docker

After building my Spring Boot application I launched each Docker image using the following command:

docker run -it -v /Projects/temp/spring-boot-example:/app/spring-boot-example -p 8080:8080 IMAGE_NAME /bin/bash

I’m mapping my “spring-boot-example” project folder to “/apps/spring-boot-example” so I can start the JAR file inside the container. Also I’m forwarding port 8080 back to my host so I can call the endpoints.

Next, inside the container, I launch the Spring Boot application:

java -jar /app/spring-boot-example/target/spring-boot-example-0.0.1-SNAPSHOT.jar

After waiting a bit, calling the endpoints a couple of times and performing a GC I measured the memory usage.

After that I called the “/loadtest” endpoint containing the array-sorting test and waited for the results.

Memory benchmark

Here are the results of the memory used by the simple Spring Boot application:

Chart with memory usage per Docker Image

At first you can see that the memory usage for Java 8 is much higher than for Java 9 and 10, good!

But the biggest shock is how much less memory OpenJ9 and J9 are using, almost 4x less memory if you compare Java 8 with OpenJ9. I’m amazed, how does this even work? Now we can almost call our Spring Boot service micro!

I’ve also experimented with running some production Spring Boot code (not just simple examples) and here I’ve seen improvements up to 40-50% decrease in memory usage.

CPU benchmark

Online I’ve read that OpenJ9 isn’t as good as HotSpot if you look at CPU intensive tasks. That is why I created a small test for this as well.

1000 arrays with 1000000 random long values being sorted. This takes around 100 seconds, this should give the JVM enough time to adjust and optimize. I’ve called the benchmark twice for each tested image. I’ve recorded the second time trying to eliminate warmup times.

Chart with CPU usage per Docker Image

In the chart we can see that indeed the J9 and OpenJ9 images are slower, not by much max 18%. It seems for this particular testcase Java 8 beats most Java 9 implementations (except coupled with OpenJ9).

What’s next?

My current project has a lot more memory issues than CPU issues on production (frequently running out of memory while having 1-2% CPU usage). We are definitely thinking about switching to OpenJ9 in the near future!

We did already encounter some issues during testing:

  1. Hessian: (binary protocol) has a build-in assumption that System.identityHashCode always returns a positive number. For HotSpot this is true but OpenJ9/J9 can also return negative numbers. This is an open issue and the Hessian project hasn’t fixed this in a couple of years, seems to be dead? Our solution is to move away from Hessian altogether
  2. Instana: We love our monitoring tool Instana, but it had some problems connecting their agent to OpenJ9/J9. Luckily the people at Instana helped us identify a bug and a fix should be published today (and is automatically updated, w00t!)

Open questions I haven’t looked in to:

  1. Can you still get/use jmap/hprof information etc in OpenJ9?
  2. How will it hold up during longer production runs?
  3. Will we find other weird bugs? It feels tricky…

Have you tried OpenJ9/J9? Let me know in the comments.

Is there anything else you’d love to see tested? The best way to contact me is to send me a tweet royvanrijn.


Java and Docker, the limitations

Java and Docker, the limitations

TLDR;

Java and Docker aren’t friends out of the box. Docker can set memory and CPU limitations that Java can’t automatically detect. Using either Java Xmx flags (cumbersome/duplicated) or the new experimental JVM flags we can solve this issue.

Docker love for Java is in its way in newer versions of both OpenJ9 and OpenJDK 10!

Mismatch in virtualization

The combination of Java and Docker isn’t a match made in heaven, initially it was far from it. For starters, the whole premise of the JVM, Java Virtual Machine, was that having a Virtual Machine makes the underlying hardware irrelevant from the program’s point of view.

So what do we gain by packaging our Java application inside a JVM (Virtual Machine) inside a Docker container? Not a lot, for the most part you are duplicating JVMs and Linux containers, which kills memory usage. This just sounds silly.

It does make it easy to bundle together your program, the settings, a specific JDK, Linux settings and (if needed) an application server and other tools as one ‘thing’. This complete container has a better level of encapsulation from a devops/cloud point of view.

Problem 1: Memory

Most applications in production today are still using Java 8 (or older) and this might give you problems. Java 8 (before update 131) doesn’t play nice with Docker. The problem is that the amount of memory and CPUs available to the JVM isn’t the total amount of memory and CPU of your machine, it is what Docker is allowing you to use (duh).

For example if you limit your Docker container to get only 100MB of memory, this isn’t something ‘old’ Java was aware of. Java doesn’t see this limit. The JVM will claim more and more memory and go over this limit. Docker will then take action into its own hands and kill the process inside the container if too much memory is used! The Java process is ‘Killed’. This is not what we want…

To fix this you will also need to specify to Java there is a maximum memory limit. In older Java versions (before 8u131) you needed to specify this inside your container by setting -Xmx flags to limit the heap size. This feels wrong, you’d rather not want to define these limits twice, nor do you want to define this ‘inside’ your container.

Luckily there are better ways to fix this now. From Java 9 onwards (and from 8u131+ onwards, backported) there are flags added to the JVM:

-XX:+UnlockExperimentalVMOptions -XX:+UseCGroupMemoryLimitForHeap

These flags will force the JVM to look at the Linux cgroup configuration. This is where Docker containers specify their maximum memory settings. Now, if your application reaches the limit set by Docker (500MB), the JVM will see this limit. It’ll try to GC. If it still runs out of memory the JVM will do what it is supposed to do, throw an OutOfMemoryException. Basically this allows the JVM to ‘see’ the limit that has been set by Docker.

From Java 10 onwards (see test below) these experimental flags are the new default and are enabled using the -XX:+UseContainerSupport flag (you can disable this behaviour by providing -XX:-UseContainerSupport).

Problem 2: CPU

The second problem is similar, but it has to do with the CPU. In short, the JVM will look at the hardware and detect the amount of CPU’s there are. It’ll optimize your runtime to use those CPU’s. But again, Docker might not allow you to use all these CPU’s, there is another mismatch here. Sadly this isn’t fixed in Java 8 or Java 9, but was tackled in Java 10.

From Java 10 onwards the available CPUs will be calculated in a different way (by default) fixing this problem (also with UseContainerSupport).

Testing Java and Docker memory handling

As a fun exercise, lets verify and test how Docker handles out of memory using a couple of different JVM versions/flags and even a different JVM.

First we create a test application, one that simply ‘eats’ memory and doesn’t free it.

import java.util.ArrayList;
import java.util.List;

public class MemEat {
    public static void main(String[] args) {
        List l = new ArrayList<>();
        while (true) {
            byte b[] = new byte[1048576];
            l.add(b);
            Runtime rt = Runtime.getRuntime();
            System.out.println( "free memory: " + rt.freeMemory() );
        }
    }
}

We can start Docker containers and run this application to see what will happen.

Test 1: Java 8u111

First we’ll start with a container that has an older version of Java 8 (update 111).

docker run -m 100m -it java:openjdk-8u111 /bin/bash

We compile and run the MemEat.java file:

javac MemEat.java

java MemEat
...
free memory: 67194416
free memory: 66145824
free memory: 65097232
Killed

As expected, Docker has killed the our Java process. Not what we want (!). Also you can see the output, Java thinks it still has a lot of memory left to allocate.

We can fix this by providing Java with a maximum memory using the -Xmx flag:

javac MemEat.java

java -Xmx100m MemEat
...
free memory: 1155664
free memory: 1679936
free memory: 2204208
free memory: 1315752
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at MemEat.main(MemEat.java:8)

After providing our own memory limits, the process is halted correctly, the JVM understands the limits it is operating under. The problem is however that you are now setting these memory limits twice, for Docker AND for the JVM.

Test 2: Java 8u144

As mentioned, with the new flags this has been fixed, the JVM will now follow the settings provided by Docker. We can test this using a newer JVM.

docker run -m 100m -it adoptopenjdk/openjdk8 /bin/bash

(this OpenJDK Java image currently contains, at the time of writing, Java 8u144)

Next we compile and run the MemEat.java file again without any flags:

javac MemEat.java

java MemEat
...
free memory: 67194416
free memory: 66145824
free memory: 65097232
Killed

The same problem exists. But we can now supply the experimental flags mentioned above:

javac MemEat.java
java -XX:+UnlockExperimentalVMOptions -XX:+UseCGroupMemoryLimitForHeap MemEat
...
free memory: 1679936
free memory: 2204208
free memory: 1155616
free memory: 1155600
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
	at MemEat.main(MemEat.java:8)

This time we didn’t set any limits on the JVM by telling it what the limits are, we just told the JVM to look at the correct settings! Much better.

Test 3: Java 10u23

Some people in the comments and on Reddit mentioned that Java 10 solves everything by making the experimental flags the new default. This behaviour can be turned off by disabling this flag: -XX:-UseContainerSupport.

When I tested this it initially didn’t work. At the time of writing the AdoptAJDK OpenJDK10 image is packaged with jdk-10+23. This JVM apparently doesn’t understand the ‘UseContainerSupport’ flag (yet) and the process was still killed by Docker.

docker run -m 100m -it adoptopenjdk/openjdk10 /bin/bash

Testing the code (and even providing the flag manually):

javac MemEat.java

java MemEat
...
free memory: 96262112
free memory: 94164960
free memory: 92067808
free memory: 89970656
Killed

java -XX:+UseContainerSupport MemEat

Unrecognized VM option 'UseContainerSupport'
Error: Could not create the Java Virtual Machine.
Error: A fatal exception has occurred. Program will exit.

Test 4: Java 10u46 (Nightly)

I decided to try the latest ‘nightly’ build of AdoptAJDK OpenJDK 10. Instead of Java 10+23 it includes 10+46.

docker run -m 100m -it adoptopenjdk/openjdk10:nightly /bin/bash

There is a problem in this nightly build though, the exported PATH points to the old Java 10+23 directory, not to 10+46, we need to fix this.

export PATH=$PATH:/opt/java/openjdk/jdk-10+46/bin/

javac MemEat.java

java MemEat
...
free memory: 3566824
free memory: 2796008
free memory: 1480320
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
  at MemEat.main(MemEat.java:8)

Succes! Without providing any flags Java 10 correctly detected Dockers memory limits.

Test 5: OpenJ9

I’ve also been experimenting with OpenJ9 recently, this free alternative JVM has been open sourced from IBMs J9 and is now maintained by Eclipse.

Read more about OpenJ9 in my next blogpost.

It is fast and is very good with memory management, mindblowlingly good, often using up to 30-50% less memory for our microservices. This almost makes it possible to classify Spring Boot apps as ‘micro’ with a 100-200mb runtime nstead of 300mb+. I’m planning on doing a write-up about this very soon.

To my surprise however, OpenJ9 doesn’t yet have an option similar to the flags currently (backported) in Java 8/9/10+ for cgroup memory limits. For example if we apply the previous testcase to the latest AdoptAJDK OpenJDK 9 + OpenJ9 build:

docker run -m 100m -it adoptopenjdk/openjdk9-openj9 /bin/bash

And we add the OpenJDK flags (which are ignored by OpenJ9) we get:

java -XX:+UnlockExperimentalVMOptions -XX:+UseCGroupMemoryLimitForHeap MemEat
...
free memory: 83988984
free memory: 82940400
free memory: 81891816
Killed

Oops, the JVM is killed by Docker again.

I really hope a similar option will be added soon to OpenJ9, because I’d love to run this in production without having to specify the maximum memory twice. Eclipse/IBM is working on a fix for this, there are already issues and even pull requests for this issue.

UPDATE: (not recommended hack)

A slightly ugly/hacky way to fix this is using the following composed flag:

java -Xmx`cat /sys/fs/cgroup/memory/memory.limit_in_bytes` MemEat
...
free memory: 3171536
free memory: 2127048
free memory: 2397632
free memory: 1344952
JVMDUMP039I Processing dump event "systhrow", detail "java/lang/OutOfMemoryError" at 2018/05/15 14:04:26 - please wait.
JVMDUMP032I JVM requested System dump using '//core.20180515.140426.125.0001.dmp' in response to an event
JVMDUMP010I System dump written to //core.20180515.140426.125.0001.dmp
JVMDUMP032I JVM requested Heap dump using '//heapdump.20180515.140426.125.0002.phd' in response to an event
JVMDUMP010I Heap dump written to //heapdump.20180515.140426.125.0002.phd
JVMDUMP032I JVM requested Java dump using '//javacore.20180515.140426.125.0003.txt' in response to an event
JVMDUMP010I Java dump written to //javacore.20180515.140426.125.0003.txt
JVMDUMP032I JVM requested Snap dump using '//Snap.20180515.140426.125.0004.trc' in response to an event
JVMDUMP010I Snap dump written to //Snap.20180515.140426.125.0004.trc
JVMDUMP013I Processed dump event "systhrow", detail "java/lang/OutOfMemoryError".
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
  at MemEat.main(MemEat.java:8)

In this case the heap size is limited to the memory allocated to the Docker instance, this works for older JVMs and OpenJ9. This is of course wrong because the container itself and other parts of the JVM off the heap also use memory. But it seems to work, appearantly Docker is lenient in this case. Maybe some bash-guru will make a better version subtracting a portion from the bytes for other processes.

Anyway, don’t do this, it might not work.

Test 6: OpenJ9 (Nightly)

Someone suggested using the latest ‘nightly’ build for OpenJ9.

docker run -m 100m -it adoptopenjdk/openjdk9-openj9:nightly /bin/bash

This will get the latest nightly build of OpenJ9, and it has two things:

  1. Another broken PATH parameter, fix that.
  2. The JVM has support for the new flag UseContainerSupport (like Java 10 will)
export PATH=$PATH:/opt/java/openjdk/jdk-9.0.4+12/bin/

javac MemEat.java

java -XX:+UseContainerSupport MemEat
...
free memory: 5864464
free memory: 4815880
free memory: 3443712
free memory: 2391032
JVMDUMP039I Processing dump event "systhrow", detail "java/lang/OutOfMemoryError" at 2018/05/15 21:32:07 - please wait.
JVMDUMP032I JVM requested System dump using '//core.20180515.213207.62.0001.dmp' in response to an event
JVMDUMP010I System dump written to //core.20180515.213207.62.0001.dmp
JVMDUMP032I JVM requested Heap dump using '//heapdump.20180515.213207.62.0002.phd' in response to an event
JVMDUMP010I Heap dump written to //heapdump.20180515.213207.62.0002.phd
JVMDUMP032I JVM requested Java dump using '//javacore.20180515.213207.62.0003.txt' in response to an event
JVMDUMP010I Java dump written to //javacore.20180515.213207.62.0003.txt
JVMDUMP032I JVM requested Snap dump using '//Snap.20180515.213207.62.0004.trc' in response to an event
JVMDUMP010I Snap dump written to //Snap.20180515.213207.62.0004.trc
JVMDUMP013I Processed dump event "systhrow", detail "java/lang/OutOfMemoryError".
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

TADAAA, a fix is on the way!

Oddly it seems this flag isn’t enabled by default in OpenJ9 like it is in Java 10 though. Again: Make sure you test this is you want to run Java inside a Docker container.

Conclusion

IN SHORT: Be aware of the mismatch, the limitations. Test your memory settings and JVM flags, don’t assume anything.

If you are running Java inside a Docker container, make sure that you have Docker memory limits AND limits in the JVM or a JVM that understands these limits.

If you’re not able to upgrade your Java version set your own limits using -Xmx.

For Java 8 and Java 9, update to the latest version and use:

-XX:+UnlockExperimentalVMOptions -XX:+UseCGroupMemoryLimitForHeap

For Java 10, make sure it understands the ‘UseContainerSupport’ (update to latest) and just run it.

For OpenJ9 (which I highly recommend for bringing down your memory footprint in production) for now set the limits using -Xmx, but soon there will be a version that understands the ‘UseContainerSupport’ flag.


In a microservices landscape; When do you update?

In a microservices landscape; When do you update?

This week I’ve been stuggling with the following question:

When is the right time to upgrade?

By upgrading, I mean everything: libraries, tools, Java versions, application servers, MQ servers…

My current project uses a reactive upgrade policy, we upgrade for four reasons:

  1. Something is broken and fixed in a later version
  2. We need or want to use a new feature
  3. Support for a version we’re using is being dropped
  4. The old version we’re using has a known security issue/CVE

The first two reasons are entirely up to the programmers to decide. The third reason is up to the company that gives us support. For the fourth upgrade reason, security, we have some automation in place. We are using the OWASP dependency checker Maven plugin for our libraries.

But:

  • Is a reactive update policy good enough?
  • Are there any pro-active strategies?
  • Do you want to invest in keeping your microservices up-to-date?
  • Do you let your services deteriorate and dispose, replace them in the future with new technologies?

More on this in my (kind-of-weekly) vlog: