File Output given repeated small operations

Question

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?

• Loki Astari: 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.
• Loki Astari: 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).
• Surt: what is the result of double value = (0.5 + (-0.5 * (deltaY / cellToY)));? 0 or 1 also?
• chrisb2244: Between 0 and 1, in the case that the if condition is true.

Answer 1

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";
 }
 }
 }
}

• chrisb2244: 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