[Adonthell-devel] Performance improvements

[Kai Sterker]

A number of the last few commits were made to improve overall
performance, to bring the engine back to near the level I measured
some time ago:

  
http://adonthell.nongnu.org/news/index.shtml#Monday%20February%2028%2020:16%202011

It's not quite there, but of course new functionality was added in the
meantime, so some slowdown has to be expected. All in all, the current
code runs about 4 times faster than a couple weeks ago. In my
profiling, I found one area that could still improve and that is
sorting objects for rendering.

The current code does sorting by brute-force, resulting in the same
objects compared over and over again. I would assume that there are
two levels of possible improvement:

1. Implement a data structure and sorting algorithm that represents
the order in which the objects need to be drawn on-screen.
2. Between two frames, remove objects no longer visible and only add
newly visible objects to the data structure.

The first step would reduce the number of comparisons required for
rendering a scene, but for each scene we would again do pretty much
the same comparisons.

The second step would only require work for figuring out which objects
are newly in the scene and which ones are gone from the scene (pretty
fast when using a hashtable) and in turn only new objects need to be
sorted into the data structure.


The problem is, there is no clear relation between any two objects
that make up a scene, making sorting more difficult. This is because
objects which do not overlap each other have an undetermined drawing
order. They will eventually fall into place, but they cause ordinary
sorting algorithms to fail, as those rely on any two objects of a set
being directly comparable.

Any ideas how to solve this issue would be welcome. In the meantime,
I'll concentrate on other things.


BTW: would be interested in hearing your performance numbers. At the
end, worldtest will print the average time per frame, assuming you run
it with the environment variable GLOG_minloglevel set to 2 or lower.
It'll be higher if you engage in dialogue with the NPC as part of the
GUI requires software rendering, so avoid this if possible. Post your
numbers, version of SDL, resolution (which is printed at the
beginning), CPU and GPU. For me it's

E0309 17:15:14.397367 11934 screen.cc:132] *** info: Set internal view
to 576 x 432.
E0309 17:15:14.397949 11934 screen.cc:133] *** info: Set display size
to 1152 x 864.
E0309 17:15:31.526919 11934 worldtest.cc:254] Rendered 665 frames in 2342 ms.
E0309 17:15:31.527304 11934 worldtest.cc:255] Average time required
per frame is 3.522 ms.

using recent SDL2 on my 2.5Ghz Core 2 Duo with an Nvidia 9600 GT.

Kai


P.S.: For the profiling, I used oprofile
(http://oprofile.sourceforge.net/). Found it to be fast and simple to
use. Unfortunately, it's not included with Ubuntu, but simple enough
to compile from source:

https://geekwentfreak-raviteja.rhcloud.com/2012/10/installing-and-using-oprofiler-in-ubuntu-12-04/