Czy porównanie 1 <10 jest tańsze niż 1 <1000000?

65

Właśnie wykorzystałem ~ 1 miliard jako liczbę z-indexw CSS i zastanawiałem się nad porównaniami, które muszą trwać. Czy istnieje różnica w wydajności na poziomie ALU w porównaniu między bardzo dużymi liczbami a bardzo małymi?

Na przykład, czy jeden z tych dwóch fragmentów byłby droższy od drugiego?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}
Viziionary
źródło
12
OP nie pyta, ile czasu zajmie rozgałęzienie. Najwyraźniej przykład ma zapewnić, że zajmie to dokładnie tyle samo czasu w obu fragmentach. Pytanie dotyczy tego, czy indywidualna CMPinstrukcja maszyny będzie wolniejsza, jeśli ibędzie większa.
Kilian Foth
18
Ponieważ odbywa się to w CSS, konwersja ciągu na liczbę całkowitą prawdopodobnie zdominuje samą operację porównania pod względem czasu spędzonego na wykonywaniu.
58
Jeśli potrzebujesz użyć 1000000000 jako indeksu Z w pliku CSS, zrobiłeś coś złego.
Bergi
6
W przypadku CSS narzut związany z konwersją tekstu na liczbę całkowitą będzie zależeć od liczby konwertowanych cyfr (gdzie liczba 6 cyfr, np. 1000000, może być około 6 razy droższa niż liczba 1 cyfr, np. 1); i narzut ten może być o rząd wielkości większy niż narzut porównań liczb całkowitych.
Brendan

Odpowiedzi:

82

Każdy procesor, nad którym pracowałem, porównuje, odejmując jeden z operandów od drugiego, odrzucając wynik i pozostawiając flagi procesora (zero, ujemne itp.) Same. Ponieważ odejmowanie odbywa się jako pojedyncza operacja, zawartość operandów nie ma znaczenia.

Najlepszym sposobem, aby na pewno odpowiedzieć na to pytanie, jest skompilowanie kodu w asemblerze i zapoznanie się z dokumentacją procesora docelowego w celu uzyskania instrukcji. Dla obecnych procesorów Intel byłby to Podręcznik programisty architektury Intel 64 i IA-32 Architectures .

Opis instrukcji CMP(„porównaj”) znajduje się w tomie 2A, na stronie 3-126 lub na stronie 618 pliku PDF i opisuje jej działanie jako:

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

Oznacza to, że drugi argument jest w razie potrzeby przedłużany o znak, odejmowany od pierwszego argumentu, a wynik umieszczany w tymczasowym obszarze procesora. Następnie flagi stanu są ustawiane w taki sam sposób, jak w przypadku instrukcji SUB(„odejmowanie”) (strona 1492 pliku PDF).

W dokumentacji CMPlub SUBdokumentacji nie ma wzmianki, że wartości argumentów mają wpływ na opóźnienie, więc każda używana wartość jest bezpieczna.

Blrfl
źródło
5
Co się stanie, jeśli liczba będzie zbyt duża dla 32-bitowej arytmetyki? Czy to nie byłoby podzielone na wolniejsze obliczenia?
Falco
3
@Falco Nie na procesorze z 64-bitową jednostką ALU (która jest właściwie prawie wszystkim z wyjątkiem obecnie osadzonej przestrzeni).
reirab
8
@Falco: Tak, ale ponieważ pytanie dotyczy wydajności ALU, implikacja jest taka, że ​​wartości mieszczą się w rozmiarze słowa procesora lub możliwościach wszelkich instrukcji SIMD, jakie może mieć. Operowanie na większej liczbie liczb musiałoby zostać zaimplementowane z wieloma instrukcjami poza procesorem. Było to bardzo powszechne 30 lat temu, gdy miałeś do czynienia z rejestrami 8- lub 16-bitowymi.
Blrfl
6
@Falco Jak wymagałoby to debugowania? To nie jest błąd; nieco wolniej jest wykonywać operacje 64-bitowe na procesorze, który natywnie nie obsługuje operacji 64-bitowych. Sugestia, że ​​nigdy nie należy używać liczby powyżej 2 ^ 31-1, wydaje się nieco śmieszna.
reirab
2
@ Falco Powiedziawszy to, czy silniki renderujące w przeglądarkach używają nawet liczb całkowitych do reprezentowania wskaźników Z? Większość silników renderujących, które znam do używania pływaków jednoprecyzyjnych do wszystkiego (do ostatniego etapu rasteryzacji), ale tak naprawdę nie studiowałem silników renderujących przeglądarki.
reirab
25

Czy istnieje różnica w wydajności na poziomie ALU w porównaniu między bardzo dużymi liczbami a bardzo małymi?

Jest to bardzo mało prawdopodobne, chyba że przejście od małej liczby do dużej zmieni typ liczbowy, powiedzmy od a intdo a long. Nawet wtedy różnica może nie być znacząca. Bardziej prawdopodobne jest, że zauważysz różnicę, jeśli Twój język programowania po cichu przełączy się na arytmetykę dowolnej precyzji pod przykrywkami.

Niemniej jednak Twój kompilator może przeprowadzać sprytne optymalizacje, o których nie wiesz. Dowiesz się, jak mierzyć. Uruchom profiler na swoim kodzie; sprawdź, które porównania trwają najdłużej. Lub po prostu uruchom i zatrzymaj stoper.

Robert Harvey
źródło
Należy wspomnieć, że proponowane liczby w pytaniu są różnego typu liczbowego w typowym 32-bitowym typie całkowitym ...
Falco
19

Wiele procesorów ma „małe” instrukcje, które mogą wykonywać operacje arytmetyczne, w tym porównania, na niektórych natychmiast określonych operandach. Operandy inne niż te wartości specjalne muszą albo używać większego formatu instrukcji, albo w niektórych przypadkach muszą używać instrukcji „ładuj wartość z pamięci”. Na przykład w zestawie instrukcji ARM Cortex-M3 istnieje co najmniej pięć sposobów na porównanie wartości ze stałą:

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

Pierwsza forma jest najmniejsza; druga i trzecia postać może, ale nie musi, wykonać tak szybko, w zależności od szybkości pamięci, z której pobierany jest kod. Czwarta forma będzie prawie na pewno wolniejsza niż pierwsze trzy, a piąta forma nawet wolniejsza, ale tej drugiej można używać z dowolną wartością 32-bitową.

Na starszych procesorach x86 instrukcje porównywania krótkich formularzy byłyby wykonywane szybciej niż te długie, ale wiele nowszych procesorów konwertuje zarówno długie, jak i krótkie formularze na tę samą reprezentację, gdy są one pobierane po raz pierwszy, i przechowuje tę jednolitą reprezentację w pamięci podręcznej. Tak więc, podczas gdy kontrolery wbudowane (takie jak te znajdujące się na wielu platformach mobilnych) będą miały różnicę prędkości, wiele komputerów opartych na architekturze x86 nie.

Należy również zauważyć, że w wielu przypadkach, w których stała jest intensywnie używana w pętli, kompilator będzie musiał załadować ją do rejestru tylko raz - przed rozpoczęciem pętli - sprawiając, że różnice czasowe będą dyskusyjne. Z drugiej strony zdarzają się sytuacje, nawet w małych pętlach, w których nie zawsze tak się dzieje; jeśli pętla jest mała, ale mocno wykonana, czasami może występować znaczna wydajność między porównaniami obejmującymi krótkie wartości bezpośrednie i tymi obejmującymi dłuższe.

supercat
źródło
W MIPS możesz mieć tylko 16-bitowe bezpośrednie, więc zdecydowanie porównanie z 1 będzie krótsze i (prawdopodobnie) szybsze niż 1000000. Może to samo z Sparc i PowerPC. I wydaje mi się, że przeczytałem z niektórych źródeł, że Intel optymalizuje również operacje na małych natychmiastach w kilku przypadkach, ale nie jestem pewien, czy będzie to porównanie
phuclv
@ LưuVĩnhPhúc: Rejestr można załadować przed pętlą. W tym momencie faktyczne porównanie będzie w obu przypadkach taką samą liczbą instrukcji.
cHao
Ponieważ Pętla była tylko przykładem operacji, a pytanie dotyczyło na przykład indeksu Z, jeśli masz 1000 obiektów, każdy z własnym indeksem Z i ustawiłeś je na 100000000 ... 1000000999 lub na 10000 ... 10999 i zapętlasz je w celu sortowania przed renderowaniem, istnieje wiele porównań i wiele instrukcji ładowania. To może mieć znaczenie!
Falco
@Falco: W takim przypadku natychmiastowe nawet nie uwzględniałoby; ładowanie i porównywanie z rejestrem wydaje się prawie nieuniknione.
cHao
@ cHao: Jeśli porównamy ze sobą indeksy Z, znajdą się w rejestrach. Jeśli niektóre zakresy wskaźników są obsługiwane w różny sposób, może to wymagać natychmiastowych porównań. Normalnie stałe byłyby ładowane przed uruchomieniem pętli, ale gdyby np. Jedna miała pętlę, która musiała odczytać pary wartości z pamięci i porównać pierwszą wartość każdej pary z pięcioma różnymi (nierównomiernie rozmieszczonymi) stałymi w zakresie 100000 do 100499 oraz innej wartości z pięcioma innymi takimi stałymi, odjęcie 100250 (przechowywane w rejestrze) może być znacznie szybsze, a następnie porównanie z wartościami -250 do 250 ...
supercat
5

Krótka odpowiedź na to pytanie brzmi: nie , nie ma różnicy czasu, aby porównać dwie liczby na podstawie wielkości tych liczb, zakładając, że są one przechowywane w tym samym typie danych (np. Obie liczby 32-bitowe lub obie długości 64-bitowe).

Co więcej, aż do wielkości słowa ALU , niezwykle mało prawdopodobne jest, aby porównanie dwóch liczb całkowitych ze sobą zajęło więcej niż 1 cykl zegara, ponieważ jest to trywialna operacja równoważna odejmowaniu. Myślę, że każda architektura, z jaką kiedykolwiek miałem do czynienia, miała porównanie liczb całkowitych w jednym cyklu.

Jedyne przypadki, o których mogłem pomyśleć, gdy porównanie dwóch liczb nie było operacją jednego cyklu, są następujące:

  • Instrukcje, w których faktycznie występuje opóźnienie pamięci podczas pobierania operandów, ale to nie ma nic wspólnego z tym, jak działa samo porównanie (i ogólnie nie jest możliwe w architekturach RISC, chociaż zwykle jest to możliwe w projektach CISC, takich jak x86 / x64.)
  • Porównania zmiennoprzecinkowe mogą być wielocyklowe, w zależności od architektury.
  • Liczby, o których mowa, nie pasują do wielkości słowa ALU, dlatego porównanie należy podzielić na wiele instrukcji.
reirab
źródło
4

@ Odpowiedź RobertHarvey jest dobra; rozważ tę odpowiedź jako uzupełnienie jego.


Należy również wziąć pod uwagę przewidywanie gałęzi :

W architekturze komputerowej predyktor gałęzi to obwód cyfrowy, który próbuje zgadnąć, w którą stronę pójdzie gałąź (np. Struktura „jeśli-to-inaczej”), zanim zostanie to z całą pewnością znane. Celem predyktora rozgałęzienia jest poprawa przepływu w potoku instrukcji. Predyktory odgrywają kluczową rolę w osiągnięciu wysokiej wydajności w wielu nowoczesnych architekturach mikroprocesorowych, takich jak x86.

Zasadniczo, w twoim przykładzie, jeśli ifinstrukcja wewnątrz pętli zawsze zwraca tę samą odpowiedź, wówczas system może ją zoptymalizować, poprawnie zgadując, w którą stronę się rozgałęzi. W twoim przykładzie, ponieważ ifinstrukcja w pierwszym przypadku zawsze zwraca ten sam wynik, będzie działać nieco szybciej niż w drugim przypadku.

Doskonałe pytanie przepełnienia stosu na ten temat

durron597
źródło
Przewidywanie rozgałęzień wpływa na czas rozgałęzienia, ale nie na sam czas porównania.
reirab
3

Zależy to od wdrożenia, ale byłoby to bardzo, bardzo mało prawdopodobne .

Przyznaję, że nie przeczytałem szczegółów implementacji różnych silników przeglądarki, a CSS nie określa żadnego konkretnego rodzaju przechowywania numerów. Uważam jednak, że można bezpiecznie założyć, że wszystkie główne przeglądarki używają 64-bitowych liczb zmiennoprzecinkowych podwójnej precyzji („podwaja się”, aby pożyczyć termin z C / C ++), aby obsłużyć większość swoich potrzeb numerycznych w CSS , ponieważ tego właśnie używa JavaScript w przypadku liczb, a więc użycie tego samego typu ułatwia integrację.

Z punktu widzenia komputera wszystkie podwójne przenoszą tę samą ilość danych: 64 bity, bez względu na to, czy wartość wynosi 1, -3,14, czy 1000000, czy 1e100 . Czas potrzebny na wykonanie operacji na tych liczbach nie zależy od rzeczywistej wartości tych liczb, ponieważ zawsze działa na tej samej ilości danych. Kompromis polega na robieniu rzeczy w ten sposób, że liczby podwójne nie mogą dokładnie reprezentować wszystkich liczb (lub nawet wszystkich liczb w swoim zakresie), ale mogą zbliżyć się wystarczająco do większości spraw, a rodzaje rzeczy CSS nie są numeryczne - wystarczająco wymagający, aby potrzebować więcej precyzji niż to. Połącz to z zaletami bezpośredniej zgodności z JavaScriptem, a masz dość mocną argumentację za podwójnymi.

Nie jest niemożliwe, aby ktoś zaimplementował CSS przy użyciu kodowania o zmiennej długości dla liczb. Jeśli ktoś używał kodowania o zmiennej długości, a następnie porównując wobec małych ilościach byłoby mniej kosztowne niż porównywanie przeciwko dużych ilościach, ponieważ duża liczba ma więcej danych do zapaści . Tego rodzaju kodowanie może być bardziej precyzyjne niż binarne, ale są one również znacznie wolniejsze, a w szczególności w przypadku CSS przyrost precyzji prawdopodobnie nie jest wystarczający, aby być wartym wydajności. Byłbym bardzo zaskoczony, gdy dowiedziałem się, że każda przeglądarka działa w ten sposób.

Teoretycznie istnieje jeden możliwy wyjątek od wszystkiego, co powiedziałem powyżej: porównywanie z zerem jest często szybsze niż porównywanie z innymi liczbami . Nie dzieje się tak dlatego, że zero jest krótkie (gdyby to był powód, to 1 powinno być tak samo szybkie, ale tak nie jest). To dlatego, że zero pozwala oszukiwać. Jest to jedyna liczba, w której wszystkie bity są wyłączone, więc jeśli wiesz, że jedna z wartości wynosi zero, nie musisz nawet patrzeć na drugą wartość jako liczbę: jeśli któryś z bitów jest włączony, to nie jest równy zero, a następnie wystarczy spojrzeć na jeden bit, aby zobaczyć, czy jest on większy czy mniejszy od zera.

The Spooniest
źródło
0

Jeśli kod ten był interpretowany za każdym razem, gdy prowadził, nie byłoby różnicy, ponieważ trwa dłużej tokenise i interpretować 10000000000000w porównaniu do 1000. Jest to jednak oczywista pierwsza optymalizacja tłumaczy w tym przypadku: tokenizuj raz i interpretuj tokeny.

Mark Hurd
źródło