RAM ή CPU επηρεάζουν περισσότερο την ταχύτητα εκτέλεσης ενός προγράμματος;

[Επισκέπτης]

Έχω ένα πρόγραμμα γραμμένο σε C# το οποίο συγκρίνει strings από δύο generic lists. Η μια έχει 140 strings που το καθένα περιέχει 20 λέξεις. Η δεύτερη λίστα έχει 340.000 strings όπου επίσης το καθένα περιέχει από 20 λέξεις. Και για κάθε string από την πρώτη λίστα ελέγχω αν υπάρχουν κοινές λέξεις με κάθε ένα από τα records της δεύτερης. Συνολικά δηλαδή γίνονται κάπου 19 δις συγκρίσεις strings. Το πρόγραμμα τρέχει με parallel linq.

Το ερώτημα μου είναι το εξής. Τι επηρεάζει περισσότερο την ταχύτητα εκτέλεσης, η CPU ή η ταχύτητα της μνήμης; Με parallel linq το πρόγραμμα καταναλώνει πάνω από 90% της CPU.

Ή για να το θέσω αλλιώς. Αν έλεγα πως θέλω να ξοδέψω €500 για να βελτιώσω την ταχύτητα εκτέλεσης τι θα ήταν προτιμότερο, να πάρω έναν επεξεργαστή με όσο το δυνατόν περισσότερους πυρήνες ή κάποιον με λιγότερους πυρήνες και ddr5 μνήμες στα 6GHz;

 

[DrKo]

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

Οπότε, εγώ θα κοιτούσα για να βελτιώσω την ταχύτητα μεταφοράς από την μνήμη στη CPU. Μπορεί να κάνω και λάθος όμως. 

Επεξ/σία 18 Ιουνίου 2022 από DrKo

[parsifal]

Υπάρχει δυνατότητα για εμπειρικά δεδομένα; Π.χ. benchmarking του προγράμματός σου σε desktop PC πλατφόρμα όπου μπορείς να παίξεις με τις διάφορες μεταβλητές όπως μείωση χρονισμού CPU/RAM, απενεργοποίηση CPU cores κλπ.

Εντελώς διαισθητικά βάσει των μεγεθών του προβλήματος, νομίζω πως ο επεξεργαστής σχετικά αραιά θα εξαναγκάζεται σε read/write από τη μνήμη RAM και περισσότερο θα βασίζεται στη L3 cache, δίνοντας προβάδισμα σε αρχιτεκτονικές με γρήγορη και μπόλικη L3.

[Επισκέπτης]

1 ώρα πριν, parsifal είπε

Υπάρχει δυνατότητα για εμπειρικά δεδομένα; Π.χ. benchmarking του προγράμματός σου σε desktop PC πλατφόρμα όπου μπορείς να παίξεις με τις διάφορες μεταβλητές όπως μείωση χρονισμού CPU/RAM, απενεργοποίηση CPU cores κλπ.

Εντελώς διαισθητικά βάσει των μεγεθών του προβλήματος, νομίζω πως ο επεξεργαστής σχετικά αραιά θα εξαναγκάζεται σε read/write από τη μνήμη RAM και περισσότερο θα βασίζεται στη L3 cache, δίνοντας προβάδισμα σε αρχιτεκτονικές με γρήγορη και μπόλικη L3.

Το έχω δοκιμάσει σε τρεις διαφορετικούς υπολογιστές. 4πύρηνο, 6πύρηνο και 8πύρηνο. Το πρόβλημα είναι ότι και οι τρεις έχουν τις ίδιες μνήμες, ddr4 στα 2,4GHz. Οπότε δεν μπορώ να έχω εικόνα πόσο θα βελτιωνόταν η απόδοση με καλύτερες μνήμες. Από υπολογιστή σε υπολογιστή έχει διαφορές και είναι και λογικό αφού όσους πυρήνες και να του ρίξεις θα τους αξιοποιήσει.

Στον 4πύρηνο κάνει κάπου 4,5 λεπτά να τρέξει, στον 6πύρηνο 3,5 λεπτά και στον οκταπύρηνο 2,5 λεπτά. Όλοι οι επεξεργαστές είναι Intel 10ης γενιάς.

1 ώρα πριν, DrKo είπε

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

Οπότε, εγώ θα κοιτούσα για να βελτιώσω την ταχύτητα μεταφοράς από την μνήμη στη CPU. Μπορεί να κάνω και λάθος όμως. 

ΟΚ, και πως γίνεται αυτό; Ας κάνεις λάθος, δεν με απασχολεί. Ιδέες ψάχνω για να δω αν μπορώ να το βελτιώσω ή αν χρειαστεί να πάω σε λύση μέσω hardware που να δώσω μεγαλύτερο βάρος.

Επεξ/σία 18 Ιουνίου 2022 από random_dude

[albNik]

Παντως εχεις πολυ χώρο για βελτίωση αλγοριθμικά. Π.χ. θα μπορούσες να συγκρίνεις τα hash των strings και να τα συνέχισες μονο αν τα hash ειναι ιδια. Επίσης αν τα hash ειναι sorted γλυτώνεις πολλες συγκρισεις. Ειμαι σίγουρος οτι το brute-force νούμερο (20*20*140*340000= 19 δις) μπορει να μειωθεί δραστικά.

Δες και τις δομές HashSet και Dictionary με αναζήτηση σε Ο(1) αντι για List O(n). 

Επεξ/σία 18 Ιουνίου 2022 από albNik

[Επισκέπτης]

31 λεπτά πριν, albNik είπε

Παντως εχεις πολυ χώρο για βελτίωση αλγοριθμικά. Π.χ. θα μπορούσες να συγκρίνεις τα hash των strings και να τα συνέχισες μονο αν τα hash ειναι ιδια. Επίσης αν τα hash ειναι sorted γλυτώνεις πολλες συγκρισεις. Ειμαι σίγουρος οτι το brute-force νούμερο (20*20*140*340000= 19 δις) μπορει να μειωθεί δραστικά.

Δες και τις δομές HashSet και Dictionary με αναζήτηση σε Ο(1) αντι για List O(n). 

Το Dictionary το σκέφτηκα. Αλλά δεν ψάχνω με Contains ώστε να χάνει χρόνο στον εντοπισμό. Συγκρίνω ένα προς ένα με όλα οπότε δεν έχω απώλεια από εκεί. Τις λίστες δηλαδή τις διαβάζω σειριακά.

Το άλλο με το hash δεν νομίζω ότι έχει εφαρμογή. Συγκρίνω όλες τις λέξεις μια προς μια. Όχι όλο το string με τις 20 λέξεις μέσα ως κάτι ενιαίο. Το δεύτερο ναι, θα είχε νόημα με hash γιατί αντί να συγκρίνω 200 χαρακτήρες θα είχα το ένα δέκατο με ένα hash.

Η ιδέα με το sortάρισμα είναι καλή. Τουλάχιστον οι όμοιες λέξεις θα είναι στην αρχή οπότε γλυτώνω περιττές αναζητήσεις.

[albNik]

Ενα παρόμοιο παραδειγμα

Αν ειχες 2 λιστες απο 1.000.000 λεξεις για να βρεις τις κοινές θα ήθελες 1 τρις συγκρίσεις, δλδ αρκετά λεπτά:  O(1000000*1000000)

foreach(var word1 in list1)
  foreach (var word2 in list2)
  {
     if(word1==word2)
       ....
  }

Αν οι λίστες ηταν sorted τοτε με List.BinarySearch θα ηταν πολύ πιο γρήγορο:  Ο(log(1000000)*1000000)

foreach(var word1 in list1)
  foreach (var word2 in sortedList2)
  {
     if(sortedList2.BinarySearch(word1)>=0)
       ....
  }

 

Με 1 dictionary και μια λίστα αυτό βγαίνει σε <1 sec:   O(1000000)

foreach(var word in list)
{
   if(dict.ContainsKey(word)
     ....
}

 

Για το πρόβλημα σου θα μπορουσες να εχεις List<Dictionary>> ...

 

  

21 λεπτά πριν, random_dude είπε

Αλλά δεν ψάχνω με Contains ώστε να χάνει χρόνο στον εντοπισμό. Συγκρίνω ένα προς ένα με όλα οπότε δεν έχω απώλεια από εκεί.

Δεν ξερω τι εννοεις "χανει χρονο " και "απωλεια" αλλα η dictionary.ContainKey είναι πολύ!!! πιο γρήγορη απο list.Contains

 

 

 

Επεξ/σία 18 Ιουνίου 2022 από albNik

[k33theod]

Για τη χρήση όλων των cores σε ένα πρόγραμμα ο προγραμματισμός είναι λίγο διαφορετικός και πρέπει να δεις αν το έχεις υλοποιήση σωστά. Νομίζω δεν είναι τόσο απλό όσο χρησιμοποιώ ένα συγκεκριμένο data structure ένα import μιας library και όλα δουλεύουν αυτόματα, χρειάζεται και άλλες αλλαγές στον κώδικα.

Oι διαφορετικές ταχύτητες που έχεις σε επεξεργαστές με περισσότερα cores μπορεί να οφείλεται στην ταχύτητα επεξεργασίας και όχι στον αριθμό των cores.

Οι συγκρίσεις που έχεις είναι πολλές. Σκέψου ότι σε κάθε σύγκρισή μια λέξη μπορεί να έχει 20-30 γράμματα και με μια μία κωδικοποίηση κειμένου utf-8 μπορεί να έχεις και 4 byte ανά χαρακτήρα.

Οι συγκρίσεις είναι πολλές οι πράξεις είναι πολλές => πας για cpu🤪

 

[Επισκέπτης]

1 ώρα πριν, albNik είπε

Για το πρόβλημα σου θα μπορουσες να εχεις List<Dictionary>> ...

 

 

Χα, αυτό είναι καλό! Δεν το είχα σκεφτεί.

[albNik]

43 λεπτά πριν, random_dude είπε

Χα, αυτό είναι καλό! Δεν το είχα σκεφτεί.

Δοκιμασε αυτο βαζοντας τα data σου στις list140_20 και list340000_20.

Η κατασκευή του wordIndicesMap δεν πρέπει να παρει πανω απο 1 sec ακομα και αν ολες οι 340000*20 λεξεις ειναι διαφορετικες.

Στο τελευταίο double loop έχεις να κάνεις 2800 dictionary lookups (λιγότερο από millisecond) αντί για 19 δις comparisons

var list140_20 = new List<List<string>>() { new List<string>() { "x", "y", "z" }, new List<string>() { "x1", "y1", "z1" }, };
var list340000_20 = new List<List<string>>() { new List<string>() { "a", "b", "c" }, new List<string>() { "a", "b", "d" }, new List<string>() { "a" } };

var wordIndicesMap = new Dictionary<string, List<int>>();  // a:{0,1,2} | b:{0,1} | c:{0} | d:{1}
for(int i = 0; i < list340000_20.Count; i++)
  foreach(var word in list340000_20[i])
  {
    if(wordIndicesMap.ContainsKey(word))
       wordIndicesMap[word].Add(i);
    else
      wordIndicesMap[word] = new List<int> { i };
    }

foreach(var sentence in list140_20)
 foreach(var word in sentence)
 {
 if(wordIndicesMap.ContainsKey(word))
 {
   var indices = wordIndicesMap[word];
    //word found in these 'rows' of 340000 x 20 'table'
  }
}

 

Επεξ/σία 18 Ιουνίου 2022 από albNik

[Theo1903]

10 hours ago, random_dude said:

Έχω ένα πρόγραμμα γραμμένο σε C# το οποίο συγκρίνει strings από δύο generic lists. Η μια έχει 140 strings που το καθένα περιέχει 20 λέξεις. Η δεύτερη λίστα έχει 340.000 strings όπου επίσης το καθένα περιέχει από 20 λέξεις. Και για κάθε string από την πρώτη λίστα ελέγχω αν υπάρχουν κοινές λέξεις με κάθε ένα από τα records της δεύτερης. Συνολικά δηλαδή γίνονται κάπου 19 δις συγκρίσεις strings. Το πρόγραμμα τρέχει με parallel linq.

 

Αν όλο σου το ζήτημα εδώ είναι να γνωρίζεις ανα πάσα ώρα και στιγμή αν/σε ποιες/πόσες εγγραφές σου υπάρχει ένα string, είναι απο τα πολύ βασικά προβλήματα του IR και η αρχαία λύση του ονομάζεται tf-idf. Πρακτικά φτιάχνεις ένα index για κάθε string, σε ποια strings υπάρχει (μπορέις να φτιάξεις και ένα id για reference) και πόσες φορές εμφανίζεται (αν σου χρειάζεται).
Hashάρεις τα strings και έχεις O(1) αναζήτηση. Γλιτώνεις το redundancy και γλιτώνεις την μέση περίπτωση του "τραβάω το string, κάνω το split, τσεκάρω 1-1 τα strings, επόμενο". 
Προφανώς το index το στήνεις απο τις λέξεις της μεγάλης λίστας και το constant search time σου λύνει τα χέρια. Αν κρατήσεις και το parallel κομμάτι της μικρής λίστας νομίζω είσαι οκ.

[Επισκέπτης]

25 λεπτά πριν, Theo1903 είπε

Αν όλο σου το ζήτημα εδώ είναι να γνωρίζεις ανα πάσα ώρα και στιγμή αν/σε ποιες/πόσες εγγραφές σου υπάρχει ένα string, είναι απο τα πολύ βασικά προβλήματα του IR και η αρχαία λύση του ονομάζεται tf-idf. Πρακτικά φτιάχνεις ένα index για κάθε string, σε ποια strings υπάρχει (μπορέις να φτιάξεις και ένα id για reference) και πόσες φορές εμφανίζεται (αν σου χρειάζεται).
Hashάρεις τα strings και έχεις O(1) αναζήτηση. Γλιτώνεις το redundancy και γλιτώνεις την μέση περίπτωση του "τραβάω το string, κάνω το split, τσεκάρω 1-1 τα strings, επόμενο". 
Προφανώς το index το στήνεις απο τις λέξεις της μεγάλης λίστας και το constant search time σου λύνει τα χέρια. Αν κρατήσεις και το parallel κομμάτι της μικρής λίστας νομίζω είσαι οκ.

Δεν γίνεται να γλυτώσω το split του string γιατί είναι λίγο πιο περίπλοκο. Θέλω να δω αν στο δεύτερο string υπάρχουν τουλάχιστον πέντε λέξεις από το πρώτο. Οπότε αναγκαστικά πρέπει να ψάξω μια προς μια.

5 ώρες πριν, albNik είπε

Δοκιμασε αυτο βαζοντας τα data σου στις list140_20 και list340000_20.

Η κατασκευή του wordIndicesMap δεν πρέπει να παρει πανω απο 1 sec ακομα και αν ολες οι 340000*20 λεξεις ειναι διαφορετικες.

Στο τελευταίο double loop έχεις να κάνεις 2800 dictionary lookups (λιγότερο από millisecond) αντί για 19 δις comparisons

 

Καταλαβαίνω τι λες, αλλά δεν έχει εφαρμογή σε αυτό που κάνω. Παρόλο αυτά ακολούθησα την αρχική σου συμβουλή για μια λίστα με dictionaries και έπεσε ο χρόνος κατά 40%. Που είναι υπεραρκετό. Πλέον αν χρειαστεί να το ρίξω κι άλλο απλά θα βασιστώ σε καλύτερη cpu.

Ευχαριστώ για τις απαντήσεις.

 

[albNik]

1 ώρα πριν, random_dude είπε

Παρόλο αυτά ακολούθησα την αρχική σου συμβουλή για μια λίστα με dictionaries και έπεσε ο χρόνος κατά 40%. Που είναι υπεραρκετό.

 Για λίγες λέξεις (20 στην περίπτωση σου) δεν βλέπεις τεράστια διαφορά στην linear αναζήτηση σε List vs Dictionary lookup εξ ου και το μικρο 40%.

1 ώρα πριν, random_dude είπε

Θέλω να δω αν στο δεύτερο string υπάρχουν τουλάχιστον πέντε λέξεις από το πρώτο.

Εξακολουθώ να πιστευω οτι υπαρχει αλγόριθμος <1 sec ακόμα και με αυτόν τον περιορισμό χωρίς να ξοδεύεις σε harware.

Γενικά μιλώντας δεν χρειάζεσαι μνήμη αφού τα δεδομένα σου είναι κατι δεκάδες MB. Αυτο που ίσως θα βοηθούσε είναι cpu με μεγαλύτερη cache. Η cache είναι σε επίπεδα L1-L2-L3. H L1 είναι εως και 100 φορες ταχυτερη απο τη RAM, L2 πιο αργη από L1, L3 πιο αργή από L2. Οταν ο cpu χρειάζεται π.χ. μια value κοιτάει πρώτα στις cache, αν υπάρχουν είναι cache-hit αλλιώς cache-miss και θα περιμένει (delay for hundreds of cpu cycles) να έρθουν από την (αργη) RAM. Οσο μεγαλύτερη η cache, ειδικά η L1 που είναι πανάκριβη τόσο καλυτέρα. Στην C# τα collections List, Array, Dictionary etc είναι cache-friendly , δλδ αν το list[5] είναι στην cache τότε υπάρχει μεγάλη πιθανότητα και οι επόμενες τιμές list[6], list[7]… να είναι εκεί. 

 

 

 

Επεξ/σία 19 Ιουνίου 2022 από albNik

[DrKo]

3 ώρες πριν, albNik είπε

Γενικά μιλώντας δεν χρειάζεσαι μνήμη αφού τα δεδομένα σου είναι κατι δεκάδες MB. Αυτο που ίσως θα βοηθούσε είναι cpu με μεγαλύτερη cache. Η cache είναι σε επίπεδα L1-L2-L3. H L1 είναι εως και 100 φορες ταχυτερη απο τη RAM, L2 πιο αργη από L1, L3 πιο αργή από L2. Οταν ο cpu χρειάζεται π.χ. μια value κοιτάει πρώτα στις cache, αν υπάρχουν είναι cache-hit αλλιώς cache-miss και θα περιμένει (delay for hundreds of cpu cycles) να έρθουν από την (αργη) RAM. Οσο μεγαλύτερη η cache, ειδικά η L1 που είναι πανάκριβη τόσο καλυτέρα.

Αυτό ακριβώς. 

[Επισκέπτης]

10 ώρες πριν, albNik είπε

 Για λίγες λέξεις (20 στην περίπτωση σου) δεν βλέπεις τεράστια διαφορά στην linear αναζήτηση σε List vs Dictionary lookup εξ ου και το μικρο 40%.

Εξακολουθώ να πιστευω οτι υπαρχει αλγόριθμος <1 sec ακόμα και με αυτόν τον περιορισμό χωρίς να ξοδεύεις σε harware.

 

ΟΚ, αλλά πως; Έχουμε δύο dictionaries.

Το πρώτο είναι {"id", "word1, word2, word3, ...., word20"}. Έχει 140 items.

To δεύτερo είναι το ίδιο, αλλά έχει 330k items.

Για κάθε item από την πρώτη λίστα θέλω να δω ποια items από την δεύτερη έχουν τουλάχιστον 5 κοινές λέξεις. Μπορεί να μην είναι και κανένα.

Μου φαίνεται απίθανο αυτό το πράγμα να μπορεί να γίνει σε λιγότερο από ένα δευτερόλεπτο.

Τώρα για το θέμα της CPU. Τα data είναι 88 MB, οπότε ας πούμε 100 μαζί με τους indexes των dictionaries. Από ότι βλέπω cache πάνω από 100ΜΒ έχουν μόνο οι Epyc και μερικοί threadripper. Είναι μια καλή λύση, αν και με βγάζει εκτός αρχικού budget.

Όπως και να 'χει, και πάλι ευχαριστώ για τις απαντήσεις. Με καλύψατε απόλυτα.