Δυναμικά Οριζόμενοι Πίνακες σε C

Directx · 17 Δεκεμβρίου 2006

Φίλε chiossif δεν ξέρω αν αυτό είναι ένα ακόμα Trivial αλλά το array2d_malloc.c χτυπά στην γραμμή 61 -memcpy(b,a,n*n*sizeof(double));- με σφάλμα μνήμης Access Overrun (CodeGuard) στην CodeGear Turbo C++ Express (Input τιμή 7).

chiossif · 17 Δεκεμβρίου 2006

Ναι, όπως έγραψα και στο mail που το έχει -κάτω κάτω- πρέπει να βάλεις b[0],a[0] αντί του b,a. Συγνώμμη πρόκειται για λάθος διότι σε ένα post προσπάθησα να λύσω τον γρίφο και παράλληλα να το βελτιώσω. Το'κανα και συννημένο και δεν μπορώ να το διορθώσω...

Τον θυμάστε τον μύθο του Αισώπου με τον βοσκό και τον λύκο;

dop · 17 Δεκεμβρίου 2006

@alkisg: αν γράφεις προγράμματα που χρειάζονται μεγάλους πίνακες και portability, χωρίς να στηρίζεσαι στο εκάστοτε stack space που σου δίνει το λειτουργικό, τότε μάλλον αυτό το C99 χαρακτηριστικό δεν κάνει. Φυσικά και δουλεύει με μικρότερα νούμερα, αλλά το ζητούμενο εδώ είναι αν δουλεύει με μεγαλύτερα - και πόσο μπορεί να είναι αυτά. Και αυτό ακριβώς θέλω να δείξω.

Γενικά, είμαι πολύ δύσπιστος ακόμα απέναντι σε C99 κώδικα - και τον αποφεύγω - γιατί όλοι οι major compilers ή δεν είναι καθόλου compliant ή είναι μερικώς compliant.

Sta · 17 Δεκεμβρίου 2006

Προφανώς καλό είναι να γράφεις σε C89 που είναι το ευρέως υλοποιημένο πρότυπο. Σε αρκετούς compilers πάντως έχει υλοποιηθεί το "variable length array" και το "define anywhere" ως extension.

alkisg · 18 Δεκεμβρίου 2006

@dop: γι' αυτό είπα για malloc + C99, π.χ.:

int a[j] = malloc(10000000);

...

free(a);

Δηλαδή χρησιμοποιείς heap αντί για stack, και η προσπέλαση του a είναι πιο "εύκολη" και πιθανώς και πιο γρήγορη...

Αυτά βέβαια ΑΝ συνεργάζεται ο compiler!

dop · 19 Δεκεμβρίου 2006

@alkisg: δεν κατάλαβα... Τι σχέση έχει το heap/stack με την ταχύτητα προσπέλασης;

alkisg · 20 Δεκεμβρίου 2006

Με το πιο εύκολη εννοούσα συντακτικά...

Για το γρήγορη: Με την C89 μέθοδο, χρειάζονται δύο προσπελάσεις pointer μέχρι να φτάσουμε στο ζητούμενο στοιχείο a[j]. Η πρώτη είναι για το ίδιο το a, και η δεύτερη για την αντίστοιχη γραμμή (ή στήλη, ανάλογα πως θεωρείς το i).

Με τη C99 μέθοδο, χρειάζεται μόνο μία προσπέλαση, αφού η μνήμη είναι συνεχόμενη. Αφού δηλαδή προσπελαστεί το a, μετά προσθέτοντας N*i+j φτάνεις στο ζητούμενο στοιχείο.

Μάλιστα μπορεί να μη χρειαστεί καν να προσπελαστεί το a (για την περίπτωση που δεν έγινε malloc αλλά δηλώθηκε στο stack).

Έτσι (λογικά αλλά χωρίς να το δοκιμάσω) η C99 θα βγάζει γρηγορότερο κώδικα.

Τις προσπελάσεις των i, j και του τελικού στοιχείου δεν τις μετράω γιατί είναι κοινές και για τις δύο περιπτώσεις...

alkisg · 20 Δεκεμβρίου 2006

Αν έχεις όρεξη κάνε μια δοκιμή, δήλωσε

a[100][100] στη main και κάνε μερικά loop (αλλά χωρίς "φόρτο" στο εσωτερικό τους για να φανεί πιο έντονα η διαφορά),

και μετά δήλωσέ το ξανά μέσω των malloc που αναφέρθηκαν παραπάνω (μία για τα αρχικά 100 + άλλες 100 malloc, μία για κάθε στήλη) και κάνε τα ίδια loop.

Βάλε τον compiler να κάνει full optimization και χρονομέτρα! Έχω την εντύπωση ότι το πρώτο θα είναι πιο γρήγορο...

edit: το test loop μπορεί να είναι:

start_timing();

for (i = 0; i < 10000000; i++)

a[3][5] = i;

stop_timing();

και για να φανεί σωστότερα η διαφορά C89/C99, από τους παραπάνω χρόνους θα πρέπει να αφαιρεθεί ο χρόνος που κάνει το παρακάτω, επειδή ο χρόνος αυτός αφορά στο for και όχι στην προσπέλαση του a:

start_timing();

for (i = 0; i < 10000000; i++)

temp = i;

stop_timing();

Τα temp, i και a καλό είναι να δηλωθούν volatile γιατί υπάρχουν και compilers που κάνουν optimize όλο το for και σου βάζουν απλά το τελικό αποτέλεσμα!

dop · 24 Δεκεμβρίου 2006

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

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

#include <sys/time.h>

struct timeval start, end;

void start_timer(void) {
gettimeofday(&start, NULL);
}

void stop_timer(void) {
gettimeofday(&end, NULL);
}

void show_time(void) {
const double stime = ((start.tv_sec*1.e6) + start.tv_usec);
const double etime = ((end.tv_sec*1.e6) + end.tv_usec);
const double time = etime - stime;

fprintf(stdout, "Time: %f us\n", time);
}

size_t random_index(const size_t N) {
const double i = ((double)rand()/(double)RAND_MAX);
return (size_t)N*i;
}

int main(int argc, char *argv[]) {
const size_t N = 10000000;
size_t dim;
size_t i;

if (argc<2)
{
	fprintf(stderr, "%s: give array size.\n", argv[0]);
	exit(-1);
}
dim = atoi(argv[1]);

int a[dim][dim];
int **b = malloc(dim*sizeof *;
if (b==NULL)
{
	perror("Error creating array");
	exit(-1);
}
for (i=0; i<dim; i++)
{
	if ( (b[i]=malloc(dim*sizeof **)==NULL )
	{
		perror("Error creating array");
		exit(-1);
	}
} 

start_timer();
for (i=0; i<N; i++)
{
	const size_t r = random_index(dim);
	const size_t c = random_index(dim);
	a[r][c] = 0;
}
stop_timer();
show_time();

start_timer();
for (i=0; i<N; i++)
{
	const size_t r = random_index(dim);
	const size_t c = random_index(dim);
	b[r][c] = 0;
}
stop_timer();
show_time();

volatile int t;
start_timer();
for (i=0; i<N; i++)
{
	const size_t r = random_index(dim);
	const size_t c = random_index(dim);
	t = i;
}
stop_timer();
show_time();

return 0;
}

Αποτελέσματα: σε gcc 4.0, οι διαφορές στην προσπέλαση του "static" C99 array σε σχέση με το dynamic array είναι αμελητέες (<5% στην χειρότερη περίπτωση). Δεδομένων των περιορισμών που έχουν αυτά τα arrays σε σχέση με τα fully dynamic, θα προτιμούσα τα δεύτερα.

chiossif · 24 Δεκεμβρίου 2006

Φίλε dop, πράγματι:

>
chiossif@SUSELinux101:~/MyCode/2006/Forums/Dops_allocation_test> ./Dops_allocation_test 1024
Time: 11187468.000000 us
Time: 11173664.000000 us
Time: 10089442.000000 us

chiossif@SUSELinux101:~/MyCode/2006/Forums/Dops_allocation_test> ./Dops_allocation_test 1024
Time: 10556052.000000 us
Time: 8535589.000000 us
Time: 7765192.000000 us

Στην πρώτη εκτέλεση είναι ΑΚΡΙΒΩΣ ο κώδικας του dop ενώ στην δεύτερη άλλαξα αμοιβαία μεταξύ τους τα a και b των γραμμών 57 και 66 (b[r][c] = 0;).

Και διαπίστωσα μια αντίστροφη επιτάχυνση. Και τα ποσοστά ΤΩΡΑ δεν συμφωνούν. Τελικά ΠΑΝΤΑ το δεύτερο είναι καλύτερο αλλά πόσο; και γιατί; Να μια νέα ωραία συζήτηση...

Πάντως, συχωρήστε με αλλά, την K&R C δεν την εγκαταλείπω, ακόμα και αν με κάποιο νέο πρότυπο μπορώ να κάνω malloc μόνο με την σκέψη μου...

Καλά Χριστούγεννα,

Υγεία, Ευτυχία και Ελευθερία σε όλο το κόσμο.

dop · 24 Δεκεμβρίου 2006

Το έτρεξες αρκετές φορές;

Δοκίμασα και το παρακάτω:

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

#include <sys/time.h>

struct timeval start, end;

void start_timer(void) {
gettimeofday(&start, NULL);
}

void stop_timer(void) {
gettimeofday(&end, NULL);
}

void show_time(void) {
const double stime = ((start.tv_sec*1.e6) + start.tv_usec);
const double etime = ((end.tv_sec*1.e6) + end.tv_usec);
const double time = etime - stime;

fprintf(stdout, "Time: %f us\n", time);
}

size_t random_index(const size_t N) {
const double i = ((double)rand()/(double)RAND_MAX);
return (size_t)N*i;
}

int main(int argc, char *argv[]) {
const size_t N = 10000000;
size_t dim;
size_t i;

if (argc<2)
{
	fprintf(stderr, "%s: give array size.\n", argv[0]);
	exit(-1);
}
dim = atoi(argv[1]);

int a[dim][dim];
int **b = malloc(dim*sizeof *;
if (b==NULL)
{
	perror("Error creating array");
	exit(-1);
}
for (i=0; i<dim; i++)
{
	if ( (b[i]=malloc(dim*sizeof **)==NULL )
	{
		perror("Error creating array");
		exit(-1);
	}
} 

start_timer();
for (i=0; i<N; i++)
{
	const size_t r = random_index(dim);
	const size_t c = random_index(dim);
	const size_t r1 = random_index(dim);
	const size_t c1 = random_index(dim);
	const size_t r2 = random_index(dim);
	const size_t c2 = random_index(dim);
	a[r][c] = a[r1][c1] + a[r2][c2];
}
stop_timer();
show_time();

start_timer();
for (i=0; i<N; i++)
{
	const size_t r = random_index(dim);
	const size_t c = random_index(dim);
	const size_t r1 = random_index(dim);
	const size_t c1 = random_index(dim);
	const size_t r2 = random_index(dim);
	const size_t c2 = random_index(dim);
	b[r][c] = b[r1][c1] + b[r2][c2];
}
stop_timer();
show_time();

volatile int t;
start_timer();
for (i=0; i<N; i++)
{
	const size_t r = random_index(dim);
	const size_t c = random_index(dim);
	const size_t r1 = random_index(dim);
	const size_t c1 = random_index(dim);
	const size_t r2 = random_index(dim);
	const size_t c2 = random_index(dim);
	t = r1 + r2;
}
stop_timer();
show_time();

return 0;
}

Αποτέλεσμα:

Time: 3497312.000000 us

Time: 3404336.000000 us

Time: 2643895.000000 us

Καλύτερη ταχύτητα για τον 2ο πίνακα (δυναμικός).

Edit: ακόμα και όταν χρησιμοποίησα και επιπλέον 2ο loop πριν το χρονομετρημένο για να αποφύγω τυχόν επιπτώσεις που θα έχει η γεμάτη data cache στην ταχύτητα, τα αποτελέσματα δεν έχουν αλλάξει όσον αφορά την σχετική επίδοση.

chiossif · 24 Δεκεμβρίου 2006

@dop:

Το προηγούμενο τo'τρεξα 2-3 φορές (PIII@669 γαρ) και τα αποτελέσματά μου είναι ενδεικτικά. Σε παρακαλώ τρέξε αντίστροφα το δεύτερο που έστειλες ΕΣΥ να δούμε ισχύει η πρόταση μου ότι "ΠΑΝΤΑ το δεύτερο είναι καλύτερο αλλά πόσο; και γιατί;"

Καλά Χριστούγεννα,

Υγεία, Ευτυχία και Ελευθερία σε όλο το κόσμο.

dop · 24 Δεκεμβρίου 2006

Το δοκίμασα και πάντα o μη malloced πίνακας είναι αργός με την τελευταία έκδοση του "benchmark".

Τώρα για τα αποτελέσματα: έχω τυχαίες προσπελάσεις για να αναγκάσω τον compiler να μην αρχίσει τα loop unrollings και να μην ψάχνει για κάποιο access pattern. Η χειρότερη συμπεριφορά των μη malloced arrays μάλλον οφείλεται στην data cache και το page-in/page-out που γίνεται.

Ο int a[][] έχει συνεχόμενες θέσεις μνήμες και φαίνεται ότι ενοχλεί τον επεξεργαστή αν οι διαστάσεις του πίνακα ΔΕΝ είναι πολλαπλάσια του 2 - τα pages είναι πάντα σε δυνάμεις του 2. Αν είναι σε δύναμη του 2 ( πχ 128 ), η απόδοση είναι καλύτερη σε σχέση με τον malloced.

alkisg · 10 Ιανουαρίου 2007

...καλλιό αργά παρά ποτέ (τώρα βρήκα χρόνο).

Ο κώδικας με τις random είναι περίπου 50 φορές πιο αργός από έναν κώδικα που δε χρησιμοποιεί random.

Επίσης, από τον κώδικα που δε χρησιμοποιεί random εμείς θέλουμε να χρονομετρήσουμε μόνο ένα κομμάτι, που είναι χρονικά το μισό του.

Συμπέρασμα; οι παραπάνω χρονομετρήσεις δεν είναι αξιόπιστες. Είναι σαν να παίρνω ένα σακουλάκι καφέ και να ανεβαίνω (εγώ, μαζί με το σακουλάκι) πάνω στη ζυγαριά. Μετά παίρνω ένα σακουλάκι ζάχαρη και ξαναανεβαίνω στη ζυγαριά.

Και τελικά προσπαθώ να καταλάβω ποιο από τα δύο σακουλάκια είναι πιο ελαφρύ. Ε, προφανώς δε θα το καταλάβω. Πρέπει να βάλω τα σακουλάκια μόνα τους.

Ως εκ τούτου, πήρα τον κώδικα του dop και έβγαλα τις random (τον επισυνάπτω παρακάτω). Βγήκαν τα παρακάτω αποτελέσματα:

alkisg@atlantis:~/experts$ ./arrays 1000

Time: 338222.000000 us

Time: 363705.000000 us

Time: 130418.000000 us

Για να αναλύσω τα αποτελέσματα, παίρνω τη διαφορά, ώστε να βρω μόνο τις εντολές που με ενδιαφέρουν, όχι τον φόρτο του for. Έτσι έχω

Time1 = 207804 μs

Time2 = 233287 μs

Τα διαιρώ και βλέπω ότι ο δεύτερος κώδικας είναι περίπου 112% πιο αργός από τον πρώτο.

Για μία μόνο προσπέλαση, θα έπρεπε πριν κάνω την διαίρεση, να διαιρέσω τα Time1 και Time2 διά του 3, επειδή στο loop έχω τρεις προσπελάσεις.

Οι παραπάνω χρονομετρήσεις έγιναν με

gcc (GCC) 3.3.5 (Debian 1:3.3.5-13)

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

#include <sys/time.h>

struct timeval start, end;

void start_timer(void) {
   gettimeofday(&start, NULL);
}

void stop_timer(void) {
   gettimeofday(&end, NULL);
}

void show_time(void) {
   const double stime = ((start.tv_sec*1.e6) + start.tv_usec);
   const double etime = ((end.tv_sec*1.e6) + end.tv_usec);
   const double time = etime - stime;

   fprintf(stdout, "Time: %f us\n", time);
}

size_t random_index(const size_t N) {
   const double i = ((double)rand()/(double)RAND_MAX);
   return (size_t)N*i;
}

int main(int argc, char *argv[]) {
   const size_t N = 10000000;
   size_t dim;
   size_t i;

   if (argc<2)
   {
       fprintf(stderr, "%s: give array size.\n", argv[0]);
       exit(-1);
   }
   dim = atoi(argv[1]);

   int a[dim][dim];
   int **b = malloc(dim*sizeof *;
   if (b==NULL)
   {
       perror("Error creating array");
       exit(-1);
   }
   for (i=0; i<dim; i++)
   {
       if ( (b[i]=malloc(dim*sizeof **)==NULL )
       {
           perror("Error creating array");
           exit(-1);
       }
   }

       const size_t r = random_index(dim);
       const size_t c = random_index(dim);
       const size_t r1 = random_index(dim);
       const size_t c1 = random_index(dim);
       const size_t r2 = random_index(dim);
       const size_t c2 = random_index(dim);

   start_timer();
   for (i=0; i<N; i++)
   {
       a[r][c] = a[r1][c1] + a[r2][c2];
   }
   stop_timer();
   show_time();

   start_timer();
   for (i=0; i<N; i++)
   {
       b[r][c] = b[r1][c1] + b[r2][c2];
   }
   stop_timer();
   show_time();

   volatile int t;
   start_timer();
   for (i=0; i<N; i++)
   {
       t = r1 + r2;
   }
   stop_timer();
   show_time();

   return 0;
}

alkisg · 10 Ιανουαρίου 2007

Τα παραπάνω τα έκανα χωρίς optimization.

Δεύτερη δοκιμή με gcc -O3 έβγαλε τα παρακάτω αποτελέσματα:

Time: 112545.000000 us

Time: 77123.000000 us

Time: 43477.000000 us

Αφαιρώ πάλι,

Time1 = 69068 μs

Time2 = 33646 μs

Διαιρώ και παίρνω ότι ο δεύτερος κώδικας χρειάζεται το 49% του χρόνου που χρειάζεται ο πρώτος. Δηλαδή με το που μπήκε optimization στη μέση, τα πράγματα αντιστράφηκαν τελείως.

Όμως δε θεωρώ τα αποτελέσματα με το optimization αξιόπιστα, γιατί ο gcc είχε την ευκαιρία να προϋπολογήσει τις θέσεις του δυναμικού πίνακα, αφού εντός του loop τα r1, c1, r2, c2 παρέμεναν σταθερά, κάτι που δε θα ισχύει σε έναν τυπικό κώδικα.

Με το που αλλάζουμε τη δήλωση των r1, c1, r2, c2 σε volatile αντί για const, ο gcc χάνει τη δυνατότητα προϋπολογισμού των θέσεων και οι δύο μέθοδοι φτάνουν να έχουν τον ίδιο χρόνο προσπέλασης:

Time: 240352.000000 us

Time: 239956.000000 us

Time: 70256.000000 us

Με το που αλλάζουμε ΚΑΙ τα a, b σε volatile, η διαφορά χρόνου ξαναγίνεται η αναμενόμενη:

Time: 235766.000000 us

Time: 252448.000000 us

Time: 71431.000000 us

Σύνδεση

Δυναμικά Οριζόμενοι Πίνακες σε C

Προτεινόμενες αναρτήσεις

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Συνδέστε για να σχολιάσετε

Κοινοποίηση σε άλλες σελίδες

Αρχειοθετημένο

Σύνδεση