17 martie 2011

Lucrul cu memoria



Cateva exemple pentru a reaminti cum se lucreaza cu pointerii ce refera zone de memorie:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#include "utils.h"

char first_name[] = " Harry";
char last_name[] = " Potter";

static char *trim(char *s){

char *p = malloc(strlen(s)+1);
strcpy(p, s);
printf("p=%x\n",p);

int i=0;
while(*p == ' ') {
p++;
i++;
}

printf("p=%x\n",p);

s = malloc(sizeof(p)+1);
s = strcpy(s, p);
free(p-i);
return s;
}

int main(void){

printf("%s %s is learning SO!\n",
trim(first_name), trim(last_name));
return 0;
}

Programul sterge spatiile libere dintr-un nume si le afiseaza, iar la sfarsit elibereaza memoria. Pointerul p se tot deplaseaza pentru a referi zona de memorie urmatoare, insa cand se face free acesta trebuie sa fie pozitionat exact pe inceputul sirului de caractere.


#include "stdlib.h"
#include "stdio.h"

#include "utils.h"

int main(void)
{
int i;
unsigned int n = 0xDEADBEEF;
unsigned char *w;

/* TODO - use w to show all bytes of n in order */
i = -1;
w = (unsigned char*)(&n);
int dim = sizeof(n);
do {
i++;
printf("%x",*(w+dim-i)); // invers!

} while (i<=dim-1);

printf("\n");

return 0;
}

In acest program se scrie numarul n in hexa, folosind pointerul w care parcurge zona de memorie octet cu octet invers, din cauza little-endianess -ului (parcurgerea de la LSB la MSB). Daca sistemul ar fi fost big-endian , atunci parcurgerea s-ar fi facut *(w+i) si nu *(w+dim-i) .


In fine, un exemplu de folosire a variabilelor statice (cu rol de variabila globala, init cu 0):

#include "stdio.h"
#include "stdlib.h"

#include "utils.h"

/**
* TODO - functia inc() must behave like a counter
* The function returns the next value in order and
* does not receive and parameter
*
* You are not allowed to use global variables
*/
int inc()
{
static int c ;
c++;
return c;
}


int main(void)
{
int i;

for (i = 0;i<=10; i++)
printf("%d\n", inc());

return 0;
}

12 martie 2011

Exemplu de bariera in Python

Exemplu de bariera - 10 thread-uri pornesc unul dupa altul si sunt afisate in ordinea intrarii lor, dupa care se face o bariera care asigura ca thread-urile vor astepta ca toate sa termine intrarea pentru a merge mai departe.
Mai departe, sunt eliberate unul cate unul si tinute intr-o alta bariera.


import threading
import time
import random

bariera = threading.Semaphore(value=0)
bariera2 = threading.Semaphore(value=0)
regcritica = threading.Semaphore(value=1)
threads = 10
n=threads
threadlist = []

# asigura ca toate thread-urile ies odata

def folosire(x):
print "[INTRARE]: ",x
barrier()
print "[IESIRE]: ",x
barrier()

def barrier():
global bariera,bariera2, regcritica,n,threads

# prima bariera este de intrare (aduna toate thread-urile)
regcritica.acquire();
n = n - 1;
if n==0:
for i in range(threads):
bariera.release();
regcritica.release();
bariera.acquire();
# a doua bariera este de iesire ( --//-- )
regcritica.acquire()
n = n + 1
if n == threads:
for i in range(threads):
bariera2.release()
regcritica.release()
bariera2.acquire()

random.seed()

for i in range(threads):
thread = threading.Thread(target=folosire, args=(i,)) # arg o functie si arg. ei
thread.start()
threadlist.append(thread)

for i in range(len(threadlist)):
threadlist[i].join()

11 martie 2011

Introducere in C#

INTRODUCERE

Variabilele/metodele unei clase pot fi de tipul:
* public - sunt vizibile pentru toate clasele
* private - vizibile doar claselor carora le apartin
* protected - vizibile claselor carora le apartin si celor care le mostenesc (subclase)

Mai putin folosite sunt cele:
* internal - pot fi accesate din acelasi cod assembler, nu si din altul
* protected internal - la fel ca internal, insa pot fi accesate si din alt cod assemble ce corespunde unei clase derivate
* static - clasa nu poate fi instantiata, membrii sai fiind la randul lor statici

Ce sunt proprietatile?
- membrii ai claselor care ofera un mecanism de citire, scriere sau calcul de valori ale campurilor private clasei respective


EXEMPLU

O clasa abstracta numita Forma. Abstracta inseamna ca nu poate fi instantiata (dar poate fi mostenita de catre o alta clasa).


public abstract class Forma {

private string culoare;
private int left;
private int top;
//proprietati ~ incapsulare
public string Culoare
{
get { return culoare; } //puteau fi actiuni + return
set { culoare = value; }
}

public int Left
{
get { return left; }
set { left = value; }
}

public int Top
{
get;
set;
}
public Forma() {
Console.WriteLine("Sunt o forma draguta");
left = 0; top = 0;
}

public void Deseneaza(string what) {
Console.WriteLine("Am desenat "+what);
}

public void Muta() {
Console.WriteLine("Am mutat o forma; left="+left+" si top="+top); //parametri
}

public void Sterge() {
Console.WriteLine("Am sters forma");
}
}


Mostenirea (derivarea) este procesul prin care o clasa primeste toate variabilele si metodele ne-private ale unei alte clase, putand avea si propriile variabile sau metode, pe langa acestea.

Interfata:
* seamana cu o clasa abstracta prin faptul ca orice clasa ce o mosteneste trebuie sa ii implementeze metodele (care exista neimplementate in interfata)
* nu poate fi instantiata direct
* clasele si structurile pot mosteni mai multe interfete, iar la randul ei o interfata poate mosteni mai multe interfete


EXEMPLU

public class Linie : Forma {

public int lungime;
Punct p1, p2;

public Linie(Punct p1, Punct p2) {
this.p1 = p1;
this.p2 = p2;
lungime = (int)Math.Sqrt(Math.Pow(p1.X - p2.X, 2) + Math.Pow(p1.Y - p2.Y,2));
Console.WriteLine("Lungimea liniei este: " + lungime);
}
}


Pe langa clase si obiecte (=instante ale claselor), se afla si structurile, niste "obiecte" mai restranse prin faptul ca nu detin metode si nu pot fi mostenite.

public struct Punct
{
public int X;
public int Y;
}


Ceva mai restrans decat structurile se afla enumeratiile .

public enum TipImagine { Bmp, Jpeg, Png }


In C# -ca o particularitate- in interiorul codului putem gasi regiuni cu simplu rol in vizibilitate . In Visual Studio aceasta regiune se poate restrange pentru a economisi spatiu ocupat pe ecran, sau se poate expanda pentru a o vedea in detaliu.

#region Variable
int a = 5;
int b = 10;
int c = a + b;
string str = c.ToString();
#endregion


Alte notiuni importante sunt:
* incapsularea - sau "ascunderea informatiei" - variabilele membre care sunt private vor fi incapsulate pentru a putea fi accesate doar de anumite metode sau proprietati.
De exemplu: intr-o clasa avem o variabila privata x si o metoda publica ce se ocupa cu setarea lui x. Astfel, nu vom putea seta variabila x direct ci prin intermediul metodei.
* polimorfismul - o clasa poate mosteni alta clasa si in acelasi timp poate suprascrie anumite metode. In C#, clasa originala ar avea metoda respectiva virtuala, in timp ce clasa ce o mosteneste o va denumi override.

09 martie 2011

Ierarhia de memorii


Urmatoarele exemple testeaza timpul efectuarii unei operatii pe un vector :

1) Consideram inmultirea unui vector de dimensiune foarte mare cu un scalar, in mai multi pasi. In pasul 1 accesam fiecare element din vector unul dupa altul si facem operatia, la pasul 2 accesam elementele din 2 in 2 cu revenire (intai consideram pozitiile impare apoi cele pare) si facem operatiile, si asa mai departe cu un pas de lungime maxima = lungimea vectorului, asa incat la final accesam doar prima pozitie din vector, reincarcam vectorul si accesam a doua pozitie.... pana la final.
Ceea ce se observa este ca, teoretic, timpii calculatii corespunzatori fiecarui pas cresc treptat, pana ajung sa se stabilizeze. Timpii cresc cu atata cat ii ia incarcarii in memoria cache a vectorului.
In programul C, s-a folosit functia gettimeofday pentru aflarea orei exacte, pana la microsecunde (care este si ordinul de marime cu care se incarca datele specific cache-ului L2). Dupa fiecare pas, se face diferenta t2-t1 si se afiseaza aceasta valoare /cam la 10.000 pasi/ (pentru a nu se scrie pe ecran prea multe valori).


#include "stdio.h"
#include "sys/time.h"
#include "time.h"
#include "stdlib.h"

int main() {
int pas = 1, n = 100000, i, *v, scalar = 4;
v = (int *)malloc(n*sizeof(int));
for (i=0; i<=n-1; i++)
v[i] = i%10;
struct timeval tv;
time_t t1, t2;

do {
gettimeofday(&tv, NULL);
t1 = tv.tv_usec;
int j;
for(j=0; j<=pas-1; j++)
for(i=j; i<=n-1; i+=pas)
v[i] *= scalar;
gettimeofday(&tv, NULL);
t2 = tv.tv_usec;
if(pas%10000==1)
printf("pasul %d:\t t1=%d t2=%d\t t2-t1=%ld\n", pas, t1,t2, t2-t1);
pas++;
} while (pas<=n-1);

return 0;
}


2) Al doilea exemplu e asemanator, doar ca nu se mai folosesc pasii anteriori, ci se variaza dimensiunea vectorului a.i. sa ocupe intre 1M la inceput -> 12 M , cu un `pas` de 0.5M .
Ceea ce ar trebui sa se observe este scaderea performantei la modul urmator:

#include "stdio.h"
#include "sys/time.h"
#include "time.h"
#include "stdlib.h"

#define MAX 3145728 // 12MB
#define pas_dim 131072 // 0.5MB

// pt cache L2

int main() {
long int n = 32768, *v; // 2^20/32
int i, scalar = 4;
v = (long int *)malloc(MAX*sizeof(long int));
for (i=0; i<=MAX-1; i++)
v[i] = i%10;

struct timeval tv;
time_t t1, t2;

do {
gettimeofday(&tv, NULL);
t1 = tv.tv_usec;
for(i=0; i<=n-1; i++)
v[i] *= scalar;
gettimeofday(&tv, NULL);
t2 = tv.tv_usec;
n = n+pas_dim;

printf("dim %ld:\t t1=%d t2=%d\t (t2-t1)/n*1000=%lf\n", n, t1,t2, (t2-t1)/(double)n);

} while (n<=MAX-1);

return 0;
}

03 martie 2011

Extinderea sistemului de fisiere din Ubuntu

Probabil ca exista mai multe metode, descrise aici, dar eu as vrea sa detaliez putin cea de-a 3-a metoda:

Pentru a redimensiona sistemul de fisiere in care este incarcat Ubuntu (sau orice alta distributie Linux), cel mai bun utilitar este gparted . Acest program se poate descarca si din bash, cu apt-get install gparted , si intr-adevar cu el se pot redimensiona anumite partitii, care intai trebuie unmounted . Insa in cazul sistemului de fisiere ( "/" ), acest lucru nu mai este posibil pentru ca odata ce Linuxul este bootat sistemul de fisiere devine mounted.

De aceea, gparted trebuie rulat live, adica bootat de pe un stick usb (asa este cel mai la indemana). Pentru aceasta, ne folosim de utilitarul unetbootin, care ruleaza si in interfata grafica. Odata pornit, se selecteaza a doua optiune "Disc Image" - ISO - si se selecteaza calea unde a fost descarcat programul gparted. In functie de locul unde dorim sa cream bootabilul, alegem tipul (sa zicem Disc USB) si Dispozitivul (aici de obicei detecteaza automat). Cu aceste setari se creeaza noul continut bootabil pe stickul USB.

Restartand calculatorul, se booteaza de pe stick (atentie la BIOS care trebuie setat sa booteze intai de pe stick) si se intra in gparted live . Programul va afisa structura partitiilor si dimensiunile lor. De tinut minte este urmatorul lucru: nu putem redimensiona sistemul de fisiere decat daca inaintea acestuia exista un spatiu nealocat. Cu alte cuvinte, degeaba avem n GB nealocati pe partitia care vine dupa sistemul de fisiere pe care vrem sa il redimensionam, nu ne vom putea folosi de acestia. De aceea, intai trebuie redimensionata (micsorata) partitia care vine inaintea sistemului de fisiere al nostru, iar cu acel spatiu nealocat putem creste dimensiunea sistemului de fisiere.