3
\$\begingroup\$

I want to write a file which contains values for each cell of a CFD computation. This will be an input file to the program which runs the computation.

Currently, the most dubious section of my code looks like:

for (int y = 0; y < ycells; y++)
{
    double yPos = yMin + (cellToY * (y + 0.5));
        for (int x=0; x<xcells; x++)
        {
            double deltaY = yProfileHeight[x] - yPos;
            if (deltaY < -cellToY)
            {
                file << "1\n";
            }
            else if (deltaY > cellToY)
            {
                file << "0\n";
            }
            else
            {
                double value = (0.5 + (-0.5 * (deltaY / cellToY)));
                file << value << "\n";
            }
        }
    }
}

For most of the file these if checks are going to be slow/useless - since depending on the value of yPos, they will all evaluate to true/false for large regions.

I can rewrite it like this (with appropriate min/max functions):

for (int y = 0; y < ycells; y++)
{
    double yPos = yMin + (cellToY * (y + 0.5));
    if (yPos < yHeightMin)
    {
        for (int x=0; x<xcells; x++)
        {
            file << "0\n";
        }
    }
    else if (yPos > yHeightMax)
    {
        for (int x=0; x<xcells; x++)
        {
            file << "1\n";
        }
    }
    else
    {
        for (int x=0; x<xcells; x++)
        {
            double deltaY = yProfileHeight[x] - yPos;
            if (deltaY < -cellToY)
            {
                file << "1\n";
            }
            else if (deltaY > cellToY)
            {
                file << "0\n";
            }
            else
            {
                double value = (0.5 + (-0.5 * (deltaY / cellToY)));
                file << value << "\n";
            }
        }
    }
}

Now my if conditions are evaluated less frequently, but I'm still left with segments like

for (int x=0; x<xcells; x++) // where xcells is ~ 1-10k
{
    file << "1\n";
}

Can I rewrite this in a way that doesn't require several thousand separate (identical) writes to a single file?

\$\endgroup\$
  • \$\begingroup\$ Have you tried timing the two versions to see if there is a significant difference in speed. It does not look like V2 is going to give you any significant advantages (both are O(n^2)) and greatly increases the complexity of understanding the code. Most compilers are already going to do common sub expression yanking anyway. \$\endgroup\$ – Martin York Nov 13 '14 at 13:22
  • \$\begingroup\$ Since the file streams are buffered I don't think a small number like 10K is that many time. The most important thing about your code (after correctness) is readability. After you have correctness and readability then you can look at better techniques for optimizations (as you can time and compare the versions). \$\endgroup\$ – Martin York Nov 13 '14 at 13:23
  • \$\begingroup\$ what is the result of double value = (0.5 + (-0.5 * (deltaY / cellToY)));? 0 or 1 also? \$\endgroup\$ – Surt Nov 13 '14 at 16:30
  • \$\begingroup\$ Between 0 and 1, in the case that the if condition is true. \$\endgroup\$ – chrisb2244 Nov 14 '14 at 2:37
2
\$\begingroup\$

Measuring is good, but it will only tell you what those data will result in, so you will need to reason on the code too and then measure that it isn't totally wrong.

The reason to change the code is the suspicion that the repeated calls to file output would be a large overhead.

// ToDo: add sanity checks.

string Duplicate(string org, size_t maxSize) {
  string dup;
  dup.reserve(org.length() * maxSize);
  for (auto i = 0; i < maxSize; ++i)
    dup.append(org); 

  return dup; // hope for NVRO
}


string Ones = "1\n";
size_t numLens = Ones.length();
string Ones = Duplicate(Ones, MaxNumberOfRepeats);
string Zeroes = Duplicate("0\n", MaxNumberOfRepeats);

Usage, dups is the number of duplicates

inline void Writer(string text, size_t dups) { 
  file << text.substr(0, dups*numLens); // potentially makes a copy
}

There is a method using char[] which doesn't make any copy. (not shown)


 double value = (0.5 + (-0.5 * (deltaY / cellToY)));

Saving on the math operations as '/' is expensive and '-0.5 *' also is a constant that might as well be calculated outside the loop.
WARNING this may result in some subtle differences in final values due to float pointiness.

Outside the loop or if cellToY is a global const make it a constexpr

constexpr double invCellToY = -0.5 / cellToY;

This leaves

double value = (0.5 + ( (deltaY * invCellToY)));

Saving a divide.


The ifs are a problem

            if (deltaY < -cellToY) {
                file << "1\n";
            }
            else if (deltaY > cellToY) {
                file << "0\n";

If they are true at a near random occurrence you have a serious performance problem. If they come in streaks you can do something like this

double deltaY = yProfileHeight[x] - yPos;
if (deltaY < -cellToY) {
    int count = 1;
    while (++x < xcells) {
        deltaY = yProfileHeight[x] - yPos;
        if (!(deltaY < -cellToY))
            break;

        ++count;
    }
    Writer(Ones, count);
} else
    ...

This guarantees one mispredict for the while so this might be a loss if they don't come in streaks. (branch prediction is somewhat dependend on global branch history so some of the lost might be redeemed again as the next x itereation should have an increased probability of predict the first if not taken after the loop exit).

This would also mean that the original code would get lots of mispredicts, you could try this

// these bool calculations should be branchless
bool LT = (deltaY < -cellToY);
bool GT = (deltaY > cellToY);
// ??? LT and GT are mutual exclusive
bool LTGT = LT | GT;

if (LTGT)
    res = LT?Ones:Zeroes;
else
    // very costly operation of turning double to string ...
    // should the result be 0 or 1 also?
    res = string(0.5 + ( (deltaY * invCellToY)))+"\n";  

fill << res;

as in some cases (trinaries) some compilers (gcc+?) can find out to generate conditional moves.

But my guess would be the while implementation would be faster as the domain suggest some form of streaks. Merge your final decision with this code.

string res;
for (int y = 0; y < ycells; y++) {
    double yPos = yMin + (cellToY * (y + 0.5));
    if (yPos < yHeightMin)  {
        Writer(Zeroes, xcells); 
    }
    else if (yPos > yHeightMax) {
        Writer(Ones, xcells); 
    } else {
        for (int x=0; x<xcells; x++) {
            double deltaY = yProfileHeight[x] - yPos;

            // exchange this with the wanted code
            if (deltaY < -cellToY) {
                file << "1\n";
            }
            else if (deltaY > cellToY) {
                file << "0\n";
            } else {
                double value = (0.5 + ( (deltaY * invCellToY)));
                file << value << "\n";
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for the time you spent reading and answering - I implemented approximately half of this and it has resulted in an approximately 22-25% speedup. I suspect the other half might also be useful but I want to check the results are coming out as expected before making too many changes \$\endgroup\$ – chrisb2244 Nov 14 '14 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.