2010-04-17:

C i lokalne tablice o

c:c++:code:easy
Czas na jakiś bardziej techniczny post. Dostałem kilka dni temu pytanie, które pozwolę sobie zacytować: "[...] dlaczego nie powinno się deklarować zmiennych w taki sposób: int a = 50; int b[a];". Chodzi tutaj oczywiście o tablice lokalne, które mają wielkość zależną od jakiejś zmienne, być może nawet zależnej od użytkownika/wejścia. Swoją odpowiedź cytuje poniżej:

Chodzi o to, że alokacja jest dokonywana na stosie, a w zależności od środowiska, na stosie może być niewiele miejsca (nawet jeśli nie w "tym" momencie, to kilka funkcji "wgłąb").
Więc jeśli 'a' jest zależne od usera, to program może się wyłożyć. Poza tym, mogą być problemy z portem na inną platformę, gdzie stos jest mniejszy. Stos ma zazwyczaj parę MB, w skrajnych wypadkach kilkanaście KB, więc duże alokacje na stosie są niemożliwe.
Kolejna sprawa ofc to żywotność takiej zmiennej (do końca bloku kodu w którym ją zadeklarowano).

Niemniej jednak, jeżeli żadne z powyższych Ci nie przeszkadza, ale wiesz o tych wadach rozwiązania, to w zasadzie można tego użyć ;) (np. jeśli kod ma być 'haxxorski' a nie 'ładny i czytelny', albo tylko prototypujesz coś).

W zasadzie po to jest heap, żeby dynamiczne alokacje robić, chociaż fakt faktem, alokacja na stosie jest szybsza, szczególnie jeśli jest to mała alokacja (poniżej strony). Powyżej jednej strony (czyli 4KB) dochodzi konieczność 'dotykania' stron na stosie - związane jest to z mechanizmem rozszerzania stosu - tj. stos jest rezerwowany cały (np. na 16mb), ale alokowane faktycznie (tj. commitowane wg notacji z MSDN) jest tylko np. 32KB (przykładowa losowa wartość - dop. Gyn). Najbliższa niezaalokowana strona ma ustawiony jakiś trigger (np. PAGE_GUARD) i jeżeli program się odwoła do tej strony (np. będziesz tam chciał zapisać wartość zmiennej), to poleci exception (wyjątek), bo ta strona nie istnieje. Ponieważ był tam PAGE_GUARD, to ten wyjątek zostanie przejęty przez handler, który po prostu rozciągnie stos na tą stronę (czyli ją doalokuje, a konkretniej docommituje).
Tak więc, jeżeli chcemy zaalokować np. 1MB na stosie (czyli 256 stron), to powyższy proceder (za pierwszym razem) będzie miał miejsce około 256 razy (minus ilość stron już zaalokowanych). Czyli 256 razy poleci wyjątek, nastąpi alokacja, etc - co ofc nie jest już specjalnie szybkie. Ba, VirtualAlloc/mmap albo HeapAlloc/malloc są dużo szybsze w takim wypadku. W momencie kiedy te strony są już zaalokowane, i następuje alokacja na stosie, to ofc jest to porównywalnie (a w zasadzie trochę szybsze) niż alokacja na Heapie, chyba, że Heap też już jest "zcachowany" ;)

Podsumowując. Można używać tej alokacji, jeśli się dokładnie zna wady i zalety i dostosuje się do sytuacji ;)


No, to tyle ;)

UPDATE: W komentarzach pojawiły się pewne sprawy, które w zasadzie wymagają dłuższego komentarza. Tak więc...

Pojawiło się pytanie, czy jakikolwiek kompilator supportuje takie lokalne tablice o "zmiennej" (tj. nie znanej w momencie kompilacji) wielkości, czy jest to zgodne ze standardem, oraz jak w zasadzie zrobić program z taką "zmienną" tablicą.

Otóż okazuje się, że jest to zgodne ze standardem C99 i nazywa się to variable length array (w skrócie VLA). W związku z czym, kompilatory które wspierają C99 będą umożliwiać tworzenia VLA. W zasadzie nie wiem czy istnieje obecnie kompilator który by w 100% wspierał C99, natomiast są (jest?) kompilatory które wspierają akurat VLA - żeby daleko nie szukać, jest to GCC, również w wersji MinGW GCC (czyli pod Windowsa).

Z kompilatorów które na pewno nie wspierają VLA mogę wymienić choćby Microsoft C/C++ Optimizing Compiler używany w IDE Visual C++ z pakietu Visual Studio - po napotkaniu konstrukcji z VLA dostajemy: error C2057: expected constant expression.
Po przegooglowaniu i przebingowaniu kilku blogów na MSDN, znalazłem informację o tym, że wsparcja dla C99 i VLA w planach nie ma:

Źródło: Visual C++ Team Blog - ISO C Standard Update (November 05, 2007):
Now, the Visual C++ compiler team receives the occasionally question as to why we haven’t implemented C99.  It’s really based on interest from our users.  Where we’ve received many requests for certain C99 features, we’ve tried to implement them (or analogues).  A couple examples are variadic macros, long long, __pragma, __FUNCTION__, and __restrict.  If there are other C99 features that you’d find useful in your work, let us know!  We don’t hear much from our C users, so speak up and make yourselves heard
Źródło: Visual C++ Team Blog - Rvalue References: C++0x Features in VC10, Part 2 [komentarze] (February 03, 2009)
Thursday, February 19, 2009 7:21 PM by morovia
# re: Rvalue References: C++0x Features in VC10, Part 2

Will VC10 support variable length array (VLA)? I really need that feature badly. Other C/C++ compilers support VLA.
Thursday, February 19, 2009 7:54 PM by Stephan T. Lavavej [MSFT]
# re: Rvalue References: C++0x Features in VC10, Part 2

[morovia]

> Will VC10 support variable length array (VLA)?

No; that is a C99 language feature.

> I really need that feature badly.

Why? C++ has std::vector.

OK, skoro MSVC++ tego nie wspiera, to rzućmy okiem na to, jak to działa w GCC, a wcześniej rzućmy okiem na to co mówi na to standard.

W standardzie C99 możemy przeczytać:
C9X adds a new array type called a variable length array type.  The inability to declare arrays
whose size is known only at execution time was often cited as a primary deterrent to using C as a
numerical computing language.  Adoption of some standard notion of execution time arrays was
considered crucial for C’s acceptance in the numerical computing world.

The number of elements specified in the declaration of a variable length array type is a runtime
expression.  Before C9X, this size expression was required to be an integer constant expression.

W starszej wersji standardu C99 którą znalazłem na dysku, jest dodatkowo świetny przykład:
extern int n;
int A[n]; // invalid: file scope VLA
extern int (*p2)[n]; // invalid: file scope VM
int B[100]; // valid: file scope but not VM
void fvla(int m, int C[m][m]); // valid: VLA with prototype scope
void fvla(int m, int C[m][m]) // valid: adjusted to auto pointer to VLA
{
 typedef int VLA[m][m]; // valid: blockscope typedef VLA
 struct tag {
   int (*y)[n]; // invalid: y not ordinary identifier
   int z[n]; // invalid: z not ordinary identifier
 };
 int D[m]; // valid: auto VLA
 static int E[m]; // invalid: static blockscope VLA
 extern int F[m]; // invalid: F has linkage and is VLA
 int (*s)[m]; // valid: auto pointer to VLA
 extern int (*r)[m]; // invalid: r has linkage and points to VLA
 static int (*q)[m] = &B; // valid: q is a static blockpointer to VLA
}

Jak mógłby wyglądać przykładowy program wykorzystujący VLA? Np. tak:
#include <stdio.h>

int
main(void)
{
 int a;
 scanf("%i", &a);

 int b[a];
 printf("%i\n", sizeof(b));

 return 0;
}

Huh? Czy w powyższym kodzie użyty jest sizeof dla VLA? Ależ tak! Jak się okazuje, w przypadku VLA sizeof staje się runtime-expression, a więc nie jest rozwiązywany w momencie kompilacji (ale ostrożnie! on nadal działa tylko z VLA).

By the way...
If you'd like to learn SSH in depth, in the second half of January'25 we're running a 6h course - you can find the details at hexarcana.ch/workshops/ssh-course


Jak wygląda skompilowany powyższy kawałek kodu (gcc -Os -S -masm=intel)?
mov DWORD PTR [esp+4], eax
mov DWORD PTR [esp], OFFSET FLAT:LC0
call _scanf
       ; Obliczenie wielkosci alokacji oraz w zasadzie rowniez
       ; wartosci sizeof() (do EDX)
mov edx, DWORD PTR [ebp-12]
sal edx, 2
lea eax, [edx+30]
and eax, -16
       ; Alokacja (wielkosc w EAX)
call ___chkstk
mov DWORD PTR [esp+4], edx
mov DWORD PTR [esp], OFFSET FLAT:LC1
call _printf

Jak widać "sizeof" zostało "zinline'owane", tj nie jest wywoływana żadna funkcja, tylko obliczenia są robione bezpośrednio w funkcji (raczej niespodzianek tu nie ma).
Jeśli zaś chodzi o ___chkstk, to jest to nic innego jak wspomniane w komentarzach przez djstronga alloca() - czyli funkcja która "dotyka" stos co stronę aby wywołać commitowanie (i ofc oblicza nową wartość esp).

W komentarzach padło również pytanie, o to czy funkcja calloc() różni się czymś od malloc() oprócz zerowania tablicy. Afair różnica jest jeszcze jedna - calloc upewnia się, że tablica jest odpowiednio zalignowana, tj adres jest podzielny przez wielkość jednego elementu tablicy. A poza tym różnic nie ma i afair calloc po prostu używa malloc. Warto rzucić okiem na MSDN.
Jeśli zaś chodzi o zerowanie tablicy, to bardzo rozbawił mnie opis funkcji w standardzie - pozwolę go sobie zacytować:
7.20.3.1    The calloc function
Both nelem and elsize must be of type size_t for reasons similar to those for fread (see
§7.19.8.1).
If a scalar with all bits zero is not interpreted as a zero value by an implementation, then calloc
may have astonishing results in existing programs transported there
.

"Astonishing results" :))))

No, i chyba tyle :)

Comments:

2010-04-17 18:36:24 = Mateusz Krzywicki
{
Na mikrokontrolerach (ST8 i MSP430) nie ma o czymś takim mowy w ogóle. Kompilatory odrzucają na wstępie.
}
2010-04-17 19:19:57 = Gynvael Coldwind
{
@Mateusz Krzywicki
Ah, to ciekawe ;)
Swoją drogą, muszę potem sprawdzić, czy jest to extension kompilatora, czy ficzer języka (tzn czy jest w standardzie)...
}
2010-04-17 19:23:24 = Tomasz Kowalczyk
{
Tzn. jeśli kod faktycznie wygląda w ten sposób:

(...)
int a = 50;
int b[a];
(...)

to chyba nie ma problemu. ;]
}
2010-04-17 19:26:22 = Gynvael Coldwind
{
@Tomasz Kowalczyk
Haha ofc masz rację :)
Natomiast jak napisałem - raczej chodziło o przypadki gdy 'a' faktycznie jest zmienne, i nie do określenia w momencie kompilacji.
}
2010-04-17 20:12:10 = beem
{
Nie widziałem nigdy kompilatora C który pozwolił by na taka deklarację tablicy.
}
2010-04-17 20:18:18 = Nick_with_golden_eyes
{
Próbowałem kiedyś napisać program, w którym:
int a;
cin >> a;
int b[a];

Jednak bez new, ani rusz, kompilator wywalał błąd.
Jak w praktyce zrobić taki program?
}
2010-04-17 20:45:48 = Dreadlish
{
Jak chcecie sobie zrobić zmienną tablicę w c, no to robicie wskaźnik i malloca puścić. "Zmienna" tablica 100%
}
2010-04-17 20:51:40 = cyriel
{
Niektore(wszystkie?) kompilatory c++ to przepuszczaja, ale z tego co pamietam jest to niezgodne ze standardem, bo rozmiar tablicy musi byc znany podczas kompilacji.
Czyli
int a=10;
int b[a];
jest ok, ale
cin >>a;
int b[a];
juz nie.
}
2010-04-17 21:17:35 = djstrong
{
Do alokacji na stosie w C służy funkcja void *alloca(size_t size);
}
2010-04-17 21:21:20 = Tomasz Kowalczyk
{
Ja do alokacji tablic stosuję zwykle funkcję calloc(), bo od razu czyści [zeruje] cały zarezerwowany obszar. Z drugiej strony nigdy nie zastanawiałem się nad tym na ile się to różni od malloc()'a, więc czy mógłbym prosić o jakiś komentarz?
}
2010-04-17 23:06:36 = Gynvael Coldwind
{
Pozwoliłem sobie zrobić update w poście i tam odpowiedzieć na Wasze pytania/wątpliwości :)
}
2010-04-18 08:33:13 = shm
{
Czyszczenie zarezerwowanego obszaru nie zawsze jest pożądaną czynnością. (Np. kiedy nie zakładamy, że obszar jest wyzerowany). Odnośnie do wyrównywania, to w OpenBSD (malloc.c z libc: http://bit.ly/9hfipU ) różnicy między mallociem a callociem nie ma, podobnie jest NetBSD ( http://bit.ly/9cBWo8 ). Calloc oczywiście zeruje pamięć, ale można wymusić, aby pamięć zarezerwowana przez malloc była domyślnie zerowana za pomocą /etc/malloc.conf. Użycie calloca ma tę przewagę, że nie popełnimy jakiegoś głupiego błędu z mnożeniem malloc(x*y), to zwykle zły pomysł.

Trochę już offtopicowo - http://www.openbsd.org/papers/eurobsdcon2009/otto-malloc.pdf - nowa implementacja malloca.

}
2010-04-18 09:29:49 = Gynvael Coldwind
{
@shm
Thx za komentarz i linka ;)
}
2010-04-18 11:19:11 = anony..ktos
{
void func(int a)
{
char* tab[a];
..
Zadziała w g++, ale gcc już tego nie przyjmie.
}
2010-04-18 11:48:49 = Gynvael Coldwind
{
@anony..ktos
U mnie działa OK (log z konsoli poniżej).
Jaką masz wersję GCC? Przetestowałem pod Debianem x86 (Linux) na gcc w wersjach 2.95, 3.4 i 4.1, na Ubuntu x86-64 na gcc w wersjach 4.3 i 4.4, oraz na Windowsie na MinGW gcc w wersji 4.4, i wszędzie działa ładnie.

--cut--
13:45:16 gynvael >type xxx.c
#include <stdio.h>

void func(int a)
{
char* tab[a];
printf("%i
", sizeof tab);
}

int
main(void)
{
func(5);
func(10);
return 0;
}


13:45:20 gynvael >gcc xxx.c -Wall -Wextra

13:45:23 gynvael >a
20
40
--cut--
}
2010-04-18 14:26:57 = Tomasz Kowalczyk
{
Dzięki wielkie za odpowiedź - zwyczajnie lubię wiedzieć co się dzieje "pod maską", a teraz była okazja do spytania. ;]
}
2010-04-18 15:44:07 = pi3
{
VLA jest dosc znana technika. Phrack tez ja zna:

http://www.phrack.com/issues.html?issue=63&id=14&mode=txt

;-)
}
2010-04-18 15:54:14 = Nick_with_golden_eyes
{
@Gynvael: dzięki za wyczerpującą odpowiedź.
}
2010-04-19 06:15:39 = CoLinS
{
Ostatnio rozmawiałem o tym z wykładowcą od języka C. On twierdził, że to nie jest zgodne ze standardem - uwierzyłem mu na słowo ;p. A tu się dowiaduję czego innego ;).
}
2010-04-19 07:31:45 = Gynvael Coldwind
{
@Tomasz Kowalczyk
;)

@pi3
Thx za linka, wygląda bardzo ciekawie :)

@Nick with golden eyes
:)

@CoLinS
Przyznaje, że też byłem zdziwiony, że jest to część standardu, a nie extension z GCC ;)))
}
2010-05-21 00:09:23 = jolek
{
Pytacie się jak to zrealizować w C++:
cin >>a;
int b[a];

A ja się pytam po co to realizować w C++, skoro dopuszcza on tablice dynamiczne? Tablicy w ogóle nie trzeba podawać rozmiaru, a można ją rozszerzać, więc taka deklaracja jest wg mnie całkowicie zbędna.
}
2010-05-21 22:09:52 = Gynvael Coldwind
{
@jolek
Oczywiście piszesz o wektorach, zgadza się?
Wektory to dobra rzecz... widziałem kiedyś post na blogu Reg'a w którym namawiał na (prawie) całkowite zastąpienie tablic wektorami (zachęcam do przeczytania - http://regedit.gamedev.pl/news_1182_stdvector_wszedzie_zamiast_tablic.html). Dodam, że w niektórych firmach jest zalecenie aby nie korzystać z new/delete, tylko właśnie z wektorów, co ma zapobiegać memory leakom (i ma to trochę sensu imo).
}
2011-12-23 20:52:10 = KrzaQ
{
@jolek: g++ pozwala na to, ale nie jest to zgodne ze standardem C++ (żadnym, ani 98, ani 03, ani 11).

Co do artykułu - bardzo fajna lektura, ale C99 w żadnym miejscu nie nakazuje VLA siedzieć na stosie. Implementacja, która po cichu je alokuje gdzie indziej jest jak najbardziej poprawna.
}
2011-12-24 10:14:00 = Gynvael Coldwind
{
@KrzaQ
+1! Czemu ja nie mam przycisku +1 ;|

Anyway, pomysł bardzo fajny, przy czym konieczne wtedy byłoby wprowadzenie niejawnych destruktorów wywołujących odpowiednie *free* na końcu bloku (co ofc nie jest dużym problemem).
}
2014-10-11 18:47:05 = yisonPylkita
{
[Gynvael] Właśnie czegoś takiego szukałem. Jak dotąd nie mogłem znaleźć w sieci różnicy w wydajności pomiędzy alokacją na stercie, a alokacją na stosie. Było tylko, że stos szybszy, jednak nikt nawet nie próbował dowodzić dlaczego tak jest. Po prostu stos szybszy i koniec.
}

Add a comment:

Nick:
URL (optional):
Math captcha: 3 ∗ 8 + 4 =