# Optimizing my code that simulates a database

Some days ago I made you a question and I got some really useful answers. I will make a summary to those of you who didn't read and I will explain my new doubts and where I have problems now.

Explanation

I have been working on a program, simulating a small database, that first of all read information from txt files and store them in the computer memory and then, I can make queries taking normal tables and/or transposed tables. The problem is that the performance is not good enough yet. It works slower than what I expect. I have improved it but I think I should improve it more. I have specific points where my program doesn't have a good performance.

Current problem

The first problem that I have now (where my program is slower) is that I spend more time to, for example table with 100,000 columns & 100 rows (0.325 min, I've improved this thanks to your help) than 100,000 rows & 100 columns (1.61198 min, the same than before). But on the other hand, access time to some data is better in the second case (in a determined example, 47 seconds vs. 6079 seconds in the first case) any idea why??

Explanation

Now let me remind you how my code works (with an atached summary of my code)

First of all I have a .txt file simulating a database table with random strings separated with "|". Here you have an example of table (with 7 rows and 5 columns). I also have the transposed table

NormalTable.txt

42sKuG^uM|24465\lHXP|2996fQo\kN|293cvByiV|14772cjZSN|
28704HxDYjzC|6869xXj\nIe|27530EymcTU|9041ByZM]I|24371fZKbNk|
24085cLKeIW|16945TuuU\Nc|16542M[Uz\|13978qMdbyF|6271ait^h|
13291_rBZS|4032aFqa|13967r^\\T|27754k]dOTdh|24947]v_uzg|
1656nn_FQf|4042OAegZq|24022nIGz|4735Syi]\|18128klBfynQ|
6618t\SjC|20601S\EEp|11009FqZN|20486rYVPR|7449SqGC|
14799yNvcl|23623MTetGw|6192n]YU\Qe|20329QzNZO_|23845byiP|


TransposedTable.txt (This is new from the previous post)

42sKuG^uM|28704HxDYjzC|24085cLKeIW|13291_rBZS|1656nn_FQf|6618t\SjC|14799yNvcl|
24465\lHXP|6869xXj\nIe|16945TuuU\Nc|4032aFqa|4042OAegZq|20601S\EEp|23623MTetGw|
2996fQo\kN|27530EymcTU|16542M[Uz\|13967r^\\T|24022nIGz|11009FqZN|6192n]YU\Qe|
293cvByiV|9041ByZM]I|13978qMdbyF|27754k]dOTdh|4735Syi]\|20486rYVPR|20329QzNZO_|
14772cjZSN|24371fZKbNk|6271ait^h|24947]v_uzg|18128klBfynQ|7449SqGC|23845byiP|


Explanation

This information in a .txt file is read by my program and stored in the computer memory. Then, when making queries, I will access to this information stored in the computer memory. Loading the data in the computer memory can be a slow process, but accessing to the data later will be faster, what really matters me.

Here you have the part of the code that read this information from a file and store in the computer.

Code that reads data from the Table.txt file and store it in the computer memory

int h;
do
{
cout<< "Do you want to query the normal table or the transposed table? (1- Normal table/ 2- Transposed table):" ;
cin>>h;
}while(h!=1 && h!=2);

string ruta_base("C:\\Users\\Raul Velez\\Desktop\\Tables\\");
if(h==1)
{
ruta_base +="NormalTable.txt"; // Folder where my "Table.txt" is found
}

if(h==2)
{
ruta_base +="TransposedTable.txt";
}

string temp; // Variable where every row from the Table.txt file will be firstly stored
vector<string> buffer; // Variable where every different row will be stored after separating the different elements by tokens.
vector<ElementSet> RowsCols; // Variable with a class that I have created, that simulated a vector and every vector element is a row of my table

ifstream ifs(ruta_base.c_str());
while(getline( ifs, temp )) // We will read and store line per line until the end of the ".txt" file.
{
size_t tokenPosition = temp.find("|"); // When we find the simbol "|" we will identify different element. So we separate the string temp into tokens that will be stored in vector<string> buffer
// --- NEW PART ------------------------------------
const char* p = temp.c_str();
char* p1 = strdup(p);

char* pch = strtok(p1, "|");
while(pch)
{
buffer.push_back(string(pch));
pch = strtok(NULL,"|");
}
free(p1);

ElementSet sss(0,buffer);
buffer.clear();
RowsCols.push_back(sss); // We store all the elements of every row (stores as vector<string> buffer) in a different position in "RowsCols"
// --- NEW PART END ------------------------------------
}

Table TablesStorage(RowsCols); // After every loop we will store the information about every .txt file in the vector<Table> TablesDescriptor
vector<Table> TablesDescriptor;
TablesDescriptor.push_back(TablesStorage); // In the vector<Table> TablesDescriptor will be stores all the different tables with all its information

DataBase database(1, TablesDescriptor);


Information already given in the previous post

After this, comes the access to the information part. Let's suppose that I want to make a query, and I ask for input. Let's say that my query is row "n", and also the consecutive tuples "numTuples", and the columns "y". (We must say that the number of columns is defined by a decimal number "y", that will be transformed into binary and will show us the columns to be queried, for example, if I ask for columns 54 (00110110 in binary) I will ask for columns 2, 3, 5 and 6). Then I access to the computer memory to the required information and store it in a vector shownVector. Here I show you the part of this code.

Problem In the loop if(h == 2) where data from the transposed tables are accessed, performance is poorer ¿why?

int n, numTuples;
unsigned long long int y;

cout<< "Write the ID of the row you want to get more information: " ;
cin>>n; // We get the row to be represented -> "n"

cout<< "Write the number of followed tuples to be queried: " ;
cin>>numTuples; // We get the number of followed tuples to be queried-> "numTuples"

cout<<"Write the ID of the 'columns' you want to get more information: ";
cin>>y; // We get the "columns" to be represented ' "y"

unsigned int r; // Auxiliar variable for the columns path
int t=0; // Auxiliar variable for the tuples path
int idTable;

vector<int> columnsToBeQueried; // Here we will store the columns to be queried get from the bitset<500> binarynumber, after comparing with a mask
vector<string> shownVector; // Vector to store the final information from the query

clock_t t1, t2;
t1=clock(); // Start of the query time

bitset<5000> binaryNumber = Utilities().getDecToBin(y); // We get the columns -> change number from decimal to binary. Max number of columns: 5000

// We see which columns will be queried
for(r=0;r<binaryNumber.size();r++) //
{
if(binaryNumber.test(r) & mask.test(r))  // if both of them are bit "1"
{
columnsToBeQueried.push_back(r);
}
}

do
{
for(int z=0;z<columnsToBeQueried.size();z++)
{
ElementSet selectedElementSet;
int i;
i=columnsToBeQueried.at(z);
Table& selectedTable = database.getPointer().at(0); // It simmulates a vector with pointers to different tables that compose the database, but our example database only have one table, so don't worry ElementSet selectedElementSet;
if(h == 1)
{

selectedElementSet=selectedTable.getRowsCols().at(n);
shownVector.push_back(selectedElementSet.getElements().at(i)); // We save in the vector shownVector the element "i" of the row "n"
}

if(h == 2)
{
selectedElementSet=selectedTable.getRowsCols().at(i);
shownVector.push_back(selectedElementSet.getElements().at(n)); // We save in the vector shownVector the element "n" of the row "i"
}
n=n+1;
t++;
}
}while(t<numTuples);

t2=clock(); // End of the query time
showVector().finalVector(shownVector);
float diff ((float)t2-(float)t1);
float microseconds = diff / CLOCKS_PER_SEC*1000000;
cout<<"Time: "<<microseconds<<endl;


Class definitions

Here I attached some of the class definitions so that you can compile the code, and understand better how it works:

class ElementSet
{
private:
int id;
vector<string> elements;

public:
ElementSet();
ElementSet(int, vector<string>);

const int& getId();
void setId(int);

const vector<string>& getElements();
void setElements(vector<string>);

};

class Table
{
private:
vector<ElementSet> RowsCols;

public:
Table();
Table(vector<ElementSet>);

const vector<ElementSet>& getRowsCols();
void setRowsCols(vector<ElementSet>);
};

class DataBase
{
private:
int id;
vector<Table> pointer;

public:
DataBase();
DataBase(int, vector<Table>);

const int& getId();
void setId(int);

const vector<Table>& getPointer();
void setPointer(vector<Table>);

};

class Utilities
{
public:
Utilities();
static bitset<500> getDecToBin(unsigned long long int);
};


Summary of my problems

• Why the load of the data is different depending on the table format???
• Why the access to the information also depends on the table (and the performance is in the opposite way than the table data load?
-
It does not sound like a codereview question. –  bcsanches Apr 7 '11 at 12:23

If you want to optimize your code, I would first suggest you to profile your code (some for windows can be found here : http://stackoverflow.com/questions/67554/whats-the-best-free-c-profiler-for-windows-if-there-are).

Programmer are usualy very poor at finding bottleneck in code and profiler will help you to find where 20% of your code run 80% of the time.

Then with thoses information, we will be able to give you a better kind of help.

-

Do you really ask why transpose table operation takes different time or do you ask for improving performance?

Both questions are related in this case and i'll try to answer them.

Consider this:

selectedElementSet=selectedTable.getRowsCols().at(n);


What is going on under the cover? The vector is copied. That means all strings in vector are copied. In transposed table there 100 000 strings and in normal one there is 100. What to do to improve perfomance?

const ElementSet&  selectedElementSet=selectedTable.getRowsCols().at(n);


As simple as that. No more copies.

After making this change i highly recommend to read more on C++ and stl library. You'll better understand how it works and would be able to eliminate more "under the cover" problems with your code.

And, of course, profiler is your best friend with performance issues.

-

First of all before optimization you must to correct some lines such as:

for(int z=0;z<columnsToBeQueried.size();z++)


You must write something as:

/*int size = columnsToBeQueried.size();
for(int z=0;z<size;z++)*/


because as I think that is count every time the size of the columnsToBeQueried and the same

binaryNumber.size()

-