"Structs" proposal: Stored objects

[AndersD]

Not sure if this at all is what people, hmm Cas and others, have been thinking about. But I had some spare time this week and sat down trying to do a solution to the problem of mapping java object fields to memory. I found a "solution" consisting of part DirectByteBuffers or sun.misc.Unsafe hacking and javassisst bytecode manipulation library. This is just a first attempt and I'm releasing it now with the hope of getting enough input to settle if its worth continue working on!

The files can be found here http://www.lysator.liu.se/~dahlberg/storedobjects.zip  beware of lousy programming and very sparse documentation (even though javadoc is included, it's quality is actually worse than sun's java.nio docs - unbelivable!

Best way to understand what I'm trying to achieve is probably to sit down and play around with the code. To wet your appetite here is a sample:

private static List<? extends Point> unsafeNoRefsStoredPoints = 
        	StoredObjectFactory.createStoredObjectList("se.liu.lysator.dahlberg.storedobject.example.UnsafePoint", 
        	        SIZE, new NoRefsUnsafeStoragePolicy<UnsafePoint>()); 
    
    private static List<? extends Point> bufferNoRefsStoredPoints = 
        	StoredObjectFactory.createStoredObjectList("se.liu.lysator.dahlberg.storedobject.example.BufferPoint", 
        	        SIZE, new NoRefsBufferStoragePolicy<BufferPoint>());   

// ...
private static void checkPerformance(List<? extends Point> points, String name) {
        int total = 0;
        for (int nr = 0; nr < points.size(); nr++) {
            Point point = points.get(nr);
		    
            // int-field:
            int y = point.getIntField();
            point.setIntField(nr);
	    int squareOfY = point.squareOfIntField();
	    y = point.getIntField();
	    total += y + squareOfY;

// ...
public class BufferPoint extends BufferObject implements Point {
    private int y;
    //...
    public int squareOfIntField() {
        return y*y;
    }
// ....

It's probably easier to understand if you load the files available in the zip above in your favourite editor/IDE and start hacking. If you're only interested in some results you can run the jar-file provided with java -jar storedobjects.jar (provided you have extracted javassisst.jar in the same directory).

Running with the above shown StoragePolicies yields Unsafe approx. 25-50% slower than a regular populated arraylist, whereas DirectByteBufffers suffer a bit more and is roughly 3-4 times slower than the arraylist. NoRefs...StoragePolicy implies that all data is accessed through a single ...Point object (only the Point's internal base offset/address is changed depending on which elementet that is accessed - should work fine if you're only interested in looping through the elements and doing some simple calculations etc).

P.S. Don't bother with trying to understand why the data classes are called ...Point - they used to be just that but evolved

[AndersD]

Since I haven't got any  replies I decided to refactor most of the design and make the "library", well..., a little easier to use (I hope).

Here is a new example:

public class VectorExample {
    private static final int SIZE = 100000;
    private static final int ITER = 10;
    
    public static void main(String[] args) {
        
        long seed = args.length == 1 ? Integer.parseInt(args[0]) : 17;
        Random normalRandom = new Random(seed);
        Random storedRandom = new Random(seed);
        
        ByteBuffer normalStorage = ByteBuffer.allocateDirect(SIZE * 3 * 4).order(ByteOrder.nativeOrder());
        ByteBuffer storedStorage = ByteBuffer.allocateDirect(SIZE * 3 * 4).order(ByteOrder.nativeOrder());
        
        String className = "se.liu.lysator.dahlberg.storedobject.example.Vector3f";
        List<Vector3f> vectors = StoredObjectFactory.bindBuffer(className, storedStorage);
        
        for (int i = 0; i < ITER; i++) {
            long start = System.nanoTime();
            storeWithoutStoredObject(normalRandom, normalStorage);
            double sum = sumAbsWithoutStoredObject(normalStorage);
            long end = System.nanoTime();
            long time = (end - start) / 1000000; // Millis
            System.out.println("Normal sum one: " + sum);
            System.out.println("Normal storage: " + time + "ms");
            
            start = System.nanoTime();
            storeWithStoredObject(storedRandom, vectors);
            sum = sumAbsWithStoredObject(vectors);
            end = System.nanoTime();
            time = (end - start) / 1000000; // Millis
            System.out.println("Stored sum one: " + sum);
            System.out.println("Stored storage: " + time + "ms");
            
            System.out.println();
            
            start = System.nanoTime();
            normalizeWithoutStoredObject(normalStorage);
            sum = sumAbsWithoutStoredObject(normalStorage);
            end = System.nanoTime();
            time = (end - start) / 1000000; // Millis
            System.out.println("Normal sum two: " + sum);
            System.out.println("Normal storage: " + time + "ms");
            
            start = System.nanoTime();
            normalizeWithStoredObject(vectors);
            sum = sumAbsWithStoredObject(vectors);
            end = System.nanoTime();
            time = (end - start) / 1000000; // Millis
            System.out.println("Stored sum two: " + sum);
            System.out.println("Stored storage: " + time + "ms");
            
            System.out.println("===");
        }
        
        System.out.println("Testing \"interop\": ");
        
        storedStorage.position(0).limit(storedStorage.capacity());
        double storedSum = sumAbsWithoutStoredObject(storedStorage);
        double normalSum = sumAbsWithoutStoredObject(normalStorage);
        System.out.println("Normal: " + normalSum);
        System.out.println("Stored: " + storedSum);
    }


    private static void storeWithoutStoredObject(Random random, ByteBuffer buffer) {
        for (int i = 0; i < SIZE; i++) {
            float x = random.nextFloat() * 5;
            float y = random.nextFloat() * 5;
            float z = random.nextFloat() * 5;
            buffer.putFloat(x);
            buffer.putFloat(y);
            buffer.putFloat(z);
        }
        buffer.flip();
    }

    private static void normalizeWithoutStoredObject(ByteBuffer buffer) {
        for (int i = 0; i < SIZE; i++) {
            float x = buffer.getFloat();
            float y = buffer.getFloat();
            float z = buffer.getFloat();
            float abs = (float) Math.sqrt(x*x + y*y + z*z);
            int position = buffer.position() - 4*3;
            buffer.position(position);
            buffer.putFloat(x / abs);
            buffer.putFloat(y / abs);
            buffer.putFloat(z / abs);
        }
        buffer.flip();
    }
    
    private static double sumAbsWithoutStoredObject(ByteBuffer buffer) {
        double total = 0;
        for (int i = 0; i < SIZE; i++) {
            float x = buffer.getFloat();
            float y = buffer.getFloat();
            float z = buffer.getFloat();
            float sum = (float) Math.sqrt(x*x + y*y + z*z);
            total += sum;
        }
        buffer.flip();
        return total;
    }
    
    private static void storeWithStoredObject(Random random, List<Vector3f> vectors) {
        for (int i = 0; i < SIZE; i++) {
            float x = random.nextFloat() * 5;
            float y = random.nextFloat() * 5;
            float z = random.nextFloat() * 5;
            vectors.get(i).set(x,y,z);
        }
    }

    private static void normalizeWithStoredObject(List<Vector3f> vectors) {
        for (int i = 0; i < SIZE; i++) {
            vectors.get(i).normalize();
        }
    }
    
    private static double sumAbsWithStoredObject(List<Vector3f> vectors) {
        double total = 0;
        for (int i = 0; i < SIZE; i++) {
            total += vectors.get(i).abs();
        }
        return total;
    }
}

public class Vector3f {
    // Direct field access not supported.
    private float x;
    private float y;
    private float z;
    
    public float getX() { return x; }
    public float getY() { return y; }
    public float getZ() { return z; }
    
    public void set(float x, float y, float z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
    
    public void normalize() {
        float abs = abs();
        x = x / abs;
        y = y / abs;
        z = z / abs;
    }

    public float abs() {
        return (float) Math.sqrt(x*x + y*y + z*z);
    }
}

Example code output is:

Normal sum one: 480355.90599921346
Normal storage: 150ms
Stored sum one: 480355.90599921346
Stored storage: 161ms

Normal sum two: 99999.99816596508
Normal storage: 143ms
Stored sum two: 99999.99816596508
Stored storage: 143ms
===
<snip>
===
Normal sum one: 481013.50420615077
Normal storage: 120ms
Stored sum one: 481013.50420615077
Stored storage: 88ms

Normal sum two: 99999.99817299843
Normal storage: 109ms
Stored sum two: 99999.99817299843
Stored storage: 70ms
===
Testing "interop": 
Normal: 99999.99817299843
Stored: 99999.99817299843

Code and executable jar are available here: http://www.lysator.liu.se/~dahlberg/storedobject-v2.jar . Note that you need the javassist library too (available here http://www.lysator.liu.se/~dahlberg/javassist.jar ).

This discussion should probably be moved to General Java Game Development?

EDIT: trailing [/code] removed