| Date: | March 29, 2006 / year-entry #113 |
| Tags: | code |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20060329-02/?p=31733 |
| Comments: | 41 |
| Summary: | One mark of punctuation can make all the difference. One program was encountering a stack overflow exception in a function that didn't appear to be doing anything particularly stack-hungry. The following code illustrates the problem: bool TestResults::IsEqual(TestResults& expected) { if (m_testMask != expected.m_testMask) { return false; } bool result = true; if (result && (m_testMask... |
One mark of punctuation can make all the difference. One program was encountering a stack overflow exception in a function that didn't appear to be doing anything particularly stack-hungry. The following code illustrates the problem:
bool TestResults::IsEqual(TestResults& expected)
{
if (m_testMask != expected.m_testMask) {
return false;
}
bool result = true;
if (result && (m_testMask & AbcTestType)) {
result = CompareAbc(expected);
}
if (result && (m_testMask & DefTestType)) {
result = CompareDef(expected);
}
if (result && (m_testMask & GhiTestType)) {
result = CompareGhi(expected);
}
if (result && (m_testMask & JklTestType)) {
result = CompareJkl(expected);
}
return result;
}
(In reality, the algorithm for comparing two tests results was much more complicated, but that's irrelevant to this discussion.) And yet on entry to this function, a stack overflow was raised. The first thing to note is that this problem occurred only on the x64 build of the test. The x86 version ran fine, or at least appeared to. It so happens that the x64 compiler aggressively inlines functions, which as it turned out was a major exacerbator of the problem. The title of this entry probably tipped you off to what happened: The helper functions accepted the test results parameter by value not by reference: bool TestResults::CompareAbc(TestResults expected); bool TestResults::CompareDef(TestResults expected); bool TestResults::CompareGhi(TestResults expected); bool TestResults::CompareJkl(TestResults expected);
and those comparison functions in turn called other
comparison functions, which also passed the
This code appeared to run fine when compiled for the x86 architecture
because the x86-targetting compiler did not inline quite as
aggressively, so the large temporaries were not reserved on the
stack until the helper comparison was actually called.
Since the comparisons went only three levels deep,
there were only three temporary copies of the
bool TestResults::IsEqual(const TestResults& expected) const; bool TestResults::CompareAbc(const TestResults& expected) const; bool TestResults::CompareDef(const TestResults& expected) const; bool TestResults::CompareGhi(const TestResults& expected) const; bool TestResults::CompareJkl(const TestResults& expected) const;
For good measure, the parameter was changed to a
(This technique is not foolproof, however.
Somebody could always cast away |
Comments (41)
Comments are closed. |
Is ‘x64’ the same as ‘x86-64’?
If so, do someone have an idea of why 64-bit extensions would ‘favor’ inlining? Or is it just because the x64 compiler is more recent and therefore ‘aware’ of the large caches available today, allowing larger (inlined) code to be generated?
Nawak: Wider addresses and more general-purpose registers means that the data to push on the stack can get larger, and also that smart inlining can allow more flexible register assignment. Both of these means that inlining will pay off more on x64.
It’s too bad that C++ doesn’t have anyway to tell from the call whether or not something is passed by reference or by value. That would have made this bug obvious, but as it is what is happening on the stack is not obvious.
I would consider a function that takes a non-const reference to always be an error. If the function needs to modify the object, pass a pointer, at least that way from looking at the call you can say "Oh I’m giving this function a pointer, maybe it’s going to change the object."
shf301:
To me, passing a pointer implies that, in fact, the value might be NULL — bringing in another failure path that you’ve got to explore.
I don’t use non-const references that much, but in some cases (functors), you need them.
I think the x64 compiler’s inliner is broken if it allows the function’s stack to grow by > 10k or so as a result of inlining. Any more than that and you’re touching so much memory that the branches probably don’t matter.
100KB object?! How the heck do you create one of those? Sounds like he’s been using a large, fixed-sized array instead of std::vector (or other standard data structure).
My head just ‘esploded! OK, admittedly I don’t do much C++, but when I see the "&" in a parameter list I think "hmmm…that parameter’s going to be modified". But you’re saying "const … &…" means "no it’s not going to be modified; we’re just gimmicking the compiler into passing a reference to the original object so’s it won’t create a stack copy"?
Sounds like a mess. Why can’t the optimizer just figure out that a passed-by-value parameter isn’t being modified and change to a pass-by-reference parameter-passing style? Or alternatively, if the compiler needs some help (I think this’s how I’ve been writing code) just put a "const" in front of the parameter name without using the "&" sign?
"const"+"&" just doesn’t seem right.
People still pass data structures by value? WHY?
Can’t compilers be told to throw a warning when people do that, or something?
Maybe I’ve just been working with Java (eww) for too long.
Re: NotAmused
"const&" is a cornerstone of C++ parameter passing. Unlike Java, C# and similar higher-level languages, C++ is very "close to the metal". As such, it MUST give you full control over how you are passing parameters. It is an essential part of design that you have control over this. Hence, in C++ code, you will see "Class const& x" in many many places where C# code would only have "Class x" and nothing else.
If you aren’t accustomed to const&, I must say, you must indeed be a pretty bad C++ programmer.
If the class was never meant to be passed by value it should have defined a private copy contructor so the offending code could not compile.
Ray:
The power of references, other than the non-NULL pointers is with operator overloading. Not being able pass arguments to traditional functions would be a bit of a pain, but it wouldn’t cause any serious issues. However, not having references makes operator overloading much harder.
I’ve had to track down too many bugs with output parameters being references. I don’t let my people do it and I’ve never run into any serious issues with that rule. Having a crash due to a NULL output parameter pointer is very quick to track down. However, having a variable in a routine unexpectedly changed usually takes a long time to locate in a large codebase.
I find it odd that nobody has yet considered limiting stack size on debug builds. Anything over 64k and you’re probably doing something wrong. Actually, even 8k is pushing it, but I know how application programmers love stack-declared character arrays.
It’s not like doing what you did automatically saves you in the general case. If anything can be implicitly converted to TestResults you can still run into it with pass by const reference. It’s much better off passing by const pointer in this case but it’s ugly.
would someone care to comment on how much of a performance difference you gain on x86 systems by passing a double to a function as a const reference (const double&) rather than just by value. ie what ‘real’ effect does saving 32 bits on the stack have?
Dan, probably none whatsoever, except that you’re eating a GPR that could possibly be used for something better. Doubles should generally be passed by value. Any structure larger than a double should be passed by const reference. At least that’s how I do it and it appears to be a good rule of thumb. The generated assembly code looks good.
So… what was this about? To display "the world is still full of bad interface designers"? I mean, noone in their right mind would make a comparison function, especially for a large object, take anything bug a const ref. Perhaps it’s more a display that Java and C++ are different languages – to make people see "if you don’t know what you’re doing; Don’t do it!"?
What I find more interesting is that Raymond found such obvious idiocy worth blogging about. Is perhaps all the noteworthy stuff already covered, or is it to raise awareness of the increse in the collective ignorance that seemingly is becoming silly?
On a related issue – is the reserved stack space for 64-bit threads doubled, or more? I’d think it is, else a 100% 64-bit "compatible" source code could catastrophically fail when compiled as a 64-bit binary, even that it works perfectly fine in 32-bit mode. Also, are the memory requirements for 64-bit XP twice that of 32-bit?
Cooney – appverifier does something similar. There’s a "Disable automatic stack expansion" check under Low Resource Simulation. If your process must be able to survive low memory conditions it might be a good idea to enable this check and if you get any breaks, either reduce stack usage or increase the initial stack size so that you never run out of committed stack space.
"So what was this about?"
It was about a bug that I thought was interesting enough to share with other people so they will recognize the mistake when they make it. (And if you think you’re so smart that you’d never make a mistake like this, then I tip my hat to you.)
"I would consider a function that takes a non-const reference to always be an error."
Personally, I consider it an error to use a pointer for anything except optional parameters (i.e. one that could be NULL if you don’t need to do anything with that parameter).
If you *really* can’t tell whether there are out parameters from the function name (which means you didn’t spend enough time thinking about the function name in the first place), you can always change the function name to add something like an "R" at the end to point out that it’s a reference.
This is just yet another example of how names are paramount in C++. If you can’t come up with a really clear and concise name for a class, the class probably doesn’t make sense. If you can’t tell what a function does from the name, you’re probably not sure what it does anyway.
Using pointers instead of references misses the whole point of references, which have nothing to do with saving a character while you’re accessing member variables, and *everything* to do with not scribbling over random memory or dereferencing a NULL pointer.
Not to mention… When you’re *inside the function*, if you use a pointer you have to worry about that every time you touch the pointer. You can’t tell what param->foo = bar will really do except by runtime inspection. With a reference (barring other stack/heap mangling such that you’re screwed anyway) you can look at param.foo = bar and know that it’s safe.
Besides, even with pointer parameters you can’t always tell just from looking at a function call whether you have an out parameter unless you happen to be directly passing the address of a variable instead of a pointer variable (well, ok, you can use Hungarian notation to fix that if you want). You still have to look at the type of the parameters, which isn’t really any easier than looking at the function prototype.
Oh, and BTW, Visual C++ (all the way back to at least 6.0) happily shows you the function signature right there when you look at it with nothing more than a mouseover. Is your tool inferior?
This really is a newbieish error. You always pass objects by const-ref by default unless you have reason not to.
NotAmused: The optimizer can’t and shouldn’t pick the "right one" for you. And that reason is user-defined copy ctors. It’s not good to have a function call site that sometimes calls a function and sometimes doesn’t depending on the phase of the moon. When you run the optimizer, goal is to have the same behavior as when you didn’t.
When you pass by value, you are copying the object via the copy constructor. When you pass by reference, no function is called and no copy is performed.
Copy ctors may be user-defined, and they can do anything – lots of useful things.
Many time passing by const-ref is the same as passing by value, but certainly not always. The optimizer can’t read your code to decide what the copy ctor really means, and that simply ignoring it and replacing it with a reference would have the same effect.
shf301: "I would consider a function that takes a non-const reference to always be an error."
Not always. It depends on what you want to do with the parameter. For example:
void x(const std::string &str) …
gives you a string you can only look at (read-only reference)
void x(std::string str) …
gives a string which you can modify, but the changes are lost when you leave the function (copy)
void x(std::string &str) …
gives you a string which you can modify, and the changes persist when you leave the function (read/write reference)
dan.g.: "would someone care to comment on how much of a performance difference you gain on x86 systems by passing a double to a function as a const reference (const double&) rather than just by value"
The general rule in this case is that anything that’ll fit into a register can be passed by value, everything else should be passed by reference.
Cooney: "I find it odd that nobody has yet considered limiting stack size on debug builds. Anything over 64k and you’re probably doing something wrong. Actually, even 8k is pushing it, but I know how application programmers love stack-declared character arrays."
Often it’s more efficient to allocate a temporary buffer on the stack than on the heap. On the stack, you change your stack pointer, and you’re done. With the heap, allocation tables need to be read and updated, and you can have contention on multi-threaded processes.
Mike: "What I find more interesting is that Raymond found such obvious idiocy worth blogging about."
Obvious idiocy is fun. Go see http://www.thedailywtf.com for examples.
Mike: What a privileged life as a programmer you seem to lead! You can just blithely assume that any good programmer is a competent C++ programmer.
I’ll admit it: This was useful to me. I’ve probably made this mistake, several times, without knowing it. Why? Well, I’m not a comp sci major. I’ve had two classes of formal programming training — one of them an intro to engineering class with a few weeks of basic Fortran, and one of them an elective on the esoterica of high-performance supercomputing.
And yet I ended up doing a dissertation on computational fluid dynamics, so I am in large part a programmer by trade.
So, I’m in a position that I suppose you haven’t considered the existence of. I believe I’m a fairly good self-taught programmer in my field; I’ve continually put a fair bit of effort into improving my skills. But I learned primarily by being a Fortran programmer (and, yes, that means I’ve done recursive algoritms in Fortran 77 which doesn’t support recursion, and encapsulated objects in Fortran 95 which supports them); C++ was something I picked up a couple of years ago as part of this consciously working at skill improvement, and I’m still largely a beginner at it.
This all means that I understand pass-by-value and pass-by-reference and pass-by-copy-in-copy-out very well, and I can tell you exactly how the Fortran standard requires compilers to handle this. But the upshot is that Fortran does this quite differently from C++; in particular, it tends to Do The Right Thing most of the time. So, although I realize C++ is different, I doubt I always remember, and this is an error that almost never has symptoms other than slowness and memory overuse.
Ray Trent said:
"If you *really* can’t tell whether there are out parameters from the function name (which means you didn’t spend enough time thinking about the function name in the first place),
you can always change the function name to add something like an "R" at the end to point out that it’s a reference."
I agree that’s the way it should be, but do you program with developers? Where I work (Maintaining and extended an old C application)
sometimes the function name doesn’t even decribe what the function does.
Using pointers does have its own problems, what I really would want is like C# has where you have to specify ref and out. Using naming correctly is great, and should be done, but unless the compiler enforces a rule it will be broken.
And as for is my tool inferior, well I just wish that I had a real tool…
One thing I don’t understand (have I missed something?):
Why doesn’t the compiler just generate memory for ONE temporary object, and copy the original over it after another function was called – or, even better, but not always possible, determine itself that the CompareXXX() functions do not change the object?
This way, the needs for stack space would be much lower.
Of course, this would not be the optimum, but better than the current behaviour.
Anyway, the generated code (which uses 3 temporary objects) has to copy the original object over the temporary object 3 times, thus, using 1 object again and again would not be much worse than this (timely and space-wise).
– strik.
Perhaps a little profiling would also have brought that issue into surface. When I was profiling my first C++ program, it was surprising to me that copy constructors took most of the running time. Especially std::vector, std::list and std::string.
A coding standard might be helpful in avoiding problems like this one.
I concur to Trent’s opinion about pointers. Use them, if you can’t avoid it – but there are usually better/safer tools in C++ anyway. It’s just an old C-coding habit which doesn’t buy you much.
When passing a pointer as a parameter, you never know what is expected by the function actually before studying it’s docs. (Maybe you are lucky and the naming of the parameter makes it obvious, although this is not always possible.) For instance the function may or may not handle NULL. It might even store that pointer somewhere for later use, so you would have to be very careful about it’s life time… and so on.
Even for optional arguments, one might prefer the use of something like boost::optional<> as long as you don’t need the tiny bit of performance a raw pointer could save you. The justification is the same as above – you never know if the pointer-argument is meant to be an optional value, a return value or something else, while using an explicit type/wrapper would make it very clear.
Besides the same holds true much more for returning pointers as function results. The life time of an object returned in such a way and the question who gets responsible for cleaning up are anything but trivial questions. Luckily there are smart pointers and alike. And usually this doesn’t even result in a performance hit as modern compilers are great when it comes to optimizing template based types – and most smart pointers are templates.
And last but not least, if you feel uneasy with non-const references, used as a return value surrogate where single return values just don’t suffice, you should consider using explicit structs or classes for it or just using tuples as the return type – like boost::tuple or the proposed std::tuple. Returning larger structs by value isn’t that much of a problem anymore, as (again) modern compilers can avoid the overhead in most cases.
I tend NEVER to use pointers unless I WANT to say "this can be NULL".
However, there is way too much old C-style code (including MFC-style :-)) that uses pointers which are assumed to be non-NULL, never checked etc. But MS is partly to blame for our bad habbits, as they didn’t do references in MFC (well, almost) and they probably could have done better in ATL, too. And you do look up to the "big guys", especially when all the books tell you how great MFC/ATL/whatever is, so you take in the good and the bad… Pitty!
Using pointers for pass-by-ref is simply not C++ style. Yes, there is a benefit of pointers of having pass-by-ref visible in the code (‘->’ or ‘*’ instead of ‘.’) But, it’s not worth the ambiguity (the "can this ptr be NULL here!?" question).
One can also argue for maintenance like this: "if we use pointer, we can allow this parameter to be NULL later", but, imo, this doesn’t happen often enough to be justified.
IMO, C# does it best by using "ref" keyword. Can we have that in C++, please?
C++ is full of subtle traps like this. Most of the time, you get away with awful inefficient, unreliable code through sheer luck.
As a friend of mine said, if you’ve never single stepped through your code, you have no idea if it works on or not.
No offense, but this doesn’t seem to qualify as blog material, especially when a lot of other MS employees are busy talking about the internals of their projects or what’s cooking on the backburner.
This is just a very basic C++ programmer error. It’s not even a fringe case or something fine-grained or nitpicky. What’s next, a blog post on the pitfalls of sprintf?
I have never been excited about some of C++’s syntax. Passing by reference, for example, seems to me to be a syntax obfuscation. It only hides the fact that what you are really doing is using a const pointer. So
bool TestResults::IsEqual(TestResults& expected)
could also be
bool TestResults::IsEqual(TestResults * const pExpected)
In this way the language syntax doesn’t hide what’s really going on.
I don’t think the argument that ‘ref’ in C# is somehow better has any merit. These are apples and oranges. C# ALWAYS passes objects by reference. I.e. these two are comparable:
// C#
public void Method(Object x) { … }
// C++
public void Method(Object& x) { … }
Note that C# simply doesn’t have const. It simplifies the language, but any Method can change anything in your object without even asking about it. If you want the equivalent of const in C#, you need to implement a special "read-only" interface to the object and have the method take that interface.
But the ‘ref’ parameter in C#:
// C#
public void Method(ref Object x) { … }
is actually comparable to this:
// C++
public void Method(Object** x) { … }
It’s a second degree pointer and unrelated to this topic.
I tend to agree with KenE and asdf.
By the way, is there a W1048576 warning: large object passed by value?
Re passing a modifyable object by reference vs. passing a pointer to it…
I constantly (no pun intended) struggle with myself about which is the better way. If your functions always take a "const Foo&" for input params, and always take a "Foo*" for output params, it’s clear at the call sites which objects are outputs. Any param that’s a pointer to Foo is gonna be modified.
If your functions take a "const Foo&" for inputs and "Foo&" for outputs, it’s not always clear at the call site what the intent of the params are. You have to start looking either at the function/variable names – and hope their names indicate their usage – or go to the called function itself – and hope it’s sufficiently documented.
Passing a reference avoids the problem of the param being null, and that usually wins out in the end. Why introduce the possibility of bugs related to null pointers when it’s not necessary?
To denis:
Actually C# passes parameters by value. For value types, a copy of the value will be sent to the method, for reference types a copy of the reference is made and passed to the method.
to denis: you mix C#’s reference types (i.e. classes) with pass-by-ref.
Denis:
C# has a unified type system, so it’s ambigious to say that "objects" are passed by reference. An Int32 is derived from ValueType which is derived from Object.
What you’re really saying is that Reference Types use references to reference them. And in method parameters, C# passes a copy of the reference to the reference type to the method.
(Unless you use the ref or out keywords on the parameter)
Vince P: What I said is that C# always passes *objects* by reference. Unlike in C++, you cannot pass class objects by value.
Vince: the unified type system is a gimmick. It’s useful, but I wouldn’t say that int is quite the same as Int32, even though it’s automatically boxable.
Are you implying that 640k isn’t enough for everyone?