Convert IP address to its binary representation

Question

For a recent lab at the university we had to match the longest prefix for an IP (v4) address by using a Trie data structure. The code works fine, but it takes about 2 minutes to load a 14 million-line routing table. I examined what was causing the slowness, and it was the (String) IP to (String) binary format conversion.

For example, the IP address 127.0.0.1 should be converted to 01111111000000000000000000000001. I my original method (slow) uses String.format, which I find much more readable and easy to follow. I then wrote a different method using a temporary char[], filled with '0' to use as padding.

The speedup of the fast method is about 6x. Below is a stripped down version for demonstration and measurement:

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        final String ip = "127.0.0.1";
        String binaryIp;
        final long start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i ++) {
            binaryIp = fast(ip);
        }

        long fast = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i ++) {
            binaryIp = slow(ip);
        }

        long slow = System.currentTimeMillis();

        System.out.println("Fast time: " + (fast - start) + " ms");
        System.out.println("Slow time: " + (slow - fast) + " ms");
    }

    public static String fast(String ip) {

        StringBuilder bStringBuilder = new StringBuilder();
        String ipParts[] = ip.split("\\.");

        for (String ipPart : ipParts) {

            String binString = Integer.toBinaryString(Integer.parseInt(ipPart));
            int length = 8 - binString.length();
            char[] padArray = new char[length];
            Arrays.fill(padArray, '0');
            bStringBuilder.append(padArray).append(binString);
        }
        System.out.println(bStringBuilder.toString());
        return bStringBuilder.toString();
    }

    public static String slow(String ip) {

        StringBuilder bStringBuilder = new StringBuilder();
        String ipParts[] = ip.split("\\.");

        for (String ipPart : ipParts) {

            String binString = Integer.toBinaryString(Integer.parseInt(ipPart));
            String binaryPart = String.format("%8s", binString).replace(' ', '0');
            bStringBuilder.append(binaryPart);
        }
        return bStringBuilder.toString();
    }
}

For which the output is:

Fast time: 3936 ms
Slow time: 23527 ms

I can't think of a more efficient way to pad a binary string appropriately... I don't think that there's any need to improve the slow method as it's now obsolete compared to fast. However, is there any way that I can improve fast?

PS - magic number 8 would be a magic number that never changes, so I don't think I need a static final int ipv4SectionLength = 8 or anything like that!

Answer 1

I come from a C background, so I tend to think of problems like this in terms of the very lowest level of data structures. In this case, I would prefer to use a char [] as an intermediary instead of a String or StringBuilder. For a simple fast function like this, I feel that using a String or StringBuilder adds unnecessary overhead.

Analyzing the original function

Looking at the original fast() function, I feel that the slowest parts of it are the calls to library functions: split(), toBinaryString(), parseInt(), fill(), etc. Since converting an IP address to a binary string is a simple function, and since speed is the motivating factor, the more we can do by ourselves the faster our function will run.

Doing the conversion manually

Here is the function I came up with, which does all of the parsing and string building directly. The first step is to parse the input string into an int. The second step is to convert the int to a char [32] array.

public static String faster(final String ip)
{
    int len      = ip.length();
    int addr     = 0;
    int fullAddr = 0;
    char [] out  = new char[32];

    // Parse the four segments of the IP address.
    for (int i = 0; i < len; i++) {
        char digit = ip.charAt(i);
        if (digit != '.') {
            addr = addr * 10 + (digit - '0');
        } else {
            fullAddr = (fullAddr << 8) | addr;
            addr = 0;
        }
    }
    fullAddr = (fullAddr << 8) | addr;

    // At this point, fullAddr holds the IP address as a 32-bit integer.
    for (int i = 0; i < 32; i++, fullAddr <<= 1)
        out[i] = ((fullAddr & 0x80000000) != 0) ? '1' : '0';
    return new String(out);
}

Timing results

I tested using a variant of the original program. The differences are:

1. I used a "warm up" period where I ran the test all the way through one set of iterations, and then I timed the second set of iterations.
2. Instead of only testing one string, I rotated through 4 different strings.
3. I only tested one function per run.

Author                 Time (ms)
------                 ---------
JS1                        468
rolfl (mapped)            2746
Eric Stein (HashMap)      2754
Toolkit                   3329
rolfl (pad)               3854
Eric Stein (pad)          4236
Chris Cirefice (Fast)     5102
Chris Cirefice (Slow)    26175

Answer 2

I don't have access to your test file, but try:

private static final String[] PAD_ZEROS= 
    new String[] {
        "00000000", 
        "0000000", 
        "000000", 
        "00000", 
        "0000", 
        "000", 
        "00", 
        "0", 
        ""
    };

   public static String fast(final String ip) {
        final StringBuilder result = new StringBuilder();
        final String octals[] = ip.split("\\.");
        for (final String octal: octals) {    
            final String binaryString = Integer.toBinaryString(Integer.parseInt(octal));
            result.append(PAD_ZEROS[binaryString.length()]);
            result.append(binaryString);
        }
        return result.toString();
    }

In general, I'd suggest avoiding hungarian notation (bStringBuilder), unnecessary abbreviations(binString), and magic numbers (if you keep the 8, it should be in a private static final class-level variable).

Note that your performance testing is flawed. The problem is the VM performs internal optimizations as it runs which can improve the performance of the system. You should test either fast or slow, but not both, in one execution. Don't test the same string over and over again, but pull in your routing file. Then, unless your whole application is to run this one method on the file and then stop, you should run for a while, throw out that data, then start measuring. Maybe do 2 executions of the file, but only time the second one. That imitates the method being called from a live system that's been running a while, instead of a cold system.

Two more things: as @rofl said, presize the StringBuilder. Also pull the System.out.println() out of your method - it's an artificial drag on the performance.

-- Working off of @rofl's other suggestion, this is 25% faster on my machine than your fast method, including the time to populate the map. It does consume more memory, and it eagerly maps numbers which may not be used. It is less elegant than @rofl's suggestion, and possibly slower, but I find it easier to read.

private static final String[] PAD_ZEROS =
        new String[] {
            "00000000",
            "0000000",
            "000000",
            "00000",
            "0000",
            "000",
            "00",
            "0",
            ""
        };

private static final Map<String, String> MAP =
        new HashMap<String, String>(256);

private static void populateMap() {
    for (int i = 0; i < 256; i++) {
        final String binaryString = Integer.toBinaryString(i);
        MAP.put(
            Integer.toString(i), 
            PAD_ZEROS[binaryString.length()] + binaryString);
    }
}

public static String faster(final String ip) {
    final StringBuilder result = new StringBuilder(32);
    final String octals[] = ip.split("\\.");
    for (final String octal: octals) {
        result.append(MAP.get(octal));
    }
    return result.toString();
}

Answer 3

Your slow code is slow because of the multiple String instances you create, and replace, and so on. It is 6 times slower because you have a binString, which you then format in to a padded string (which likely has internal string representations, and then finally you search/replace values in that too.

The fast code does not have any transformations, it is simply an additive process, and Strings get created just once, and there is only one creation... of a String, and 1 creation of a char[] array

There are two ways you can improve the performance of your fast method:

1. set the initial size of the StringBuilder(...) which will always be 32.
2. create a single PAD array, and use a sub-portion of it for the results

I have the code:

private static final char[] PAD_ARRAY = new char[8];

static {
    Arrays.fill(PAD_ARRAY, '0');
}

public static String fast(String ip) {

    StringBuilder bStringBuilder = new StringBuilder(32);
    String ipParts[] = ip.split("\\.");

    for (String ipPart : ipParts) {

        String binString = Integer.toBinaryString(Integer.parseInt(ipPart));
        bStringBuilder.append(PAD_ARRAY, 0, 8 - binString.length()).append(binString);
    }
    //System.out.println(bStringBuilder.toString());
    return bStringBuilder.toString();
}

There is a different way to solve these sorts of problems, though, and that is to pre-process a chunk of the work. I was disappointed that this approach was only slightly faster than your fast version, though.

Consider this code which pre-populates an array of binary representations:

private static final String[] IPMAP = buildIPMap();
private static final String[] buildIPMap() {
    String[] ret = new String[256];
    for (int i = 0; i < ret.length; i++) {
        int[] bits = new int[8];
        for (int b = 0; b < 8; b++) {
            if ((i & (1 << b)) != 0) {
                bits[b] = 1;
            }
        }
        final String bitwords = String.format("%d%d%d%d%d%d%d%d", bits[7], bits[6], bits[5], bits[4], bits[3], bits[2], bits[1], bits[0]);
        ret[i] = bitwords;
    }
    return ret;
}

Now, you can have the following code:

public static String mapped(String ip) {
    StringBuilder sb = new StringBuilder(32);
    for (String block : ip.split("\\.")) {
        sb.append(IPMAP[Integer.parseInt(block)]);
    }
    return sb.toString();
}

In my testing, the different solutions have the following characteristics:

Task Routing -> Slow: (Unit: MICROSECONDS)
  Count    :    100000      Average  :    3.8060
  Fastest  :    2.2880      Slowest  : 9464.0360
  95Pctile :    6.3870      99Pctile :   11.6600
  TimeBlock : 8.366 4.366 5.914 3.657 2.696 2.944 2.547 2.724 2.443 2.407
  Histogram : 84962 12731  1761   277   173    81     9     0     1     4     0     0     1

Task Routing -> Fast: (Unit: MICROSECONDS)
  Count    :   100000      Average  :   0.4710
  Fastest  :   0.2910      Slowest  : 129.1240
  95Pctile :   0.7420      99Pctile :   1.9220
  TimeBlock : 1.442 0.397 0.485 0.353 0.331 0.360 0.339 0.338 0.335 0.334
  Histogram : 84577 12020  2676   294   305    95    20     4     9

Task Routing -> Mapped: (Unit: MICROSECONDS)
  Count    :    100000      Average  :    0.4540
  Fastest  :    0.2890      Slowest  : 1663.1440
  95Pctile :    0.6670      99Pctile :    1.6780
  TimeBlock : 1.392 0.381 0.441 0.341 0.334 0.342 0.327 0.331 0.327 0.331
  Histogram : 87774  9244  2313   283   297    69    13     0     6     0     0     0     1

Answer 4

One approach is to delay using strings until the last moment:

public String decimalToBinary(String decimalRepresentation) {
    String[] octets = decimalRepresentation.split("\\.");
    if (octets.length != 4)
        throw new IllegalArgumentException("Invalid IP Address: " + decimalRepresentation);
    int ipAddressValue = 0;
    for (int i = 0; i < 4; i++) {
        ipAddressValue <<= 8;
        ipAddressValue |= Integer.parseInt(octets[i]);
    }
    String binaryRepresentation = Integer.toBinaryString(ipAddressValue);
    return "00000000000000000000000000000000".substring(binaryRepresentation.length()).concat(binaryRepresentation);
}