Re: Better sorting using threads?
Thanks for everyone's feedback. I'm always very happy to have ignorance on my part removed! As far as interface is concerned yes I completely respect the fact that it's there to hide details and help us focus on behavior not implementation. And yes I'm sort of kicking myself for not realizing an array is really just some thing that lets you index into it with a number. Doh! That being said, once containers get large, understanding the Big O notation for operations can become important factors in choosing one implementation over another. One of the things I do like about STL ( don't want to digress too far in this direction ) is that documentation provides gaurantees about Big O notation. Do this type of gaurantee exist anywhere in Cocoa's containers? --aj From: Jeffrey Oleander jgo...@yahoo.com To: Gwynne Raskind gwy...@darkrainfall.org; Ken Ferry kenfe...@gmail.com; Andrew James andrew_a_ja...@yahoo.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Sun, March 14, 2010 12:34:35 PM Subject: Re: Better sorting using threads? On Fri, 2010/03/12, Andrew James andrew_a_ja...@yahoo.com wrote: From: Andrew James andrew_a_ja...@yahoo.com Subject: Re: Better sorting using threads? To: Gwynne Raskind gwy...@darkrainfall.org, Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Date: Friday, 2010 March 12, 13:55 My concern is that keeping traditional C-arrays in sorted order means 1) finding the location for insert ( O(n) ) 2) copying a range of contiguous memory to make the location available 3) copying in new value I've made the assumption that NSArray wraps an old school contiguous C-style array ( ala C++ std:::vector ) With many sorted container insertion inserting in sorted order means 1) finding the location for inserter ( O(nlogn) ) or the like 2) create node with new value 3) swizzle some pointers to include new values .. ( ala C++ std::set ) I have a hard time seeing how this is more expensive for very large container than sorting an array when needed. The initial poster was indicating he has a container with thousands of members. Please educate me where my post illustrates ignorance. Cheers, --aj Well, encapsulation requires a certain amount of enforced ignorance. We're not supposed to know exactly how it does it. We're only supposed to know the public interface and let it do its thing as it wishes to do it, even changing when the maintainers of the class decide to make changes. I may be implemented as a Fibonacci heap, or a binary tree for all we know, using a contiguous block of memory or nodes allocated one at a time. There are hints in the interface provided, but no promises beyond it regarding implementation. From: Gwynne Raskind gwy...@darkrainfall.org To: Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Fri, March 12, 2010 9:14:35 AM Subject: Re: Better sorting using threads? On Mar 12, 2010, at 2:25 AM, Ken Ferry wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Probably the best thing to do if you want this is to maintain the sort yourself by inserting new objects in the correct position. You can find the position using -[NSArray indexOfObject:inSortedRange:options:usingComparator:] ... ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Mon, Mar 15, 2010 at 1:11 PM, Andrew James andrew_a_ja...@yahoo.comwrote: Thanks for everyone's feedback. I'm always very happy to have ignorance on my part removed! As far as interface is concerned yes I completely respect the fact that it's there to hide details and help us focus on behavior not implementation. And yes I'm sort of kicking myself for not realizing an array is really just some thing that lets you index into it with a number. Doh! That being said, once containers get large, understanding the Big O notation for operations can become important factors in choosing one implementation over another. One of the things I do like about STL ( don't want to digress too far in this direction ) is that documentation provides gaurantees about Big O notation. Do this type of gaurantee exist anywhere in Cocoa's containers? Yes, but you probably won't like the guarantees, since they're pretty conservative. See CFArray.h, CFDictionary.h. There are no guarantees for NSArray or NSDictionary because they can have arbitrary subclasses. However, in standard cases you'll be getting the same behavior as with the un-subclassable CFArray and CFDictionary. -Ken --aj -- *From:* Jeffrey Oleander jgo...@yahoo.com *To:* Gwynne Raskind gwy...@darkrainfall.org; Ken Ferry kenfe...@gmail.com; Andrew James andrew_a_ja...@yahoo.com *Cc:* Cocoa-Dev List cocoa-dev@lists.apple.com *Sent:* Sun, March 14, 2010 12:34:35 PM *Subject:* Re: Better sorting using threads? On Fri, 2010/03/12, Andrew James andrew_a_ja...@yahoo.com wrote: From: Andrew James andrew_a_ja...@yahoo.com Subject: Re: Better sorting using threads? To: Gwynne Raskind gwy...@darkrainfall.org, Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Date: Friday, 2010 March 12, 13:55 My concern is that keeping traditional C-arrays in sorted order means 1) finding the location for insert ( O(n) ) 2) copying a range of contiguous memory to make the location available 3) copying in new value I've made the assumption that NSArray wraps an old school contiguous C-style array ( ala C++ std:::vector ) With many sorted container insertion inserting in sorted order means 1) finding the location for inserter ( O(nlogn) ) or the like 2) create node with new value 3) swizzle some pointers to include new values .. ( ala C++ std::set ) I have a hard time seeing how this is more expensive for very large container than sorting an array when needed. The initial poster was indicating he has a container with thousands of members. Please educate me where my post illustrates ignorance. Cheers, --aj Well, encapsulation requires a certain amount of enforced ignorance. We're not supposed to know exactly how it does it. We're only supposed to know the public interface and let it do its thing as it wishes to do it, even changing when the maintainers of the class decide to make changes. I may be implemented as a Fibonacci heap, or a binary tree for all we know, using a contiguous block of memory or nodes allocated one at a time. There are hints in the interface provided, but no promises beyond it regarding implementation. From: Gwynne Raskind gwy...@darkrainfall.org To: Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Fri, March 12, 2010 9:14:35 AM Subject: Re: Better sorting using threads? On Mar 12, 2010, at 2:25 AM, Ken Ferry wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Probably the best thing to do if you want this is to maintain the sort yourself by inserting new objects in the correct position. You can find the position using -[NSArray indexOfObject:inSortedRange:options:usingComparator:] ... ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Mar 15, 2010, at 1:11 PM, Andrew James wrote: That being said, once containers get large, understanding the Big O notation for operations can become important factors in choosing one implementation over another. One of the things I do like about STL ( don't want to digress too far in this direction ) is that documentation provides gaurantees about Big O notation. Do this type of gaurantee exist anywhere in Cocoa's containers? No. There isn't even any documentation about the underlying data formats or algorithms used by the container classes; you just use the nice shiny APIs. Very Apple-like :) I missed the start of this thread, but I'll add (perhaps redundantly) that NSArray, at least its mutable variety, at large sizes switches from a flat vector implementation to one that's more of a two-level tree. This is done to keep insertions and deletions fast. I think what motivated this implementation is that mutable NSArrays are heavily used in the Cocoa text system. As always, you should be avoiding thinking about such details until you've written your code, profiled it, and identified actual hot-spots involving arrays. Also, you should be using NSArray's sort methods rather than trying to make your own, since those methods have direct access to the internal array guts and can work much faster than you going through the API. —Jens___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Fri, 2010/03/12, Andrew James andrew_a_ja...@yahoo.com wrote: From: Andrew James andrew_a_ja...@yahoo.com Subject: Re: Better sorting using threads? To: Gwynne Raskind gwy...@darkrainfall.org, Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Date: Friday, 2010 March 12, 13:55 My concern is that keeping traditional C-arrays in sorted order means 1) finding the location for insert ( O(n) ) 2) copying a range of contiguous memory to make the location available 3) copying in new value I've made the assumption that NSArray wraps an old school contiguous C-style array ( ala C++ std:::vector ) With many sorted container insertion inserting in sorted order means 1) finding the location for inserter ( O(nlogn) ) or the like 2) create node with new value 3) swizzle some pointers to include new values .. ( ala C++ std::set ) I have a hard time seeing how this is more expensive for very large container than sorting an array when needed. The initial poster was indicating he has a container with thousands of members. Please educate me where my post illustrates ignorance. Cheers, --aj Well, encapsulation requires a certain amount of enforced ignorance. We're not supposed to know exactly how it does it. We're only supposed to know the public interface and let it do its thing as it wishes to do it, even changing when the maintainers of the class decide to make changes. I may be implemented as a Fibonacci heap, or a binary tree for all we know, using a contiguous block of memory or nodes allocated one at a time. There are hints in the interface provided, but no promises beyond it regarding implementation. From: Gwynne Raskind gwy...@darkrainfall.org To: Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Fri, March 12, 2010 9:14:35 AM Subject: Re: Better sorting using threads? On Mar 12, 2010, at 2:25 AM, Ken Ferry wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Probably the best thing to do if you want this is to maintain the sort yourself by inserting new objects in the correct position. You can find the position using -[NSArray indexOfObject:inSortedRange:options:usingComparator:] ... ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
Yes, that's what I mean. But it worked fine on Leopard and Tiger... It's all academic now anyway, I rewrote it around my own, STL-based collection classes. I just thought I'd mention it in case it bit anybody else. I didn't keep a copy of the code, sorry. And I know about the difference between copy and mutableCopy Ken so it wasn't that, but it was a nice idea to suggest it. Paul Sanders. - Original Message - From: Greg Parker gpar...@apple.com To: Paul Sanders p.sand...@alpinesoft.co.uk Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Saturday, March 13, 2010 12:01 AM Subject: Re: Better sorting using threads? mutating method sent to immutable object, you mean? That suggests your NSMutableDictionary object isn't as mutable as you thought. It might not be a thread-related bug. -- Greg Parker gpar...@apple.com Runtime Wrangler ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Mar 12, 2010, at 2:25 AM, Ken Ferry wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Probably the best thing to do if you want this is to maintain the sort yourself by inserting new objects in the correct position. You can find the position using -[NSArray indexOfObject:inSortedRange:options:usingComparator:]. That's two lines instead of one to add an object to an array, which is not bad. That method is new in 10.6, but something similar has been in CoreFoundation for a while. CFArrayBSearchValues is usable on NSArray since CFArray is bridged. You can also look at -[NSArray sortedArrayHint]. The deal there is that you extract an opaque hint from a sorted array, change the array, and resort passing in the hint. This is optimized for the case when the array is still mostly sorted, but with some things out of place. I maintain a simple sorted array by rerunning -sortUsingFunction:context: for every insert (or set of inserts, since the vast majority of inserts into the array are groups of objects together). So far I haven't had any speed issues with it at all. But my case is pretty simple; it's a small array of around 100 objects, and the sort function is trivial (object.integerProperty comparison). -- Gwynne ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
All, My concern is that keeping traditional C-arrays in sorted order means 1) finding the location for insert ( O(n) ) 2) copying a range of contiguous memory to make the location available 3) copying in new value I've made the assumption that NSArray wraps an old school contiguous C-style array ( ala C++ std:::vector ) With many sorted container insertion inserting in sorted order means 1) finding the location for inserter ( O(nlogn) ) or the like 2) create node with new value 3) swizzle some pointers to include new values .. ( ala C++ std::set ) I have a hard time seeing how this is more expensive for very large container than sorting an array when needed. The initial poster was indicating he has a container with thousands of members. Please educate me where my post illustrates ignorance. Cheers, --aj From: Gwynne Raskind gwy...@darkrainfall.org To: Ken Ferry kenfe...@gmail.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Fri, March 12, 2010 9:14:35 AM Subject: Re: Better sorting using threads? On Mar 12, 2010, at 2:25 AM, Ken Ferry wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Probably the best thing to do if you want this is to maintain the sort yourself by inserting new objects in the correct position. You can find the position using -[NSArray indexOfObject:inSortedRange:options:usingComparator:]. That's two lines instead of one to add an object to an array, which is not bad. That method is new in 10.6, but something similar has been in CoreFoundation for a while. CFArrayBSearchValues is usable on NSArray since CFArray is bridged. You can also look at -[NSArray sortedArrayHint]. The deal there is that you extract an opaque hint from a sorted array, change the array, and resort passing in the hint. This is optimized for the case when the array is still mostly sorted, but with some things out of place. I maintain a simple sorted array by rerunning -sortUsingFunction:context: for every insert (or set of inserts, since the vast majority of inserts into the array are groups of objects together). So far I haven't had any speed issues with it at all. But my case is pretty simple; it's a small array of around 100 objects, and the sort function is trivial (object.integerProperty comparison). -- Gwynne ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/andrew_a_james%40yahoo.com This email sent to andrew_a_ja...@yahoo.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Fri, Mar 12, 2010 at 11:55 AM, Andrew James andrew_a_ja...@yahoo.com wrote: I've made the assumption that NSArray wraps an old school contiguous C-style array ( ala C++ std:::vector ) This assumption is false. --Kyle Sluder ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On 12 Mar 2010, at 20:20, Kyle Sluder wrote: On Fri, Mar 12, 2010 at 11:55 AM, Andrew James andrew_a_ja...@yahoo.com wrote: I've made the assumption that NSArray wraps an old school contiguous C-style array ( ala C++ std:::vector ) This assumption is false. There was a good analysis of NSArrays at http://ridiculousfish.com/blog/archives/2005/12/23/array/ Cheers, Chris ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
Just a heads-up to say that when I created an NSMutableDictionary on the main thread and then tried to mutate it in a subthread, Snow Leopard threw an exception (trying to mutate a non-mutable object, or somesuch). I was, of course, protecting the mutable dictionary against reentrancy problems and the same code worked fine on Leopard and Tiger. I guess Apple think it's dangerous to let us play with the sharp toys... Paul Sanders ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Mar 12, 2010, at 3:23 PM, Paul Sanders wrote: Just a heads-up to say that when I created an NSMutableDictionary on the main thread and then tried to mutate it in a subthread, Snow Leopard threw an exception (trying to mutate a non-mutable object, or somesuch). I was, of course, protecting the mutable dictionary against reentrancy problems and the same code worked fine on Leopard and Tiger. I guess Apple think it's dangerous to let us play with the sharp toys... mutating method sent to immutable object, you mean? That suggests your NSMutableDictionary object isn't as mutable as you thought. It might not be a thread-related bug. -- Greg Parker gpar...@apple.com Runtime Wrangler ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
No, that would mean that you tried to mutate a non-mutable dictionary. :-) You were getting lucky before in that some dictionary was passed to you that was typed as NSDictionary, but _happened_ to be of the subclass NSMutableDictionary. _That's_ what changed on you. Be aware that if you send -copy to an NSMutableDictionary, you get a non-mutable NSDictionary. -Ken On Fri, Mar 12, 2010 at 3:23 PM, Paul Sanders p.sand...@alpinesoft.co.ukwrote: Just a heads-up to say that when I created an NSMutableDictionary on the main thread and then tried to mutate it in a subthread, Snow Leopard threw an exception (trying to mutate a non-mutable object, or somesuch). I was, of course, protecting the mutable dictionary against reentrancy problems and the same code worked fine on Leopard and Tiger. I guess Apple think it's dangerous to let us play with the sharp toys... Paul Sanders ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/kenferry%40gmail.com This email sent to kenfe...@gmail.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. --aj From: Ken Ferry kenfe...@gmail.com To: Ken Thomases k...@codeweavers.com Cc: Cocoa-Dev List cocoa-dev@lists.apple.com Sent: Wed, March 10, 2010 11:37:31 PM Subject: Re: Better sorting using threads? On Wed, Mar 10, 2010 at 10:34 PM, Ken Thomases k...@codeweavers.com wrote: On Mar 10, 2010, at 11:50 PM, Graham Cox wrote: I've got a situation where sorting an array using sort descriptors is slow. The number of items being sorted is not enormous - about 2,000 - but there could be several sort descriptors and the main string one is using a localized and natural numeric comparison. I cache the results and take a lot of care only to resort when needed, but that doesn't help on the first run through which often takes in the order of 10-20 seconds. The interface that displays the results therefore beachballs for this time. I'm considering using threads to help, where a thread is used to perform the sort itself, and until the sort has finished the UI can display a busy indicator (indeterminate circular progress indicator) next to the selected row in the table. This is in the master table of a master-detail interface where the detail displays the sorted items selected. While busy the detail view can be blank or show the previous arrangement. So my question is, is threading a good solution? While NSMutableArray isn't marked as thread-safe, the array in question can be arranged to not be used outside of the sorting thread, and only substituted for the returned sorted items when complete. Or can array sorting not be done on a thread at all? This is a sensible solution. NSMutableArray is safe so long as only one thread is accessing it at a time. Even more specifically, NSMutableArray is safe so long as either (1) no thread is mutating the array (but an arbitrary number are accessing it) (2) only one thread is accessing the array (and possibly mutating it) Same deal for NSDictionary, and, for that matter, NSImage. Also, rest of email, seconded. :-) -Ken However, sorting 2000 items should not take 10-20 seconds! Have you profiled to find out what's actually taking the time? If a property of the objects has to be massaged into another form before the comparison can take place, it can be a performance win to do that massaging once for each object before the sort and cache the result. Otherwise, it may end up being performed over and over, each time one object is compared to another. (I wouldn't worry about the localized, numeric comparison of strings, though. I don't think there's a good way to preflight those, and I wouldn't think that would be a significant factor in the slowness. But, of course, don't trust my intuition -- measure.) Regards, Ken ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/kenferry%40gmail.com This email sent to kenfe...@gmail.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/andrew_a_james%40yahoo.com This email sent to andrew_a_ja...@yahoo.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Mar 11, 2010, at 11:15 AM, Andrew James wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Depends entirely on need. Keeping a container sorted on insert can be quite expensive; potentially considerably more expensive than doing a single batch sort at the end. On-the-fly sorted containers are generally only applicable when updates to the container will be frequently interleaved with read operations. b.bum ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Probably the best thing to do if you want this is to maintain the sort yourself by inserting new objects in the correct position. You can find the position using -[NSArray indexOfObject:inSortedRange:options:usingComparator:]. That's two lines instead of one to add an object to an array, which is not bad. That method is new in 10.6, but something similar has been in CoreFoundation for a while. CFArrayBSearchValues is usable on NSArray since CFArray is bridged. You can also look at -[NSArray sortedArrayHint]. The deal there is that you extract an opaque hint from a sorted array, change the array, and resort passing in the hint. This is optimized for the case when the array is still mostly sorted, but with some things out of place. -Ken On Thu, Mar 11, 2010 at 10:38 PM, Bill Bumgarner b...@mac.com wrote: On Mar 11, 2010, at 11:15 AM, Andrew James wrote: Does Cocoa have sorted containers so that an object can be inserted in sorted order? If so it seems like this would be far less expensive. Depends entirely on need. Keeping a container sorted on insert can be quite expensive; potentially considerably more expensive than doing a single batch sort at the end. On-the-fly sorted containers are generally only applicable when updates to the container will be frequently interleaved with read operations. b.bum ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/kenferry%40gmail.com This email sent to kenfe...@gmail.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Better sorting using threads?
I've got a situation where sorting an array using sort descriptors is slow. The number of items being sorted is not enormous - about 2,000 - but there could be several sort descriptors and the main string one is using a localized and natural numeric comparison. I cache the results and take a lot of care only to resort when needed, but that doesn't help on the first run through which often takes in the order of 10-20 seconds. The interface that displays the results therefore beachballs for this time. I'm considering using threads to help, where a thread is used to perform the sort itself, and until the sort has finished the UI can display a busy indicator (indeterminate circular progress indicator) next to the selected row in the table. This is in the master table of a master-detail interface where the detail displays the sorted items selected. While busy the detail view can be blank or show the previous arrangement. So my question is, is threading a good solution? While NSMutableArray isn't marked as thread-safe, the array in question can be arranged to not be used outside of the sorting thread, and only substituted for the returned sorted items when complete. Or can array sorting not be done on a thread at all? --Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Mar 10, 2010, at 11:50 PM, Graham Cox wrote: I've got a situation where sorting an array using sort descriptors is slow. The number of items being sorted is not enormous - about 2,000 - but there could be several sort descriptors and the main string one is using a localized and natural numeric comparison. I cache the results and take a lot of care only to resort when needed, but that doesn't help on the first run through which often takes in the order of 10-20 seconds. The interface that displays the results therefore beachballs for this time. I'm considering using threads to help, where a thread is used to perform the sort itself, and until the sort has finished the UI can display a busy indicator (indeterminate circular progress indicator) next to the selected row in the table. This is in the master table of a master-detail interface where the detail displays the sorted items selected. While busy the detail view can be blank or show the previous arrangement. So my question is, is threading a good solution? While NSMutableArray isn't marked as thread-safe, the array in question can be arranged to not be used outside of the sorting thread, and only substituted for the returned sorted items when complete. Or can array sorting not be done on a thread at all? This is a sensible solution. NSMutableArray is safe so long as only one thread is accessing it at a time. However, sorting 2000 items should not take 10-20 seconds! Have you profiled to find out what's actually taking the time? If a property of the objects has to be massaged into another form before the comparison can take place, it can be a performance win to do that massaging once for each object before the sort and cache the result. Otherwise, it may end up being performed over and over, each time one object is compared to another. (I wouldn't worry about the localized, numeric comparison of strings, though. I don't think there's a good way to preflight those, and I wouldn't think that would be a significant factor in the slowness. But, of course, don't trust my intuition -- measure.) Regards, Ken ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On 11/03/2010, at 5:34 PM, Ken Thomases wrote: However, sorting 2000 items should not take 10-20 seconds! Have you profiled to find out what's actually taking the time? Thanks Ken, your response prompted me to question my assumptions, and indeed, the culprit was something else entirely. As a result I probably no longer need to worry about the sorting time and will stick to doing it synchronously for now. --Graham ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
Re: Better sorting using threads?
On Wed, Mar 10, 2010 at 10:34 PM, Ken Thomases k...@codeweavers.com wrote: On Mar 10, 2010, at 11:50 PM, Graham Cox wrote: I've got a situation where sorting an array using sort descriptors is slow. The number of items being sorted is not enormous - about 2,000 - but there could be several sort descriptors and the main string one is using a localized and natural numeric comparison. I cache the results and take a lot of care only to resort when needed, but that doesn't help on the first run through which often takes in the order of 10-20 seconds. The interface that displays the results therefore beachballs for this time. I'm considering using threads to help, where a thread is used to perform the sort itself, and until the sort has finished the UI can display a busy indicator (indeterminate circular progress indicator) next to the selected row in the table. This is in the master table of a master-detail interface where the detail displays the sorted items selected. While busy the detail view can be blank or show the previous arrangement. So my question is, is threading a good solution? While NSMutableArray isn't marked as thread-safe, the array in question can be arranged to not be used outside of the sorting thread, and only substituted for the returned sorted items when complete. Or can array sorting not be done on a thread at all? This is a sensible solution. NSMutableArray is safe so long as only one thread is accessing it at a time. Even more specifically, NSMutableArray is safe so long as either (1) no thread is mutating the array (but an arbitrary number are accessing it) (2) only one thread is accessing the array (and possibly mutating it) Same deal for NSDictionary, and, for that matter, NSImage. Also, rest of email, seconded. :-) -Ken However, sorting 2000 items should not take 10-20 seconds! Have you profiled to find out what's actually taking the time? If a property of the objects has to be massaged into another form before the comparison can take place, it can be a performance win to do that massaging once for each object before the sort and cache the result. Otherwise, it may end up being performed over and over, each time one object is compared to another. (I wouldn't worry about the localized, numeric comparison of strings, though. I don't think there's a good way to preflight those, and I wouldn't think that would be a significant factor in the slowness. But, of course, don't trust my intuition -- measure.) Regards, Ken ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/kenferry%40gmail.com This email sent to kenfe...@gmail.com ___ Cocoa-dev mailing list (Cocoa-dev@lists.apple.com) Please do not post admin requests or moderator comments to the list. Contact the moderators at cocoa-dev-admins(at)lists.apple.com Help/Unsubscribe/Update your Subscription: http://lists.apple.com/mailman/options/cocoa-dev/archive%40mail-archive.com This email sent to arch...@mail-archive.com
