Re: Różne czasy dla identycznych zgłoszeń
Jak się okazało, może być jeszcze jedna przyczyna: cache procesora. To dłuższa historia.
O cache:
Poprzedni komputer sprawdzaczkowy był dość wiekowy i miał mały rozmiar cache. Ten jest współczesny i cache jest kilkupoziomowy, bardziej efektywny. Popatrzmy na dwa poniższe programy, oba wypełniają tablicę o rozmiarze 100000000 jedynkami. Nie robią tego po kolei, trochę skaczą. Pierwszy, t1.cpp, skacze co 3:
...a drugi, t2.cpp, co 10001:
(Btw, aby cała tablica została wypełniona, długość skoku musi być względnie pierwsza z rozmiarem tablicy)
Na moim komputerze wykonanie instrukcji
daje następujące wyjście:
...czyli blisko 3-krotną różnicę. To żadne zaskoczenie, w pierwszym przypadku cache jest dużo efektywniej wykorzystywany. Dociekliwi mogą podejrzeć pliki z kodem assemblera i sprawdzić, że skompilowane programy faktycznie wyglądają podobnie. Komputer sprawdzaczki jest szybszy i ma lepszy cache, więc różnica jest jeszcze większa:
O rdzeniach:
Gdy jest sprawdzanych więcej programów jednocześnie, korzysta się z większej liczby rdzeni procesora. Nasze wcześniejsze testy pokazywały, że czas działania procesu jest liczony poprawnie niezależenie od obciążenia rdzeni. W tym celu trzeba było między innymi zrezygnować z mechanizmu zwiększania częstotliwości obciążonego procesora, oferowanego przez serwer. Ten mechanizm powodował, że obciążony serwer szybciej sprawdzał programy niż nieobciążony. Coś, czego nie wzięliśmy pod uwagę to pamięć cache, którą procesy wyrywają sobie nawzajem. Nie mamy na to wpływu, ale zjawisko niestety występuje.
O punktacji:
Całą sprawa wyszła na światło dzienne gdy niedawno włączyliśmy więcej workerów sprawdzających. Przy pełnym rejudge'u zmieniły się czasy działania programów, co skutkowało zmianą punktacji zawodników. Programy, które to dotknęło były dalekie od optymalnych i niedaleko progu odcięcia, ale i tak różnice były większe niż byśmy chcieli.
Co dalej:
Z powrotem przełączyliśmy sprawdzaczkę na pojedynczy worker. Będzie to skutkować tym, że podczas konkursów typu Spot masowe rejudge'e będą trwać dłużej, ale dzięki temu zyskamy większą stabilność oceny. Cache czy nie cache, najlepsze co można zrobić z punktu widzenia zawodnika, to wymyślić i mądrze zaimplementować dobry algorytm.
Jeszcze jedno:
Autor modułu uruchamiającego mówi, że jądro linuksa i tak liczy czas z pewną niedokładnością, na którą również nie mamy wpływu. To jednak są bardzo drobne różnice, rzędu 1-3%.
Mam nadzieję, że więcej problemów z oceniarką już nas nie czeka