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?
1 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 if
s 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";
}
}
}
}
-
\$\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– chrisb22442014年11月14日 05:24:59 +00:00Commented Nov 14, 2014 at 5:24
double value = (0.5 + (-0.5 * (deltaY / cellToY)));
? 0 or 1 also? \$\endgroup\$if
condition is true. \$\endgroup\$