Memory Optimization help (no debugging)

[trentkg]

I need some help optimizing my memory usage.

I am making a c++ program to study the effect of leads on scoring ability in soccer. I am taking data on every world cup since 1930. To organize my data, I have a class WC as well as a struct Game and within each game a linked list of struct Event.

class WC{

public:
	std::vector<Gamep> GameList; //list of pointers to games that have taken place in the WC, ordered by appearance on wikipedia 
	std::string RN; //Notes on Ranking

	WC( std::string); //
	
	void addGame(Gamep); 
	void FrequencyTable();
	
	};

struct Game{
	
	std::string TeamA; //the two teams playing in the game. 
	unsigned int rankA;
	std::string TeamB;
	unsigned int rankB;
	unsigned int finalA; // A final score
	unsigned int finalB; //B final score
	Eventp ev; //pointer to the the first event in the game. namely, first time someone scores
	unsigned int EventNum; //number of events in the game
	std::string notes; //is it the final? any notes on game
	};


struct Event {
	unsigned int scoreA; //score of teamA at any point in time
	unsigned int scoreB; //score of teamB 
	unsigned int STime; //start/end time of the event
	unsigned int ETime;
	struct Game *thegame; //pointer to a game the Event is in
	struct Event *nextevent; //pointer to next event in line, or null
	
	}; 

As you can, an event is paramaterized by when someone scores. For each event there is a start time, an end time, and a current score, as well as a pointer to the next event. Events are the heart of what I am studying -- I want to study the effect of events on future events as well as future outcomes or other variables (such as opposing goals per minute or probability of comebacks)


To create a game, I have a function MGame that allocates new space using new . To create an event, I have a function MEvent that takes the parameters of event and a game to put it in. It allocates new space for the event using new and places that event in the Game. I then make a ton of calls to all of these functions in main to create the data I'm working on, like so...

int main() {
 
 WC WC1930 ("FIFA retrospective ranking");
 
 Gamep FM = MGame("France", "Mexico", 7, 13, 4, 1, "Group 1");
 
 addEvent(1, 0, 19, 40, FM);
 addEvent(2, 0, 40, 43, FM);
 addEvent(3, 0, 43, 70, FM);
 addEvent(3, 1, 70, 87, FM);
 addEvent(4, 1, 87, 90, FM);
 
 WC1930.addGame(FM);

....
return 0;
}

///MGame and AddEvent look like...

Gamep MGame ( string Aname, string Bname, unsigned int rA, unsigned int rB, unsigned int fA, unsigned int fB, string nts) {
	Gamep tempG = new Game;
	
	
	tempG->TeamA = Aname;
	tempG->rankA = rA;
	tempG->rankB = rB;
	tempG->TeamB = Bname;
	tempG->finalA = fA;
	tempG->finalB = fB;
	tempG->ev = NULL;
	tempG->EventNum = 0;
	tempG->notes = nts;
	
	return tempG;
	}

void addEvent( unsigned int Ascore, unsigned int Bscore, unsigned int TimeS, unsigned int TimeE, Gamep g) { //new event and current event. adds an event to the long list of events 
     Eventp nwevnt = new Event;
	 
	 nwevnt->scoreA = Ascore;
	nwevnt->scoreB = Bscore;
	nwevnt->STime = TimeS;
	nwevnt->ETime = TimeE;
	nwevnt->thegame = g;
	nwevnt->nextevent = NULL;
	 
	 
	 //now we place the event in the game g
	 
		if((g->ev) == NULL) {
		g->ev = nwevnt;
		++(g->EventNum); 
		}

		else {
       Eventp temp;
	   temp = g->ev;
	   while(temp->nextevent != NULL)
	   temp = temp->nextevent; // find the last event 
       temp->nextevent = nwevnt; 
        ++(g->EventNum);
		}
        
        
     }



	

	 

My problem is that so far I only have one world cup and I already have an output file that is 91 MB. This seems huge -- there are only 17 games with a total of 88 events. I want to add maybe 20 more world cups.

So, I decided to rewrite my program, this time with Game as a class, and instead of having a struct Event, in each Game I have a vector of ints that have order Stime, score of team A, score of team B. This will eliminate some unneded data that was in the struct Event (such as saving a bunch of pointers in events to the game they're in, and pointers to the next event) and be 88 fewer calls to new, because events are now a bunch of vectors within games instead of structs.

class Game{
	public: 
	std::string TeamA; //the two teams playing in the game. somehow we should put rank in? 
	std::string TeamB;
	int rankA;
	int rankB;
	int finalA; // A final score
	int finalB; //B final score
	std::vector<int> EventV; //a vector of events in the form TIME, A Score, B Score, 
	std::string notes; //is it the final? any notes on game
	
	Game( std::string, std::string, int, int, int, int, std::string);
	void addEvent( int, int, int );
	
	
	};

class Game{
	public: 
	std::string TeamA; //the two teams playing in the game. somehow we should put rank in? 
	std::string TeamB;
	int rankA;
	int rankB;
	int finalA; // A final score
	int finalB; //B final score
	std::vector<int> EventV; //a vector of events in the form TIME, A Score, B Score, 
	std::string notes; //is it the final? any notes on game
	
	Game( std::string, std::string, int, int, int, int, std::string);
	void addEvent( int, int, int );
	
	
	};

void Game::addEvent( int time, int Ascore, int Bscore) { //adds event to the vector of events
	 
	 EventV.push_back(time);
	 EventV.push_back(Ascore);
	 EventV.push_back(Bscore);
        
        
     }



	

//Make a game		 
Game::Game(string ATeam, string BTeam, int rA, int rB, int fA, int fB, string nts) {

	TeamA = ATeam;
	TeamB = BTeam;
	rankA = rA;
	rankB = rB;
	finalA = fA;
	finalB = fB;
	notes = nts;
	}

so PGame.addEvent( int int int) just pops on the start time, score of team A, and score of team B for a given event. I feel like this should take up less memory, because there is no longer the superflous pointers that were in each Struct Event.

The problem is that now my output file is 123 MB. Once again, this seems huge, and its even larger than before. whats going on here? All I'm really doing to the data so far is entering all of it in main, i.e. making calls like...

int main() { 

WC WC1930("FIFA retrospective ranking");
 
 Gamep FM = new Game("France", "Mexico", 7, 13, 4, 1, "Group 1");
 
 
 (*FM).addEvent(19, 1, 0);//19 minute, 1,0
 (*FM).addEvent(40, 2, 0);//40 minute, 2,0 et
 (*FM).addEvent(45, 3, 0);
 (*FM).addEvent(70, 3, 1);
 (*FM).addEvent(87, 4, 1);
 
 WC1930.addGame(FM);

....//Functions that mess with all the data I have, like FrequencyTable()
.....

delete FM;
return 0;
}

over and over, for every game, and then finally I have a function FrequencyTable() that is a member function of the class WC that prints out a frequency table for how many events are scored in each minute ( minute on the x-axis, frequency on the y-axis) for a given world cup.

I also make sure to delete all of my games in main after making my call to FrequencyTable.

So I could really use any tips at all as for memory optimization. I thought that fewer new calls would surely mean a smaller file, but I guess not -- maybe I'm using the stack more this time around? Maybe function calls are just taking up a ton more space than i would have expected? this is surprising to me given I only have one major function, and, all in all, there really isn't that much data -- just a ton of calls to constructors.

Cheers,

-Trent

[Gaminic]

What exactly do you mean by output file?

[coder777]

There must be a fundamental mistake in how you store your data. 17 games with a total of 88 events makes total 1496 events. Let's say you store 1 kb of data per event (but you're storing less) that'd be ~ 1.5 MB.

I'm not able to say what's the problem is (since you don't show the code), but you should do such a calculation (reasonable values!). If your actual data size exceeds that value you have another problem than optimizing.

[trentkg]

By output file I mean the executable produced by compilation.

Coder --

Thats 88 total events dispersed between 17 total games (around 4.5 events per game, or 4.5 total goals per game).

For clarity's sake here is my initial code.

struct Event {
	unsigned int scoreA; //score of teamA at any point in time
	unsigned int scoreB; //score of teamB 
	unsigned int STime; //start/end time of the event
	unsigned int ETime;
	struct Game *thegame; //pointer to a game the Event is in
	struct Event *nextevent; //pointer to next event in line, or null
	
	}; 
	

typedef struct Event *Eventp;
typedef struct Game *Gamep;

struct Game{
	
	std::string TeamA; //the two teams playing in the game. somehow we should put rank in? 
	unsigned int rankA;
	std::string TeamB;
	unsigned int rankB;
	unsigned int finalA; // A final score
	unsigned int finalB; //B final score
	Eventp ev; //pointer to the the first event in the game. namely, first time someone scores
	unsigned int EventNum; //number of events in the game
	std::string notes; //is it the final? any notes on game
	};
	
	



//classes

class WC{

public:
	std::vector<Gamep> GameList; //list of pointers to games that have taken place in the WC, ordered by appearance on wikipedia 
	std::string RN; //Notes on Rank

	WC( std::string); //I should instead use the default constructor, botht of these values are initialized ot zero and should be built upon (don't even need string!)
	// we also need a find game function, given two teams? 
	
	void addGame(Gamep); 
	void FrequencyTable();
	std::vector<Eventp> SortEvents(unsigned int, bool ); 
	
	
	};
	


 
//find a game
//start with the first event
//look in the first event and find score time
// then go to the second event until NULL
// then look at the next game list untill NULL
// then you're done. print each one when uou're done. 
	
typedef class WC *wcp;



//functions

Gamep MGame ( std::string A, std::string B, unsigned int rA, unsigned int rB, unsigned int fA, unsigned int fB, std::string n);

void addEvent( unsigned int Ascore, unsigned int Bscore, unsigned int TimeS, unsigned int TimeE, Gamep g);

int mod(int);

my source file:

#include "FIFA.h"

//implementation files for all FIFA shiat


using namespace std;


int mod(int a) {
	if( a < 0)
		return -a;
	else return a;
	}


void addEvent( unsigned int Ascore, unsigned int Bscore, unsigned int TimeS, unsigned int TimeE, Gamep g) { //new event and current event. adds an event to the long list of events 
     Eventp nwevnt = new Event;
	 
	 nwevnt->scoreA = Ascore;
	nwevnt->scoreB = Bscore;
	nwevnt->STime = TimeS;
	nwevnt->ETime = TimeE;
	nwevnt->thegame = g;
	nwevnt->nextevent = NULL;
	 
	 
	 //now we place the event in the game g
	 
		if((g->ev) == NULL) {
		g->ev = nwevnt;
		++(g->EventNum); 
		}

		else {
       Eventp temp;
	   temp = g->ev;
	   while(temp->nextevent != NULL)
	   temp = temp->nextevent; // find the last event 
       temp->nextevent = nwevnt; 
        ++(g->EventNum);
		}
        
        
     }



	

//Make a game		 
Gamep MGame ( string Aname, string Bname, unsigned int rA, unsigned int rB, unsigned int fA, unsigned int fB, string nts) {
	Gamep tempG = new Game;
	
	
	tempG->TeamA = Aname;
	tempG->rankA = rA;
	tempG->rankB = rB;
	tempG->TeamB = Bname;
	tempG->finalA = fA;
	tempG->finalB = fB;
	tempG->ev = NULL;
	tempG->EventNum = 0;
	tempG->notes = nts;
	
	return tempG;
	}


//member functions

void WC::addGame (Gamep g) { 
	GameList.push_back(g);
	}
	
	WC::WC(std::string n) {
	RN = n;
	}

void WC::FrequencyTable() {

unsigned int Freq[120];
int i;
for(i = 0; i < 120; ++i)
Freq[i] = 0;

Gamep thegame;
Eventp theevent;

i = 0; 

//place values into that array... ++ to every value for every minute an event is scored
//first look through the games GameList
while( i <  GameList.size()) {
thegame = GameList[i]; // while loop over all of the games

theevent = thegame->ev;

while(theevent!= NULL) { //while loop over all of the events in the game, for each event we increment frequency
Freq[(theevent->STime)-1] += 1; //scoring in minute 30 goes to Freq[29] bc we count zero
theevent = theevent->nextevent;

} 

++i;
}

//now we print the table

i = 0;
std::cout << "\n"; 
while( i < 120) {
std::cout << i+1 << ": " << Freq[i] << "\n";
++i;
}


}




vector<Eventp> WC::SortEvents(unsigned int SD, bool b) {//SD - score difference, bool -> true for true 1-0, 2-0, 3-0 leads, F for all else
unsigned int i = 0;
int sd;
vector<Eventp> sortE;
Eventp tempe;


	while( i < GameList.size() ) {
	
	tempe = GameList[i]->ev;	
		
		
		while(tempe != NULL) {
			sd =(tempe->scoreA - tempe->scoreB);
				
			if( b == false)
				sd = mod(sd); //we can do this because team A will always be the first to score
				
			if(sd == SD ) {
				sortE.push_back(tempe); //don't think this will work
				if( b == true)
					break;
				}
				
			tempe = tempe->nextevent;
			}	
			
	++i;
	}
	
	
	return sortE;
	}
	

			
		
	


int main() {
 
 WC WC1930 ("FIFA retrospective ranking");
 
 Gamep FM = MGame("France", "Mexico", 7, 13, 4, 1, "Group 1");
 
 addEvent(1, 0, 19, 40, FM);
 addEvent(2, 0, 40, 43, FM);
 addEvent(3, 0, 43, 70, FM);
 addEvent(3, 1, 70, 87, FM);
 addEvent(4, 1, 87, 90, FM);
 
 WC1930.addGame(FM);

....//ton of addEvent, MGame and addGame calls later....

WC1930.FrequencyTable();

vector<Eventp> SortedEvents;

SortedEvents = WC1930.SortEvents(1, true);

int i, wins=0;
int losses=0;
int ties = 0;
int total;

total = SortedEvents.size();

for(i = 0; i<total; ++i)//this part will surely not work for all cases of sorted events
{
	if(SortedEvents[i]->thegame->finalA > SortedEvents[i]->thegame->finalB ) 
		++wins;
	else if(SortedEvents[i]->thegame->finalA < SortedEvents[i]->thegame->finalB )
		++losses;
	else ++ties; 
	}



cout<< "\n 1-0 EVENT BREAKDOWN   " ;
cout << "\n The number of 1-0 leads leading to wins were:" << wins;
cout <<" \n losses: " << losses;
cout << "\n ties:" << ties;
cout << "\n total games:" << total;


 
 return 0;
 
 }

[rapidcoder]

If the executable file is so huge, it means you probably statically link it to some huge libraries. I'd recommend looking at the config of your compiler.

[coder777]

I'm working on a project that contains about 100.000 (one hundred thousand) lines of code. That results in an executable size of about 4 MB.

So I think it's rather kb what you see in your case.

I'd recommend that you build that structure rathe static const like so:

const Game MGame[] =
{
  {"France", "Mexico", 7, 13, 4, 1, "Group 1"},
  { ... }
};
const Event MEvent[] =
{
  { 1, 0, 19, 40, &MGame[0] },
  { ... }
};

I'd furth recommend that you write a gui program to enter all the data and either having the data separately or so that it can be compiled.

[Gaminic]

It's a bit too much code to look through (and it's probably unrelated to the reason your files are so big, as rapidcoder said), but your typedefs make it very confusing [for outsiders] to see where things are passed by value and where by pointer, as well as tracking memory leeks.

Also, there's a similar topic around that offers some tips/insights:
http://www.cplusplus.com/forum/windows/52960/

[trentkg]

Oops!

I compile remotely on a linux command prompt, but write on a windows text editor. looks like i confused things while using my file transfer software and the executable file is only 123 KB, not MB.

But, now that I have your attention, I'd love some more advice!

~Gaminic

I only have two typdefs -- that Gamep is a pointer to a game and Eventp is a pointer to an event. I'm sorry if that wasn't more clear. Code is meant to be read though (and not just by the person who wrote it!) and I'm all for making good habits so I'll try and correct this.

~coder 777
Declaring my structs as consts seems like a good idea, however after creating each Game I also have to use addEvent to addEvents to it. addEvent goes into the struct game and alters the NULL event pointer to point to another event. I believe this would not work with const, no?

But I am very interested in your suggestion to write a gui to enter all the data. This raises a ton of new questions I have regarding data entry, as well as using multiple sourcer/header files.

First, how do I access objects I've defined in one source file in another?

I know how to combine multiple project files using makefiles and the make command, but as far as I know I can only access functions and types of classes/structs.

Put simply, How do I access the struct Game *MypracticeGame that I have defined in WC1930data.cpp in, say, main.cpp? Or the class WC that I've defined in WC1930data.cpp in main.cpp? THis should be fairly straightforward no?


Next, does anyone have any good resources to point me towards for designing a simple GUI in c++ for data entry? I am also willing to learn C#, since this is sort of a "learning" project and I'm sure they already have classes defined to help me here. Plus, C# is used by a lot of software consulting companies I'm applying for.

. My original idea was just to read everything into the command prompt. You know, something simple like....

string TeamAName;
int AfinalScore;

cout<< "\nHello! Lets make a game. Enter A's Team Name:";
cin << TeamAName;
cout <<"\nNow enter A's final score:";
cin << Afinalscore;

//etc etc until I've entered all variables of interest for this game

PGame = MGame( TeamAName,Afinalscore, ...., ...., .... etc etc);

Two problems I see with this.

One is that If i mess up somewhere, there's not an easy way to go back, at least not like in say, excel, where I can just erase the value in the excel workbook and put in a new one. Though I'm sure I could work around this somehow, this would definitely be easier with a GUI

THe second problem is, once I run the program and enter all of my data, I would have to define all of these games and data in a way that they would continue to exist event after main() returns. I'm assuming I do this by making all of my World cups, games and events static. Then I would have to find a way to access them in another program (which I don't now how to do, as stated earlier).

Anyways, thanks a lot for all of your guys suggestions in helping a newbie out. Much appreciated!

-Trent

[coder777]

Declaring my structs as consts seems like a good idea, however after creating each Game I also have to use addEvent to addEvents to it. addEvent goes into the struct game and alters the NULL event pointer to point to another event. I believe this would not work with const, no?

You can set the pointer on initialization. Since everthing is known at the very start up you can create arrays instead of singly linked list:

struct Game{
	...
	Eventp ev; //pointer to the the first event in the game. namely, first time someone scores
	unsigned int EventNum; //number of events in the game
	..
	};


struct Event {
	...
	// if you acces the event only from the game the following is not needed: 
	// struct Game *thegame; //pointer to a game the Event is in
	// You can make an array so the following is not needed: 
	// struct Event *nextevent; //pointer to next event in line, or null
	
	};

// This is how you can make it const:

const Event EventsForAGame[] =
{
  { 1, 0, 19, 40 }, { 2, 0, 40, 43 }, { ... }
};

//                   TeamA     TeamB     .... ev              EventNum                                          notes
const Game AGame = { "France", "Mexico", ..., EventsForAGame, sizeof(EventsForAGame) / sizeof(*EventsForAGame), ... };

This way you can build the whole structure. I hope you get the float...

First, how do I access objects I've defined in one source file in another?

I know how to combine multiple project files using makefiles and the make command, but as far as I know I can only access functions and types of classes/structs.

Put simply, How do I access the struct Game *MypracticeGame that I have defined in WC1930data.cpp in, say, main.cpp? Or the class WC that I've defined in WC1930data.cpp in main.cpp? THis should be fairly straightforward no?

You simply #include <WC1930data.hpp> (where the definitions reside)

Use an IDE to cope with a project (like code::blocks http://www.codeblocks.org/ which works with windows and linux)

Next, does anyone have any good resources to point me towards for designing a simple GUI in c++ for data entry? I am also willing to learn C#, since this is sort of a "learning" project and I'm sure they already have classes defined to help me here. Plus, C# is used by a lot of software consulting companies I'm applying for.

You need Visual C#. I think the express version is free.

Normally such a task is done with databases. As a beginner it might not that easy

[trentkg]

~Coder777

Thanks a ton for the help. Your suggestions for the structs makes sense, very similar to what I had initially -- there is no need for a struct inside of Game, as I can just make all of the information in Game into an array or a vector.

You simply #include <WC1930data.hpp> (where the definitions reside)

Wow. Thats it? Is there documentation on this somewhere? I can't find anything under #include. I thought about doing this but I thought it would cause some errors to include a cpp source file (I thought only header files were OK). Where would I have even looked this up? and why is the .cpp changed to a .hpp?

A gui would be nice, but hte more I think about it the more I think its going to be a ton of work.

I can think of three other ways.

Idea one: Use the cout and cin of <iostream> to read in values. The problem with this is that I want to save this data and analyze it in different ways at a later time... I don't see a way to save this data after reading it into the command prompt once the program closes. Am I missing something? Either way, even if I read in a bunch of data, that cpp file has a main(), and I can't have another file that analyzes that data with another main().


Idea two: I write a function MWorldCup that takes a comma deliminated text file (or something similar...suggestions?) and returns a WC that is full of games and events. I would do this using one of the stream classes. So now what happens is I have a bunch of CSV files floating around (each one corresponding to a world cup) that I just call on in main whenever I need to access their data. These files will exist forever (unlike if I input the data into the command prompt) and I can access them whenever. Also, even if my function that creates the WC class from this data is messed up, the original data will never be erased or altered in any way. In this version I would still have a bunch of files like 1930WCdata.cpp, but they would just have one function: a call to MWorldcup, that would return a WC, that I would later call in my main() source file.

Idea three: (even kookier) I write a C++ program that writes a C++ program. I read in values for games and events in the command prompt and this program writes the code (using one of the stream files again, this time one that outputs a file) needed to implement these structures in C++. For this I again use the stream classes, only this time my C++ program will create a new file upon execution. This option has the ballar advantage that all of my data is now saved in cpp files, making all of this data much easier to manage...I think?


Anyways, I know option two and three are definitely doable. The question is which one will be easier. Right now I'm leaning on idea 2 being easier, but the problem is that my CSV excel files (or whatever format I figure out is best) will have to have a very set format -- if I deviate from this, mess up and put in an extra space or something, I could run into problems and really screw things up. Maybe it won't be too difficult.

Option three though I think would be much easier once everything is written - I just have to enter the value the command prompt asks me for ("ENTER SCOREA") and hit enter. Literally all of the thinking will be taken out of data entry.

Plus... writing a C++ program that writes C++ code? Even if its very simple code its writing, be honest. Thats way cool.

[coder777]

Wow. Thats it? Is there documentation on this somewhere? I can't find anything under #include. I thought about doing this but I thought it would cause some errors to include a cpp source file (I thought only header files were OK). Where would I have even looked this up? and why is the .cpp changed to a .hpp?

Um, do you understand the difference between source and header file? Yes, you can only include header files (therefore .hpp or if you you will .h)

the precompiler replaces #include <xxx.h> with the content of xxx.h. Therefore you cannot include implementation or source files (the linker will complain about multiple definitions). Ok you can but only once (and then it shouldn't be part of your project)

A gui would be nice, but hte more I think about it the more I think its going to be a ton of work.

There're free gui libraries like QT or wxWidget and Visual C# (which uses .Net). All of them come with a designer (where you can arrange the items and create the functions to deal with them).

The Gui is just for the convenience. The output is another subject. Unfortunately today as a programmer you need that knowledge in many (if not most) cases.

Plus... writing a C++ program that writes C++ code?

Yes that's ok. Those gui designers do that too


EDIT:

Put simply, How do I access the struct Game *MypracticeGame that I have defined in WC1930data.cpp in, say, main.cpp?

Write a header that has a line like extern Game *MypracticeGame; (you need to include the header where 'Game' is declared) and then you can access 'MypracticeGame' when you include that header. I hope that's clear now?

EDIT2: if your variable is const it can be completely within the header file otherwise it must be separated in header and source

[ne555]

This ain't java.
¿why are you using new?

I don't see the use of a gui here. Just work with streams.

I write a function MWorldCup that takes a comma deliminated text file (or something similar...suggestions?)

xml, check out boost::serialization

but the problem is that my CSV excel files (or whatever format I figure out is best) will have to have a very set format -- if I deviate from this, mess up and put in an extra space or something, I could run into problems and really screw things up

That is not a problem but a feature. Besides, spaces are usually ignored.

(metaprogramming) This option has the ballar advantage that all of my data is now saved in cpp files

Don't do that. Your program will lose generallity.

[Gaminic]

CSV parsing is very easy. As long as your table is regular (every row has the same size, every column has the same size), translating CSVs to a table won't be a problem.