java - Custom "hash table" implementation: Why is it so slow? (bytecode generation) -
today, answered ordinary question of java beginner. little bit later thought fun take question , implemented wants.
i created simple code runtime class generation. of code taken template, possible change declare fields. generated code 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 loaded jvm using custom classloader.
then implemented "static hashtable". programmer enters possible keys , generates class (where each key field). in moment have instance of class, may save or read generated fields using reflection.
here 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 = ""; (int = 0; < 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]; (int = 0; < 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 })); (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())); (int = 0; < fields.size(); i++) { outputstream.write(new byte[]{0x00, 0x01}); outputstream.write(tobytes((short) (12 + 2 * i))); outputstream.write(tobytes((short) (12 + 2 * + 1))); outputstream.write(new byte[]{0x00, 0x00}); } // methods , rest of 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(); (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 field doesn't exist or not accessible."); } } public object get(string name) { try { return this.generatedclass.getdeclaredfield(name).get(container); } catch (exception e) { throw new runtimeexception("such field doesn't exist or 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; (char = 'a'; <= 'z'; a++) { (char b = 'a'; b <= 'z'; b++) { (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(); (long = 0; < 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(); (long = 0; < 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, terribly slow. expected little bit faster data stored in fields, manipulated jvm (using native code). serious explanation can think of reflection extremely slow.
to make clear, not going use anyway. event if faster code terrible , unmaintainable not worth of it. functionality limited (key must valid field name etc). looked cool experiment.
anyway, have idea why 100 times slower "ordinary" hash table? guess caused reflection, appreciate other people's opinions.
update: caused reflection antimony , nsf pointed out. tried set static field in "normal" way , using reflection. according test, reflection 280 times slower. have no idea why.
reflection slower 1 magnitude compared regular code jvm cannot perform optimizations:
http://docs.oracle.com/javase/tutorial/reflect/index.html
yours interesting approach not practical @ i'm afraid.
also test might issue well: notice 2 test cases executed 1 after another, in second 1 gc might kick in.
Comments
Post a Comment