W zadanku DES, pomimo dużych danych wejściowych, był problem z rozróżnieniem złożoności rozwiązań za pomocą testów dlatego, że "gorsze" rozwiązania dobrze korzystały z cache. (pomijając, że być może limity były źle dobrane)

Teraz pytanie, czy to oznacza, że dobrze byłoby (jedna z opcji):

(a) Wprowadzić na Potyczkach liczniki instrukcji jak na OI i oceniać rozwiązania z teoretycznym założeniem, że losowy dostęp do pamięci zajmuje O(1)

(b) Wrócić na OI do realnego pomiaru czasu, bo losowy dostęp do pamięci nie jest O(1), tylko bardziej O(sqrt(n)) - Tomek Czajka podlinkował: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

(c) Zmodyfikować pomiar za pomocą liczników instrukcji, żeby wypluwał "czas" w modelu, gdzie losowy dostęp do pamięci rozmiaru n zajmuje magiczna_stała*sqrt(n) - co może być dość problematyczne

Ja chyba lubię po prostu realny pomiar - lubię implementować algorytmy, żeby je odpalić na realnej maszynie, a nie żeby miały dobry czas w jakimś teoretycznym modelu obliczeń. Ciekawa sprawa, że być może trzeba zrewidować to całe założenie O(1) dostępu do pamięci w algorytmice. A co Wy myślicie?

Tak z ciekawości jak dokładnie zrealizowany jest ten pomiar instrukcji?

To, że mam dwa razy więcej wykonanych instrukcji wcale nie oznacza iż mój jest dwa razy wolniejszy. Wręcz może być dużo szybszy jeśli ładnie rozbija zależności w kodzie i wykorzystuje wszystkie ALU.

Da się też zrobić szybki algorytm dziel i rządź dla DES bez losowego skakania po pamięci, tak jak wspomniałem dalej w wątku.

Też wolę realny czas działania a nie liczbę instrukcji. Szczególnie że jest opcja uruchomienia próbnego i można sobie zmierzyć na docelowej maszynie.

Jeśli zaś miałaby być liczba instrukcji, to na pewno musiałoby to być napisane wyraźnie wprost.

Szczerze to nie wiem dokładnie, ale wydaje mi się, że implementacja na OI (przynajmniej ta oryginalna) po prostu zlicza liczbę instrukcji asm i każda ma taki sam koszt, łącznie z operacją odczytu pamięci. Czyli każdy cykl procesora to jedna instrukcja i tyle. Czyli inaczej niż w rzeczywistości, gdzie instrukcja może trwać kilka-kilkanaście cykli i pipelinuje się równolegle z innymi instrukcjami. Nie ma kar za dostęp do pamięci ani za ify, które źle się branch-predictują, ani nic takiego. Chyba...

"Wykorzystywany model opiera się na zliczaniu instrukcji wykonanych przez uruchomiony program, co w odzwierciedla procesor z bardzo dużą pamięcią podręczną. Ewaluację takiego modelu na zadaniach Olimpiady Informatycznej można zobaczyć w rozdziale 3 następującej pracy:

Sz. Acedański, Wykorzystanie sprzętowych liczników zdarzeń do oceny wydajności algorytmów. Praca magisterska, WMiM UW (2009)."
https://homepage.accek.net/wp-content/papercite-data/pdf/acemgr09.pdf

Osobiście też jestem za realnym czasem, ale problem z nim jest taki, że nie jest on zawsze taki sam. Pewnie nie tylko mi się zdarzyło że jakieś rozwiązanie co się wywaliło na TL, po wysłaniu prośby o ponowne sprawdzenie przeszło. Nie wiem co może mieć na to wpływ: obciążenie? Ale chyba organizatorzy nie puszczają kilku rzeczy na raz na jednej sprawdzaczce?

> po wysłaniu prośby o ponowne sprawdzenie przeszło

To można dwa razy próbować??

Zgadzam się jednak, że determinizm i przenośność modelu to jest spora zaleta limitu na instrukcje zamiast na czas.

Jest taki minus, że gcc nie optymalizuje pod względem takiego kryterium, więc pewnie można sporo zaoszczędzić pisząc samemu w asemblerze (wiem, że przepisy zabraniają), albo jakoś sztucznie zmieniając kod tak żeby wyszło mniej instrukcji mimo że wolniejszych.

Na przykład: https://godbolt.org/z/rW8Pzvssa
x % n jest skompilowane do 4 instrukcji (nie licząc końcowego ret)
x % 5 jest skompilowane do 11 instrukcji, jako optymalizacja, bo dzielenie przez 5 można wykonać łatwiej używając prostszych operacji

No i zgadzam się z Adamem, że jest pewna satysfakcja w tym, że obliczamy coś na prawdziwej maszynie a nie na modelu.

> To można dwa razy próbować??

Nie mogę teraz tego znaleźć (pewnie to było jeszcze w sio a nie w sio2), ale z tego co pamiętam kiedyś zarobiłem na takiej operacji punkt czy 2.