[C++] - Διαχειρηση μνήμης

[bnvdarklord]

Καλησπέρα,

 

Έχω κάποια προβλήματα σε ενα πρόγραμμα που φτιάχνω μια υλοποιηση του Djikstra.

 

Το φαινομενικό προβλημα ειναι οτι αποτυχγαίνει το find σε ένα map μου έχω. Δηλαδή λεει οτι βρήκε κάτι, ενώ δεν ειναι στο map μεσα. Έτρεξα το Dr. Memory (το βρηκα σαν παραπλησιο του memcheck του Valgrind που δεν υπαρχει για windows) και μου λεει οτι υπάρχουν θέματα στην κλάση που διαχειρίζομαι τα Labels του αλγορίθμου.

 

Υποπτευομαι οτι μπορει να εχω κανει καποιο λαθος με τους copy/move constructors, καθώς δεν είμαι πολυ καλος στην C++, και πάλι απο δω μου ειπαν να βάλω.

 

Ο κώδικας της Label ειναι σε αρχείο, γιατι τα tabs χανονται με το copy paste.

 

Ευχαριστώ πολύ.

Label.zip

[Praetorian]

Από κάποια παραδείγματα που βρίσκω από σύντομο search, σε παρόμοιες περιπτώσεις (υποθέτω ότι στο map σου έχεις keys τύπου Label), ορίζουν κανονικά (δηλαδή όχι μέσω των άλλων operators) μόνο το overload για τον τελεστή <.  (γιατί το > και το == προκύπτουν από αυτόν). (και από ότι καταλαβαίνω τυπικά χρησιμοποιείται αυτός ο operator για την find (?))

http://stackoverflow.com/questions/13965082/should-i-overload-operator-when-i-use-stl-sets
http://www.cplusplus.com/reference/map/map/key_comp/

Returns a copy of the comparison object used by the container to compare keys.

By default, this is a less object, which returns the same as operator<.

This object determines the order of the elements in the container: it is a function pointer or a function object that takes two arguments of the same type as the element keys, and returns true if the first argument is considered to go before the second in the strict weak ordering it defines, and false otherwise.

Two keys are considered equivalent if key_comp returns false reflexively (i.e., no matter the order in which the keys are passed as arguments).

 

Δεν μπορώ να βρω περίπτωση στον κώδικά σου που ενώ τα Labels είναι διαφορετικά, η "<" σύγκριση θα επέστρεφε false άσχετα με τη σειρά των arguments (και οπότε η find θα επέστρεφε κάτι εσφαλμένα), αλλά υπάρχουν κάποια όχι τόσο ξεκάθαρα σημεία. 

Πχ εδώ:

template <typename T> bool Label<T>::operator >(const Label<T> &other) const
{
	if (this->size != other.getSize())
		return false;

	for(int i = 0; i < size; i++)
	{
		if(this->criteria[i] > other.getCriteria(i))
			return true;
		else if(this->criteria[i] < other.getCriteria(i))
			return false;
	}
	
	return true;
}

Τι εξυπηρετεί ακριβώς το κομμάτι

	if (this->size != other.getSize())
		return false;

 Μπορείς να έχεις ταυτόχρονα δύο Labels a και b να είναι a>b και b>a επειδή δεν έχουν το ίδιο size; 

 
Και από αυτό ο κώδικάς σου για τον < operand οδηγεί σε:

!(*this >= other)

που πάει σε 

! ( (*this > other) || (*this == other) );

Το οποίο κάνει evaluate σε true αν τα operands δεν έχουν το ίδιο size.
Και τότε μπορεί να ισχύει a < b και ταυτόχρονα b < a ανάλογα με το ποιο operand πάει αριστερά.
Που δεν μου φαίνεται σωστό.
 
Επίσης, αν έχεις a και b με το ίδιο size, τότε το == αποφαίνεται true, αν όλα τα περιεχόμενα του criteria είναι ίσα (σωστά). Το ίδιο όμως κάνει και το > (γιατί όχι false? ).

 

Δεν είμαι σίγουρος, αλλά θα πρότεινα για αρχή να ορίσεις πλήρως το overload για:

- τον < operator, που να μην κάνει πάντα evaluate σε true άσχετα με τη σειρά των operands (στην περίπτωση διαφορετικού size).

- τον == operator (αν και σε αυτή την περίπτωση μπορεί να οριστεί και ως return !( (*this < other) || (other < *this) )

- και τους υπόλοιπους μέσω των δύο παραπάνω (ή μόνο του < ). 

 

Disclaimer, έχω καιρό να πιάσω C++.

[παπι]

Νομιζω η καλυτερη λυση ειναι να βαλεις ενα breakpoint στο find και να μπεις μεσα. 

btw στο init ειναι αχρηστη η for, η new εχει ηδη καλεσει τους defualt constructors

[bnvdarklord]

Σχετικά με τα Labels δεν θελω να γινεται συγκριση μεταξυ {2, 3} και {3, 5, 1} που δεν εχουν ιδιο size, για αυτο το εβαλα false. Παντα παιζω με 1 size στο προγραμμα παντως.

 

 

Τα υπολοιπα που αναφέρεις Preatorian θα τα κοιταξω.

 

 

Σχετικά με το map.

 

Βασικά προκειται για εναν map<int, HeapHandle> οπου το HeapHandle* ειναι ενα handle σε ενα boost::fibonacci_heap, που αναφέρεται στα labels. Δηλαδη αν παρω ενα handle και πω (*handle) περνω το Label που θελω.

 

Αυτο που συμβαινει ειναι το εξής.

 

Μπαίνουν καποια Label IDs μεσα στο map αυτο, και μετά καποια γινονται update κανονικα. Ξαφνικά το πρόγραμμα ζηταέι ενα id που δεν υπάρχει στο map(το οποιο συμβαινει, και οταν συμβει θα πρεπει να γινει add στο map αντι για update), αλλα το find επιστρέφει οτι υπάρχει. Δεν αποτυγχάνει από την 1η φορα δηλαδή.

 

Το find γινεται σε κατι τετοιο

Labels -> map<int, HeapHandle>
 
 
template <typename T> int LabelManager<T>::getHandle(int nodeID, HeapHandle &handle)
{
if(Labels.find(nodeID) == Labels.end())
{
return -1;
}
else
{
handle = Labels[nodeID];
return 0;
}
}

* To HeapHandle ειναι κατι τετοιο αν εχει σημασια:

 

 

typedef compare < greater < Label<T> > > HeapComparator;
typedef fibonacci_heap< Label<T>, HeapComparator > LabelFibMinHeap;
typedef typename LabelFibMinHeap::handle_type HeapHandle;

 

 

[Directx]

[..]Δηλαδή λεει οτι βρήκε κάτι, ενώ δεν ειναι στο map μεσα. Έτρεξα το Dr. Memory (το βρηκα σαν παραπλησιο του memcheck του Valgrind που δεν υπαρχει για windows) και μου λεει οτι υπάρχουν θέματα στην κλάση που διαχειρίζομαι τα Labels του αλγορίθμου.

 

Υποπτευομαι οτι μπορει να εχω κανει καποιο λαθος με τους copy/move constructors, καθώς δεν είμαι πολυ καλος στην C++, και πάλι απο δω μου ειπαν να βάλω.[..]

Χμ.. ο Dr. Memory μπορεί να χτυπάει για διάφορους λόγους (σχετικούς με το πρόβλημα σου ή ίσως άσχετους με αυτό). Για παράδειγμα στην περίπτωση του operator= το criteria γίνεται πάντα new T (δεν ελέγχεις επίσης για self-assignment) ενώ μπορεί να είναι ήδη δεσμευμένο (δεν υπάρχει κάποιο delete[]) οπότε αποκτάς αμέσως ένα memory leak αφού ο pointer του ήδη δεσμευμένου criteria αντικαθίσταται από ένα νέο. Αυτό το σφάλμα πάω στοίχημα ότι ο Dr. Memory θα το πιάσει και θα σου πει ότι έχεις θέματα με την Label class.. (ψάξε γενικά το class σου για τέτοιες περιπτώσεις μη αποδέσμευσης ήδη δεσμευμένης μνήμης).

[Praetorian]

Εφόσον τα keys που έχεις στο map είναι integers (Label Ids) και όχι αντικείμενα Label, δεν νομίζω τελικά να είναι το πρόβλημα στο overload των comparison operators (αν και καλό θα ήταν να διορθώσεις το ambiguity).

 

Αυτο που συμβαινει ειναι το εξής.

 

Μπαίνουν καποια Label IDs μεσα στο map αυτο, και μετά καποια γινονται update κανονικα. Ξαφνικά το πρόγραμμα ζηταέι ενα id που δεν υπάρχει στο map(το οποιο συμβαινει, και οταν συμβει θα πρεπει να γινει add στο map αντι για update), αλλα το find επιστρέφει οτι υπάρχει. Δεν αποτυγχάνει από την 1η φορα δηλαδή.

 

Οι προσθήκες μέσα στο map γίνονται πάντα αφότου έχεις καλέσει την getHandle() (για να διαπιστώσεις αν θα γίνει insert ή update) ή αρχικά βάζεις key-values χωρίς έλεγχο? 

Τι επιστρέφεται στο handle από τη getHandle(), όταν η find βρίσκει id που δεν υπάρχει στο map;

[bnvdarklord]

Για παράδειγμα στην περίπτωση του operator= το criteria γίνεται πάντα new T (δεν ελέγχεις επίσης για self-assignment) ενώ μπορεί να είναι ήδη δεσμευμένο

 

Μμμ εκανα ενα delete[] criteria αμεσως πριν το new, και κρασάρει πολυ νωριτερα. Θα το κοιταξω περισσοτερο.

 

 

Εφόσον τα keys που έχεις στο map είναι integers (Label Ids) και όχι αντικείμενα Label, δεν νομίζω τελικά να είναι το πρόβλημα στο overload των comparison operators (αν και καλό θα ήταν να διορθώσεις το ambiguity).

 

 

Ναι, εφτιαξα τις ατελειες των τελεστών, τώρα δουλευουν σωστά. (Παντα false σε περιπτωση ανισων label, αν ειναι ισα το > ειναι false κτλ)

 

 

 

Οι προσθήκες μέσα στο map γίνονται πάντα αφότου έχεις καλέσει την getHandle() (για να διαπιστώσεις αν θα γίνει insert ή update) ή αρχικά βάζεις key-values χωρίς έλεγχο? 

Τι επιστρέφεται στο handle από τη getHandle(), όταν η find βρίσκει id που δεν υπάρχει στο map;

 

Ναι, αν το getHandle επιστρέψει -1 (= δεν το βρηκε) το κανω insert.

 

Ουσιαστικά τα handles που δειχνουν στο queue αποθηκευονται παράλληλα και στο map, ωστε να μπορω να βλεπω οποτε θελω τα labels των κομβων.

[παπι]

Δεν αναεβαζεις το project να το "περασω" απο το debugger;

υγ αν το ανεβασεις, κανε clean (debug->clean) πρωτα και μετα διεγραψε τις βασεις

[bnvdarklord]

Θα το ανέβαζα, αλλα εφ'ενός ειναι πτυχιακή, αφ'ετέρου εχει 450ΜΒ input data.

 

Για να κανω debug στο visual studio αρκει το Release να το κανω Debug? Εχω επιλεγμένο το Release γιατι κανει 40 λεπτα να φορτώσει τα δεδομένα και να φτιαξει τις αρχικες δομες με το Debug, ενώ με το Release 15 δευτερόλεπτα.

[παπι]

40 λεπτα;

[bnvdarklord]

Ναι, αν επιλεξω debug. Με το Release κανει 15 δευτερολεπτα πανω κατω. Φτιάχνει το γράφημα φορτώνοντας ολα αυτα τα input data, για αυτο αργει τόσο υποθετω.

[παπι]

Περιεργο. Μαλλον επειδη στο release μπαινει και το optimization, δεν κανει πληρες compile.

Τεσπα, δεν μπορει να δουλεψει με λιγοτερα data?

[bnvdarklord]

Ισως επισης επειδη κρατάει και πράγματα για το debug. Οπως και να χει. Θα δουλεψει με λιγοτερα data, απλα επειδη μιλάμε για 4-5 αρχεια που συσχετιζονται μεταξύ τους, θελει δουλεια για να φτιαχτούν σωστά. Θα δω αυριο μηπως κανω κατι τετοιο.

 

Εν τω μεταξύ φτιαχνοντας απλα 2 Labels και λεγοντας l1 = l2 δεν κρασάρει με το delete στο criteria. Κατι εχω κανει πολυ στραβα φαινεται.

[Directx]

Μμμ εκανα ενα delete[] criteria αμεσως πριν το new, και κρασάρει πολυ νωριτερα. Θα το κοιταξω περισσοτερο.

Κοιτάζοντας τον κώδικα λίγο περισσότερο βλέπω ότι σε ορισμένους ctor που χρειάζεται, δεν αρχικοποιείς τον δείκτη criteria σε NULL με άμεση συνέπεια την αστοχία της delete[] αν δεν έχει κληθεί η private διαδικασία init και ο criteria pointer δείχνει σε κάποια τυχαία τιμή.

 

Αυτό μπορεί να συμβεί στον ctor template <typename T> Label<T>::Label(const Label<T>& other) όπου γίνεται απευθείας ανάθεση του other στην class οπότε εκτελείται ο operator= δίχως το criteria να είναι αρχικοποιημένο σε NULL άρα το delete[] του operator= αστοχεί.

 

Αν ο ctor τροποποιηθεί ως εξής τότε γλυτώνεις από ένα ακόμα σφάλμα μνήμης σε περιπτώσεις χρήσης του ctor αυτού.

template <typename T> Label<T>::Label(const Label<T>& other)
{
	criteria = NULL;

	*this = other;	// ?
}

Ψάξε για άλλα ανάλογα σφάλματα στον κώδικα σου.

[bnvdarklord]

Γιατι πρεπει να αρχικοποιηθει σε null για να δουλεψει το delete?

 

(criteria = nullptr ειναι το ιδιο ε; )

Λοιπόν μιας και το Debug του Visual Studio για καποιο λογο αποφάσισε να μην βλεπει την boost, κανω debug με gdb και g++. Το οποιο αντι τα 40 λεπτά του visual studio κανει 1.5 λεπτό. Τόσο σαπιο ειναι το vs;
  
Anyway. Πέρνω αυτό που δεν εχω ιδεα τι εννοει

warning: HEAP[a.exe]:
warning: Invalid address specified to RtlFreeHeap( 006F0000, 75E7F480 )


Program received signal SIGTRAP, Trace/breakpoint trap.
0x77bb0575 in ntdll!TpWaitForAlpcCompletion () from C:\Windows\system32\ntdll.dll