2014-09-20 25 views
15

Kiedy chcę się upewnić, że wpis, którego chcę użyć, zwykle to robię.Czy dzieje się to wolniej z powodu dwóch wyszukiwań zamiast jednego?

#include <unordered_map> 

struct type { int member; }; 
std::unordered_map<type> map; 

if (map.find(key) != map.end()) 
    map[key].member = 42; 

Myślę jednak, że wykonuje dwa wyszukiwań dla key w mapie mieszania. To buforuje wyszukiwanie.

#include <unordered_map> 

struct type { int member; }; 
std::unordered_map<type> map; 

auto find = map.find(key); 
if (find != map.end()) 
    find->second.member = 42; 

Pierwsza opcja wydaje się bardziej wyrazista. Czy to naprawdę wolniej?

Odpowiedz

15

Tak, ponieważ dwukrotnie przeszukujesz klucz: map[key] szukaj klucza dokładnie tak, jak map.find, którego wynik odrzucono.

To tak, jakby otworzyć szufladę, aby zobaczyć, czy jest dany obiekt, powiedz "ach tak!" i zamknij szufladę, a następnie otwórz ją ponownie i zbadaj obiekt, aby ją zmienić.

Drugi kod otwiera szufladę, wyszukaj obiekt i zmień go.

Mogą istnieć optymalizacje kompilatora, które pozwolą uniknąć podwójnego wyszukiwania lub które mogą zredukować wyszukiwanie w stałym czasie, i może istnieć optymalizacja kompilatora, która pozwoli uniknąć zapisania w pamięci zmiennej auto find (może to być Rejestr procesora, ponieważ jego użycie jest bardzo lokalne).

Cały problem w efekcie zmniejszenia porównując czas dwukrotnie hash obliczeń dwukrotnie (i chodzić ewentualne mapa gniazdo, w przypadku kolizji hash) i czasu, aby uzyskać dostęp do dodatkowej zmiennej:

2*H < H+M 

Oznacza to H < M. Jeśli M jest rejestrem, a H nie jest banalne, to trudno jest H być mniej niż M.

+1

Nie wiesz, że będzie to szybsze ", dopóki nie zostanie zmierzone za pomocą profilowania. A co z dodatkowym zapisem do pamięci, który jest przedmiotem handlu dla 'find' i wyszukiwania hash są szybkie. –

+1

Lokalna zmienna automatyczna (iterator mapy) jest najprawdopodobniej zoptymalizowana w rejestrze procesora. Spacer wewnątrz drzewa mapy jest wykonany z pewnością dwa razy (i jeśli mapa ma węzeł 2^10, wymaga 10 odczytów w rzadkich miejscach pamięci) A ponieważ lokalizacje są rzadkie, buforowanie i wyszukiwanie hash niekoniecznie pomaga. Wektory (zamiast mapy) będziesz prawie pewny. –

+3

Czy istnieje szansa, że ​​kompilator optymalizuje to? – danijar

22

może być wolniejsze, nie może (jesteś teraz robi dodatkowy zapis w swoje „przyspieszyć”), ale tak naprawdę nie należy się martwić o takich drobnych optymalizacji kiedy pisania kodu. Napisz wyraźny kod ekspresyjny. Jeśli twój program naprawdę działa zbyt wolno, uruchom narzędzia profilowania i znajdź wąskie gardła. Jeśli ten kod jest w rzeczywistości problem , wtedy i tylko wtedy spróbuj "przyspieszyć" i sprawdzić, czy to ma znaczenie.

+2

Chociaż zgadzam się z większością odpowiedzi (+1) - w rzeczywistości nie wiemy, czy istnieje dodatkowy zapis w pamięci. Kompilator może po prostu używać rejestrów lub zapisywać w pamięci (co prawdopodobnie dzieje się w zoptymalizowanej kompilacji). –

+0

@MaciejPiechotka ma rację, zredagowana odpowiedź odpowiednio - dzięki –

+1

Po prostu "programy często spędzają niesamowite ilości czasu w miejscach * darndest *". :-) –

2

Chyba że masz konkretny powód, aby zachować wartość w istniejącej pozycji (jeśli już istnieje) można pominąć pierwszy przeszukiwanie całkowicie i po prostu ustawić nową wartość:

#include <unordered_map> 

struct type { int member; }; 
std::unordered_map<key_t, type> map; 

map[key].member = 42; 

To będzie modyfikować istniejący wpis (jeśli taki istnieje) i wstaw nowy wpis, jeśli nie istnieje.

+0

Podejrzewam, że OP nie chce utworzyć wpisu, jeśli jeszcze go tam nie ma. W przeciwnym razie logika "jeśli nie zostanie znaleziona, a następnie utworzy" w "mapie [x]" jest najlepszym wyborem ekspresyjnym. –

+0

Jestem tego świadomy, dzięki. – danijar

+0

@EmilioGaravaglia: ... a jednak to, co mówi, brzmi: "Kiedy chcę się upewnić, że wpis, który chcę użyć, istnieje [...]" –

2

Tak, może być wolniejsza. Jeśli szukasz czegoś bardziej ekspresyjnego, powinieneś zamknąć enkoder std:unordered_map (co i tak może być dobrym pomysłem) i odsłonić wskaźnik. Następnie można napisać coś takiego:

auto thing = getThing(key); 
if (thing) 
    thing->member = 42; 
+0

Nie rozumiem, dlaczego standardowy kontener nie zapewnia takich informacji metoda. – danijar

8

Tak, to może być wolniejsze, ale prawdopodobnie nie wymiernie wolniej.Jest jakaś dodatkowa praca zaangażowany:

  1. Haszysz będzie prawdopodobnie obliczana dwa razy, chyba że masz sufficiently smart compiler, extentions wykorzystanie dostawców takich jak pure or const lub użyć podobnej metody. Zauważ, że jeśli hash jest trywialne i kompilator wie, że jest to kod większości kompilatorów prawdopodobnie są wystarczająco inteligentne w dzisiejszych czasach.
  2. Stanowisko wiadra trzeba znaleźć drugi raz (chyba że kompilator nie zauważy, że jest to ten sam hash więc nie trzeba przeliczyć)
  3. traversal list kolizji (lub podobny sposób w zależności od rozdzielczości kolizji) musi zostać wykonany. Znowu - wystarczająco inteligentny kompilator zauważy, że robimy to dwa razy, właściwie nic nie modyfikujemy itd. Możemy mieć takie kompilatory w dzisiejszych czasach, ale nie jestem w 100% pewny, czy tam jesteśmy. Nawet jeśli nie są, to są przechowywane w pamięci podręcznej i prawdopodobnie nie narzucą żadnych znaczących kosztów (w porównaniu na przykład do robienia haszyszu lub nieudanego odczytu). Nie wchodzenie w szczegóły architektury procesora Odczytywanie L1 $ powoduje ~ 4 cykle opóźnienia w i7 (dane z pamięci, mogą być błędne) i procesor może wykonywać inne prace podczas oczekiwania na to.

Więc Podsumowując, jeżeli:

  • Twoja funkcja skrótu jest drogie (na przykład musi wziąć hash ciąg).
  • Kompilator jest niewystarczająco inteligentny, aby wydedukować, że funkcja skrótu nie modyfikuje obiektu i rzeczywiście zwraca tę samą wartość.
  • To kod w wewnętrznej pętli.

następnie może zobaczyć różnicę.


Jako ostatnie słowo - prawdopodobnie nie będzie miało to znaczenia i nie będzie to duża różnica architektoniczna, ale optymalizacja 5s. Pisz więc, co jest łatwiejsze do utrzymania, i wróć do pytania, gdy profiler pokaże, że to działanie powoduje spowolnienie.