9
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Check out this answer, it seems to speed things up a bit, and also shortens your code. \$\endgroup\$ – tim Mar 18 '15 at 16:36
  • 2
    \$\begingroup\$ Each octet only has 256 different values. Precompute a Map<String, String> for this. \$\endgroup\$ – Thorbjørn Ravn Andersen Mar 18 '15 at 23:14
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is amazing, and exactly the kind of code needed to do the job! It cut my original 2-minute run on 14.5 million IPs to just 21 seconds, including processing the input file and building the Trie. @rolfl had good improvements as well, but this one takes the cake. Since it's just a utility method, I don't mind the implementation being a bit more complicated with the binary operations :) \$\endgroup\$ – Chris Cirefice Mar 23 '15 at 17:00
10
\$\begingroup\$

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();
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I considered a raw use of a Map as well, it is actually significantly slower than the alternatives, because it requires the hashCode() and equals() calculation of each value created. It's slow.. ;-) \$\endgroup\$ – rolfl Mar 18 '15 at 17:29
  • \$\begingroup\$ I believe it. I only tested against his original methods, not yours. \$\endgroup\$ – Eric Stein Mar 18 '15 at 17:55
  • 4
    \$\begingroup\$ 8 bits/byte is not a magic number. If I see something converting a number to binary, 8 isn't a "magic" number. Are you saying if I (hypothetically) want to print out a number's binary representation, I should replace the 8 in void printBinary(int num) { for (int i = 0; i < 8; i++) { System.out.println(num >> 7); num <<= 1; } } with BITS_PER_BYTE? Because that's just ridiculous \$\endgroup\$ – Cole Johnson Mar 18 '15 at 20:37
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I think the reason the performance isn't that much better may be that you still have to parse the String into an int even though the input and output are both Strings. \$\endgroup\$ – Eric Stein Mar 18 '15 at 17:07
  • \$\begingroup\$ This line: if ((i & (1 << b)) == 1) { should be if ((i & (1 << b)) != 0) {. I know this because I actually built and ran your program. \$\endgroup\$ – JS1 Mar 19 '15 at 9:23
1
\$\begingroup\$

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);
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.