πολλαπλά nested ifs

[Aztec]

 

Όποιος μπορεί ας προτείνει ένα πιο κομψό τρόπο να γραφτεί το παρακάτω foor-loop.

for (int i = 0; i < MAX_NO_TRIANGLES; i++) {
   if (Triangles[i].mA == v2 || Triangles[i].mB == v2 || Triangles[i].mC == v2) {
       if (Triangles[i].mA == v3 || Triangles[i].mB == v3 || Triangles[i].mC == v3) {
           if (Triangles[i].mA == v1 || Triangles[i].mB == v1 || Triangles[i].mC == v1) {
           }
           else {
              adjTriangle = i;
              i = MAX_NO_TRIANGLES;
           }
       }
   }
 
   if (i == MAX_NO_TRIANGLES-1) {
      if (Triangles[i].mA == 0 && Triangles[i].mB == 0 && Triangles[i].mC == 0)
         return 1;
   }
}

 

 

Mπορεί να μην το έχω πιάσει καλα αλλά αυτο δεν γράφεται ως ακολούθως αν τα v1<>v2<>v3 ?

if Triangles[i].mA + Triangles[i].mB + Triangles[i].mC == v1 + v2 + v3 then

μάλλον δεν παίζει τώρα που το ξανασκέφτομαι γιατι μπορει να επικαλύπτονται συνδυασμοί

[Dr.Fuzzy]

@defacer

Ο τρόπος με τα continue είναι όντως πιο pleasing to the eye αλλά δεν έχει κανένα effect στο resulting dataflow structure (ο HL synthesizer προφανώς κάνει το ίδιο optimization στο translation)

 

@jimex

O τρόπος σου έχει περισσότερα operations (λογικό) στο ίδιο pipeline stage και 1 κύκλο latency παραπάνω (λόγω acc +) αλλά καλύτερο throughput.   

[jimex]

...

 

Δε θα γλιτώσει κάτι. Το θέλει καθαρά για θέμα ταχύτητας και όχι οπτικό σε κάτι που ο compiler του δύσκολα θα κάνει optimization.

 

@jimex

O τρόπος σου έχει περισσότερα operations (λογικό) στο ίδιο pipeline stage και 1 κύκλο latency παραπάνω (λόγω acc +) αλλά καλύτερο throughput.   

 

Αναμενόμενο στις περισσότερες μη ιδιότροπες αρχιτεκτονικές. Παλιοί καλοί τρόποι της C που δε συναντάς σε άλλες γλώσσες και ευτυχώς πολλά τέτοια τα αναλαμβάνει πλέον ο compiler.

 

Επίσης μπορείς και το zero να το βάλεις στο acc πολλαπλασιασμένο *7 και να έχεις ένα switch με 3 cases. Tο 9, το 4 και το 7. Try it.

[Dr.Fuzzy]

Δε θα γλιτώσει κάτι. Το θέλει καθαρά για θέμα ταχύτητας και όχι οπτικό σε κάτι που ο compiler του δύσκολα θα κάνει optimization.

 

 

Αναμενόμενο στις περισσότερες μη ιδιότροπες αρχιτεκτονικές. Παλιοί καλοί τρόποι της C που δε συναντάς σε άλλες γλώσσες και ευτυχώς πολλά τέτοια τα αναλαμβάνει πλέον ο compiler.

 

Επίσης μπορείς και το zero να το βάλεις στο acc πολλαπλασιασμένο *7 και να έχεις ένα switch με 3 cases. Tο 9, το 4 και το 7. Try it.

 

Κάπως έτσι δηλαδή, αλλά τo if (i == MAX_NO_TRIANGLES - 1 && zero) ;

legalizeEdge_label1: for (int i = 0; i < MAX_NO_TRIANGLES; i++) {
int acc = (Triangles[i].mA == v2 || Triangles[i].mB == v2
|| Triangles[i].mC == v2) * 1;
acc += (Triangles[i].mA == v3 || Triangles[i].mB == v3
|| Triangles[i].mC == v3) * 3;
acc += (Triangles[i].mA == v1 || Triangles[i].mB == v1
|| Triangles[i].mC == v1) * 5;
bool zero = Triangles[i].mA == 0 && Triangles[i].mB == 0
&& Triangles[i].mC == 0;
acc += zero * 7;
 
switch (acc) {
case 9:
break;
case 7:
break;
case 4:
adjTriangle = i;
i = MAX_NO_TRIANGLES;
}
 
if (i == MAX_NO_TRIANGLES - 1 && zero)
return 1;
}

[Papakaliati]

 

Κάπως έτσι δηλαδή, αλλά τo if (i == MAX_NO_TRIANGLES - 1 && zero) ;

legalizeEdge_label1: for (int i = 0; i < MAX_NO_TRIANGLES; i++) {
int acc = (Triangles[i].mA == v2 || Triangles[i].mB == v2
|| Triangles[i].mC == v2) * 1;
acc += (Triangles[i].mA == v3 || Triangles[i].mB == v3
|| Triangles[i].mC == v3) * 3;
acc += (Triangles[i].mA == v1 || Triangles[i].mB == v1
|| Triangles[i].mC == v1) * 5;
bool zero = Triangles[i].mA == 0 && Triangles[i].mB == 0
&& Triangles[i].mC == 0;
acc += zero * 7;
 
switch (acc) {
case 9:
break;
case 7:
break;
case 4:
adjTriangle = i;
i = MAX_NO_TRIANGLES;
}
 
if (i == MAX_NO_TRIANGLES - 1 && zero)
return 1;
}

 

 

Αντε να καταλαβει καποιος τι γινεται εκει μεσα. Το να αποφυγεις nested ifs, κανοντας τον κωδικα σου ενα μυστηριο που δεν μπορει κανενας να αποκρυπτογραφισει ακομη και αν εισαι πανω απο το κεφαλι του 30 ωρα, δεν ειναι η λυση...

 

Χιλιες φορες τα 3 ifs και να καταλαβεις με την πρωτη ματια τι γινεται. 

 

Πραγματικα αμα συναντουσα σε κωδικα συναδελφου μου αυτο το ειδος κωδικα, θα πηγαινα με την μια στο ΗR για παραπονα.

[imitheos]

Όποιος μπορεί ας προτείνει ένα πιο κομψό τρόπο να γραφτεί το παρακάτω foor-loop.

for (int i = 0; i < MAX_NO_TRIANGLES; i++) {
   if (Triangles[i].mA == v2 || Triangles[i].mB == v2 || Triangles[i].mC == v2) {
       if (Triangles[i].mA == v3 || Triangles[i].mB == v3 || Triangles[i].mC == v3) {
           if (Triangles[i].mA == v1 || Triangles[i].mB == v1 || Triangles[i].mC == v1) {
           }
           else {
              adjTriangle = i;
              i = MAX_NO_TRIANGLES;
           }
       }
   }
 
   if (i == MAX_NO_TRIANGLES-1) {
      if (Triangles[i].mA == 0 && Triangles[i].mB == 0 && Triangles[i].mC == 0)
         return 1;
   }
}

 

Μέσα στο κενό σώμα του if == v1 θα βάλεις κάτι στο μέλλον ? Αν όχι, έχει κάποιο νόημα ? Επίσης σε κάποιο από τα δύο σώματα του if θα υπάρχει κάποιο continue ή break ? Αν όχι, το for δεν θα φτάσει πάντα στο τέλος του (όπου και i == MNT - 1 και θα εκτελεστεί το if οπότε μπορεί να βγει εκτός του for) ?

 

Εγώ πιστεύω η λύση του Kercyn είναι πιο κομψή από το *5 + *3, κτλ που προτάθηκε μετά.

[Dr.Fuzzy]

@Papakaliati

Οι συγκεκριμένες αλλαγές δεν είναι for cosmetic reasons, έχουν αντίκτυπο και καθορίζουν όπως είπα το τελικό architecture. Ο κώδικας προορίζεται για high level synthesis και παρόλο που μπορεις να οδηγήσεις τη σύνθεση με διαφορά directives (pragmas) σε πολλές περιπτώσεις δεν ειναι αρκετό οποτε πρέπει να επεμβεις χειροκίνητα στον ιδιο τον κώδικα. Αν επρόκειτο για sw υλοποίηση που θα γινόταν run sequentially σε κάποιο CPU προφανώς και εγώ θα έκανα παράπονα, αλλα εδω ειναι τελείως διαφορετική περίπτωση. Δηλαδή να το πω απλά εχουμε χύμα συνδυαστικά και ακολουθιακα στοιχεία και παμε να δημιουργήσουμε μια processing pipeline δομή με αυτα.

[Papakaliati]

@Papakaliati

Οι συγκεκριμένες αλλαγές δεν είναι for cosmetic reasons, έχουν αντίκτυπο και καθορίζουν όπως είπα το τελικό architecture. Ο κώδικας προορίζεται για high level synthesis και παρόλο που μπορεις να οδηγήσεις τη σύνθεση με διαφορά directives (pragmas) σε πολλές περιπτώσεις δεν ειναι αρκετό οποτε πρέπει να επεμβεις χειροκίνητα στον ιδιο τον κώδικα. Αν επρόκειτο για sw υλοποίηση που θα γινόταν run sequentially σε κάποιο CPU προφανώς και εγώ θα έκανα παράπονα, αλλα εδω ειναι τελείως διαφορετική περίπτωση!

 

 

Με ποιον τροπο η διαφορετικη διατυπωση μιας μεθοδου που οδηγει στο ιδιο αποτελεσμα καθοριζει το τελικο architecture;

Γιατι η ταξη μεγεθους και στις δυο περιπτωσεις ειναι η ιδια. Ενα for στην μια περιπτωση, ενα for εχεις και στην αλλη...

 

  Το μονο που καταφερες ειναι να μην καταλαβαινει κανενας τι κανεις στην δευτερη περιπτωση, χωρις να εχεις το παραμικρο οφελος. Αρα αμα στο μελλον θελησει να δει καποιος τον αλγοριθμο στο συνολο του ωστε να πετυχει τυχον ουσιαστικες βελτιωσεις, εχεις κανει την δουλεια του αρκετα πιο δυσκολη. O αριθμος των operations ειναι ο ιδιος και στις δυο λυσεις.

 

Προφανως δεν εχω καταλαβει ακριβως τον σκοπο. Αυτο που υποπτευομαι ομως, ειναι οτι περα απο καθαρα ακαδημαικο και θεωρητικο επιπεδο, δεν εχει και πολυ σημασια;

[gon1332]

Έχεις δει σε τί μετατρέπονται τα || και && από κάτω;

 

Είδες διαφορά με logical operators vs if-then-else;

 

Φαντάζομαι το switch-case μετατρέπεται σε lut φάση;

[Dr.Fuzzy]

@Papakaliati

Ο τρόπος που σκέφτεσαι ειναι καθαρά sw wise, αλλα εδω έχουμε διαφορετικό target. Δες τι ειναι high level logic synthesis αν θες και ποιος ο λόγος χρήσης της έναντι της κλασικής απευθείας περιγραφής HW σε RTL. Πέραν του ακαδημαϊκού-θεωρητικού επιπέδου, commercial HLS tools χρησιμοποιούνται σχεδόν πλέον σε όλο το System-on-a-Chip (SoC) design flow απο όλες τις VLSI εταιρίες για hw/sw co-design και co-simulation.

 

Προφανώς και κανει διαφορά και όπως είπα σε προηγούμενο ποστ η υλοποίηση του jimax αντιστοιχεί σε μια αρχιτεκτονική δομή που εχει καλύτερο throughput.

 

Τέλος αυτός που μελλοντικά θα δει την υλοποίηση, τον ενδιαφέρει να δει ενα high level data flow diagram, το pipeline και μια high level περιγραφή του αλγορίθμου διότι σκέφτεται hw wise και όχι sw wise. Αν παλι έστω οτι ήταν ομαδική δουλεια σε εταιρία και έβλεπε την υλοποίηση σε C++ θα καταλάβαινε το λόγο που γράφτηκε ετσι.

 

@gon1332

Ναι έχει διαφορά, με τα logic operation σε σχέση με την pure if-else εχω μεγαλύτερο concurrency (περισσότερα συνδυαστικά operations). Το switch-case δεν το εχω δοκιμάσει ακόμα αλλα φανταζομαι θα φτιάξει ενα περισσότερο balanced architecture με περισσότερα resources και μικρότερο κρίσιμο μονοπάτι.

[k33theod]

Εάν περιγράψεις το πραγματικό πρόβλημα ίσως πάρεις κάποια καλύτερη ιδέα σαν αλγόριθμο και πιο σωστό κώδικα,

 

Με τα if ελέγεις τρείς ιδιότητες αν έχουν κάποια συγκεκριμένη τιμή

και μετά πάλι αν έχουν κάποια άλλη τιμή και μετά κάποια άλλη

 

Έστω ότι  Triangles[i].mA = v2 γιατί αμέσως μετά να ελέγξω άν Triangles[i].mA == v3 και μετά Triangles[i].mA ==v1

 

Μήπως σε καλύπτει πχ το sorted(Triangles.mA, Triangles.mB, Triangles.mC)==sorted(v1,v2,v3) δεν ξέρω πως μεταφράζεται σε c++ 

Νομίζω οδηγεί στο ίδιο αποτέλεσμα με τα nested ifs

[Dr.Fuzzy]

Συνοπτικά εναι πρόβλημα Delaunay τριγωνισμου με πολυ μεγάλο FPS rate σε point clouds, οποτε δε τίθεται θέμα αλγορίθμου αλλα βελτιστοποιήσεων latency/throughput σε επιμέρους κομμάτια σαν αυτο που έκανα ποστ.

[παπι]

int i;
for (i = 0; i < MAX_NO_TRiANGLES; i++) {
   if ( !(
            (Triangles[i].mA == v2 || Triangles[i].mB == v2 || Triangles[i].mC == v2)
        &&  (Triangles[i].mA == v3 || Triangles[i].mB == v3 || Triangles[i].mC == v3)
        &&  (Triangles[i].mA == v1 || Triangles[i].mB == v1 || Triangles[i].mC == v1)
   ))
     break;
}
if (
    i == MAX_NO_TRiANGLES - 1
    && Triangles[i].mA == 0 
    && Triangles[i].mB == 0 
    && Triangles[i].mC == 0){
    return 1;
}
//i is adjTriangle

Για βελτιστοποιηση το γραφεις σε shader, θα ειναι χ800 με χ3000

[jimex]

Με ποιον τροπο η διαφορετικη διατυπωση μιας μεθοδου που οδηγει στο ιδιο αποτελεσμα καθοριζει το τελικο architecture;

Γιατι η ταξη μεγεθους και στις δυο περιπτωσεις ειναι η ιδια. Ενα for στην μια περιπτωση, ενα for εχεις και στην αλλη...

 

  Το μονο που καταφερες ειναι να μην καταλαβαινει κανενας τι κανεις στην δευτερη περιπτωση, χωρις να εχεις το παραμικρο οφελος. Αρα αμα στο μελλον θελησει να δει καποιος τον αλγοριθμο στο συνολο του ωστε να πετυχει τυχον ουσιαστικες βελτιωσεις, εχεις κανει την δουλεια του αρκετα πιο δυσκολη. O αριθμος των operations ειναι ο ιδιος και στις δυο λυσεις.

 

Προφανως δεν εχω καταλαβει ακριβως τον σκοπο. Αυτο που υποπτευομαι ομως, ειναι οτι περα απο καθαρα ακαδημαικο και θεωρητικο επιπεδο, δεν εχει και πολυ σημασια;

 

Τσούκου. Δεν είναι θέμα η θεωρητική τάξη του αλγορίθμου ή ο αριθμός των operations. Καμία σχέση με αυτά και αυτό γιατί το sw δεν τρέχει σε κάποια θεωρητική αρχιτεκτονική, αλλά στο μέταλλο και όλες οι εντολές της αρχιτεκτονικής δεν τρέχουν στον ίδιο χρόνο. Επίσης οι εντολές στην πραγματικότητα δεν είναι τόσο ανεξάρτητες (όπως μπορεί να φαντάζεσαι ή όχι) σε ένα pipelined σύστημα και επίσης πρέπει να λάβεις υπόψη διπλές ALU, το πόσο καλό είναι το branch prediction unit και πάει λέγοντας.

 

Οι μη ωραίες οπτικά βελτιστοποιήσεις είναι πολύ κοινές στο low level κομμάτι και χρησιμοποιούνται ακόμη και σήμερα σε κώδικα για kernels, drivers, embedded devices και γενικά όπου η ταχύτητα παίζει κρίσιμο ρόλο. Από τον καρκίνο βελτιστοποιήσεων τύπου Duff's Device  που χρησιμοποιούνταν μέχρι και σχεδόν δέκα χρόνια πριν μέχρι το παραπάνω. Φυσικά, αν πρόκειται για κώδικα που θα τρέξει αποκλειστικά σε συγκεκριμένη αρχιτεκτονική και θέλει εκτεταμένες τέτοιες βελτιώσεις που δεν μπορεί να κάνει ο compiler, ίσως είναι προτίμοτερο να γίνεται κανείς σπαρτιάτης.

 

 

Για βελτιστοποιηση το γραφεις σε shader, θα ειναι χ800 με χ3000

 

Αν υπάρχει GPU ναι.

[gon1332]

@Dr.Fuzzy

 

Αχαα. Αν αντικαθιστούσες τα logic με binary ops; Φαντάζομαι δε θα έχεις πολύ μεγαλύτερο κέρδος σε σχέση με την απαλοιφή των if-else. Απλά κουβέντα να γίνεται.