Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?

FROM : Aurélien Hugelé
DATE : Thu Dec 23 19:17:23 2004

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_removed> 
>  <http://www.gandreas.com/> oh my!
> Mad, Bad, and Dangerous to Know
>
>