Raport de evaluare - limita de memorie

[•mirceacool]

Salut,

Am observat in raportul de evaluare ca daca declar un sir global si nu il folosesc deloc, nu se considera memorie consumata. 

La OJI in anii precedenti evaluatoarele au fost construite sa masoare memoria altfel. Daca declari un tablou global, acesta trebuie sa se supuna, impreuna cu tablourile declarate in functii si in main constrangerii de "Limita totala de memorie", indiferent daca le folosesti sau nu.

1. Ati putea sa explicati tehnic cum masurati voi memoria si eventual cum fac cei din comisiile de pe la OJI asta?
2. Nu vi se pare derutant pentru noi, cei care folosim infoarena pentru pregatire?

[•freak93]

Atunci cand compilezi cu -O2, cum facem si noi, si la judeteana, nationala etc compilatorul face multe optimizari ca programul tau sa mearga repede. Scrie in regulament cum se compileaza programul si aceasta optiune apare acolo.

Optimizarile sunt multe si inteligente, dar majoritatea sunt chestii pe care si orice om care s-ar uita pe sursa ta ar putea sa le faca, cum ar fi sa scoate matricile, vectorii care nu sunt folositi, ca e doar in avantajul tau asta.

1. Noi masuram memoria strict cat consuma programul tau, la fel ca si comisia OJI, in cazul tau pur si simplu acel tabel nu mai exista, nu are treaba cum se masoara memoria.
2. Nu stiu cum sa raspund la asta avand in vedere ca nu e vina nimanui, trebuie sa te documentezi despre programele pe care le folosesti, este multa informatie pe internet, nu trebuie decat sa cauti.

[•cata00]

Noroc,

Am primit PM despre discuția asta, așa că răspund. Precizez de la început că nu am nicio afiliere cu OJI sau alt nivel de olimpiadă. Ca să nu încep fiecare frază cu „din câte știu eu...”, considerați că tot ce scriu aici este din câte știu eu.

OJI se corectează pe Windows. În schimb, evaluatorul IA rulează sub Linux. De aici decurge o diferență importantă. Iată întâi ce zice „man top” (boldul îmi aparține).

RES  --  Resident Memory Size (KiB)
           The non-swapped physical memory a task has used.
VIRT  --  Virtual Memory Size (KiB)
           The  total  amount  of  virtual  memory  used by the task.  It
           includes all code, data and shared libraries plus  pages  that
           have  been swapped out and pages that have been mapped but not
           used.

Deci în Linux există conceptul de memorie pe care ai declarat-o, dar încă n-ai accesat-o și deci „nu se pune” la o eventuală limitare. Să considerăm următorul program:

Cod:

#include <stdio.h>

#define N (100 * 1024 * 1024)

int main(void) {
  unsigned char v[N];
  while (1) {
  }
  return 0;
}

Dacă îl rulez, merge bine-mersi, iar top zice:

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND     
23954 cata      20   0    4192    356    280 R 100.0  0.0   0:49.77 test        

Pare deci că kernelul a mapat cumva doar 4 MB, iar programul folosește efectiv 356 KB. Să încercăm acum:

Cod:

#include <stdio.h>

#define N (100 * 1024 * 1024)

int main(void) {
  unsigned char v[N];
  int i;
  for (i = 0; i < N; i++) {
    v[i] = 111;
  }
  while (1) {
  }
  return 0;
}

Acesta dă segfault. Pare deci că programul chiar cere acei 100 MB pe stivă, ceea ce nu se poate. În varianta a 3-a facem vectorul global:

Cod:

#include <stdio.h>

#define N (100 * 1024 * 1024)
unsigned char v[N];

int main(void) {
  int i;
  for (i = 0; i < N; i++) {
    v[i] = 111;
  }
  while (1) {
  }
  return 0;
}

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND     
24061 cata      20   0  106592 102788    312 R 100.0  1.3   1:22.81 test        

Aici într-adevăr programul folosește 100 MB (nu știu de ce sunt 106 -- poate din cauza diferenței între 1.000 și 1.024).

În Windows, în schimb, dacă declari un vector static, chiar ți-l alocă. Bineînțeles, nu e normal să folosim Windows la olimpiadă și este regretabil că o generație întreagă de informaticieni de elită, smântâna cremei ca să zic așa, cresc dependenți de software neliber. Dar asta este situația curentă și, în timp ce milităm pentru renunțarea la Windows, lucrăm în contextul dat. Deci ești dator să știi că infoarena pregătește utilizatori adevărați, linuxiști, dar că ce merge pe IA nu va merge la OJI. Te cred că ești nemulțumit și te invit să militezi alături de noi pentru eliminarea Windows-ului din toate fazele olimpiadei (și, dacă se poate, din viețile noastre).

Acum, referitor la măsurarea memoriei. Codul infoarena este liber (mulțumim!) și poți vedea ce face programul jrun în particular. Caută funcția update_from_proc() și vei vedea că, într-o buclă, jrun cere de la sistem date despre câtă memorie folosește programul executat.

De ce așa? Pentru că nu este trivial altfel. Nu există o metodă bună de sandboxing. Ce decurge de aici? Că, dacă faci verificarea în buclă prea des, vei gâtui programul și va ajunge jrun să ruleze mai mult decât programul. Dar, dacă o faci prea rar, riști să măsori incorect memoria maximă folosită, căci poți avea ghinionul să măsori de o parte și de alta a unui vârf.

Cam astea-s contribuțiile mele; evident, corectați-mă dacă aberez.

[•mirceacool]

@freak93

Cred ca nu ai dreptate in privinta OJI. Poate ai dreptate in privinta ONI, unde se evalueaza si sub Linux.

Te invit sa descarci evaluatorul oficial folosit la OJI 2014(evaluare sub Windows).

http://www.infoarena.ro/downloads?action=download&file=OJI_2014.zip&safe_only=false

Daca setezi calea catre versiunea de compilator pe care o folosesti, poti sa compilezi chiar folosind evaluatorul, cu "materialul clientului" si cu optiunile de compilare pe care le folosea comisia la OJI in 2014.

Sa zicem ca setezi limita totala de memorie 2MB(din care 1 MB stiva, sa zicem, irelevant pentru ca declaram global) si declari global un tablou de 2 milioane de ints(roughly 8MB). Navighezi in tab-ul Evaluare si incerci o evaluare, vei obtine in raportul de evaluare "Memorie depasita!" fara sa accesezi macar un indice in tabloul respectiv.

[•mirceacool]

Catalin,

Apreciez mult lamuririle tale. Cred ca de acolo apare diferenta, mi se pare amuzant ca la nivel de comisii cu oameni profesionisti inca nu s-a reusit sa se creeze un layer de abstractizare astfel incat formularea din enuntul problemei sa insemne acelasi lucru si pe Windows si sub Linux. Efectiv comisia masoara altceva la OJI(unde se evalueaza doar sub Windows) decat masoara la ONI(evaluare si sub Linux) si formularile de pe foaie sunt la fel. 

Semantic, e o diferenta intre limitarea memoriei pe care programul tau o aloca si limitarea memoriei pe care programul tau o foloseste si cred ca la un moment dat comisiile vor trebui sa exprime mai clar asta. Pentru ca in momentul asta sub Linux se refera la o chestie si sub Windows la alta chestie. Nu stiu exact care sunt limitarile sub Windows de a calcula memoria folosita efectiv de catre program la un moment dat. Nici macar nu stiu daca la asta ar trebui sa se refere limita de pe foaie. Stiu doar ca nu ar trebui ca formularea sa aiba o semantica platform-dependent.

In legatura cu inertia pe care tu crezi ca sistemul o induce catre folosirea de software neliber, eu cred ca are un efect exact invers. Eu am vazut oameni cu un nivel foarte superficial de intelegere a sistemelor de operare libere, dar care erau foarte porniti in directia asta tocmai pentru ca aveau si ei o calificare la OJI si simteau ca ar trebui sa foloseasca alte unelte decat colegii lor. Daca in calitate de dev e oarecum firesc sa lucrezi sub Linux(e mai ieftin, cel putin), mi se pare ca sistemul din Romania induce ideea ca in liceu esti hip daca folosesti Linux. 

[•freak93]

Mda, am uitat cu desavarsire ca la OJI se evalueaza pe windows (poate si din dorinta mea de a crede ca am trecut de acest nivel)