After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 672095 - glib needs stable sort function
glib needs stable sort function
Status: RESOLVED FIXED
Product: glib
Classification: Platform
Component: general
unspecified
Other All
: Normal normal
: ---
Assigned To: gtkdev
gtkdev
Depends on:
Blocks:
 
 
Reported: 2012-03-14 20:20 UTC by Alexander Larsson
Modified: 2012-03-21 02:32 UTC
See Also:
GNOME target: ---
GNOME version: ---


Attachments
Add g_stable_sort_with_data based on glibc msort (9.26 KB, patch)
2012-03-14 20:21 UTC, Alexander Larsson
none Details | Review
Remove wrong comments about sort stability in g_array_sort docs (1.09 KB, patch)
2012-03-14 20:21 UTC, Alexander Larsson
reviewed Details | Review
Add g_array_stable_sort_with_data (1.88 KB, patch)
2012-03-14 20:21 UTC, Alexander Larsson
none Details | Review
Add g_stable_sort_with_data based on glibc msort (10.47 KB, patch)
2012-03-14 20:49 UTC, Alexander Larsson
none Details | Review
Add g_array_stable_sort_with_data (2.86 KB, patch)
2012-03-14 20:49 UTC, Alexander Larsson
none Details | Review
Make g_array_sort* methods use a stable sort (2.39 KB, patch)
2012-03-15 07:49 UTC, Alexander Larsson
none Details | Review
Make g_qsort_with_data stable, based on glibc msort (18.03 KB, patch)
2012-03-16 11:52 UTC, Alexander Larsson
none Details | Review
Make g_array_sort* methods use a stable sort (3.59 KB, patch)
2012-03-16 11:52 UTC, Alexander Larsson
none Details | Review
Remove now unused qsort_r checks (1.85 KB, patch)
2012-03-16 11:52 UTC, Alexander Larsson
none Details | Review
gqsort.c: Fix C99ism's, GCCism and clean up formatting of code (9.24 KB, patch)
2012-03-19 08:35 UTC, Fan, Chun-wei
none Details | Review
Fix C99isms and GCCism in glib/gqsort.c (1.53 KB, patch)
2012-03-20 05:23 UTC, Fan, Chun-wei
none Details | Review
glib/gqsort.c: Fix C99ism/GCCism (1.57 KB, patch)
2012-03-21 02:32 UTC, Matthias Clasen
committed Details | Review

Description Alexander Larsson 2012-03-14 20:20:49 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.
Comment 1 Alexander Larsson 2012-03-14 20:21:22 UTC
Created attachment 209773 [details] [review]
Add g_stable_sort_with_data based on glibc msort
Comment 2 Alexander Larsson 2012-03-14 20:21:32 UTC
Created attachment 209774 [details] [review]
Remove wrong comments about sort stability in g_array_sort docs

The method that was explained does not work
Comment 3 Alexander Larsson 2012-03-14 20:21:39 UTC
Created attachment 209775 [details] [review]
Add g_array_stable_sort_with_data
Comment 4 Colin Walters 2012-03-14 20:26:34 UTC
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?)
Comment 5 Benjamin Otte (Company) 2012-03-14 20:33:40 UTC
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
Comment 6 Benjamin Otte (Company) 2012-03-14 20:37:56 UTC
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.
Comment 7 Alexander Larsson 2012-03-14 20:49:48 UTC
Created attachment 209778 [details] [review]
Add g_stable_sort_with_data based on glibc msort
Comment 8 Alexander Larsson 2012-03-14 20:49:51 UTC
Created attachment 209779 [details] [review]
Add g_array_stable_sort_with_data
Comment 9 Alexander Larsson 2012-03-14 21:00:58 UTC
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.
Comment 10 Alexander Larsson 2012-03-14 21:02:44 UTC
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.
Comment 11 Benjamin Otte (Company) 2012-03-14 21:41:40 UTC
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.
Comment 12 Alexander Larsson 2012-03-15 07:35:05 UTC
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.
Comment 13 Alexander Larsson 2012-03-15 07:49:46 UTC
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.
Comment 14 Alexander Larsson 2012-03-16 11:52:28 UTC
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
Comment 15 Alexander Larsson 2012-03-16 11:52:33 UTC
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.
Comment 16 Alexander Larsson 2012-03-16 11:52:36 UTC
Created attachment 209924 [details] [review]
Remove now unused qsort_r checks
Comment 17 Alexander Larsson 2012-03-16 11:54:24 UTC
New alternate series that completely replaces our qsort/qsort_r use and makes g_qsort_with_data() stable.
Comment 18 Benjamin Otte (Company) 2012-03-16 12:24:46 UTC
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.
Comment 19 Fan, Chun-wei 2012-03-19 08:35:32 UTC
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!
Comment 20 Javier Jardón (IRC: jjardon) 2012-03-19 13:02:36 UTC
*** Bug 671704 has been marked as a duplicate of this bug. ***
Comment 21 Fan, Chun-wei 2012-03-19 15:05:52 UTC
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!
Comment 22 Javier Jardón (IRC: jjardon) 2012-03-19 17:14:46 UTC
(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.
Comment 23 Matthias Clasen 2012-03-20 01:29:21 UTC
I've fixed the c99ism. Please reopen if there's any more build issues with this code.
Comment 24 Fan, Chun-wei 2012-03-20 05:23:17 UTC
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!
Comment 25 Matthias Clasen 2012-03-21 02:31:54 UTC
The following fix has been pushed:
b08b301 glib/gqsort.c: Fix C99ism/GCCism
Comment 26 Matthias Clasen 2012-03-21 02:32:02 UTC
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.