Eliminating while
(This can be considered to be a meditation on one aspect of Sean Parent's "no raw loops" dictum.)
The while loop is about as close to the bare metal as you can get while using structured programming idioms. It translates effortlessly into a test and a goto and in many cases the test is a couple of assembler instructions if the while loop is testing a location in memory (e.g. while(*cp++ == ' ')).
If you need speed in a tight inner loop in a highly time-sensitive application, while is an excellent candidate.
There are two other idiomatic uses of while() which are, as one might say, "worthwhile".
The first is
while(true)
{
...
}
as an idiomatic way of marking an infinite loop which will be terminated only by a resource failure or program shutdown. (But see below for why this is not ideal when used to delimit a loop which can be terminated by an internal break statement - and this includes control loops for threads which have to terminate cleanly at exit.)
The second is as a control for extraction of data from a source which can be queried for status either by looking at the return value of a call or by a straight status check; the classic C example being
while ((cp = fread(buf, 1, 512, fileptr)) != NULL)
Its equivalent C++ example is:
std::istream& str...
// Perform an initial read operation.
while(str) (
...
//Perform a read operation at the bottom of the loop
}
(Though we'll be returning to that case.)
Generally, though, it's used for loop controls where the control can't be comfortably fitted into the form of a for loop. In modern C++ almost all of those uses should be looked at very carefully.
Consider, for example, the venerable
while (std::isspace(str[i])) ++i;
Short, reasonably efficient (assuming that the array access gets optimized away), idiomatic. Then consider
auto i = str.find_first_not_of(" \t\n");
I would not want to bet that the second is any less efficient than the first. It is slightly longer, but that's the price it pays for greater expressiveness.
Up until C++17 there was a catch: this worked only when starting at the beginning of the string. But C++17 introduced the string_view, where it's cheap to drop an initial prefix. With string views, you can always, reasonably cheaply, put yourself into a position to use the second form.
(Note that until C+23 to use this with decrementing the index isn't available. Then we get find_last_not_of().)
What about while (std::isalnum(str[i])) ++i;? Using the model above would require 62 characters.
Well, we can fall back on:
auto iter = std::ranges::find_if_not(str, std::isalnum);
//Etc.
This may not be quite as efficient, depending on inlining and the compiler implementation. But if we're not in a context which requires the utmost in efficiency - that is, most contexts - that is not a major concern. There's still a gain in expressiveness.
Very frequently, while loops are used to handle loops with complicated terminating conditions. It pays to look at the conditions carefully.
Consider
while ((err == Error::None) && (numProcessed++ < m_limit))
fun (...);
Those look like similar conditions, but they aren't. The first is a guard against an unexpected error, and the second is a general check against a known capacity limit. Those are not really the same, and can be modelled differently.
Consider instead
std::ranges::for_each_n(src | std::views::take_while([&](const auto&inVal) { return err == Error::None}}), m_limit, fun);
If you aren't processing a range, that's not an issue:
std::ranges::for_each(std::views::iota_view(0, m_limit) | std::views::take_while([&](const int inVal) { return err == Error::None}}), fun);
In fact, the general form of the while loop can be represented by
std::ranges::for_each(std::views::iota_view(0) | std::views::take_while([&](const int inVal){return cond();}, fun);
Note, though, that you have to watch out - a condition which would have been expressed by a break in the while version has to be expressed in the test in the iota version, or you will have a runaway loop. In a few cases you really do want an infinite loop, in which case that's just fine: an example would be a loop in which the exit condition is signalled by throwing an exception.
The iota_view is less obvious than the simple while form and carries additional risks, but it does force showing all of the conditions which lead to a break in the loop up front.
There is a world of difference between
std::ranges::for_each(std::views::iota_view(0) | std::views::take_while([&](const int inVal){ return cond(); }, fun);
which means "run forever until the (ultimately expected) condition in the take_while filter is met", and
std::ranges::for_each(std::views::iota_view(0, N) | std::views::take_while([&](const int inVal){ return cond(); }, fun);
Frequently, a little examination will turn the first into the second, once the conditions of the loop are better understood.
More critically, so far we have been using only for_each as the simplest form of a loop. Simplest: and least expressive.
One major problem with while loops is that they do not guarantee that an examination of the conditions gives you a good idea of the loop. There could be multiple conditions internal to the loop which lead to a break statement. Careful inspection is needed to determine the true conditions. The iota view version (or in slightly different circumstances, an istream_iterator or boost tokenizer version) requires that all the loop controls be up front and easily determinable.
(It's also good form to move the equivalent of early continue statements out of the loop. One can do this by putting those conditions into filter views.
Note that in cases where a terminating condition will continue to be true once it is true once you can get very similar effect with
std::ranges::for_each(std::views::iota_view(0, N) | std::views::take_while([&](cond()), fun);
and
std::ranges::for_each(std::views::iota_view(0, N) | std::views::filter([&](cond()), fun);
But with very different levels of efficiency. The first will cut short the loop once the conditions are met. The second will simply suppress the processing of the values but continue calling the iota view until all the values are generated.)
Let's look at a concrete example. Here's a loop using while from an early edition of a customized parser for an XML file:
if (!m_verseComplete)
{
std::string str;
std::getline(inStream, str);
while (!str.empty() && inStream.good())
{
if (!inStream.good())
return std::make_pair(Token{ ""s, TokenType::End },
&theNullParser);
if (auto offset = str.find("</verse>"); offset == std::string::npos)
m_text.append(" ").append(str);
else
{
m_text.append(" ").append(str.substr(0, offset));
break;
}
std::getline(inStream, str);
}
if (str.empty()) // Gap with no end of verse
{
std::source_location sl = std::source_location::current();
return std::make_pair(
Token{ str + "-" + sl.function_name() + ":"
+ boost::lexical_cast<std::string>(sl.line()),
TokenType::Error },
&theNullParser);
}
}
if (m_isForSection)
return std::make_pair(Token{ m_text, TokenType::PsalmVerse },
&theInSectionParser);
else
return std::make_pair(Token{ m_text, TokenType::PsalmVerse },
&theInterPsalmParser);
Here is a version which shifts all the tests into a single condition and uses take_while (it fixes a couple of small bugs, as well, so it isn't an exact copy of the functionality):
std::string error;
std::ranges::for_each(
std::ranges::iota_view{ 0 }
| std::views::take_while([&](const int inVal) {
return error.empty() && inStream.good() && !m_verseComplete;
}),
[&](const int inVal) {
std::string str;
std::getline(inStream, str);
if (str.empty()) // Gap with no end of verse, or stream failed
{
std::source_location sl = std::source_location::current();
error = "<Empty String>-"s + sl.function_name() + ":"
+ boost::lexical_cast<std::string>(sl.line());
}
else if (auto offset = str.find("</verse>");
offset == std::string::npos)
m_text.append(" ").append(str);
else
{
m_text.append(" ").append(str.substr(0, offset));
m_verseComplete = true;
}
});
if (!inStream.good())
return std::make_pair(Token{ ""s, TokenType::End }, &theNullParser);
else if (!error.empty())
return std::make_pair(Token{ error, TokenType::Error }, &theNullParser);
else if (m_isForSection)
return std::make_pair(Token{ m_text, TokenType::PsalmVerse },
&theInSectionParser);
else
return std::make_pair(Token{ m_text, TokenType::PsalmVerse },
&theInterPsalmParser);
34 lines remain 34 lines, so we're not longer than we were before. The loop is wider in scope, but also simpler, because return statements have been, necessarily, moved out to after the end of the loop.
However, we haven't (yet) gained a lot by not using a simple while. If anything, we've added complexity by replacing a single word with a compound control, but because we're now using an STL algorithm we have the ability to move away from the inexpressive for_each to something more expressive. What are we doing? Well, we're building a string step-by-step. That corresponds to using std::transform (to return a string value) along with an output iterator which can build the string. This needs a little more setup, but not much change to the lambda, except to return a value rather than doing the appending internally.
std::string error;
std::ostringstream result;
result << m_text;
std::ostream_iterator<std::string> iter(result);
std::ranges::transform(
std::ranges::iota_view{ 0 }
| std::views::take_while([&](const int inVal) {
return error.empty() && inStream.good() && !m_verseComplete;
}),
iter,
[&](const int inVal) -> std::string {
std::string str;
std::getline(inStream, str);
if (str.empty()) // Gap with no end of verse, or stream failed
{
std::source_location sl = std::source_location::current();
error = "<Empty String>-"s + sl.function_name() + ":"s
+ boost::lexical_cast<std::string>(sl.line());
return {};
}
else if (auto offset = str.find("</verse>");
offset == std::string::npos)
return " " + str;
else
{
m_verseComplete = true;
return " " + str.substr(0, offset);
}
});
if (!inStream.good())
return std::make_pair(Token{ ""s, TokenType::End }, &theNullParser);
else if (!error.empty())
return std::make_pair(Token{ error, TokenType::Error }, &theNullParser);
else if (m_isForSection)
return std::make_pair(Token{ result.str(), TokenType::PsalmVerse },
&theInSectionParser);
else
return std::make_pair(Token{ result.str(), TokenType::PsalmVerse },
&theInterPsalmParser);
It's now evident just from looking at the control logic what the loop does: it iteratively extends the string in result until (1) the stream fails, (2) there is a parsing error, or (3) we reach an end of the token to be returned.
Sometimes, there seems to be no point in getting rid of while.
std::string str;
while (str.empty() && inStream.good())
std::getline(inStream, str);
This clears out blank lines until one non-blank line is found.
(It is not, by the way, equivalent to
str << inStream;
because the latter would leave the newline after the token while the former consumes it. You would need a subsequent call to read one byte to consume the extra character. And it's hard to argue that any such call is clearer than the original while loop.)
Let's say we want to ignore comments at the top of the file, in either SGML or standard UNIX format. That would be:
std::string str;
while ((str.empty() || str.begins_with("#") || str.begins_with("<--"))
&& inStream.good())
std::getline(inStream, str);
Simply extending the test is not an obvious reason to change the loop structure.
However, the loop doesn't live in a vacuum. More precisely, the initial description - clears out blank lines - is at too low a level. Why are we clearing out blank lines? To find the first non-blank line. The full context is:
std::string str;
while ((str.empty() || str.begins_with("#") || str.begins_with("<--"))
&& inStream.good())
std::getline(inStream, str);
if (!inStream.good())
return GetEndTokenPair();
if (str != "<psalter>")
{
std::source_location sl = std::source_location::current();
return std::make_pair(
Token{ str + "-" + sl.function_name() + ":"
+ boost::lexical_cast<std::string>(sl.line()),
TokenType::Error },
&theNullParser);
}
return InPsalterParser::getNextToken(inStream);
That means that we have a different and higher-level model to communicate: "find the first substantive line and evaluate it". That can be clarified with an STL approach:
std::string str;
if (std::ranges::any_of(std::ranges::iota_view{ 0, 50 }
| std::views::take_while([&](const int inVal) {
return inStream.good();
}),
[&](const int inVal) -> bool {
if (str.empty() || str.starts_with("#")
|| str.starts_with("<--"))
{
std::getline(inStream, str);
return false;
}
else
return true;
}))
{
if (str == "<psalter>")
return InPsalterParser::getNextToken(inStream);
else
{
std::source_location sl = std::source_location::current();
return std::make_pair(
Token{ str + "-" + sl.function_name() + ":"
+ boost::lexical_cast<std::string>(sl.line()),
TokenType::Error },
&theNullParser);
}
}
else
return GetEndTokenPair();
We have also put a reasonable limit on the size of a header comment: 50 lines.
Breaking out calls for public consumption
Simple while conditions do not lend themselves to algorithms simply based on ranges; if they did, they would already be expressed in a for loop format operating on sets of data.
Or maybe they do.
Remember I said we would return to the idiomatic
std::istream& str...
// Perform an initial read operation.
while(str) (
...
//Perform a read operation at the bottom of the loop
}
?
Well, maybe we want to ask ourselves what we are extracting from the stream.
Usually, what gets read from a stream or a file or a socket turns into some form of structured data. You just might have a process read from a socket to dump the data to file without looking at the data structure, but it's a rare use case.
(I once had a set of files which were delivered from another system onto VMS which were structured as fixed-length record files, in the form you might use for a binary application; they were text data. A text editor would not open them. (Well, emacs would, but the people who wanted to edit the files weren't using emacs.) I wrote a tiny application to open a file, open an output file as a STREAM_LF file (don't ask, it was VMS: I may have used a native variable-length record file, it's a long time ago and I can't recall the fine details) and just copy from one file pointer into another. Such use cases are vanishingly rare.)
If we're extracting words or lines or a succession of doubles we can convert the stream into a set of calls to a notional container using an istream_iterator.
If we're extracting data of a meaningful form to the program, records of some sort which become objects, then we might not want a loop at that level at all. We might want to write a specialized tokenizer which has the interface of an input iterator. At a low level we might actually use a very short while loop (depending on the data structure: if you know that each record is one line, or five lines, or 234 bytes, or is a leading binary integer giving a record length followed by a record while isn't very likely to be in your thoughts) to pull out one, and one only instance of an object per call, and make that instance be what a dereferencing of the iterator delivers.
We can now use any of the standard algorithms which can take an input iterator to replace the raw logic which had been done in the while loop.
The outer looping call can now take any number of forms (e.g. transform, or copy_if, or accumulate, or sample, or count_if) which are more focussed than for_each or for_each_n.
This level of effort is probably worthwhile if this represents a public interface in a package. In any other case some other form of loop control which avoids the (not very great) extra overhead of providing an iterator interface might be preferred, unless the interface would be very heavily used indeed within the package. Even then transform or fold_left using an iota_view control are good candidates for consideration.
Comments
Post a Comment