Custom "hash table" implementation: Why is it so slow? (bytecode generation)

Question

Today, I answered an ordinary question of some Java beginner. A little bit later I thought it would be fun to take his question seriously and so I implemented exactly what he wants.

I created a simple code for runtime Class generation. Most of the code is taken from a template, the only possible change is to declare some fields. Generated code could be written as:

public class Container implements Storage {
    private int    foo; // user defined (runtime generated)
    private Object boo; // user defined (runtime generated)

    public Container() {
        super();
    }
}

The generated Class file is then loaded into the JVM using a custom ClassLoader.

Then I implemented something like "static hashtable". Programmer enters all the possible keys and then it generates a Class (where each key is as a field). In the moment we have instance of this class, we may also save or read those generated fields using reflection.

Here is a whole code:

import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Random;

class ClassGenerator extends ClassLoader {
    private ArrayList<FieldInfo> fields = new ArrayList<ClassGenerator.FieldInfo>();

    public static class FieldInfo {
        public final String   name;
        public final Class<?> type;

        public FieldInfo(String name, Class<?> type) {
            this.name = name;
            this.type = type;
        }
    }

    private static class ComponentTypeInfo {
        private final Class<?> type;
        private final int      arrayDimensions;

        public ComponentTypeInfo(Class<?> type, int arrayDimensions) {
            this.type            = type;
            this.arrayDimensions = arrayDimensions;
        }
    }

    private static ComponentTypeInfo getComponentType(Class<?> type) {
        Class<?> tmp   = type;
        int      array = 0;

        while (tmp.isArray()) {
            tmp = tmp.getComponentType();
            array++;
        }

        return new ComponentTypeInfo(tmp, array);
    }

    public static String getFieldDescriptor(Class<?> type) {
        ComponentTypeInfo componentTypeInfo  = getComponentType(type);
        Class<?>          componentTypeClass = componentTypeInfo.type;
        int               componentTypeArray = componentTypeInfo.arrayDimensions;
        String            result             = "";

        for (int i = 0; i < componentTypeArray; i++) {
            result += "[";
        }

        if (componentTypeClass.isPrimitive()) {
            if (componentTypeClass.equals(byte.class))    return result + "B";
            if (componentTypeClass.equals(char.class))    return result + "C";
            if (componentTypeClass.equals(double.class))  return result + "D";
            if (componentTypeClass.equals(float.class))   return result + "F";
            if (componentTypeClass.equals(int.class))     return result + "I";
            if (componentTypeClass.equals(long.class))    return result + "J";
            if (componentTypeClass.equals(short.class))   return result + "S";
            if (componentTypeClass.equals(boolean.class)) return result + "Z";

            throw new RuntimeException("Unknown primitive type.");
        } else {
            return result + "L" + componentTypeClass.getCanonicalName().replace('.', '/') + ";";
        }
    }

    public void addField(String name, Class<?> type) {
        this.fields.add(new FieldInfo(name, type));
    }

    private Class<?> defineClass(byte[] data) {
        return this.defineClass(null, data, 0, data.length);
    }

    private byte[] toBytes(short[] data) {
        byte[] result = new byte[data.length];

        for (int i = 0; i < data.length; i++) {
            result[i] = (byte) data[i];
        }

        return result;
    }

    private byte[] toBytes(short value) {
        return new byte[]{(byte) (value >> 8), (byte) (value & 0xFF)};
    }

    public Class<?> getResult() throws IOException {
        ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
        outputStream.write(toBytes(new short[]{
            0xCA, 0xFE, 0xBA, 0xBE, // magic
            0x00, 0x00, 0x00, 0x33, // version
        }));

        // constantPoolCount
        outputStream.write(toBytes((short) (0x0C + (this.fields.size() * 2))));

        // constantPool
        outputStream.write(toBytes(new short[]{
            0x01, 0x00, 0x09, 'C', 'o', 'n', 't', 'a', 'i', 'n', 'e', 'r',
            0x01, 0x00, 0x10, 'j', 'a', 'v', 'a', '/', 'l', 'a', 'n', 'g', '/', 'O', 'b', 'j', 'e', 'c', 't',
            0x01, 0x00, 0x06, '<', 'i', 'n', 'i', 't', '>',
            0x01, 0x00, 0x03, '(', ')', 'V',
            0x01, 0x00, 0x04, 'C', 'o', 'd', 'e',

            0x07, 0x00, 0x01, // class Container
            0x07, 0x00, 0x02, // class java/lang/Object

            0x0C, 0x00, 0x03, 0x00, 0x04, // nameAndType
            0x0A, 0x00, 0x07, 0x00, 0x08, // methodRef

            0x01, 0x00, 0x07, 'S', 't', 'o', 'r', 'a', 'g', 'e',
            0x07, 0x00, 0x0A, // class Storage
        }));

        for (FieldInfo field : fields) {
            String name            = field.name;
            String descriptor      = getFieldDescriptor(field.type);

            byte[] nameBytes       = name.getBytes();
            byte[] descriptorBytes = descriptor.getBytes();

            outputStream.write(0x01);
            outputStream.write(toBytes((short) nameBytes.length));
            outputStream.write(nameBytes);

            outputStream.write(0x01);
            outputStream.write(toBytes((short) descriptorBytes.length));
            outputStream.write(descriptorBytes);
        }

        outputStream.write(toBytes(new short[]{
            0x00, 0x01, // accessFlags,
            0x00, 0x06, // thisClass
            0x00, 0x07, // superClass
            0x00, 0x01, // interfacesCount
            0x00, 0x0B  // interface Storage 
        }));

        // fields
        outputStream.write(toBytes((short) this.fields.size()));
        for (int i = 0; i < fields.size(); i++) {
            outputStream.write(new byte[]{0x00, 0x01});
            outputStream.write(toBytes((short) (12 + 2 * i)));
            outputStream.write(toBytes((short) (12 + 2 * i + 1)));
            outputStream.write(new byte[]{0x00, 0x00});
        }

        // methods and rest of the class file 
        outputStream.write(toBytes(new short[]{
            0x00, 0x01,                     // methodsCount
                // void <init>
                0x00, 0x01,                 // accessFlags
                0x00, 0x03,                 // nameIndex
                0x00, 0x04,                 // descriptorIndex,
                0x00, 0x01,                 // attributesCount
                    0x00, 0x05,             // nameIndex
                    0x00, 0x00, 0x00, 0x11, // length
                    0x00, 0x01,             // maxStack
                    0x00, 0x01,             // maxLocals,
                    0x00, 0x00, 0x00, 0x05, // codeLength
                        0x2A,               // aload_0
                        0xB7, 0x00, 0x09,   // invokespecial #9
                        0xB1,               // return
                    0x00, 0x00,             // exceptionTableLength
                    0x00, 0x00,             // attributesCount

            0x00, 0x00,                     // attributesCount
        }));

        return defineClass(outputStream.toByteArray());
    }
}

class SuperTable<T> {
    private Class<?> generatedClass = null;
    private Storage  container      = null;

    public SuperTable(String[] keys, Class<T> type) {
        ClassGenerator classGenerator = new ClassGenerator();

        for (String key : keys) {
            classGenerator.addField(key, type);
        }

        try {
            this.generatedClass = classGenerator.getResult();
            this.container      = (Storage) generatedClass.newInstance();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }

    public void put(String name, Object value) {
        try {
            this.generatedClass.getDeclaredField(name).set(container, value);
        } catch (Exception e) {
            throw new RuntimeException("Such a field doesn't exist or is not accessible.");
        }
    }

    public Object get(String name) {
        try {
            return this.generatedClass.getDeclaredField(name).get(container);
        } catch (Exception e) {
            throw new RuntimeException("Such a field doesn't exist or is not accessible.");
        }
    }
}

public class Test {
    private static final String[] keys       = new String[(int) Math.pow(26, 3)];
    private static final Random   randomizer = new Random();

    static {
        int index = 0;

        for (char a = 'a'; a <= 'z'; a++) {
            for (char b = 'a'; b <= 'z'; b++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    keys[index] = new String(new char[]{a, b, c});
                    index++;
                }
            }
        }
    }

    public static float test1(Hashtable<String, Integer> table, long count) {
        long time0 = System.currentTimeMillis();

        for (long i = 0; i < count; i++) {
            boolean step = randomizer.nextBoolean();
            String  key  = keys[randomizer.nextInt(keys.length)];

            if (step) {
                table.put(key, randomizer.nextInt());
            } else {
                table.get(key);
            }
        }

        return System.currentTimeMillis() - time0;
    }

    public static float test2(SuperTable<Integer> table, long count) {
        long time0 = System.currentTimeMillis();

        for (long i = 0; i < count; i++) {
            boolean step = randomizer.nextBoolean();
            String  key  = keys[randomizer.nextInt(keys.length)];

            if (step) {
                table.put(key, randomizer.nextInt());
            } else {
                table.get(key);
            }
        }

        return System.currentTimeMillis() - time0;
    }

    public static void main(String[] args) throws Exception {
        Hashtable<String, Integer> table  = new Hashtable<String, Integer>();
        SuperTable<Integer>        table2 = new SuperTable<Integer>(keys, Integer.class);

        long count = 500000;

        System.out.printf("Hashtable: %f ms\n", test1(table, count));
        System.out.printf("SuperTable: %f ms\n", test2(table2, count));
    }
}

It works, but it is terribly slow. I expected it would be a little bit faster as data are stored in fields, which are manipulated by JVM (using a native code). The most serious explanation which I can think of is that reflection is extremely slow.

To make it perfectly clear, I was not going to use it anyway. Event if it actually was faster that code is so terrible and unmaintainable it would not be worth of it. A functionality is also very limited (key must be a valid field name etc). It just looked like a cool experiment.

Anyway, does anybody have an idea why is it about 100 times slower than "ordinary" hash table? I guess it is caused by a reflection, but I would appreciate other people's opinions.

Update: It is really caused by reflection as Antimony and NSF pointed out. I tried to set up some static field in the "normal" way and using reflection. According to this test, reflection is about 280 times slower. But I have no idea why.

Answer 1

OK, I got it. I thought the method getDeclaredField is native and JVM stores fields in some hash table. In such a case, my solution would be probably really very fast.

However, getDeclaredField is not native. Somehow it obtains all declared fields as an array and then, using searchFields, finds a correct one.

Here is an excerpt from the Oracle JDK:

private Field searchFields(Field[] fields, String name) {
    String internedName = name.intern();
    for (int i = 0; i < fields.length; i++) {
        if (fields[i].getName() == internedName) {
            return getReflectionFactory().copyField(fields[i]);
        }
    }
    return null;
}

From what we see, it iterates through the array and compares the names.

Now it makes sense perfectly. In the example above, there is 17 576 fields. When we assume that typically a field will be located somewhere in the middle, it give us about 8800 iterations just to locate a field.

Field's methods set and get are native neither. In some point, it must obviously fall out into the native code, but it is done much later than I expected.

So, what my code really does? Instead of using some JVM's internal hash table (which might not even exist), it actually uses an ordinary array on at least one layer.

Just from this, not even taking care of the other layers, it must be terribly slower - and it is.

Credits: Antimony and NSF for kicking in the right way.

Answer 2

reflection is normally slower by one magnitude compared to regular code as JVM cannot perform certain optimizations:

http://docs.oracle.com/javase/tutorial/reflect/index.html

Yours is an interesting approach however not practical at all I'm afraid.

Also the test might be a issue as well: notice the two test cases are executed one after another, where in the second one GC might kick in.

Answer 3

First off, standard reflection in Java is really slow. But even if it wasn't, I'm not sure why you expect this code to be fast.

Think about how the JIT would optimize this code if it was somehow smart enough to optimize across reflection and it was coded to optimize for this case. The best way to optimize it is to build a hashtable with the classname as key to look up each field behind the scenes. But at that point, you've just created a slower version of the hash table! And this is the best possible ideal case!

Further compounding the issue is that JITs are designed to optimize the common case. Noone in their right mind would ever do this, so it is unlikely to be optimized.