bugGNUstep - Bugs: bug #37130, NSArray does not implement sorting...

Group
 
 

bug #37130: NSArray does not implement sorting and insertion assuming sorted

Submitter:  Thomas Davie <beelsebob>
Submitted:  Fri 17 Aug 2012 12:51:29 PM UTC
   
 
Category:  Base/Foundation Severity:  3 - Normal
Item Group:  Change Request Status:  Fixed
Privacy:  Public Assigned to:  thebeing
Open/Closed:  In Test
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Wed 03 Oct 2012 02:03:46 PM UTC, comment #13: 

I think this is now OK ... just needs testing.

Build gnustep-base with --with-sort-algorithm=timsort to try it out.

Richard Frith-Macdonald <CaS>
Group Member
Thu 20 Sep 2012 09:38:08 AM UTC, comment #12: 

Re-openeng ... while the restructuring is generally really nice, theres a problem that it doesn't work for realistic data.  I fixed a minor error in the new shellsort code and changed the configure script to use shellsort rather than timsort ... which should restore functionality to be (I hope) basically what it was before this re-working, so people should be able to use base again.  The configure option can still be used to turn on timsort or quicksort though.

The problems are:
minor ... quicksort code won't even compile
major ... timsort segfaults a lot

Richard Frith-Macdonald <CaS>
Group Member
Wed 19 Sep 2012 01:42:49 PM UTC, comment #11: 

Hi,

as it turns out, the sorting stuff in -base needed a little love in general  (for instance, -sortUsingFunction: and -sortUsingSortDescriptors: were implemented without resusing any code, one implemeting shellsort, the other quicksort). I consolidated all this stuff into an API that can be used with blocks, functions, or sort descriptors and also has plugable sort algorithms. I implemented the NSComparator related sorting/insertion point searching methods using this.

For the stable sort algorithm (actually, I made it the default for all sorting) we now have timsort. It seems to work well in my tests, but it is a complex beast and could definitely use some more testing and a few pairs of eyes looking at it.

Cheers,


Niels

Niels Grewe <thebeing>
Group Member
Wed 12 Sep 2012 01:32:53 PM UTC, comment #10: 

Sure, my point was simply that you cannot use quick sort for all sorting here, as it is not stable, and it is possible to request a stable sort.  In my implementation I didn't really see enormous reason to implement two separate sorts, when one, stable one would do.

I would back up your suspicion with the fact that if you set a breakpoint in a comparator, you will commonly see calls to mergeSort on the stack... Of course, they could have done something nuts like name it merge sort and not actually implement that, but it seems to suggest they did indeed use it.

Timsort would indeed be a nice choice too, and I suspect you're dead right that you would need a bloody big threshold on the size of the split arrays for merge sort to end up faster across multiple threads (or even gcd queues).

Thomas Davie <beelsebob>
Wed 12 Sep 2012 12:54:39 PM UTC, comment #9: 

Well, actually, the documentation states that sorting is only required to be stable if you actually request it (though Apple might actually always do stable sorting and just doesn't want to make any guarantees for the general case, I didn't check.)

As far as the choice of sort algorithm is concerned, I highly suspect that Apple has actually implemented their sorting stuff with mergesort, because it is inherently easy to do it in parallel and they seem to like that :-) (by the way: while Thomas' mergesort implementation is stable, you can also do mergesort in an unstable way, depending on how you slice the array).

Another alternative that we could consider is timsort, which is the default sorting algorithm in Python, Android and Java 7 and is said to be marvellously fast for partially pre-sorted inputs as they occur in real-world settings. It is stable, but I didn't see any obvious avenues for parallel execution. (Anyways, I suspect that you'd need to throw a lot of cores at a parallel mergesort to beat timsort in something other than a contrived micro-benchmark).

(Actually, you can read that as an endorsement that I might consider it a fun project to implement timsort in -baseā€¦)

Cheers,

Niels

Niels Grewe <thebeing>
Group Member
Tue 11 Sep 2012 07:53:53 AM UTC, comment #8: 

Quicksort would produce an invalid implementation, as it is not stable.

Thomas Davie <beelsebob>
Tue 11 Sep 2012 06:04:03 AM UTC, comment #7: 


Without copyright assignment we can't merge the code (though obviously we can merge pulic interface bits) ... in effect we have to treat this as a request to implement this functionality.

I've been searching the web for information about sorts, and it seems that the best overall performer for general sorting is thought to be quicksort (at least, I cound comments to that effect on wikipedia and in a couple of other places) ... the merge sort is certainly better for some cases, but with arrays we should probably use the existing quicksort implementation from NSSortDescriptor.

Richard Frith-Macdonald <CaS>
Group Member
Fri 24 Aug 2012 01:18:56 PM UTC, comment #6: 

If it helps, (though I imagine it won't :() you're also welcome to have the code under the WTFPL.

Thomas Davie <beelsebob>
Fri 24 Aug 2012 01:16:14 PM UTC, comment #5: 

Hmm, not sure, I think using two arrays, merging from one into the other and swapping them in each recursion step should give the same performance as creating a new array for each step. The only additional work is to copy the objects over to the additional array at the start.

In the mean time I have also read up on merge sort and the best way to do it seems to use the pre-existing runs. But that would require a bit more coding.

Back tot he original question, what to do with the code? Adam, Greg, Richard? Any position on whether we may merge this code?

Fred Kiefer <FredKiefer>
Group Member
Sat 18 Aug 2012 02:55:35 PM UTC, comment #4: 

I can see the argument for wanting an in place merge sort there.  The reason I chose not to do that was because an in-place merge sort is slower O(n*log(n)^2) in the worst case, though the extra allocation and copying may offset that.  I can't say I benchmarked both solutions, so it may be that doing it in-place is in fact fast enough, and consumes significantly less RAM for large arrays.

Thomas Davie <beelsebob>
Sat 18 Aug 2012 02:33:07 PM UTC, comment #3: 

I had a look at his code and think that most of it should be fine to merge, even without a copyright assignment. Most of the code size are method and constant declarations, no problem here. The merge sort itself is a standard implementation (although I would like to see it rewritten to do less array copying. Maybe we could create one mutable array at the start and sort that inplace? This sounds like the missing method NMutableArray -sortWithOptions:usingComparator:)

The only code that includes real genuine ideas is the method
-indexOfObject:inSortedRange:options:usingComparator: which is nicely written. Not sure how to handle that.

We should also stop a minute here and rethink the different sorting implementations in base. In NSArray.m we already have a shell sort and in NSSortDescriptor.m a quicksort implementation. Could we base all these on this new implementation?

Fred Kiefer <FredKiefer>
Group Member
Sat 18 Aug 2012 02:08:37 PM UTC, comment #2: 

Just for the records, on the mailing list Thomas send these two comments:


I have not, and will not, but you can hear-by consider the patch to be BSD 3 clause licensed to you (and anyone else).  If you need to have the code in a way that's assigned to the FSF, feel free to use it as a basis for your own patch that you do assign.

And

Sorry Niels, that may have come across as overly assertive/aggressive.  I did not mean that I will not because of some political stance, but instead simply that in this instance I can not.  This was done on my company's time, and they have allowed me to license the code out to you in an open way; but the copyright belongs to them, so I can not do more than that.

Hope that clarifies my position

Fred Kiefer <FredKiefer>
Group Member
Sat 18 Aug 2012 07:15:32 AM UTC, comment #1: 

Nice!

Thanks alot for the patch, especially since it removes one item from my todo list :-). I have one remark, though: If you want to call blocks in gnustep-base, you need to use the CALL_BLOCK macro, which ensures that we can compile gnustep-base with GCC and still use blocks properly.

Since this is clearly a substantial patch: Have you signed a copyright assignment with the FSF? -- We'd require that before incorporating the patch.

Many thanks,

Niels

Niels Grewe <thebeing>
Group Member
Fri 17 Aug 2012 12:51:29 PM UTC, original submission:  

NSArray does not implement

- (NSArray *)sortedArrayUsingComparator:(NSComparator)cmptr;
- (NSArray *)sortedArrayWithOptions:(NSSortOptions)opts usingComparator:(NSComparator)cmptr;
or
- (NSUInteger)indexOfObject:(id)obj
              inSortedRange:(NSRange)r
                    options:(NSBinarySearchingOptions)opts
            usingComparator:(NSComparator)cmp;

Patch attached

Thomas Davie <beelsebob>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #26377:  NSArray.diff added by beelsebob (10KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by CaS (Posted a comment)
  • -email is unavailable- added by FredKiefer (Posted a comment)
  • -email is unavailable- added by thebeing (Posted a comment)
  • -email is unavailable- added by beelsebob (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-10-03 CaS StatusIn Progress Fixed
        Open/ClosedOpen In Test
    2012-09-20 CaS StatusReady For Test In Progress
        Open/ClosedIn Test Open
    2012-09-19 thebeing StatusConfirmed Ready For Test
        Open/ClosedOpen In Test
    2012-08-24 FredKiefer StatusNone Confirmed
    2012-08-18 thebeing Item GroupBug Change Request
        Assigned toNone thebeing
    2012-08-17 beelsebob Attached File- Added NSArray.diff, #26377

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code