NSMutableDictionary znacznie wolniejszy niż Java Map ... dlaczego?

Question

Poniższy kod, który odwzorowuje proste obiekty wartościowe na obiekt, działa w Javie ponad 15 razy szybciej niż w Objective-C przy użyciu XCode 7 beta3, "Najszybsze, agresywne optymalizacje [-Ofast]". Mogę uzyskać ponad 280M odsyłaczy/sekundę w Javie, ale tylko około 19M w przykładzie objc. (Opublikowalam odpowiedni kod Javy tutaj, poniewaz rozpoczal to jako porównanie Swift: Swift Dictionary slow even with optimizations: doing uncessary retain/release?).

To jest uproszczona wersja mojego prawdziwego kodu, który jest zdecydowanie związany z czasem szukania hash i wykazuje również tę ogólną różnicę wydajności. W poniższym teście testuję wartość null tylko po to, aby kompilator nie optymalizował wyszukiwania, ale w prawdziwej aplikacji używałbym tej wartości w większości przypadków.

Kiedy patrzę na instrumenty, widzę dużo czasu spędzonego na zachowaniu/zwolnieniu, msgSend i niektórych blokujących połączeniach, których nie rozumiem.

Wszelkie sugestie na temat tego, co może być przyczyną 10-15 razy wolniej niż Java lub wszelkie obejścia byłyby mile widziane. Mogę faktycznie zaimplementować idealny skrót taki jak ten poniżej, więc gdybym mógł go znaleźć, mógłbym użyć szybkiego słownika int-object dla systemu iOS.

@interface MyKey : NSObject <NSCopying> 
    @property int xi; 
@end 

@implementation MyKey 
    - (NSUInteger)hash { return self.xi; } 
    - (BOOL)isEqual:(id)object { return ((MyKey *)object).xi == self.xi; } 
    - (id)copyWithZone:(NSZone *)zone { return self; } 

@end 

    NSMutableDictionary *map = [NSMutableDictionary dictionaryWithCapacity:2501]; 
    NSObject *obj = [[NSObject alloc] init]; 

    int range = 2500; 
    for (int x=0; x<range; x++) { 
     MyKey *key = [[MyKey alloc] init]; 
     key.xi=x; 
     [map setObject:obj forKey:key]; 
    } 

    MyKey *key = [[MyKey alloc] init]; 
    int runs = 50; 
    for (int run=0; run<runs; run++) 
    { 
     NSDate *start = [NSDate date]; 

     int reps = 10000; 
     for(int rep=0; rep<reps; rep++) 
     { 
      for (int x=0; x<range; x++) { 
       key.xi=x; 
       if ([map objectForKey:key] == nil) { NSLog(@"missing key"); } 
      } 
     } 

     NSLog(@"rate = %f", reps*range/[[NSDate date] timeIntervalSinceDate:start]); 
    } 

Answer 1

Można reimplement metodę -isEqual: tak aby uniknąć udostępniające właściwości:

- (BOOL) isEqual:(id)other 
{ 
    return _xi == ((MyKey*)other)->_xi; 
} 

To nie byłoby dopuszczalne, jeśli klasa MyKey może być podklasy, ale widzę z kodu Java, że ​​klasa jest final.

Answer 2

Złożoność obliczeniowa w NSMutableDictionary jest następny (z pliku CFDictionary.h):

The access time for a value in the dictionary is guaranteed to be at 
worst O(N) for any implementation, current and future, but will 
often be O(1) (constant time). Insertion or deletion operations 
will typically be constant time as well, but are O(N*N) in the 
worst case in some implementations. Access of values through a key 
is faster than accessing values directly (if there are any such 
operations). Dictionaries will tend to use significantly more memory 
than a array with the same number of values. 

Znaczy, prawie cały czas trzeba mieć O (1) złożoność na dostęp/wstawiania/usuwania. W przypadku Javy HashMap powinieneś uzyskać prawie to samo.

Według badań this nie ma żadnych korzyści przy korzystaniu z inicjatora wygodności dictionaryWithCapacity:.

W przypadku użycia liczby całkowitej jako klucza prawdopodobnie możliwe byłoby zastąpienie słownika tablicą.

W tym WWDC session wyjaśnił objc_msgSend problemy z wydajnością i jak sobie z nimi poradzić. Pierwsze rozwiązanie to użycie kontenerów C++ i STL. Drugi to użycie Swift, ponieważ w przeciwieństwie do Objective-C jest dynamiczny tylko wtedy, gdy się go zauważa.