Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 3 ] 
Różne czasy dla identycznych zgłoszeń 
Autor Wiadomość
Gwiazda 3Gwiazda 3Gwiazda 3Gwiazda 3
Avatar użytkownika

Dołączył(a): 11 paź 2010, o 21:22
Posty: 163
Post Różne czasy dla identycznych zgłoszeń
Otóż w przeciągu minuty miałem wysłane 2 zgłoszenia do zadania słownik z artykułu wyszukiwanie binarne. Id zgłoszeń: 31125, 31126. Zgłoszenie te są identyczne - kod skopiowany, wklejony.
Piszę w sprawie czasów podanych przez sprawdzaczkę. W niemal wszystkich testach czasy są identyczne lub bardzo podobne.
"niemal", ponieważ w 8. teście czas dla 1. zgłoszenia to 59ms, a dla 2. - 85ms.
Tutaj to nieistotne, ale na konkursach (np. spotach) różnica czasów prawie 50% może zdecydować o kilku punktach.
Przed chwilą (czyli po kilku godzinach) dla ponownego sprawdzenia czasów wysłałem ten sam kod i otrzymałem 68, 62 i znów 62ms czyli już stabilnie.
Dodam, że w moim algorytmie brak jakichkolwiek randomistycznych funkcji.

Z czego to wynika? Sprawdzaczka może przerabiać różne zgłoszenia w tym samym czasie i w efekcie program może działać wolniej? Czy takie sytuacje są możliwe np. na spocie?


15 lut 2011, o 20:55
Zobacz profil
Avatar użytkownika

Dołączył(a): 17 gru 2010, o 00:08
Posty: 14
Post Re: Różne czasy dla identycznych zgłoszeń
Kamil Dębowski napisał(a):
Otóż w przeciągu minuty miałem wysłane 2 zgłoszenia do zadania słownik z artykułu wyszukiwanie binarne. Id zgłoszeń: 31125, 31126. Zgłoszenie te są identyczne - kod skopiowany, wklejony.
Piszę w sprawie czasów podanych przez sprawdzaczkę. W niemal wszystkich testach czasy są identyczne lub bardzo podobne.
"niemal", ponieważ w 8. teście czas dla 1. zgłoszenia to 59ms, a dla 2. - 85ms.
Tutaj to nieistotne, ale na konkursach (np. spotach) różnica czasów prawie 50% może zdecydować o kilku punktach.
Przed chwilą (czyli po kilku godzinach) dla ponownego sprawdzenia czasów wysłałem ten sam kod i otrzymałem 68, 62 i znów 62ms czyli już stabilnie.
Dodam, że w moim algorytmie brak jakichkolwiek randomistycznych funkcji.

Z czego to wynika? Sprawdzaczka może przerabiać różne zgłoszenia w tym samym czasie i w efekcie program może działać wolniej? Czy takie sytuacje są możliwe np. na spocie?


Przyczyny mogą być dwie.
Po pierwsze, w tym zadaniu sam algorytm działa bardzo szybko i istotną operacją staje wczytywanie danych, co zawsze wprowadza pewien niedeterminizm.
Po drugie, każdy program może mieć pewien stały niedeterminizm czasu działania. W prawdziwych zadaniach, np na Spotach, czasy wykonania są znacznie dłuższe, przez co różnice stają się zaniedbywalne. Duża różnica może się pojawić jedynie dla programów o bardzo krótkim czasie działania.
Przy okazji zmiany komputera oceniarki robiliśmy testy na wszystkich historycznych zgłoszeniach, żeby sprawdzić czy komputer pod obciążeniem (wszystkie rdzenie zajęte na 100%) ocenia tak samo jak komputer bez obciążenia. Różnice nie przekraczały 1-2%.
Na Spotach zgłoszenia zwykle albo przechodzą z dobrym zapasem, albo nie mają szans się zmieścić w limicie dla niektórych testów wydajnościowych. Czyli nie ma się chyba czym przejmować.
Gdybyś jednak dostrzegł, że coś nie działa jak powinno, będziemy wdzięczni za zgłoszenie.


16 lut 2011, o 10:42
Zobacz profil
Avatar użytkownika

Dołączył(a): 17 gru 2010, o 00:08
Posty: 14
Post Re: Różne czasy dla identycznych zgłoszeń
Cytuj:
Przyczyny mogą być dwie.
...

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:
Kod:
#define SIZE 100000000
#define MULT 3
int t[SIZE];
int main() {
  for (long long i = 0; i < SIZE; ++i)
     t[(i * MULT) % SIZE] = 1;
  return 0;
} 
...a drugi, t2.cpp, co 10001:
Kod:
#define SIZE 100000000
#define MULT 10001
int t[SIZE];

int main() {
  for (long long i = 0; i < SIZE; ++i)
     t[(i * MULT) % SIZE] = 1;
  return 0;
}

(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
Kod:
g++ -O2 -S t1.cpp && g++ -O2 t1.cpp -o t1 && g++ -O2 -S t2.cpp && g++ -O2 t2.cpp -o t2 && time t1 && time t2 

daje następujące wyjście:
Kod:
real    0m0.808s
user    0m0.500s
sys 0m0.320s

real    0m2.317s
user    0m1.930s
sys 0m0.390s 

...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:
Kod:
real    0m0.476s
user    0m0.280s
sys 0m0.193s

real    0m1.868s
user    0m1.677s
sys 0m0.187s 


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 :)


16 mar 2011, o 00:04
Zobacz profil
Wyświetl posty nie starsze niż:  Sortuj wg  
Dział zablokowany Ten wątek jest zablokowany. Nie możesz w nim pisać ani edytować postów.  [ Posty: 3 ] 


Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość


Nie możesz rozpoczynać nowych wątków
Nie możesz odpowiadać w wątkach
Nie możesz edytować swoich postów
Nie możesz usuwać swoich postów
Nie możesz dodawać załączników

Skocz do:  
cron


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group. Forum style based on STSoftware Hestia.
Przyjazne użytkownikom polskie wsparcie phpBB3 - phpBB3.PL