Malloc + 2d arrays + C

[Vasilis Vasaitis]

On Tue, Mar 19, 2002 at 11:41:13PM +0000, Christos Ricudis wrote:
> In article <mailman.1016575926.18713.linux-greek-users at lists.hellug.gr>, Vasilis Vasaitis wrote:
> 
> >   Αντιθέτως, είναι από τα λίγα πράγματα που ο συγκεκριμένος κώδικας
> > καταφέρνει να κάνει σωστά. Αντί να κάνει malloc() ολόκληρο τον πίνακα, και
> > μετά να χρησιμοποιεί πολλαπλασιασμό (μπλιαχ) για την «διδιάστατη»
> > προσπέλαση, κάνει πρώτα malloc() έναν πίνακα από δείκτες, και σε καθέναν από
> > αυτούς μετά έναν πίνακα από χαρακτήρες. Ή αλλιώς, instant 2D, the C way.
> 
> Pragma poy einai o lan8asmenos tropos na ylopoihseis ena disdiastato array, 
> otan ta bounds ths deyterhs diastashs einai constant, poso mallon a priori 
> gnwsta. 
> 
> Sthn periptwsh toy 'disdiastatou array' exeis : 
> 
> * Ena memory allocation sto initialization
> * Ena pollaplasiasmo kai mia pros8esh ana access
> * Ena memory deallocation sto telos
> 
> Sthn periptwsh toy 'array of N pointers' exeis : 
> 
> * N memory allocations sto initialization (+ malloc housekeeping)
> * To fetching toy pointer kai mia pros8esh ana access
> * N memory deallocations sto telos
> 
> Poio apo ta dyo sou fainetai pio aplo, grhgoro, cache friendly, ktl ktl ktl? 

  - Απλό: Το δεύτερο φυσικά. Είναι πολύ πιο απλό, εύκολο, κατανοητό και μη
επιρρεπές σε λάθη να γράψεις A[y][x], παρά A[y*w+x].

  - Γρήγορο: Το δεύτερο φυσικά. Στις περισσότερες περιπτώσεις θα έχεις τόσες
πράξεις ανάμεσα στην κατανομή και την αποδέσμευση μνήμης, που το overhead
είναι αστείο μπροστά στη συνολική επεξεργασία (όχι πάντα ομολογουμένως).
Αντίθετα, το να κάνεις έναν πολλαπλασιασμό ανά προσπέλαση μνήμης είναι απλά
εξωφρενικό, δεδομένου ότι είναι μια από τις πιο αργές πράξεις και
προσπαθούμε να τον αποφύγουμε ακόμα και στους αλγορίθμους μέσα. ΟΚ, αν η
διάσταση είναι δύναμη του δύο, τον γλυτώνεις με ολισθήσεις, αλλά δεν έχεις
συχνά τέτοια πολυτέλεια.

  - Cache friendly: Ανάλογα με το μέγεθος της διάστασης, μπορεί να έχει
σημασία ή όχι.

  Αλλά σε κάθε περίπτωση, αν οι πολλές κατανομές σου φαίνονται πρόβλημα,
ομολογώ ότι προσωπικά τις περισσότερες φορές κάνω κάτι ενδιάμεσο:

    char **A;
    A = malloc(height * sizeof *A);
    *A = malloc(width * height * sizeof **A);
    for (int i = 1; i < height; i++)
	A[i] = A[i-1] + width;

    /* processing goes here */

    free(*A);
    free(A);

  Α, και κάτι άλλο. Στην δεύτερη περίπτωση, γενικά δεν έχεις πρόσθεση στην
προσπέλαση, τουλάχιστον όχι ως ξεχωριστή εντολή. Σε τέτοιες περιπτώσεις
συνήθως την πρόσθεση του index στον δείκτη την αναλαμβάνει ο αθροιστής του
υποσυστήματος διευθύνσεων, οπότε έχεις απλά μια εντολή του στυλ:

	movl	(%ebx,%edx,4), %eax

  Αλλά πάλι, μόνο από x86 ξέρω, αλλού μπορεί να μην έχει τέτοιες ευκολίες.
Αλλά εντάξει, αλλού δεν έχει καν πολλαπλασιασμό, οπότε τι να λέμε τώρα...

-- 
Vasilis Vasaitis
vvas at hal.csd.auth.gr

"Don't do drugs. Santa Claus is watching."
		-- winamp.com


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
URL: <http://lists.hellug.gr/pipermail/linux-greek-users/attachments/20020320/039f5dc7/attachment.pgp>