Dynamická alokace a qsort (jazyk C)

24.1.2017 00:06 | Přečteno: 1639× | Ostatní | poslední úprava: 24.1.2017 00:14

Program po zadání prázdného řetězce srovná dle abecedy již vložené řádky. Nejsem si úplně jist správným postupem u dynamické alokace, ale zdá se, že program funguje správně.

soubor sorting.h

int cmp(char *s1, char *s2);
char **alloclines(int n);
void print(char **l, int n);
int readline(char *l);
char **realloclines(char** memold, int *nold);
void freelines(char **l, int n);

soubor sorting.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "sorting.h"

#define MAXLINE		1000

int main()
{	
	char **lines, line[MAXLINE];
	int nlines = 0, nmem = 5;
	
	lines = alloclines(nmem);
	
	while (readline(line) > 1) {		
		
		if (nlines >= nmem)	
			lines = realloclines(lines, &nmem);		
		
		strcpy(lines[nlines], line);
		nlines++;	
	}
	
	qsort((void*) lines, nlines, sizeof(char *), (int (*)(const void *, const void*))
 cmp); 
	
	print(lines, nlines);	
	
	freelines(lines, nlines);	
	
	return 0;
}

int cmp(char *s1, char *s2)
{
	char *t1 = *(char**)s1;
	char *t2 = *(char**)s2;

	return strcmp(t1, t2);
}


char **alloclines(int n)
{		
	char **p;
	int i;
	
	p = (char **) malloc(sizeof(char *) * n);
	
	if (p == NULL) {
		printf("alloclines() error\n");
		exit(1);
	}
	
	for (i = 0; i < n; i++) {
		p[i] = (char *) malloc(sizeof(char) * MAXLINE);
		
		if (p[i] == NULL) {
			printf("alloclines() error\n");
			exit(1);
		}	
	}
	
	return p;
}

void print(char **l, int n)	 
{	
	int i;
	
	for (i = 0; i < n; i++)
		printf("%s", l[i]);
}

int readline(char *l)
{	
	fgets(l, MAXLINE, stdin); 
	
	return strlen(l);
}


char **realloclines(char** memold, int *nold)
{
	char **memnew;	
	int i, nnew;
	
	nnew = *nold * 2;	
	
	memnew = (char **) realloc(memold, sizeof(char *) * nnew);
	
	if (memnew == NULL) {
		printf("realloclines() error\n");
		exit(1);
	}
	
	for (i = *nold ; i < nnew; i++) {
		memnew[i] = (char *) malloc(sizeof(char) * MAXLINE);
		
		if (memnew[i] == NULL) {
			printf("realloclines() error\n");
			exit(1);
		}	
	}
	
	*nold = nnew;
	
	return memnew;
}

void freelines(char **l, int n)
{
	int i;
	
	for (i = 0; i < n; i++) 
		free((void *)l[i]);

	free((void *)l);
}

       

Komentáře

[sad]

Objevil jsem chybu ve funkci freelines(), druhý argument má být nmem.

[Dušan Kreheľ]

Tvoj program skoro robí ako príkazy # cat | sort

Súbor sorting.h napíš tak, aby zabránilo vnorenému vkladaniu:

#ifndef SORTING_H
#define SORTING_H

char **alloclines(int n);
char **realloclines(char** memold, int *nold);
int cmp(char *s1, char *s2);
int readline(char *l);
void freelines(char **l, int n);
void print(char **l, int n);

#endif

Sprav, nech načítava ne do prázdneho riadku, ale dokiaľ je vstup. Vstup ukončíš v konzole CTRL + D. ...

if(fgets(...) == NULL)
{
    // vstup bol ukončený
}

A funkciu main dávaj nakoniec v súbore (alebo najdôležitejšiu funkciu, ak tam nie je main v zdrojovom kóde). Taký nejaký profesionálnejší štandard.

A ďalšia poznámka. Neplytvaj pamäťou. Tj. alokuj pamäť na riadok, až keď budeš mať riadok načítaný. Vtedy vieš jeho veľkosť, a miesto MAXLINE alokuješ reálnu veľkosť.

A použi štruktúru (dátový typ), popíš ňou riadky a s ňou pracuj. A aj tú daj na spracovanie funkciám ako parameter. To potom bude krása.

A keď chceš profesionálnejšie, tak aj testuj stupy pre funkcie. Chyba je NULL, a co ak všade pošlem napr. pre char **realloclines(char** memold, int *nold) ako memold NULL alebo *NULL;

[sad]

Díky za rady.

[R]

Hlavne je ten .h subor uplne zbytocny a tie deklaracie funkcii z neho tiez. Staci presunut funkcie tak, aby boli pred ich pouzitim uz definovane (tzn. okrem ineho aj ten main na konci).

[Kate]

Protože proč programovat přehledně, když to jde i húř :)

[Petr]

přehledně v céčku?

smutný vočičko, když jsem pečená?

[kralyk z abclinuxu]

Jenže on má pravdu, .h soubor pouze pro main.c opravdu moc nemá moc smysl. .h soubor má smysl, pokud ho bude někdo includovat, nejlépe více souborů než jen main.c

[R]

Co je prehladne na tom, pridavat do kodu zbytocne riadky a aby to nebolo malo, tak ich dat do samostatneho zbytocneho suboru?

[Michal Kubeček]

Většinou se tomu snažím vyhnout, ale někdy je přehlednější řadit funkce podle toho, jak k sobě logicky patří, a nemuset se nechat svazovat tím, která kterou volá (někdy to ani nejde). Na druhou stranu, pokud není funkce zamýšlena jako určená k volání z jiného souboru, stačí na to deklarace na začátku a není potřeba ji dávat do hlavičkového souboru - nebo to spíš není ani žádoucí (a stejně by bylo lepší ji rovnou deklarovat jako static).

[xkucf03]

Tvoj program skoro robí ako príkazy # cat | sort

If you hold a UNIX shell up against your ear. Can you hear the C?

:-)

[Kvakor]

Tvoj program skoro robí ako príkazy # cat | sort A ďalšia poznámka. Neplytvaj pamäťou. Tj. alokuj pamäť na riadok, až keď budeš mať riadok načítaný. Vtedy vieš jeho veľkosť, a miesto MAXLINE alokuješ reálnu veľkosť.

Jednoduché řešení je mít samostatný buffer pro vstup a v okamžiku, kdy je řádek načtený, tak ho vykopírovat na čílové místo něčím na způsob strdup(), takže se použije jen tolik paměti, co je třeba. Onen vstupní buffer může být ve většině případů dokonce staticky alokovaný, případně dynamicky alokovaný na určitou předem nastavenou velikost, protože pokud nepotřebujeme neomezeně dlouhé řádky, je jednodušší řešení nesmyslně dlouhé řádky zahazovat (k čemu je např. konfugurační soubor, z jehož čtení nám půjdou oči šejderm a při jehož editaci se uscrollujeme k smrti ) .

No a pokud je třeba dynamická alokace, tak nemá smysl zvyšovat velikosti po jednotkách byte, minimální granularita většiny implementací hald je většinou kolem šestnácti byte a pokud se paměť opravdu přidává, tak je to minimálně o velikosti jedné stránky (4KB na x86 a běžných ARMech, dá se zjistit dynamicky přes getpagesize() nebo sysconf()). Když už, tak zvětšovat právě o velikost stránky nebo něco strovnatelného.

Mimo toho, že se ušetří čas, kderý by se zbytečně trávil managementem haldy (bez toho, že by zavolal sbrk()), to má vliv i na nižší fragmentaci haldy, obzvlášť pro pesimální případy, kde délka řádku monotóně roste s jeho pozicí (takže nelze znovu použít uvolněné "díry" v haldě).

PS: Když se toto alokuje opravdu, ale opravdu hodně (IIRC, limit je 128MB u GNU libc), tak malloc() a spol. začnou požívat místo haldy přímé mapování anonymní paměti pčes mmap() (tedy, v unixech, jask se to dělá ve Windows, nemám potuchy). Osobně si myslím, že pak je lepší se na paměťový management přes malloc() a spol. vykvajznout a buď použít nějaký lepší alokátor, nebo si to dělat ručně právě přes malloc(), což má navíc výhodu v tom, že můžeme mnohem přesněji ovlivnit, jak se s pamětí nakládá (přes madvise())nebo kdy se paměť uvolní (nutné, když jednu chvíli potřebujeme spoustu paměti a v té náskledujcí jí musíme zase uvolnit pro někoho jiného).

[Dušan Kreheľ]

Alebo napríklad použi/inšpiruj sa GNU rozšírením getline(). Viď tam príklad v časti Example.

[Jendа]

IIRC, limit je 128MB u GNU libc

Moje mallopt(3) říká, že ten limit je 128 KiB.

[kralyk z abclinuxu]

tak malloc() a spol. začnou požívat místo haldy přímé mapování anonymní paměti pčes mmap()

Python (resp. CPython) dělá něco takového taky. Debugování memory leaků je pak výborný :-/

[...]

Měmory leak v Pythonu? Wtf?

[Jistota Desetinásobku]

Ten můžeš mít v jakémkoli jazyce, klidně i s GC nebo RAII.

[...]

Code or it didnt happen

[smazáno]

>>> import kerberos
>>> kerberos.authGSSClientInit("HTTP@krbhost.example.com")
(1, <PyCObject object at 0x7f56004e65d0>)
>>> 

Ano, muze za to kerberos modul napsany v C, ale hadam ze debugovani python C extensions mel prave kralyk na mysli.

[Jistota Desetinásobku]

Žádný jazyk/kompilátor/VM neví, které objekty (obecně data) jsou legitimní a chceš je držet v paměti, a které jsou tam jen zapomenuté a nikdy už nebudou potřeba. Pokud si např. programátor při zpracování každého řádku/requestu něco někam uloží a pak to po sobě neuklidí, počítač nemůže vědět, jestli to byl záměr (a na konci se bude dělat třeba nějaký součet nebo statistika) nebo jestli je to memory leak.

Existují nástroje, které tyhle chyby dokáží s určitou mírou pravděpodobnosti/chybovosti odhalit, ale rozhodně to za tebe nevyřeší jazyk/kompilátor. GC nebo RAII jsou dobré věci a hodně chybám dokáží předejít, ale ne všem -- odpovědnost je vždycky na programátorovi a ten by si neměl naivně myslet, že když nedělá v céčku, ale něčem vyšším, že se ho memory leaky netýkají. Třeba dneska se jedny z největších prasečin dějí na webu resp. v JavaScriptu -- časté jsou stránky/aplikace, které vyžírají enormní množství paměti, neuklízí po sobě (a kromě toho ti vyžerou i takty CPU potažmo baterku, když tam nějaká je).

[kralyk z abclinuxu]

Měmory leak v Pythonu? Wtf?

Python-C interop. Céčková strana naalokuje nějaké pythonní objekty a neuvolní je. Tyhle objekty můžou bejt naalokovaný přes malloc, ale někdy taky přes mmap (zcela bez volání mallocu). Nástroje jako valgrind a podobně tohle nedohledají. Nakonec jsem to řešil trasováním mmap syscallu a koukal na backtraces, abych zjistil, odkud se to alokuje. Možná existuje chytřejší způsob.

[pavlix]

Pythoní kód leakuje běžně a řeší se to podle mě daleko hůř než u céčkovského kódu.

[.]

Jasně. Jak výše vyplynulo, leakuje nějakej c bazmek, ale může za to Python.

[pavlix]

To jste ovšem poněkud pod jiným komentářem.

[kralyk z abclinuxu]

Jasně. Jak výše vyplynulo, leakuje nějakej c bazmek, ale může za to Python.

Tenhle čistě pythonní kód u mě sežere ~1GB RAM:

#!/usr/bin/env python2

import sys

class Foo(object):
    def __init__(self, other=None):
        self.other = other

    def __del__(self):
        pass

if __name__ == "__main__":
    for i in range(1000000):
        foo = Foo()
        bar = Foo(foo)
        baz = Foo(bar)
        foo.other = baz
    sys.stdin.readline()

(V Pythonu 3 mi to nejde reprodukovat, proto then python2)

Jinak ale leaky jdou vytvořit i bez triků s __del__, viz třeba tenhle kód:

#!/usr/bin/env python3

import sys


foobar = []

def avg_line_length(file):
    avg = len(file.readline())
    if avg == 0:
        return 0
    else:
        avg -= 1
    n = 1
    for line in file:
        n += 1
        avg = avg + (len(line) - 1 - avg) / n
        foobar.append(line)
    return avg

if __name__ == "__main__":
    print(avg_line_length(sys.stdin))
    sys.stdin.readline()

Tady je sice hodně zřejmý, kde a proč to leakuje, ale jakmile budeš mít nějakou větší codebase ve který bude podobný problém zašmodrchaný a rozetřený přes X modulů, už nebude tak snadný to dohledat.

Tož tak.

[Petr]

Já tomu python3 kódu moc nerozumím, ale za ten leak považuješ ten foobar?

[kralyk z abclinuxu]

Já tomu python3 kódu moc nerozumím, ale za ten leak považuješ ten foobar?

Jj. Kvůli němu má ten program lineární paměťovou složitost místo konstantní.

[Petr]

Tomu se ale snad nedá říkat leak, to je skladiště, které jsi zcela explicitně vytvořil.

[JS1]

Skladiste, ktere se nepouziva, je leak. Treba kdyby se ta smycka dela v serveru, byl by to problem.

[Petr]

Tak s takovou definicí může leakovat skutečně cokoliv. A v některých případech to dokonce může být v očích pozorovatele.

[kralyk z abclinuxu]

To se ale principielně od toho céčka neliší.

Leak je paměť (nebo obecně jakýkoli resource), který program nepotřebuje, ale přitom neuvolnil. GC ti zajistí uvolnění těch objektů, u kterých umí na 100% dokázat, že už je nepotřebuješ (a umí je uvolnit). Když na nějaký objekt program už nemá referenci/pointer, je triválně dokázané, že už ten objekt nemůže potřebovat (nejde to). Ten foobar v tom prográmku výše není k ničemu potřeba, ale GC to nepozná. Být to v nějakém jazyce s nějakým chytrým kompilátorem, mohl bys dostat warning, něco jako "Value assigned to foobar is never used" nebo podobně...

A ano, to, jestli program nějaký resource potřebuje, může být věc názoru. Např. v některých C/C++/apod. programech jsou objekty, který se jednou naalokujou a záměrně nikdy neuvolní. Valgrind to může označit za leak, ale přitom programátor to za leak nepovažuje.

[xkucf03]

Být to v nějakém jazyce s nějakým chytrým kompilátorem, mohl bys dostat warning, něco jako "Value assigned to foobar is never used" nebo podobně...

Nevím, jak u pole, ale u obecného objektu dost těžko – máš totiž nějakou instanci a na ní voláš nějakou metodu (append) a jestli tu instanci pak někam přiřadíš nebo s ní uděláš něco jiného je jedno – ta užitečnost mohla spočívat v tom, že jsi volal tu metodu a instance na základě toho něco dělala.

[kralyk z abclinuxu]

Jj, to je pravda. (U vestavěného typu by to sice teoreticky mohlo jít, ale pro kompilátory to je typicky příliš složitý případ...)

[kralyk z abclinuxu]

Jinak ještě poznámka:

leakuje nějakej c bazmek, ale může za to Python.

Za leak může C bazmek, to je bez debat. Za to, že ten leak šel blbě dohledat nicméně může CPython, protože se snaží bejt chytrej a používat vlastní alokační fígle s mmap(). Jak moc jsou tyhle fígle užitečný, to nevim, možná jsou, ale mám svoje pochybnosti...

[Jardík]

1) Nepoužívej datový typ int pro účel velikosti něčeho v paměti. Velikost toho typu může být nedostatečná, nebo naopak příliš velká. Používej typ size_t. Funkce jako malloc, calloc, realloc, všechny mají parametr typu size_t. Funkce qsort taky očekává parametry typu size_t. Používáním intu se můžeš dopustit závažných chyb, např. přetečení a následné předání špatné velikosti daným funkcí, kvůli konverzím.

2) Pokud funkce realloc selže, původní buffer není uvolněn. Máš tam možný memory leak ... sice hned voláš exit(), ale může tě to naučit špatným zvyklostem, třeba až takovou kontrolu někdy dáš do nějaké vlastní knihovny, co ukončovat program nebude.

3) Komparátor funkce qsort má typ int (*)(const void *, const void*). Tvůj má úplně jinou signaturu. To přetypování je hnus, nejsem si jistý, ale asi se dokonce bude jednat i o UB, teoreticky by ty funkce nemusely být volatelné stejným způsobem. A obzvláště, když v tom komparátoru stejně přetypováváš, tak můžeš nechat signaturu správně.

4) Dynamická alokace je většinou od toho, abys nemusel mít nějaký fixně veliký buffer, což stejně pro jednotlivé řádky máš. Jednotlivé řádky bych alokoval až poté, co ho přečteš.

5) Asi je zbytečné mít extra funkci pro realokaci, funkci realloc můžeš předat NULL jako první parametr a bude se chovat jako malloc. Stačí inicializovat proměnnou předem na NULL a nemusíš pak mít 2 funkce, co dělají to samé.

6) Ukazatele (kromě ukazatelů na funkce) jsou implicitně přetypovatelné na void*, netřeba přetypovávat, pokud voláš funkci free(). void* ukazatele jsou implicitně přetypovatelné na ukazatele na jiné (platí pouze v C, v C++ to neplatní).

[vlastikroot]

Co bys mi rekl na to, ze pouzivam na vsechny inty (tzn. i size) fixni typy jako uint8_t? Me prijde size_t jako plytvani pameti na nuly.

[smazáno]

ja bych ti na to zacitoval nejznamejsi citaci Knutha a pak rekl ze plytas stejne jak size_t akorat to tak na prvni pohled nevypada

[Maxmilian Prdel]

Uplne spatne. Hele chlape, nechces jit delat pro Mikroskrot? Tam neumi programovat nikdo, tak si tam aspon nebudes pripadat tak blbe.