Sorting

Lately, I have started thinking a lot on sorting algorithms. I think I may have some really good ideas; the thing is, though, that I know little about the matter, so chances are my ideas are tremendously bad.

I have been looking for a tool on the internet that lets me play with lots of sorting algorithms and lets me compare them. Maybe I’m looking for something too specific, but I have had no luck.

So I have started making my own tool =)

These are the specifications:

  • The user has to be able to compare among a variety of algorithms.
  • See stats about each algorithms, like time spent, number of iterations, comparisons made etc.
  • I want the algorithm to run via Coroutines*
  • The user has to be able to visualize the output online
  • Be able to sort large amounts of integers.

*I could go with threads, which would be much faster and optimized; but I would lose control over the algorithm and that is a crucial feature if I want accurate representation.

I have open-sourced the code, and it’s available on my github page.

Drawing the graph

During a while, I really struggled with the representation of medium-size arrays (above 20.000).

My first attempt was representing each bar with a GUI Image: a simple rect. Obviously, that didn’t allow me for many items, and I quickly changed the approach and I decided to go with pure meshes (a simple quad per bar), but the performance wasn’t much higher.

My following idea was low level drawing using the Unity GL class. The performance was much higher, being able to represent several tens of thousands, even if at low frame rates. That, however, wasn’t enough for my specifications. I have to admit I didn’t clearly understand why I couldn’t manage to draw more than 100.000 tris without severely lowering the framerate (I mean, those tris were even being batched. Why was it so expensive?); until I figured out the problem was not the amount of tris but the amount of meshes. Considering I was drawing one mesh per bar, I guess it is not cheap to draw so many meshes per frame.

After that, I decided to combine the meshes into one alone. Instead of using the GL class, I would instantiate every bar individually, each one in a different gameobject and rendered with a MeshFilter and a MeshRenderer; and then combine all of them into one single game object. I had to do some fancy algorithm, as meshes in Unity cannot exceed 65535 tris, so, in the end, more than one mesh would be created. With that approach, I was able to render more than a million of tris with still quite good amount of frames per second. The solution, however, was flawed: Instantiating and “deleting” was an expensive task  (even though I was using a pooling system), so having large arrays took an inconceivable amount of time. Still not the final solution, but close.

Instantiating game objects and deleting them are both expensive tasks, so I decided to go without gameobjects. Instead, I would create procedural meshes of a maximum of 16000 bars each (because of the limit of ~64k tris per mesh) and draw them using Graphics.DrawMesh. The results were splendid: Instantiating several hundred of thousand bars took only a fraction of a second, and the cost of rendering them was completely negligible. In top of that, I implemented a pooling system, so further instantiation would be virtually instantaneos.

Updating the graph

Every frame, if any value has been changed by the algorithm (and I check that through a callback), I rebuild the mesh needed to represent that new value.

This can actually be done at a pretty solid rate even with large arrays. This, however, can be changed by setting the max amount of bars that every mesh represents. By default, it’s set to 16k (explaned above), which leaves for very few meshes for rendering very very large loops when updating. So, in the end, setting the right amount of bars per mesh is a tradeoff between performance when drawing and performance when updating the mesh.

ToDo

  • Let the user decide the amount of bars per mesh through the interface*
  • Every window should show some stats about its current algorithm.
  • Add more algorithms.

*Right now it’s not done because I would like to prepare the pooling system for different size of meshes, so not only meshes of 16k are stores. Not complicated at all, but time consuming.