Compiling and efficiency problems

[aarelovich]

Hi:

I need to write a program that essentially needs to mane a list of a list of a list (that's right 3 times) of a certain class I created. I was having some efficiency problems so I decided to change all of the accesses to the structure form structure[i][j][k] to using the .at() function. I wrote a little code just to test this:

This is the Class named Tile.h


class Tile
{
public:
Tile(qreal p, QList<quint16>);
Tile();

//Definition of basic operations
bool operator == (Tile t);

//Definition of sets and getters.
QList<quint16> Indexes(){return indexes;}
qreal param(){return parameter;}
void setParam(qreal p){parameter = p;}
void setIndexes(QList<quint16> ind){indexes = ind;}

//Function use Mainly for Debugging
QString toString();

virtual ~Tile();

private:
qreal parameter;
QList<quint16> indexes;
};


And the Tile.cpp


Tile::Tile(qreal p, QList<quint16> ind){
indexes = ind;
parameter = p;
elegibility = 0;
}

Tile::Tile(){
parameter = 0;
}

/****************Operators************************* */
bool Tile::operator == (Tile t){
QList<quint16> comp = t.Indexes();
bool res = true;
for (int i = 0; i < comp.size(); i++){
if (comp.at(i) != indexes.at(i)){
res = false;
break;
}
}
return res;
}

/***********toString******************/
QString Tile::toString(){
QString ws = "";
for (int i = 0; i < indexes.size(); i++){
ws = ws + " " + QString::number(indexes.at(i));
}

if(indexes.size() == 0){
ws = "Nothing to show: Value is: " + QString::number(parameter);
}

return ws;
}

Tile::~Tile(){
}


Then I wrote this code in a constructor just to test using this



int Im = 5;
int Jm = 10;
int Km = 6000;
for (int i = 0; i < Im; i++){
QVector < QVector<Tile> > temp2;
for(int j = 0; j < Jm; j++){
QVector<Tile> temp;
for (int k = 0; k < Km; k++){
QList<quint16> ind;
ind << k;
Tile t(0,ind);
temp << t;
}
temp2 << temp;
}
test << temp2;
}


Where test is defined by:


QVector < QVector< QVector<Tile> > > test;


So then I write this line in a button action just to see if it would compile


test.at(2).at(5).at(3940).setParam(test.at(2).at(5 ).at(3940).param() + 15.0);


And it doesn't and I get these two errors
passing ‘const Tile’ as ‘this’ argument of ‘qreal Tile::param()’ discards qualifiers
passing ‘const Tile’ as ‘this’ argument of ‘void Tile::setParam(qreal)’ discards qualifiers

So I change it to this in order for it to work


test[2][5][3940].setParam(test[2][5][3940].param() + 15.0);


And this works but according to the Qt documentation [] is a lot more inefficient that at(). So I want it to change it to see if my algorithm would go a bit faster.

So my question is are there any suggestion on how to make this a bit more efficient to see if I can shave off some minutes to the my algortihms runs or am I just stuck with the slow program. Or maybe on how could I manage a list of a list of a list of classes in a more efficient way.

Thanks for any help

[wysota]

And this works but according to the Qt documentation [] is a lot more inefficient that at(). So I want it to change it to see if my algorithm would go a bit faster.
[] is defined as:

template <typename T>
inline const T &QVector<T>::operator[](int i) const
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
return p->array[i]; }
template <typename T>
inline T &QVector<T>::operator[](int i)
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
return data()[i]; }

and at() defined as:

template <typename T>
inline const T &QVector<T>::at(int i) const
{ Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
return p->array[i]; }

You can see they are identical. Only the non-const version of [] is slower but that is obvious as data may need to be copied (which is what data() does).



So my question is are there any suggestion on how to make this a bit more efficient to see if I can shave off some minutes to the my algortihms runs or am I just stuck with the slow program. Or maybe on how could I manage a list of a list of a list of classes in a more efficient way.

I suggest you use some faster structure than a list. What does your list represent? Can't you use a has instead?

[aarelovich]

I'm sorry I don't know what a "has" is.

I'll try to explain as abstractly as possible what my structure represents.
The thing is that I need to partition the n dimensions of a user specified space each into p partitions, each value of p different for each of the n dimensions. So say that I have 3 dimensions and each dimension (representing a variable in a certain user defined range, -10 to 10, -5 to 5 and -6 to 6) is parted into say 5 6 and 7, I would have partition the entire space into 5*6*7 = 210 partitions of the space (represented by what I call a tile, so 210 tiles). These need to be copied another d times (each offseted a little differently so that the same 3 D value doesn't necessarily fall in the same tile for all of the d copies) in order to create the full structure. And I need A copies of this structure, again according to user input.

Now the problem becomes how I use it. Say I get the 3 dimension value -3.4, 2, 5.6. This falls within one and only one of the limits of the 210 tiles for each of the d structures. I need to find it in each (that why I redifined the == method in Tile so as to use the indexOf() function of the QVector). And do some operation to the value (param) of that particular tile.

It's complex but that is what I need to do. Can that "has" help? I'm sorry if it sounds complicated, it really is

Thanks for any help.

[wysota]

I'm sorry I don't know what a "has" is.
Sorry :) I typed too fast, it should say "hash".

In my opinion you should have a hash indexed by three (or "n" to follow your abstract example) real values which would allow you to quickly navigate through your data.


struct HashKey {
HashKey(double _one, double _two, double_three){ one = _one; two = _two; three = _three; }
double one;
double two;
double three;
bool operator==(const HashKey &other) const {
return ((one==other.one) && (two==other.two) && (three==other.three));
}
};

uint qHash(const HashKey &key) { return qHash( qHash(key.one)+qHash(key.two)+qHash(key.three)); }
//...
QHash<HashKey, Tile> data;

data[HashKey(-3.4, 2, 5.6)] = Tile(...);

Note that knowing the index (key), retrieving a value from the vector is faster (O(1)) than retrieving a value from a hash (amortized O(lg(n))). But on the other hand you waste lot of time iterating over a sparse vector. For instance your comparison operator is awfully slow, there are ways to significantly speed it up (for instance calculating hashes of vectors and comparing the hashes instead of vectors themselves).

[aarelovich]

Hi. Okay. I'll read a bit about hashes and I'll try implementing what you've suggested as soon as I get a moment

Thanks

[aarelovich]

Hi:

So I've been thinking a lot about your suggestions and there are a couple of problems.
The first is that the state (the collection of variable values) (say (3.5, 1, -2)) has a tile with a correspoding index partition, say (1,2,3), in one of the d copies (called tilings) of the structure I mentioned and will have indexes (2,2,3) in another of the d copies because (as I tried to explain) each of the d copies has a random offset in each dimension (in this case 3) that causes the index 0,0,0 to correspond to different state values. So I have to, no matter what calculate the index of the corresponding tile of each of the tilings. But I could use the indexes like you mentioned to create the hashes out of a QList<int> indexes variable. So I slightly adapted the code you gave me to this on tiletests.h (I assumed you mistyped and my function had to have a different name that qHash)


uint Hash(QList<int> ind) { return qHash( qHash(ind.at(0))+qHash(ind.at(1))+qHash(ind.at(2)) ); } // The real code would have for cycle that addeded up as many elements as there were on the list.


Then I ran a test with this code


QList<int> ind;
ind << 1 << 2 << 3;
qDebug() << "1 >> :" << Hash(ind);
ind.clear();
ind << 5 << 6 << 7;
qDebug() << "2 >> :" << Hash(ind);
ind.clear();
ind << 3 << 2 << 1;
qDebug() << "3 >> :" << Hash(ind);


The result as I expected was this:
1 >> : 6
2 >> : 18
3 >> : 6

Which means I can't used the code exactly like this because the set of indexes 1,2,3 and 3,2,1 clearly point to a different tile.

So I came up with this idea: I would like to use a QString as a key so that (1,2,3) becomes "1,2,3" and (3,2,1) becomes "3,2,1" which would mean each key would be different. I'm going to do the tests anyways, but I would like to hear your ideas on well, my idea.

Thanks for all the help.

[wysota]

I assumed you mistyped and my function had to have a different name that qHash
No, I didn't. The function has to be called qHash and take a const reference to your key class.

[ktk]

If you care about speed you should also look at passing parameters as const reference instead of value. saves a copy, even if it is a shallow one with shared containers...

Here:



class Tile
{
public:
Tile(qreal p, QList<quint16>); // Here
...
bool operator == (Tile t); // Here, also make it const
...
QList<quint16> Indexes(){return indexes;} // make function const
qreal param(){return parameter;} // same
void setParam(qreal p){parameter = p;}
void setIndexes(QList<quint16> ind){indexes = ind;} // const ref
...
virtual ~Tile(); // will you ever derive from Tile?
...
QString ws = ""; // = "" not needed.

if(indexes.size() == 0){ // .isEmpty()
...


Now,



passing ‘const Tile’ as ‘this’ argument of ‘qreal Tile::param()’ discards qualifiers
passing ‘const Tile’ as ‘this’ argument of ‘void Tile::setParam(qreal)’ discards qualifiers


... that's the consequence of the missing 'const' qualification of your getters.
Make them const, and it will work.


Sorry :) I typed too fast, it should say "hash".

In my opinion you should have a hash indexed by three (or "n" to follow your abstract example) real values which would allow you to quickly navigate through your data.


struct HashKey {
HashKey(double _one, double _two, double_three){ one = _one; two = _two; three = _three; }
double one;
double two;
double three;
bool operator==(const HashKey &other) const {
return ((one==other.one) && (two==other.two) && (three==other.three));
}
};

uint qHash(const HashKey &key) { return qHash( qHash(key.one)+qHash(key.two)+qHash(key.three)); }
//...
QHash<HashKey, Tile> data;

data[HashKey(-3.4, 2, 5.6)] = Tile(...);

Note that knowing the index (key), retrieving a value from the vector is faster (O(1)) than retrieving a value from a hash (amortized O(lg(n))). But on the other hand you waste lot of time iterating over a sparse vector. For instance your comparison operator is awfully slow, there are ways to significantly speed it up (for instance calculating hashes of vectors and comparing the hashes instead of vectors themselves).

A hash is not "amortized O(lg(n))", it is has worst case O(n), and all depends on the hash function...

[aarelovich]

Hi:

Well, if you didn't mistype I'm sure I understand how I should use the hash.

However I did try to test the difference in performance between a hash and my old approach and I've got very dissapointing results:
This is my constructor:


int Im = 5;
int Jm = 10;
int Km = 36864;
Actions = Im;
NumTiles = Km;
TilesInTiling = Jm*Km;
NumTilings = Jm;
QVector<quint16> Mod;
QVector<quint16> ind(6);
ind.fill(0);

//Six dimensions with divisions 12 12 4 4 4 4
Base << 1 << 12 << 144 << 576 << 2304 << 9216;
Mod << 12 << 12 << 4 << 4 << 4 << 4;

start = QTime::currentTime();

for (int i = 0; i < Im; i++){
for(int j = 0; j < Jm; j++){
for (int k = 0; k < Km; k++){
Tile t;
t.setParam(k);
test[HashKey(ind,i,j)] = t;
ind = IncMod(ind,Mod);
}
}
}

qDebug() << "The size is" << test.count() << "and it took" << start.msecsTo(QTime::currentTime()) << "ms";

ind.fill(0);
start = QTime::currentTime();
for (int i = 0; i < Im; i++){
QVector <QVector <Tile> > temp1;
for(int j = 0; j < Jm; j++){
QVector<Tile> temp2;
for (int k = 0; k < Km; k++){
Tile t;
t.setParam(k);
t.setIndexes(ind.toList());
temp2 << t;
ind = IncMod(ind,Mod);
}
temp1 << temp2;
}
testvec << temp1;
}
qDebug() << "The size is" << testvec.size() << "and it took" << start.msecsTo(QTime::currentTime()) << "ms";



Then what I did is write a test code with the exact same calculations the real program would have to do except I used fantasy-on-the-fly-made-up numbers instead of real program values.

This is the code that was supposed to test the hash:


//Simulation of Eval and Deriv
qreal sum = 0;
QVector<uint> hashes;
for (int act = 0; act < Actions; act++){
sum = 0;
hashes.clear();
for (int tiling = 0; tiling < NumTilings; tiling++){
QVector<quint16> ind;
ind << 8 << 6 << 3 << 3 << 0 << 1;
hashes << HashKey(ind,act,tiling);
}
for (int i = 0; i < NumTilings; i++){
Tile t;
t = test.value(hashes.at(i));
sum = sum + t.getParam();
}
//qDebug() << "Suma: " << sum;
}

//Simulation of Update.
QHashIterator<uint, Tile> iter(test);
while (iter.hasNext()) {
iter.next();
uint key = iter.key();
Tile t;
//qDebug() << "Pruebo con llave" << key;
t = test.take(key);
//qDebug() << "Anduvo";
t.DecayTraces(0.7,.8);
if (hashes.contains(key)){
t.IncrementEtrace();
t.setParam(t.getParam() + 0.8*0.6*t.Elegibility());
}
test[key]=t;
}


And the code as it is right now for the vector structure:


//Simulation of eval and deriv
qreal sum = 0;
QVector<Tile> tiles;
QVector<quint16> visited_indexes;
for (int act = 0; act < Actions; act++){
sum = 0;
tiles.clear();
for (int tiling = 0; tiling < NumTilings; tiling++){
QVector<quint16> ind;
ind << 8 << 6 << 3 << 3 << 0 << 1; //In the real program these come from another function.
Tile t(0,ind.toList());
tiles << t;
}
int action = 3; //This would also come from somewhere else;
for (int i = 0; i < NumTilings; i++){
int index = testvec[action][i].indexOf(tiles.at(i));
sum = sum + testvec[action][i][index].getParam();
}
//qDebug() << "Sum: " << sum;
}


//Simulation of Upadate
bool InTakenAction = false;
int action = 2;
QVector<int> index_list;
index_list << 1 << 2 << 3 << 4 << 5 << 6 << 7 << 8 << 9 << 10;
int temp_index;
for (int i = 0; i < Actions; i++){
for (int j = 0; j < NumTilings; j++){
if (i == action){
temp_index = index_list.at(j);
InTakenAction = true;
}
else
InTakenAction = false;
for (quint16 k = 0; k < NumTiles; k++){
testvec[i][j][k].DecayTraces(0.7,0.8);
if (InTakenAction && (k == temp_index)){
testvec[i][j][k].IncrementEtrace();
testvec[i][j][k] = testvec[i][j][k] + 0.8*0.6*testvec[i][j][k].Elegibility();
}
}
}
}


I called each test 10 times and measured the time with QTime like in the constructor. These were the results I got:
The size is 1843200 and it took 2290 ms
The size is 5 and it took 4425 ms
Total Time for Test Hash 21711 ms
Total Time for Test QVector 2889 ms

My old method is far better, which leads me to believe that I have done something wrong. I think that the problem is the fact That I have to take and then insert each tile in the QHash in order to modify it.

I really hope that someone can give me an idea of what I'm doing wrong.

[aarelovich]

Ktk
I saw your replies as soon as I finished my new post. I'll look into what you are saying.

Thanks.

[wysota]

A hash is not "amortized O(lg(n))", it is has worst case O(n), and all depends on the hash function...

My bad, it's amortized O(1). Old habits cause interference...


My old method is far better, which leads me to believe that I have done something wrong.

If you are iterating over all items at once then QHash will always be slower than QVector. It's the lookup that makes hashes fast - if you don't know the index in the container but know what item (key) you are looking for.

[aarelovich]

You are absolutely right.
I realized that I could "fuse" both solutions. If I can calculate an absolute index I could collapse the three QVectors into one and calculate the index and access it directly saving the time to look for it. Maybe with that and the const ideas from ktk I'll be able to save some time. I'll try it and post back.

Thanks for all the help.

[aarelovich]

Hi:

Well that did the trick. I used only One very large qvector and do a simple math calculation given a series of indexes in order to calculate (instead of search) for the position in the vector. The results after I did 20 tryouts (like the one described in the code above) was the following
The old way: 5802 ms
The new way: 1682 ms which is roughly 28% of the normal time. I'll make the modifications (which are mostly simplifactions) to the old code now that I'm convinced it'll make a difference.

Thanks for all the help.