• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

  • Follow-Ups:
    • Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
      • From: glenn andreas <email@hidden>
References: 
 >Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ? (From: Aurélien Hugelé <email@hidden>)
 >Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ? (From: glenn andreas <email@hidden>)

  • Prev by Date: Re: iCal Alarms
  • Next by Date: Re: scaling down without NSImage while printing
  • Previous by thread: Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
  • Next by thread: Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
  • Index(es):
    • Date
    • Thread