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

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
    }
}

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.

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.

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.

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.

@ 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

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.

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.