Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
- Subject: Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
- From: Aurélien Hugelé <email@hidden>
- Date: Thu, 23 Dec 2004 19:17:23 +0100
for those of you that are interested :
here is my test code : compiled with gcc3.3 -03
#import <Foundation/Foundation.h>
#define CAPACITY 20000
int main (int argc, const char * argv[]) {
NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];
// initialize randomization
srandomdev();
NSMutableArray* array = [[NSMutableArray alloc] initWithCapacity:CAPACITY];
int i ;
for(i = 0 ; i < CAPACITY ; i++)
{
NSNumber* nbr = [[NSNumber alloc] initWithLong:random()];
[array addObject:nbr];
[nbr release];
}
// find the half last range of the array (let's say it will force the worst case scenario)
i = CAPACITY;
while(i-- > CAPACITY/2)
{
// CASE 1 : "slow" indexOfObject:
// [array indexOfObject:[array objectAtIndex:i]];
// CASE 2 : "fast" indexOfObjectIdenticalTo:
[array indexOfObjectIdenticalTo:[array objectAtIndex:i]];
}
[array release];
[pool release];
return 0;
}
RESULTS :
// CASE 1 : "slow" indexOfObject:
# Report 0 - Session 1 - Time Profile of Essais
SharkProfileViewer
# Generated from the visible portion of the outline view
+ 13.9 s _dyld_start (dyld)
| + 13.9 s _start (Essais)
| | + 13.9 s main (Essais)
| | | + 13.9 s -[NSCFArray indexOfObject:] (Foundation)
| | | | + 13.9 s CFArrayGetFirstIndexOfValue (CoreFoundation)
| | | | | + 9.7 s CFEqual (CoreFoundation)
| | | | | | + 7.4 s __CFNumberEqual (CoreFoundation)
| | | | | | | + 6.8 s __CFNumberEqualValue (CoreFoundation)
| | | | | | | | 4.5 s __CFNumberGetValue (CoreFoundation)
| | | | | 298.2 ms __CF_INVOKE_CALLBACK (CoreFoundation)
| | | | 1.0 ms CFArrayGetCount (CoreFoundation)
| | | - 6.0 ms -[NSPlaceholderNumber initWithLong:] (Foundation)
| | | - 4.0 ms CFArrayAppendValue (CoreFoundation)
| | | 2.0 ms objc_msgSend (libobjc.A.dylib)
| | | - 2.0 ms +[NSNumber allocWithZone:] (Foundation)
| | | 1.0 ms dyld_stub_objc_msgSend (Essais)
| | | 1.0 ms -[NSCFArray addObject:] (Foundation)
| | | 1.0 ms CFRelease (CoreFoundation)
| | - 6.1 ms _call_mod_init_funcs (Essais)
- 14.1 ms thandler (mach_kernel)
- 7.0 ms shandler (mach_kernel)
- 1.0 ms _dyld_init (dyld)
- 1.0 ms idle_thread_continue (mach_kernel)
- 1.0 ms thread_continue (mach_kernel)
// CASE 2 : "fast" indexOfObjectIdenticalTo:
# Report 0 - Session 2 - Time Profile of Essais
SharkProfileViewer
# Generated from the visible portion of the outline view
+ 3.5 s _dyld_start (dyld)
| + 3.5 s _start (Essais)
| | + 3.5 s main (Essais)
| | | + 3.4 s -[NSCFArray indexOfObjectIdenticalTo:] (Foundation)
| | | | 1.3 s CFArrayGetValueAtIndex (CoreFoundation)
| | | | + 1.2 s main (Essais)
| | | | | 1.2 s CFArrayGetValueAtIndex (CoreFoundation)
| | | | 635.2 ms dyld_stub_CFArrayGetValueAtIndex (Foundation)
| | | - 9.0 ms -[NSPlaceholderNumber initWithLong:] (Foundation)
| | | - 2.0 ms CFArrayAppendValue (CoreFoundation)
| | | - 1.0 ms -[NSCFArray addObject:] (Foundation)
| | | 1.0 ms objc_msgSend (libobjc.A.dylib)
| | | 1.0 ms dyld_stub_CFArrayAppendValue (Foundation)
| | | 1.0 ms dyld_stub_objc_msgSend (Essais)
| | | 1.0 ms random (libSystem.B.dylib)
| | | - 1.0 ms NSPopAutoreleasePool (Foundation)
| | - 3.0 ms _call_mod_init_funcs (Essais)
| | - 1.0 ms __keymgr_dwarf2_register_sections (libSystem.B.dylib)
- 10.1 ms thandler (mach_kernel)
- 8.0 ms shandler (mach_kernel)
- 2.0 ms _dyld_init (dyld)
almost 5 times faster !
imo the algorithm is clearly different :
| | | + 3.4 s -[NSCFArray indexOfObjectIdenticalTo:] (Foundation)
| | | | 1.3 s CFArrayGetValueAtIndex (CoreFoundation) => it seems the index is IMMEDIATLY found ??
whereas :
| | | + 13.9 s -[NSCFArray indexOfObject:] (Foundation)
| | | | + 13.9 s CFArrayGetFirstIndexOfValue (CoreFoundation) => the index must be found by enumerating the array...
i've looked at CFArray source code :
CFIndex CFArrayGetFirstIndexOfValue(CFArrayRef array, CFRange range, const void *value) {
const CFArrayCallBacks *cb;
CFIndex idx;
CF_OBJC_FUNCDISPATCH2(__kCFArrayTypeID, CFIndex, array, "_cfindexOfObject:inRange:", value, range);
cb = __CFArrayGetCallBacks(array);
for (idx = 0; idx < range.length; idx++) {
const void *item = __CFArrayGetBucketAtIndex(array, range.location + idx)->_item;
if (value == item || (cb->equal && INVOKE_CALLBACK2(cb->equal, value, item))) // THIS IS WERE THE TEST IS DONE, AND IT SEEMS THAT THEY USE " == " as an optimization too (they can avoid the cb->equal function call if value == item)
return idx + range.location;
}
return kCFNotFound;
}
too bad the code of NSCFArray is not available ;)
anyone ?
On 23 déc. 04, at 15:58, glenn andreas wrote:
On Dec 23, 2004, at 7:21 AM, Aurélien Hugelé wrote:
hi list !
i'm tuning my application and since a long time ago, i noticed that using indexOfObjectIdenticalTo: is far (i mean something like 1000 x faster on 20 000 items) faster that indexOfObject:
IMO indexOfObject is just Olog(n) because it needs full traversal of the array if the searched object is the last one.
but indexOfObjectIdenticalTo: use probably the same algorithm except that the equality test is faster (address equality instead of (slower?) isEqual: message)
but i think the speed difference would not be so large. I suppose that in fact, NSArray use an internal structure to link an object address to its index in the array...
Am i totally wrong ? is it "normal" that a "==" test is 1000 times faster than isEqual: ?
what's your opinion ?
That you should use Shark and sample your application and actually see what it is doing.
(Though certainly == is one instruction and isEqual is perhaps hundreds of instructions).
Glenn Andreas email@hidden
<http://www.gandreas.com/> oh my!
Mad, Bad, and Dangerous to Know
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden