Η σελίδα μας αναβαθμίστηκε, γι' αυτό τον λόγο τα μέλη μας θα πρέπει να ζητήσουν νέο κωδικό πρόσβασης από την υπηρεσία "Αποστολή κωδικού πρόσβασης".
Εάν το email με τον νέο κωδικό δεν έρθει στο inbox κοιτάξτε και στο spam folder. Ο server είναι φρέσκος και δεν έχει το reputation που του αξίζει.

File I/O

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
lakritidis
Δημοσιεύσεις: 401
Εγγραφή: 04 Αύγ 2005 14:35
Τοποθεσία: Katerini
Επικοινωνία:

File I/O

Δημοσίευση από lakritidis » 15 Οκτ 2008 12:06

Καλησπέρα.

Έχουμε στο δίσκο ένα directory με περίπου 300,000 web σελίδες.

Ένα πρόγραμμα, διαβάζει τις σελίδες μία προς μία και χτίζει κάποιες δομές δεδομένων στη μνήμη και στο δίσκο. Αυτό παίρνει περίπου 70 λεπτά.

Αν τώρα μαζέψουμε το περιεχόμενο σε ένα μεγάλο αρχείο και το διαβάσουμε σειριακά και κάνουμε ακριβώς την ίδια δουλειά, τότε χρειαζόμαστε μόνο 8 λεπτά. Σημειώστε ότι στο μεγάλο αυτό αρχείο εφαρμόζεται και compression (zlib), οπότε στα 8 αυτά λεπτά συμπεριλαμβάνεται και ο χρόνος για decompression.

Το πρόγραμμα είναι γραμμένο σε C. Η μεγάλη αυτή διαφορά οφείλεται προφανώς στο fopen()/fclose() των 300,000 αρχείων. Το λειτουργικό είναι Ubuntu 8.04 και ο δίσκος έχει ext3 file system.

Η ρουτίνα που διαβάζει τα αρχεία του directory είναι:

Κώδικας: Επιλογή όλων

DIR *dir = opendir(WEB_PAGE_REPOSITORY);

if (dir) {
	struct dirent *ent;
	struct stat results;
	FILE *WebPage;

	while((ent = readdir(dir)) != NULL) {
		chdir(WEB_PAGE_REPOSITORY);
		WebPage = fopen(ent->d_name, "r");

		if(!WebPage) { 
			printf("error file");
		} else {
			stat(ent->d_name, &results);
			int filesize = results.st_size;

			if (filesize > 0) {
				char *DocText = (char*)malloc((filesize + 1) * sizeof(char));
				fread(DocText, sizeof(char), filesize, WebPage);
				DocText[filesize] = '\0';

				// Do Your Staff

				free(DocText);
			}
		}
		fclose(WebPage);
	}				
} else {
	fprintf(stderr, "Error opening directory\n");			
}
Υπάρχει τρόπος να γίνει γρηγορότερο το Open/Close των αρχείων?

1. Αν κάνω μαζικό fopen τα αρχεία; (κάπου είδα ότι μέχρι 512 αρχεία μπορώ να έχω ανοιχτά ταυτόχρονα, ή τέλος πάντων υπάρχει κάποιος τέτοιος περιορισμός). Εννοώ fopen τα πρώτα 512, process, close, fopen τα επόμενα 512 κτλ.
2. Αν αλλάξω filesystem (XFS κτλ)
3. Αν πάρω καλύτερο δίσκο (πχ Western Digital raptor με 10000 rmp spindle speed) πόσο μεγάλη βελτίωση θα δω;

Edit: Να σημειώσω εδώ ότι το πρώτο πρόγραμμα έχει CPU utilization πεπίπου 8%, ενώ το δεύτερο (αυτό που κάνει 8 min) 50% (είναι dual core CPU).

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

File I/O

Δημοσίευση από dva_dev » 15 Οκτ 2008 18:11

Δοκίμασε για αρχή τα εξής:
το chdir βγάλτο έξω από το while, μια φορά αρκεί να τρέξει.
Τα αρχεία σου έχουν κάποιο μέγιστο μέγεθος; Δέσμευσε το μέγιστο που μπορεί να χρειάζεσαι μία φορά στην αρχή και ελευθέρωσε το πάλι μία στο τέλος, μην το κάνεις κάθε φορά που ανοιγοκλείνεις ένα αρχείο.

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

File I/O

Δημοσίευση από soteres2002 » 15 Οκτ 2008 23:08

Ο χρόνος θα μειωθεί αν αλλάξεις τον τρόπο αποθήκευσης των σελίδων και τον τρόπο ανάκτησής αυτών, δηλαδή να χρησιμοποιήσεις άλλο έξυπνο αλγόριθμο, και δεν ξέρω άν υπάρχει γνωστός τέτοιος αλγόριθμος που μπορείς να πάρεις έτοιμο και να έχεις πολύ καλά αποτελέσματα στο hardware που έχεις. Σίγουρα με ένα απλό ΡC δεν πρόκειται να έχεις σοβαρές βελτιώσεις ακόμα και αν βρείς αλγόριθμο με σταθερή πολυπλοκότητα, αν έχεις τεράστιους όγκους πληροφορίας. Απαιτούνται πολλοί πόροι και ώρα. Eξακολουθώντας να χρησιμοποιείς όμως αυτόν τον trivial ακολουθιακό αλγόριθμο ο χρόνος εκτέλεσης αυξάνει περίπου γραμμικά με το μέγεθος ή το πλήθος των αρχείων αν υποθέσεις ότι ο χρόνος συμπίεσης παίρνει περίπου τον ίδιο χρόνο.

Ένας τρόπος να μειώσεις την χρονική πολυπλοκότητα, είναι να τον μετατρέψεις σε παράλληλο, γίνεται πολύ εύκολα. Αυτό γίνεται με προσθήκη μερικών οδηγιών στον κώδικα ώστε να το παραλληλοποιήσεις με χρήση OpenMP(I), ή να κάνεις τον κώδικα multithreaded χρησιμοποιώντας πάλι κάποια lib για νήματα. Σίγουρα ακόμα και με τη δεύτερη λύση θα υπάρχει τρομερή διαφορά σε σχέση με την απόδοση του κώδικα που παραθέτεις. Το ζήτημα είναι τι hardware έχεις για να το πραγματοποιήσεις αυτό. Ενα dual core PCάκι δεν κάνει για τέτοιες δουλειές, θέλεις παράλληλο σύστημα με πολλές CPUs για να έχεις γρήγορες απαντήσεις. Έχεις τρομερή ανάγκη για γρήγορο I/O και ένα PC με 1 ή 2 διαύλους δεν έχει τόσο μεγάλο I/O bandwidth για να γίνονται όλα αυτά γρήγορα.

Να ρωτήσω κάτι μόνο απο περιέργεια; Αυτό το directory με τις 300.000 τι ρόλο ακριβώς παίζει;

lakritidis
Δημοσιεύσεις: 401
Εγγραφή: 04 Αύγ 2005 14:35
Τοποθεσία: Katerini
Επικοινωνία:

File I/O

Δημοσίευση από lakritidis » 15 Οκτ 2008 23:56

Φίλε soteres
Eξακολουθώντας να χρησιμοποιείς όμως αυτόν τον ακολουθιακό αλγόριθμο ο χρόνος εκτέλεσης αυξάνει περίπου γραμμικά με το μέγεθος των αρχείων αν υποθέσεις ότι ο χρόνος συμπίεσης παίρνει περίπου τον ίδιο χρόνο.
Ίσως δεν έχεις δίκιο εδώ. Η συμπίεση είναι ταχύτατη. Το μέγεθος των αρχείων δεν επηρρεάζει (πολύ), επηρρεάζει το πλήθος τους. Αυτό που είναι αργό είναι το open/close και όχι κάτι άλλο. Δεν υπάρχει άλλο bottleneck γιατί τα ίδια data τα επεξεργάζομαι σε υπο-δεκαπλάσιο σχεδόν χρόνο αν αυτά βρίσκονται σε ένα μόνο αρχείο.

Ένα μικρό bottleneck είναι αυτό που ανέφερε ο dva_dev με τα συνεχή malloc/free μέσα στο loop, το οποίο και διόρθωσα και τώρα θέλει 63 λεπτά αντι για 68.

Πιστεύω ότι αν είχα τη δυνατότητα να ρωτήσω απευθείας τα allocation tables του λειτουργικού για το πού βρίσκονται πραγματικά τα αρχεία στο δίσκο και τα διάβαζα, θα ήμουν γρήγορος. (Ή μήπως την έχω τη δυνατότητα;)

Έχεις εν μέρει δίκαιο σε αυτό που λες για το μεγάλο bandwidth και το mutli CPU σύστημα, όμως όλα αυτά μπορούν να γίνουν και με distributed σύστημα με low comodity PCs (μιλάμε για pentium 3 και 4), με την τεχνική MapReduce.

Το σύστημα που φτιάχνω δουλεύει με το δεύτερο τρόπο (το προγραμμα με τα 8min) , διότι ο storeServer που επικοινωνεί με τον crawler συμπιέζει και αποθηκεύει τις σελίδες απευθείας σε δύο μεγάλα incrementing αρχεία πριν αναλάβει ο indexer.

Θα ήθελα όμως να ρίξω όλη τη wikipedia στο index χωρίς crawl (http://static.wikipedia.org/).

Επίσης έχεις δίκιο για την εξάρτηση από το hardware που υπάρχει και τελικά μάλλον είναι πέρα από τις δυνατότητες που έχω.

Anyway ευχαριστώ πολύ και τους δυο σας...

Edit
Το directory με τις 300.000 σελίδες είναι το αποτέλεσμα του crawling 2 ημερών και κάτι. Ο κώδικας που παραθέτω είναι από μια παλαιότερη έκδοση ενός indexer που διαβάζει τα αρχεία αυτά και δημιουργεί έναν inverted index για queries. Τώρα, όλες οι σελίδες συμπιέζονται και στοιβάζονται σε μεγάλα αρχεία, όπως κάνει η Google (ιεροσυλία).

Άβαταρ μέλους
cordis
Administrator, [F|H]ounder, [C|S]EO
Δημοσιεύσεις: 27564
Εγγραφή: 09 Οκτ 1999 03:00
Τοποθεσία: Greece
Επικοινωνία:

File I/O

Δημοσίευση από cordis » 16 Οκτ 2008 13:17

Ίσως θα πρέπει να αναθεωρήσεις τον τρόπο του indexing και να μπαίνουν απευθείας στο 'μεγάλο' αρχείο.
Δεν απαντάω σε προσωπικά μηνύματα με ερωτήσεις που καλύπτονται από τις ενότητες του forum. Για ο,τι άλλο είμαι εδώ για εσάς.
- follow me @twitter

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

File I/O

Δημοσίευση από soteres2002 » 16 Οκτ 2008 14:56

lakritidis έγραψε:Φίλε soteres
Eξακολουθώντας να χρησιμοποιείς όμως αυτόν τον ακολουθιακό αλγόριθμο ο χρόνος εκτέλεσης αυξάνει περίπου γραμμικά με το μέγεθος των αρχείων αν υποθέσεις ότι ο χρόνος συμπίεσης παίρνει περίπου τον ίδιο χρόνο.
Ίσως δεν έχεις δίκιο εδώ.
Ναι είχα τσοντάρει κι ένα "ή το πλήθος των αρχείων" το οποίο είχα διαγράψει μετά από τα τόσα re-edits που έκανα χτες στο reply. Η συμπίεση είναι αστάθμητος παράγοντας, δεν επηρεάζει πάντα το χρόνο εκτέλεσης ειδικά αν έχεις να κάνεις μόνο με τεχτ δεδομένα. Το πλήθος προφανώς θα επηρεάζει την χρονική πολυπ. ασχέτως αν γίνεται συμπίεση η όχι. :(

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες