What do you use for sorting?

[cero]

I have some sprites I need sorted by Y to appear in proper Z order. Using the supplied newlib's qsort works, but it takes half a frame for an array of 16 sprites, astoundingly inefficient.

I was thinking about copying musl's qsort into the project, and inlining the comparison. What do others use?

[Stef]

half of a frame for qsort on 16 objects ??? There is definitely something wrong, qsort is fast... I plan to add a generic sort implementation in SGDK so you pass an array of 'object' then you supply your own comparator callback so you will be able to compare independent element using internal qsort implementation easily.

[tryphon]

A good way of having sorted list is not to use list in fact, but rather another structure, such as heaps.

[cero]

I believe adding complex heap code to sort 16 sprites is slightly overkill

[tryphon]

In fact, not much more than using quicksort But maybe heap isn't the best suited here. My point is : "don't sort the list every frame, you'll end doing the same work over and over".

I guess you're in the following situation :

* the objects are more or less the same between two frames (at the worst, one is killed or another appear)
* concerning their priorities : most of the time, only two are exchanged

So there must be a structure well suited. For example, if you already have a sorted list :
* you can destroy an element then stick all the next elements to the left (logarithmic to find the pos, since you can use dichotomia), and your list remains sorted (linear, or constant if you use pointers)
* you can add an element by first shifting the greater elements to the right (same complexity)
* if list[1] become greater than list[0], you only have to swap them

As a side note, some implementations of quicksort performs really badly on already sorted lists, but I have no doubt Stef is well aware of that (no irony inside, I don't even check)

[cero]

Musl's qsort was even slower than newlib's. Next trying freebsd's.

It's not really the same work, because all objects move, and so their order will change frame to frame.

[cero]

FreeBSD's was almost line-for-line identical to newlib's, but it only took 1/4 frame, most likely because I use -O3 and newlib used -O2.

[cero]

Optimized it by removing 32-bit divides and multiplies, now it's 1/6 frame. I can post this version if you want it for SGDK Stef?

[cero]

Inlining the comparison function sped it up by 25%. Now it's at quite an acceptable speed.

[Stef]

Division and multiply inside your sorting code ???
Did you tried to derive from the one inside SGDK (just implementing for object by using an array of pointer), sorting 16 elements should only take a few percents of a frame.

[cero]

Here's the FreeBSD original source:
https://github.com/oza/FreeBSD-8.0-dynt ... rn/qsort.c

It works using pointers, so the multiplication and division are necessary to work with objects of arbitrary size.

Edit: I didn't know sgdk had a sorting function already, but sorting an array of integers is not very useful. The Partition_* functions should also be static inline, there's no need for them to be separately emitted.

Not sure if I'll try to benchmark one derived from that one, since I already have enough speed.

[ehaliewicz]

For small lists of objects that don't move position often, insertion sort is probably the algorithm you want.

Edit: actually read the whole thread, nevermind

[Sik]

Insertion sort may still be faster even with arbitrary sizes because it doesn't need multiplication or division at all (not even 16-bit) as it's always moving in steps of one entry. Addition and substraction are enough.

Another thing to take into account is that if the entries themselves are large enough, maybe it'd be useful to turn them into a double linked list, and then just sort the elements within the list (this way you only have to touch the pointers instead of the whole thing). The big downside is that most sorting algorithms would be a pain to work with entries being scattered all over the place... except incidentally insertion sort, since it traverses the list linearly and hence only has to follow the pointers.

So don't underestimate what insertion sort can do, especially on such an old system. Even if the sorting position changes often.

[Miquel]

Three remarks:

- Probably you don't want to only sort by Y-axis but also group them by type. For example, a cloud will always be behind or on top of other types of objects/sprites.

- Like tryphon said it will be better if you work with a list already sorted. When a sprite/object moves you just check with neighbours, most of the time just one. Also collision detection can be heavily improved that way.

- In C, when working with arrays don't do indexing, just use pointers. 68000 will be more kind then.

[Stef]

I made a new generic purpose quicksort implementation in SGDK, i was shocked by the poor performance of it though (specially for already sorted list). Definitely need to do an insertion sort implementation soon !