Tag Archives: java

TDME2 – The port of my JAVA based 3D engine to C++11 using J2C

1. Introduction

This is a short (success) story of porting my 3D engine, named TDME, from JAVA 1.6 to C++11.

To introduce myself a bit I can tell that I became in 2010 jobwise and by accident part of a 20-25 man power team that created browser games.

I did this for 3+ years, while playing a key role doing backend stuff, and came to the conclusion that creating games was the most interesting, challenging and also most fun thing to do.

For some reasons I decided in 2012 that I wanted to dig deeper. My interest ranged from multiplayer network code to 3D realtime rendering and such as alternative efficient data storage than relational databases.

Then I just started to develop TDME as a hobby project, which means doing a lot of research, doing a lot of trial and error and just do programming with a strong hands on mentality. This way I got a small JAVA based 3D visualization engine with some basic physics system built in which included e.g. collision detection.

On the backend side a friend of mine helped out and ported parts of the JAVA based TDME engine like collision detection to C++. Later I added network code. TDMECPP was born.

Yes, my luck was that I had some mates with me all the time that were kind enough to support me. Some of them still do and I am very thankful for that. They provided art assets, did game design and helped out gaining ideas for tools and such.

Then we actually decided to create a 3D realtime multiplayer game which type is known as MOBA.

Soon we had a game prototype that even had a multiplayer game mode included.

And now we get to the point. It turned out that doing such kind of game with JAVA in frontend (and C++ in backend) was not the best idea.

2. The issues with TDME/JAVA

2.1 Garbage collection

I had to fight garbage collection which blocked the frontend unpredictable for
even a second sometimes which is bad for such kind of game.

There was this one idea to fix this by allocating all the memory required on game session start up and never release it until the game session was finished, which improved the situation but lead to e.g. ugly code. At the end I decided that this approach was not good enough.

2.2. JIT

One minor thing was also that you could watch getting logic being handled by JIT step by step. Means logic would take some more time if being executed first and later be faster.
Not that big issue but still an issue. The idea to work around that was to have a warm up run or something similar. But I never tried.

2.3. Multi threading

There were some other hacks required because this way getting feasible multi threading ready logic was harder to implement as this kind of code was not renentrant by default even if it could be in C++ easily.

The game was multithreaded. It had one thread for visualization engine, one for game logic plus physics and one for path finding.

2.4. Network latency

Another issue was that frontend network code had too high network latency which I had no influence on as I was just using JAVA functionality. Using JNI and roll something own was not an option for me for various reasons.

2.5. SIMD

Another very valid point is that JAVA does not allow to do SIMD explicitly.

2.6. JAVA and C++ in the same project

Last point is that having C++ in backend and JAVA in frontend means that you can not share code between them thus having game logic twice. And I just did not wanted to do JNI or such.

3. The C++ port

I decided to try a complete C++ port of TDME. Meanwhile TDME had approximatively a 2 MB big codebase. So I searched the web for a JAVA to C++ translator and found J2C. I also checked the option to compile JAVA to native executables but found nothing feasible.

3.1. What does J2C do by default?

J2C is a Eclipse plugin for JAVA 1.6. Basically It is able to parse the sources of a JAVA project into a AST / syntax tree and prints this tree as C++11 into a new project. The generated project also includes a working makefile as well as JRE classes with empty definitions that are required by the project being ported.

You need to know first that during the whole process the top priority was to get a part running first, then fix or improve things, and test if it still works. This way the port might have taken a bit longer but it was the safest way.

3.2. What did I do to adapt J2C to suite the needs

  • parse JAVADOC and add it into method declaration in header files
  • do not use full namespace in definitions or declarations, always import classes in header of files
  • .hpp -> .h
  • removed null pointer checks (and thus throwing NullPointerExeption)
  • some other minor things

3.3. Port pre process

  • Namespace root simplification net.drewke.tdme -> tdme
  • use as less as possible JAVA classes
    • use own ArrayList, HashMap, Console, … classes
  • Rename some classes to avoid name collision

3.4. Port post process

  • not 100% of the generated code did compile, there were problems with a few files, but they were easy to fix
  • remove JOGAMP
    • use OpenGL and OpenAL instead
    • replace it with GLUT for Window management, GL context initialization and HID events
  • implement required generated JRE classes/methods, because they get not implemented by J2C!
  • import code from TDMECPP like
    • jsonbox
    • tinyXML
  • get rid of JAVA API usage for accessing JSON and XML files and use the above
  • replace JAVA data containers with STL data containers like std::vector, std::map
  • get completely rid of java::lang::String and friends, rather use std::wstring
  • remove dependency of each class from java::lang::Object and it methods
  • refactor left required classes from JRE into tdme::utils and use them instead of JRE ones
  • get completely rid of JRE classes and remove them
  • refactor static class initialization methods to static variable definitions
  • convert engine to use std::string instead of std::wstring
  • use call/return by reference and constness for various classes like std::string, tdme::math::*
  • convert J2C constructor (structure) to ordinary C++ constructors
  • do memory management
    • put variables on stack instead of heap where appropriate
      • J2C creates everything on heap
    • implement destructors to release memory eventually
  • Include and use 3rd party libraries for certain JAVA functionality, e.g.
    • libpng for loading textures
    • vorbis/ogg for audio package
    • pthreads for multi threading
  • do inlining where appropriate
  • convert JAVA protected package modifier, which has been transformed to C++ by just using C++ public modifier, to be implemented via friend class relatationship
  • manually transfer TDME code comments to TDME2 because Eclipse AST / syntax tree does not contain them thus J2C can just not do it

4. Where are we now?

TDME2 is the result of TDME(-JAVA) port to C++11 and TDMECPP. Check its GitHub site.
It already has lots of stuff build in. But please note that TDME2 had no release yet.
A bit of stuff is still left to finish the port. SIMD is missing still too.
But I already continued development on TDME2, as requirements were added, like adding FBX model file support with FBXSDK and much more.

One very good side effect is that now I can now port the engine to other platforms where JAVA is not available or parts of its eco system like JOGAMP.
E.g. I plan to port the engine to Haiku and maybe NetBSD. Lets see.

Yes. I love open source software and open source operating systems.
TDME2 already runs on MacOSX, Windows and Linux.

Now I use the engine for a new game that I am developing with our team. It already works great!!!

I am btw. currently hired to port a medium sized Flash game to OpenFL/Haxe.
Somebody seems to have faith in my porting abilities. 🙂

FYI: This whole process took about 4 months!!!

5. Links

Iterating hash map values, keys without iterator allocations / JAVA

1. The problem

Nobody likes lags. So for some (real time) applications like real time rendered 3D games it is nessessary to avoid memory allocations and garbage collection when beeing e.g. ingame as GC might block your game just when you do not need or want it.

Additionally there is no way to control garbage collection in standard JVMs.

When profiling your application with tools like Visual VM (http://visualvm.java.net) you will notice iterators very fast as one main cause for frequent garbage collection.

While you can work around creating iterators of ArrayList using simple old for loops like


	//
	ArrayList arrayList = new ArrayList();
	arrayList.add("Blues");
	arrayList.add("Rock ann Roll");
	arrayList.add("Swing");

	// avoids creating an iterator
	for (int i = 0; i < 3; i++)
	for (int j = 0; j < arrayList.size(); j++) {
		String value = arrayList.get(j);
		System.out.println(value);
	}

	// will create 3 iterators!
	for (int i = 0; i < 3; i++)
	for (String value : arrayList) {
		System.out.println(value);
	}

you simply can not work around looping over keys or values within a java.util.HashMap.

The following code will always create iterators on heap!


	// create hash map
	HashMap<string, string=""> hashMap = new HashMap<string, string="">();
	hashMap.put("1", "Blues");
	hashMap.put("2", "Rock and roll");
	hashMap.put("3", "Swing");

	// iterate values, will create 3 iterators!
	for (int i = 0; i < 3; i++)
	for (String value : hashMap.values()) {
		System.out.println(value);
	}

	// iterate keys, will create 3 iterators!
	for (int i = 0; i < 3; i++)
	for (String key : hashMap.keySet()) {
		System.out.println(key);
	}

	// iterate entries, will create 3 iterators!
	for (int i = 0; i < 3; i++)
	for (Map.Entry<string, string=""> entry : hashMap.entrySet()) {
		System.out.println(entry.getKey() + ":" + entry.getValue());
	}

2. The solution

As there is no way to avoid creating iterators in theses cases I just programmed an own unordered hash map which is set up to reuse a single values and key iterator.

There is one drawback as you can not do nesting with the same hash map iterator in it self which is rarely required.

Basically a hash map does some kind of partition based on a hash function (which is provided e.g. in String.hashCode(), …, Object.hashCode())

Here it is called buckets. Each bucket can contain several key value pairs.
The bucket is identified by the hash function of the key object. The key value pair is finally identified by Object.equals() in a bucket as a bucket can contain multiple key value pairs.

The number of buckets always equals the number of elements stored in a hash map.

In best case you would have N buckets for N elements and each bucket would contain a single key value pair.
In this case the complexity for put, get, remove would be O(1). With collisions (means multiple key value pairs in one bucket) complexity will have a little O(n) shadow.


    package net.drewke.tdme.utils;

    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.Map;

    /**
     * Hashmap which keeps track of keys and values in a array list
     * @author Andreas Drewke
     *
     * @param 
     * @param 
     */
    public class HashMap<K,V> {

            /**
             * Values Iterator 
             * @author Andreas Drewke
             * @param 
             * @param 
             */
            public static class ValuesIterator<K,V> implements Iterator, Iterable {

                    private HashMap<K,V> hashMap;
                    private int bucketIdx;
                    private int keyValuePairIdx;
                    private int elementIdx;

                    /**
                     * Public constructor
                     * @param hashmap
                     */
                    public ValuesIterator(HashMap<K,V> hashmap) {
                            this.hashMap = hashmap;
                            reset();
                    }

                    /**
                     * Reset
                     * @return this iterator
                     */
                    public Iterator reset() {
                            this.bucketIdx = 0;
                            this.keyValuePairIdx = 0;
                            this.elementIdx = 0;
                            return this;
                    }

                    /*
                     * (non-Javadoc)
                     * @see java.lang.Iterable#iterator()
                     */
                    public Iterator iterator() {
                            return reset();
                    }

                    /*
                     * (non-Javadoc)
                     * @see java.util.Iterator#hasNext()
                     */
                    public boolean hasNext() {
                            return elementIdx < hashMap.elements;
                    }

                    /*
                     * (non-Javadoc)
                     * @see java.util.Iterator#next()
                     */
                    public V next() {
                            while (bucketIdx < hashMap.buckets.size()) {
                                    ArrayList<Pair<K,V>> bucket = hashMap.buckets.get(bucketIdx);
                                    if (keyValuePairIdx == bucket.size()) {
                                            keyValuePairIdx = 0;
                                            bucketIdx++;
                                    } else {
                                            Pair<K,V> keyValuePair = bucket.get(keyValuePairIdx++);
                                            elementIdx++;
                                            return keyValuePair.value;
                                    }
                            }
                            return null;
                    }
            }

            /**
             * Keys Iterator 
             * @author Andreas Drewke
             * @param 
             * @param 
             */
            public static class KeysIterator<K,V> implements Iterator, Iterable {

                    private HashMap<K,V> hashMap;
                    private int bucketIdx;
                    private int keyValuePairIdx;
                    private int elementIdx;

                    /**
                     * Public constructor
                     * @param hashmap
                     */
                    public KeysIterator(HashMap<K,V> hashmap) {
                            this.hashMap = hashmap;
                            reset();
                    }

                    /**
                     * Reset
                     * @return this iterator
                     */
                    public Iterator reset() {
                            this.bucketIdx = 0;
                            this.keyValuePairIdx = 0;
                            this.elementIdx = 0;
                            return this;
                    }

                    /*
                     * (non-Javadoc)
                     * @see java.lang.Iterable#iterator()
                     */
                    public Iterator iterator() {
                            return reset();
                    }

                    /*
                     * (non-Javadoc)
                     * @see java.util.Iterator#hasNext()
                     */
                    public boolean hasNext() {
                            return elementIdx < hashMap.elements;
                    }

                    /*
                     * (non-Javadoc)
                     * @see java.util.Iterator#next()
                     */
                    public K next() {
                            while (bucketIdx < hashMap.buckets.size()) {
                                    ArrayList<Pair<K,V>> bucket = hashMap.buckets.get(bucketIdx);
                                    if (keyValuePairIdx == bucket.size()) {
                                            keyValuePairIdx = 0;
                                            bucketIdx++;
                                    } else {
                                            Pair<K,V> keyValuePair = bucket.get(keyValuePairIdx++);
                                            elementIdx++;
                                            return keyValuePair.key;
                                    }
                            }
                            return null;
                    }
            }

            /**
             * @author Andreas Drewke
             * @param 
             * @param 
             */
            private static class Pair<K,V> {
                    private K key;
                    private V value;
            }

            private int capacity = 256;
            private int elements = 0;
            private ArrayList<ArrayList<Pair<K,V>>> buckets = new ArrayList<ArrayList<Pair<K,V>>>();
            private HashMap.ValuesIterator<K,V> valuesIterator = new ValuesIterator<K,V>(this);
            private HashMap.KeysIterator<K,V> keysIterator = new KeysIterator<K,V>(this);

            /**
             * Public constructor
             */
            public HashMap() {
                    for (int i = 0; i < capacity; i++) {
                            buckets.add(new ArrayList<Pair<K,V>>());
                    }
            }

            /**
             * Clears this hash table
             */
            public void clear() {
                    elements = 0;
                    for (int i = 0; i < capacity; i++) {
                            buckets.get(i).clear();
                    }
            }

            /**
             * Grow hash map
             */
            private void grow() {
                    // store old buckets
                    ArrayList<ArrayList<Pair<K,V>>> oldBuckets = buckets;

                    // create new buckets
                    buckets = new ArrayList<ArrayList<Pair<K,V>>>();
                    capacity*= 2;
                    elements = 0;
                    for (int i = 0; i < capacity; i++) {
                            buckets.add(new ArrayList<Pair<K,V>>());
                    }

                    // recreate bucket table
                    for (int i = 0; i < oldBuckets.size(); i++) {
                            ArrayList<Pair<K,V>> bucket = oldBuckets.get(i);
                            for (int j = 0; j < bucket.size(); j++) {
                                    Pair<K,V> keyValuePair = bucket.get(j);
                                    put(keyValuePair.key, keyValuePair.value);
                            }
                    }
            }

            /**
             * Get the associated value of given object / key
             */
            public V get(K key) {
                    ArrayList<Pair<K,V>> bucket = buckets.get(Math.abs(key.hashCode()) % capacity);
                    for (int i = 0; i < bucket.size(); i++) {
                            Pair<K,V> keyValuePair = bucket.get(i);
                            if (keyValuePair.key.equals(key)) return keyValuePair.value;  
                    }
                    return null;
            }

            /**
             * Removes associated value of given object / key
             */
            public V remove(K key) {
                    ArrayList<Pair<K,V>> bucket = buckets.get(Math.abs(key.hashCode()) % capacity);
                    for (int i = 0; i < bucket.size(); i++) {
                            Pair<K,V> keyValuePair = bucket.get(i);
                            if (keyValuePair.key.equals(key)) {
                                    bucket.remove(i);
                                    elements--;
                                    return keyValuePair.value;  
                            }
                    }
                    return null;
            }

            /**
             * Put given value with associated key into this hash map
             */
            public V put(K key, V value) {
                    if (elements + 1 >= buckets.size()) grow();
                    V oldValue = remove(key);
                    ArrayList<Pair<K,V>> bucket = buckets.get(Math.abs(key.hashCode()) % capacity);
                    Pair<K,V> keyValuePair = new Pair<K,V>();
                    keyValuePair.key = key;
                    keyValuePair.value = value;
                    bucket.add(keyValuePair);
                    elements++;
                    return oldValue;
            }

            /**
             * @return number of elements
             */
            public int size() {
                    return elements;
            }

            /**
             * @return Values Iterator
             */
            public ValuesIterator<K,V> getValuesIterator() {
                    valuesIterator.reset();
                    return valuesIterator;
            }

            /**
             * @return Keys Iterator
             */
            public KeysIterator<K,V> getKeysIterator() {
                    keysIterator.reset();
                    return keysIterator;
            }

            /*
             * (non-Javadoc)
             * @see java.lang.Object#toString()
             */
            public String toString() {
                    String string = new String();
                    for (int i = 0; i < buckets.size(); i++) {
                            ArrayList<Pair<K,V>> bucket = buckets.get(i);
                            for (int j = 0; j < bucket.size(); j++) {
                                    Pair<K,V> keyValuePair = bucket.get(j);
                                    if (string.length() > 0) string+=", ";
                                    string+= keyValuePair.key + "=" + keyValuePair.value;
                            }
                    }
                    string ="HashMap[" + string + "]";
                    return string;
            }

    }

With the own hash map implementation you can iterate over values and keys while allocating no new iterators as they are reused:


	// create hash map
	HashMap<string, string=""> hashMap = new HashMap<string, string="">();
	hashMap.put("1", "Blues");
	hashMap.put("2", "Rock and roll");
	hashMap.put("3", "Swing");

	// iterate values, will reuse iterator
	for (int i = 0; i < 3; i++)
	for (String value : hashMap.getValuesIterator()) {
		System.out.println(value);
	}

	// iterate over keys, will reuse iterator
	for (int i = 0; i < 3; i++)
	for (String key : hashMap.getKeysIterator()) {
		System.out.println(key);
	}