Corona Quick Thought – performance: use native methods whenever you can

I recently saw a Corona tutorial of the painter’s algorithm, where the author demonstrated how they had depth-sorted their sprites by screen y-coordinate in order to simulate depth in 2D.

The effect works well, but I was surprised to see that the author had implemented their own insertion sort in pure Lua rather than rely on Lua’s built-in table.sort() (a quicksort implementation).

(I’ll avoid mentioning where to find that tutorial, lest this seem like my intent is just to criticize that work, ‘cuz it isn’t. I’ll try to use it as a case study for a general principle, while trying to avoid nitpicking it as a specific case. Unless that author wants a link back, then sure, just let me know! Fair?)

I won’t delve into comparing the merits of various sort algorithms (much), except to say that the choice of an insertion sort was probably a good one. If the number of sprites is relatively small, and if they remain “mostly” sorted from frame to frame, then those are nearly ideal conditions for an insertion sort.

However, …, it’s really hard to beat native code! Especially on a mobile device. If there’s an existing library routine that already does something, you are almost always better off using the built-in rather than rolling your own with interpreted Lua. Even if the built-in isn’t quite a perfect “fit” for your usage. (only in an extreme case with a known-optimal solution might you “win” via interpreted code versus a more generic solution in native code)

The example here is that a somewhat-less-than-optimal-quicksort in native code is going to beat the pants off (aka orders of magnitude) even a more-optimal-insertion-sort if in interpreted code. Even with a relatively small list (50-ish sprites or so?), and even if already mostly sorted. (and certainly even moreso in general cases where those ideal conditions for an insertion sort aren’t met, giving the advantage to quicksort anyway)

You can apply this principle across the board, whenever/wherever possible. For example, it’s not uncommon to see “tedious” string parsing being done with interpreted Lua that could have been accomplished so much more efficiently via string.gsub() and/or string.find(). Granted that Lua’s pattern-matching syntax can seem a bit “obscure”, but it’s well worth the time to learn the libraries.

And performance is not the only issue here. The Lua libraries have been battle-tested, so usually there’s no concern about the “correctness” of the implementation – you can just rely on it working. Huge time saver, why reinvent the wheel?

Back to sorting, let’s whip up an example for those who might not be familiar with table.sort().

table.sort() can work directly on a list of atomic values (numbers, strings), or can accept a comparison function to deal with a list of arbitrary table (aka an “object” in typical usage) values having sortable properties within. (a comparison function can also be used to handle primary-secondary type sorts on multiple properties as well)

(and for advanced readers, note that table.sort() can operate directly on a list of tables, provided they’ve got a metamethod for the less-than operator)

A quick silly example just to illustrate some various bits:

Leave a Reply