does a Qt application run faster on a windows 64 bit machine?

[pkohut]

Just did the Kd-tree tests using a dataset of 1,000,000 points. The FindNearest routine is the most heavily used routine in the app. Because of L1 and L2 cache misses preloading the left or right node (leaf) is worse than than using if-then-else-then case. Since I brought it up before figured better show results (preloading works in some conditions, measurements have to be done though to weed out adverse changes)
edit: the tests were performed on already highly optimized code. This thread http://www.theswamp.org/index.php?to...0856#msg400856 and the one after talk in detail about the changes made a few months back which resulted in an 18% speed boost.

The test code connects all points within R(ange) of each other.

31.81126 seconds for query range of 1000, of 1,000,000 points

pNode1 = pNode->left;
if(dx > 0.0)
    pNode1 = pnode->right;

pNode1 = pNode->left;
if(dx > 0.0)
    pNode1 = pnode->right;

To copy to clipboard, switch view to plain text mode 

31.53121 seconds for query range of 1000, of 1,000,000 points

if(dx > 0.0)
   pNode1 = pNode->right;
else
   pNode1 = pNode->left;

if(dx > 0.0)
   pNode1 = pNode->right;
else
   pNode1 = pNode->left;

To copy to clipboard, switch view to plain text mode 

Current code optimization, eliminate the if statement.
30.50571 seconds for query range of 1000, of 1,000,000 points

int bDxGreaterThanZero = dx > 0.0;
KDNODE<T, DIM> * pNode1 = (KDNODE<T, DIM> *) ((sizeof_t*)&pNode->left)[bDxGreaterThanZero];

int bDxGreaterThanZero = dx > 0.0;
KDNODE<T, DIM> * pNode1 = (KDNODE<T, DIM> *) ((sizeof_t*)&pNode->left)[bDxGreaterThanZero];

To copy to clipboard, switch view to plain text mode 

This works because the left and right nodes are purposely paired next to each other in the KDNODE structure.

Hard to say. Most compilers perform short-circuit evaluation of such constructs; as soon as any evaluation fails the body of the loop is skipped, so putting your least likely cases first can often yield a big payoff.

From the latest divide and conquer code of that swamp thread,

if(	fabs(pts[high].x - pts[low].x) <= distance &&
        fabs(pts[high].y - pts[low].y) <= distance &&
        pts[low].distanceTo(pts[high]) <= distance) {

if(	fabs(pts[high].x - pts[low].x) <= distance &&
        fabs(pts[high].y - pts[low].y) <= distance &&
        pts[low].distanceTo(pts[high]) <= distance) {

To copy to clipboard, switch view to plain text mode 

is slower than

if(	(fabs(pts[high].x - pts[low].x) <= distance) &
        (fabs(pts[high].y - pts[low].y) <= distance) &&
        pts[low].distanceTo(pts[high]) <= distance) {

if(	(fabs(pts[high].x - pts[low].x) <= distance) &
        (fabs(pts[high].y - pts[low].y) <= distance) &&
        pts[low].distanceTo(pts[high]) <= distance) {

To copy to clipboard, switch view to plain text mode 

The above changes to the code shaved 3.5% off the previous runtime.
http://www.theswamp.org/index.php?to...0856#msg400856
p.s. the thread after talks about preloading in detail. There I describe the reduced run time results from preloading.

[wysota]

Simple probabilities will give a good idea of what to expect, but branch prediction penalties between machine architecture are not equal or weighted the same. Measurements must be done.

What I meant doesn't require branch prediction. Handling division by zero is an uncommon case as it is very uncommon to find any useful algorithm that in most cases causes a division by zero so the pure algorithm analysis should determine that it is a rare case (or not).

True enough, however this requires a complete rewrite of the code and data structures which might be beyond the abilities of the OP.

Still the extra speed is worth considering such an approach. And even if not, it's a good guess (I haven't seen the exact code so that's just a guess) some parts of the current structure of the algorithm can be paralellized (e.g. by using QtConcurrent) especially if the calculations are iteration based.

Hard to say. Most compilers perform short-circuit evaluation of such constructs; as soon as any evaluation fails the body of the loop is skipped, so putting your least likely cases first can often yield a big payoff.

"Most compilers" or "all compilers"? Isnt't this part of the standard that the very first failed component stops the evaluation of the whole condition? The same way as with OR. If only "most" compilers optimized it, code would not be deterministic.

[qt_gotcha]

dear all, thanks alot for all your answers and even helping me with my code. I'll implement some of your advises and start some testing

[qt_gotcha]

if you are still following this, by far the most operations are of the kind:
for r = 0 to nrrows
for c = 0 to nrcols
do somthing

are tghese for loops expnsive and can it be done more efficient?
thanks

edit: I see there is tons of this on the internet, I''ll start reading...

[pkohut]

if you are still following this, by far the most operations are of the kind:
for r = 0 to nrrows
for c = 0 to nrcols
do somthing

are tghese for loops expnsive and can it be done more efficient?
thanks

edit: I see there is tons of this on the internet, I''ll start reading...

>>snippet from previous message
This type of models typically simulate the water balance for gridded maps of 500x500 cells and use some 400 steps to do that<<

It's the work done in the loops that can get expensive, with the possibilibty of each of the 400 steps processed serially. Without changing the core of your the application, apply const to all the variables that should be/are constant, especially inside those loops.

How long does it take to process a typical model?

[pkohut]

In the code you have these macros defined

#define Drc     Data[r][c]
#define DrcOutlet     Data[r_outlet][c_outlet]
#define MV(r,c) IS_MV_REAL4(&Mask->Data[r][c])
#define FOR_ROW_COL_MV for (int r = 0; r < nrRows; r++)\
		for (int c = 0; c < nrCols; c++)\
		if(!IS_MV_REAL4(&Mask->Data[r][c]))
 
#define FOR_ROW_COL_MV_CH for (int  r = 0; r < nrRows; r++)\
		for (int  c = 0; c < nrCols; c++)\
		if(!IS_MV_REAL4(& ChannelMask->Data[r][c]))

#define Drc     Data[r][c]
#define DrcOutlet     Data[r_outlet][c_outlet]
#define MV(r,c) IS_MV_REAL4(&Mask->Data[r][c])
#define FOR_ROW_COL_MV for (int r = 0; r < nrRows; r++)\
		for (int c = 0; c < nrCols; c++)\
		if(!IS_MV_REAL4(&Mask->Data[r][c]))

#define FOR_ROW_COL_MV_CH for (int  r = 0; r < nrRows; r++)\
		for (int  c = 0; c < nrCols; c++)\
		if(!IS_MV_REAL4(& ChannelMask->Data[r][c]))

To copy to clipboard, switch view to plain text mode 

Normally, not a big fan of macros, but in this circumstance they work well.

With the exception of any code that relies on variables r and c directly (looked like only a few), the macros can be changed and loops simplified (flattened). How much of a speed up is unknown. I'd change a few functions and benchmark to see if the effort is worth it.

// return the row and col index, computed from input idx and nCols
void RowColFromIndex(int & row, int & col, int idx, int nCols)
{
    row = idx / nCols;
    col = idx % nCols;
}
 
// return the flat index computed from inputs row, col, nCols
int IndexFromRowCol(int row, int col, int nCols)
{
    return row * nCols + col;
}
 
#define DrcIdx     Data[rIdx][cIdx]
#define FOR_ROW_COL_MV for (int idx = 0; idx < nrRows * nrCols; ++idx)\
		int rIdx, cIdx; \
		RowColFromIndex(rIdx, cIdx, idx, nrCols); \
		if(!IS_MV_REAL4(&Mask->Data[rIdx][cIdx]))
 
#define FOR_ROW_COL_MV_CH for (int  idx = 0; idx < nrRows * nrCols; ++idx)\
		int rIdx, cIdx; \
		RowColFromIndex(rIdx, cIdx, idx, nrCols); \
		if(!IS_MV_REAL4(& ChannelMask->Data[rIdx][cIdx]))

// return the row and col index, computed from input idx and nCols
void RowColFromIndex(int & row, int & col, int idx, int nCols)
{
    row = idx / nCols;
    col = idx % nCols;
}

// return the flat index computed from inputs row, col, nCols
int IndexFromRowCol(int row, int col, int nCols)
{
    return row * nCols + col;
}

#define DrcIdx     Data[rIdx][cIdx]
#define FOR_ROW_COL_MV for (int idx = 0; idx < nrRows * nrCols; ++idx)\
		int rIdx, cIdx; \
		RowColFromIndex(rIdx, cIdx, idx, nrCols); \
		if(!IS_MV_REAL4(&Mask->Data[rIdx][cIdx]))

#define FOR_ROW_COL_MV_CH for (int  idx = 0; idx < nrRows * nrCols; ++idx)\
		int rIdx, cIdx; \
		RowColFromIndex(rIdx, cIdx, idx, nrCols); \
		if(!IS_MV_REAL4(& ChannelMask->Data[rIdx][cIdx]))

To copy to clipboard, switch view to plain text mode 

So, basically anywhere variable r and c are used need to be changed to rIdx and cIdx (using rIdx and cIdx helps find errors while porting).

[wysota]

All those loops can be easy paralellized. These that don't depend on the order of calculations can be done with QtConcurrent or with a simple OpenCL kernel. Those that depend on the order of execution are a bit more tricky but I'm sure they can be sped up as well. If you use OpenCL you can get a speed-up in the magnitude of 10-50x. With QtConcurrent the speed-up depends on the number of cpu cores (so it's probably around 2-4x max). There is also a possibility to use SIMD optimizations available in your CPU such as SSE.

[pkohut]

All those loops can be easy paralellized. These that don't depend on the order of calculations can be done with QtConcurrent or with a simple OpenCL kernel. Those that depend on the order of execution are a bit more tricky but I'm sure they can be sped up as well. If you use OpenCL you can get a speed-up in the magnitude of 10-50x. With QtConcurrent the speed-up depends on the number of cpu cores (so it's probably around 2-4x max). There is also a possibility to use SIMD optimizations available in your CPU such as SSE.

While technically true, there is no free lunch. "easy paralellized" "simple OpenCl kernel", again are dependent an the OP's capabilities and understanding of parallel programming issues.

[wysota]

While technically true, there is no free lunch. "easy paralellized" "simple OpenCl kernel", again are dependent an the OP's capabilities and understanding of parallel programming issues.

It's not that bad. If you have a for loop such as the following:

for(int r = 0; r < rows; ++r) {
    for(int c = 0; c < cols; ++c) {
        doSomething(r,c);
    }
}

for(int r = 0; r < rows; ++r) {
    for(int c = 0; c < cols; ++c) {
        doSomething(r,c);
    }
}

To copy to clipboard, switch view to plain text mode 

Can be rewritten as

QFutureSynchronizer<void> waiter;
for(int r = 0; r < rows; ++r) {
    for(int c = 0; c < cols; ++c) {
        waiter.addFuture(QtConcurrent::run(doSomething, r, c));
    }
}
waiter.waitForFinished(); // or do something else in the meantime

QFutureSynchronizer<void> waiter;
for(int r = 0; r < rows; ++r) {
    for(int c = 0; c < cols; ++c) {
        waiter.addFuture(QtConcurrent::run(doSomething, r, c));
    }
}
waiter.waitForFinished(); // or do something else in the meantime

To copy to clipboard, switch view to plain text mode 

This doesn't require any skills and provided that doSomething() does more than just add two ints together, you will get a decent speed improvement on a multicore system. Of course there is a good chance the loop can be substituted with a flat call to QtConcurrent::mappedReduced(). OpenCL is more tricky although I see the OP's calculations are mostly simple vector operations (additions and multiplications) so the code doesn't need many changes.

[qt_gotcha]

thanks for the help and suggestions guys, I really apreciate it.