What do you use for sorting?

SGDK only sub forum

Moderator: Stef

cero
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

What do you use for sorting?

Post by cero » Mon Jun 27, 2016 5:38 pm

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
Very interested
Posts: 2976
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: What do you use for sorting?

Post by Stef » Mon Jun 27, 2016 6:02 pm

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
Very interested
Posts: 303
Joined: Sat Aug 17, 2013 9:38 pm
Location: France

Re: What do you use for sorting?

Post by tryphon » Tue Jun 28, 2016 7:41 am

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

cero
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

Re: What do you use for sorting?

Post by cero » Tue Jun 28, 2016 8:05 am

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

tryphon
Very interested
Posts: 303
Joined: Sat Aug 17, 2013 9:38 pm
Location: France

Re: What do you use for sorting?

Post by tryphon » Tue Jun 28, 2016 8:31 am

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
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

Re: What do you use for sorting?

Post by cero » Tue Jun 28, 2016 10:54 am

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
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

Re: What do you use for sorting?

Post by cero » Tue Jun 28, 2016 11:12 am

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
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

Re: What do you use for sorting?

Post by cero » Tue Jun 28, 2016 11:54 am

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
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

Re: What do you use for sorting?

Post by cero » Tue Jun 28, 2016 12:07 pm

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

Stef
Very interested
Posts: 2976
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: What do you use for sorting?

Post by Stef » Tue Jun 28, 2016 5:16 pm

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
Very interested
Posts: 259
Joined: Mon Nov 30, 2015 1:55 pm

Re: What do you use for sorting?

Post by cero » Tue Jun 28, 2016 5:52 pm

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
Interested
Posts: 43
Joined: Tue Dec 24, 2013 1:00 am

Re: What do you use for sorting?

Post by ehaliewicz » Fri Jul 01, 2016 6:00 pm

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
Very interested
Posts: 879
Joined: Thu Apr 10, 2008 3:03 pm
Contact:

Re: What do you use for sorting?

Post by Sik » Sun Jul 03, 2016 12:24 pm

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.
Sik is pronounced as "seek", not as "sick".

Miquel
Very interested
Posts: 448
Joined: Sat Jul 30, 2016 12:33 am

Re: What do you use for sorting?

Post by Miquel » Mon Aug 22, 2016 7:59 pm

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.
It’s not what you think.
Perhaps, just perhaps, is our family making sure we listen from now on.
We need to talk about Mercury too.
We need to talk about so many things… I fear I don’t remember all.

Stef
Very interested
Posts: 2976
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: What do you use for sorting?

Post by Stef » Mon Aug 22, 2016 9:06 pm

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 !

Post Reply