10
\$\begingroup\$

Can somebody please try and help me speed up my code? The file is ~12MB (you can download it here). It takes around 500-600 milliseconds to run on my i7 4790k.

import java.io.FileInputStream;
import java.math.BigInteger;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Created by Jonathan on 4/1/2016.
 */
public class HexDumper {

    public static void main(String[] args) throws Exception {
        Deque<String> lines = new ArrayDeque<>(1_000_000);
        lines.add("Address  00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F\n");

        long s = System.currentTimeMillis();
        FileChannel channel = new FileInputStream("client.dll").getChannel();
        ByteBuffer buffer = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size());
        byte[] bytes = new byte[16];
        int offset = 0;
        while (buffer.remaining() > 0) {
            buffer.get(bytes);
            lines.add(new DataRow(offset, bytes).toString());
            offset += 16;
        }

        System.out.println(System.currentTimeMillis() - s);
        Files.write(Paths.get("dump.txt"), lines);
    }

    public static class DataRow {

        private final int offset;
        private final byte[] values;

        public DataRow(int offset, byte[] values) {
            this.offset = offset;
            this.values = values;
        }

        public int offset() {
            return offset;
        }

        public byte[] values() {
            return values;
        }

        private  final static char[] HEX_ARRAY = "0123456789ABCDEF".toCharArray();

        private static String bytesToHex(byte[] bytes, int bundleSize) {
            char[] hexChars = new char[(bytes.length * 2) + (bytes.length / bundleSize)];
            for (int j = 0, k = 1; j < bytes.length; j++, k++) {
                int v = bytes[j] & 0xFF;
                int idx = (j * 2) + j / bundleSize;

                hexChars[idx] = HEX_ARRAY[v >>> 4];
                hexChars[idx + 1] = HEX_ARRAY[v & 0x0F];
                if ((k % bundleSize) == 0) {
                    hexChars[idx + 2] = ' ';
                }
            }
            return new String(hexChars).trim();
        }

        @Override
        public String toString() {
            String row = "0000000000000" + bytesToHex(BigInteger.valueOf(offset).toByteArray(), 4);
            row = row.substring(row.length() - 8) + " ";
            row += bytesToHex(values, 1);
            return row;
        }
    }

}

Is it possible to make it dump the hex values any faster? I've tried other hex editors both Java and C++ and they seem to scan the file instantly.

\$\endgroup\$
6
\$\begingroup\$

The slowness

For each 16 bytes, the program creates:

  • a new DataRow object
  • a BigInteger
  • a char[]
  • several String

Yeah I can see how that might be slow with large inputs...

Memory use

The program is not very streamlined. It reads all the input in memory, builds the output in the desired format, and finally print everything. You could reduce the memory footprint dramatically by printing as you go. (Eliminate the Deque.)

Design

The toString method is not designed for advanced custom formatting. It's designed to return a simple and fast representation, typically used in debugging. For the purpose of formatting the data in an object in a custom format, it's recommended to have a dedicated method.

Instead of a class containing a value and an offset that is used only once when formatting, it would be more natural to have a simple utility function that takes these values as parameters.

Suggested implementation

This function returns the same as new HexDumper.DataRow(...)), but a lot simpler:

private String hexdumpLine(int offset, byte[] bytes) {
    StringBuilder builder = new StringBuilder(8 + 3 * 16);
    builder.append(String.format("%08X", offset));
    for (byte b : bytes) {
        builder.append(' ').append(String.format("%X", b));
    }
    return builder.toString();
}

The simplicity comes from the "cheat", using String.format("%X", ...) for the hexadecimal representation, and for the 0-padding of the address.

Unfortunately, String.format is slow, and according to your measurements this solution is actually slower than your original. So we're better off hand-crafting that part instead:

private String hexdumpLine(int offset, byte[] bytes) {
    StringBuilder builder = new StringBuilder(8 + 3 * 16);
    appendPaddedHexFormat(builder, offset);
    for (byte b : bytes) {
        builder.append(' ')
                .append(toHexDigit((b >> 4) & 0xF))
                .append(toHexDigit(b & 0xF));
    }
    return builder.toString();
}

private char toHexDigit(int value) {
    return HEX_ARRAY[value];
}

private void appendPaddedHexFormat(StringBuilder builder, int offset) {
    builder.setLength(8);
    int value = offset;
    for (int i = 7; i >= 0; --i) {
        builder.setCharAt(i, toHexDigit(value & 0xF));
        value >>= 4;
    }
}

This should be faster than the original, because it creates much fewer objects. As a further optimization, you could reuse the same StringBuilder by calling setLength(0) after (or before) each use.

\$\endgroup\$
  • \$\begingroup\$ Using String.format for some reason adds almost 10x latency to my program (~500ms using my current method, ~5000ms using String.format). \$\endgroup\$ – Jonathan Beaudoin Apr 2 '16 at 18:56
  • \$\begingroup\$ @JonathanBeaudoin I optimized a bit further. \$\endgroup\$ – janos Apr 3 '16 at 8:01
  • \$\begingroup\$ You may increase the speed and memory usage by reusing the StringBuilder, and using StringBuilder.getChars to write the stringbuilder to a reused char array so you don't need to make new strings to throw away \$\endgroup\$ – Ferrybig Apr 6 '16 at 7:18
1
\$\begingroup\$

If anyone is curious on the progress I made, I decided to switch it to Kotlin and I optimized it a ton. It now completes the exact same task as OP in 200-320ms

What changed? My first objective was to remove the numerous amounts of redundant object creation for every row of 16 bytes in the file. My first example was creating a new HexRow, BigInteger, char[], String objects which in even in a relatively small file (12mb), was generating millions of these types of objects.

So as you can see in the example below:

  • I removed the need for a Deque since I write to the BufferedWriter as I complete each iteration
  • I removed the need for the internal class since I can just call the bytesToHex method directly.
  • I also made a char[] cache which is reused over and over so only two objects are made.
  • Lastly, I removed the need to create BigIntegers since I convert the int directly to a reusable byte[]
  • I switched to using System.arrayCopy and copying the bytes of the file 16 bytes at a time into a reusable byte[] and used System.arrayCopy to copy data from the filedata into the bytes[]

List item

package com.beaudoin

import com.google.common.primitives.Ints
import java.io.BufferedWriter
import java.io.FileInputStream
import java.io.FileWriter
import java.io.PrintWriter
import java.nio.channels.FileChannel

fun main(args: Array<String>) {
    val s = System.currentTimeMillis()

    val channel = FileInputStream("client.dll").channel
    val buffer = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size())
    val data = ByteArray(buffer.capacity())
    buffer.get(data)

    val writer = PrintWriter(BufferedWriter(FileWriter("dump.txt", false)))
    val bytes = ByteArray(16)

    for (offset in data.indices step 16) {
        System.arraycopy(data, offset, bytes, 0, bytes.size);
        writer.println(bytesToHex(offset, 4, offsetCharCache) + bytesToHex(bytes, 1, bytesCharCache))
    }
    println(System.currentTimeMillis() - s)
}

fun bytesToHex(value: Int, width: Int, hexChars: CharArray) = bytesToHex(Ints.toByteArray(value), width, hexChars)

fun bytesToHex(bytes: ByteArray, width: Int, hexChars: CharArray = CharArray(((bytes.size * 2) + (bytes.size / width)))): String {
    for (i in bytes.indices) {
        val v = bytes[i].toInt() and 0xFF
        val idx = (i * 2) + i / width

        hexChars[idx] = HEX_ARRAY[v.ushr(4)]
        hexChars[idx + 1] = HEX_ARRAY[v and 0x0F]
        if (idx + 2 < hexChars.size) {
            hexChars[idx + 2] = ' '
        }
    }
    return String(hexChars);
}

private val HEX_ARRAY = "0123456789ABCDEF".toCharArray()
private val offsetCharCache = CharArray(9)
private val bytesCharCache = CharArray(48)
\$\endgroup\$
  • \$\begingroup\$ A answer on Code Review SE should include a explanation of the changed codes, and the reasons why it's faster. You should edit your answer to include this information. Answers that don't include a explanation are not really a code review, but rather a "use this and it will work" kind of answer. \$\endgroup\$ – Ferrybig Apr 6 '16 at 7:22
  • \$\begingroup\$ @Ferrybig I've modified the answer. Is this more acceptable in regards to codereview etiquette? \$\endgroup\$ – Jonathan Beaudoin Apr 6 '16 at 17:49

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.