Performance Issues and Solutions

Jan 30, 2016 at 4:24 PM
Firstly I would like to thank the author for writing this library.

Recently I have used this Triangulator and embedded it into our game project, it worked greatly, except for suffering from performance issues - to be exactly, GC issues.

In our test, the library generates 4.3MB of GC allocation while triangulating a convex polygon of 128 vertices. This is a great performance impact, as we are using this library in a mobile game. So we digged a bit into the source code and made some optimization. After the tuning, the GC allocation dropped to less than 300KB in the same test.

The code was heavily modified in order to be embeddable into our game, so please pardon me for not being able of sharing the modified code. However I'll explain the issues we found and give solutions to them.

The major issues happens on the four static collections, which can be found easily at the top of Triangulator.cs. Let's start from the latter two: one storing convex vertices and the other for concave ones. They are of type CyclicalList<T>, which is practically a List<T> with cyclical indexing support - but they don't need it because they store incontinuous vertices. Furthermore, as these two complementary lists are primarily used for storing vertex states (convex or not) rather than being enumerated, they can be replaced by a fixed-length array of bool values, indexed by Vertex.index to determine the convexity of the vertex. This will increase performance significantly, as these lists are consulted quite frequently, the optimization reduces the query job from O(n) to O(1). GC allocation is also much reduced.

Then we can head to the first two collections. The first one stores the original vertices, which will be consumed during the triangulation process; the latter one remembers ear vertices. Both them are of type CyclicalLinkedList<T>, which, a little beyond my expectations, are the same with CyclicalList<T>, can be accessed with cyclical indices. The first collection has to be a LinkedList because it needs good remove performance, however it is frequently accessed by indices, which is quite an expensive job for a LinkedList. The primary reason it needs indexing is, it has to find vertices from the second collection - which is a CyclicalLinkedList, too, but don't have to be cyclical at all. So the optimization here is, change the second collection to a LinkedList<LinkedListNode<Vertex>>, storing nodes from the first collection, rather than plain vertices. Then the first collection will never need to be indexed again, all code of accessing the previous or next sibling of a vertex can be changed by using LinkedListNode.

There are still some places which could be optimized, but the abovementioned collections are prime to hunt down, especially for a real time context (like games).