GNOME Bugzilla – Bug 672095
glib needs stable sort function
Last modified: 2012-03-21 02:32:02 UTC
Gtk needs a stable sort function for the CSS machinery, and the documented way to get one in the g_array_sort API docs just doesn't work. We need a real one, and there is one in glibc we can use (msort). Appending patches.
Created attachment 209773 [details] [review] Add g_stable_sort_with_data based on glibc msort
Created attachment 209774 [details] [review] Remove wrong comments about sort stability in g_array_sort docs The method that was explained does not work
Created attachment 209775 [details] [review] Add g_array_stable_sort_with_data
Review of attachment 209774 [details] [review]: You might instead change the note to say that the documentation previously suggested a method for stable sorting which doesn't work, rather than just removing it. (Why doesn't it work?)
I'm all for landing something like this. But there's one API-question: Why do we not just make g_array_sort() stable? If you need to care about the performance implications between stable and unstable sorting algorithms, you are likely going to use your own algorithm anyway. I would in fact just change g_qsort_with_data() to do an msort even though the name kinda implies it's gonna do a qsort. A few nitpicks on the actual patches: - Why is the configure.ac change in there? - Should the copied code be made to use gsize and gpointer instead of the regular types? - The docs aren't hooked up into gtk-doc - The docs are wrong. (Copy/pasted and not fixed up I guess?) - The docs of g_array_sort() and g_array_sort_stable() should interlink and describe the differences or link to http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Also, looking at http://rosettacode.org/wiki/Sort_stability it seems that major programming languages - like Java - get by with just providing a stable sort algorithm in their public API. So I'd say there's absolutely no reason to provide 2 different sorting algorithms and expect the developers using them to know when to use which one. I certainly wouldn't, I consider myself one of the smarter users of glib.
Created attachment 209778 [details] [review] Add g_stable_sort_with_data based on glibc msort
Created attachment 209779 [details] [review] Add g_array_stable_sort_with_data
New versions of the sort patch, fixing docs, symbols and some gnuisms. Some comments: - Why is the configure.ac change in there? The original code used __alignof__(uint32_t), i replaced this C extension with some standard autoconf checks. - Should the copied code be made to use gsize and gpointer instead of the regular types? We didn't do this for gqsort.c, although i did convert the uint32_t etc types so that things would build. I think its nice to minimize the difference so we can merge fixes or whatnot. As for only supporting a stable sort. I dunno. Its what glibc does too (i.e. its qsort uses this implementation by default, although it had some magic to detect when the array is too large and then fall back to the inplace quicksort to avoid allocating and copying a lot of memory. On the other hand, stable vs non-stable sort is a standard CS thing, and e.g. C++ does have both availible. Its also nice to be able to have the default fast sort be able to call the system qsort rather than always using the glib copy, but its very hard to reliably detect whether the native qsort is stable. (In fact its not really possible even on glibc since it switches to an unstable sort only under memory pressure.) Walters: It breaks if the sort is non-stable, for instance it may swap an item into its right position, moving whatever was there somewhere else (where it will later be sorted from). However, now the swapped out item has been reordered and comparing its new address does not give the original order.
Hmm... Or are you proposing keeping g_qsort_with_data and g_stable_sort_with_data, but then only having one sort helper in g_array? That makes a lot of sense to me. If you really care you can get the fast one, but normally you just get the stable one.
I was thinking about both. I think for GArray it's pretty obvious you only want one function. I don't care much about the direct sort functions - for all I care we could have 20 sort function - because nobody ever looks at them. But as not even the libc guys know when to choose which sort function I'd argue just having one sort function is the least maintenance with no loss in functionality.
I don't agree with that. I think we want to have an algorithmically optimal sort availible *somewhere*, especially one that is the architecture optimal one (i.e. the libc one) if possible. On the other hand I don't think we should double all highlevel sort utility API calls as that makes the "easy" APIs too complex. So. I'll change the patches around to this.
Created attachment 209805 [details] [review] Make g_array_sort* methods use a stable sort Also, remove previous comments about sort stability in g_array_sort docs, as the method that was explained does not work. Adds a new comment about this.
Created attachment 209922 [details] [review] Make g_qsort_with_data stable, based on glibc msort We need a stable sort, and we might as well always use it rather than have multiple sort versions. This picks up the glibc merge sort implementation which it uses by default for qsort, except we don't fall back to non-stable quicksort in some cases like glibc
Created attachment 209923 [details] [review] Make g_array_sort* methods use a stable sort Also, remove previous comments about sort stability in g_array_sort docs, as the method that was explained does not work. Adds a new comment about this.
Created attachment 209924 [details] [review] Remove now unused qsort_r checks
New alternate series that completely replaces our qsort/qsort_r use and makes g_qsort_with_data() stable.
I didn't look at the copy/paste code for the msort(). The rest looks fine to me. So from my point of view, feel free to commit.
Created attachment 210076 [details] [review] gqsort.c: Fix C99ism's, GCCism and clean up formatting of code (In reply to comment #9) > New versions of the sort patch, fixing docs, symbols and some gnuisms... Hi, Sorry I am reopening this as I found that there are C99ism's and GCCism's that still are in the code, and would therefore break non-GCC builds of GLib. I have attached a patch to remedy this, and this has been checked on Visual C++ (32/x64 bit) and Fedora 16-x64/GCC with the glib/tests/sort.c test program. With blessings, thank you!
*** Bug 671704 has been marked as a duplicate of this bug. ***
Sorry for the noise... Apparently my post (comment #19) did not re-open this bug. Re-opening this bug due to remaining GCCism and C99ism in the code in gqsort.c (please see comment #19). p.s. I looked at bug 671704, I'm sorry, but I didn't get how that bug is a duplicate of this bug, but I did not touch the status of that bug as probably Javier is more knowledgeable in that regard, IMHO. With blessings, and thank you!
(In reply to comment #21) > p.s. I looked at bug 671704, I'm sorry, but I didn't get how that bug is a > duplicate of this bug, but I did not touch the status of that bug as probably > Javier is more knowledgeable in that regard, IMHO. My mistake, is not related at all.
I've fixed the c99ism. Please reopen if there's any more build issues with this code.
Created attachment 210143 [details] [review] Fix C99isms and GCCism in glib/gqsort.c (In reply to comment #23) > I've fixed the c99ism. Please reopen if there's any more build issues with this > code. Hi, Unfortunately there is yet another C99ism and GCCism that is in the code. This patch I came up with fixes this, and it is verified on my Visual C++ 2008/2010 and Fedora 16 systems. With blessings, thank you!
The following fix has been pushed: b08b301 glib/gqsort.c: Fix C99ism/GCCism
Created attachment 210217 [details] [review] glib/gqsort.c: Fix C99ism/GCCism -There were a number of variables that were declared in the middle of the block, so move these declarations to the start of the block -There was a use of mempcpy, but it is a GCC extension, so use memcpy since we didn't care about the return value of the call to mempcpy.