Is there a general rule when to favor a heap object over a stack object if the stack object is passed by value a lot?



  • I think that if the stack object is relatively small, then always avoid creating objects on the heap even if there is 'a lot' of copying of the stack object. Is that right? In terms of speed, it is probably hard to say for every example, but I actually ran a simple test and, yes assigning a stack object is faster that creating and assigning a small heap object by pointer.

    By the way, the Google C++ style guide doesn't touch this topic:
    http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml

    Does anybody have a list of rules like the 'style' guide but on other 'guru' C++ topics such as performance (when to use heap objects versus stack objects)?


  • Moderators



  • Thanks man. I am trying to avoid using the heap as using the 'new' construct has been shown to be slower and can be harder to debug.

    At first, I over used the 'new' construct and put too many objects on the heap.

    At this point, after again re-factoring, I am having second thoughts. Every situation is somewhat different. However,* what is the test* to shed light on when it is ridiculous to use a stack object rather than a heap object with the consideration that there is 'passing by value' and 'copying by value' happening.

    My limited understanding and experience on this issue, from searching the web mainly, is that in terms of performance, if the object is small (and that's arbitrary) then it is faster to work with objects on the stack by value rather that using 'new'. This is because of the 'new' and 'delete' ...

    What I would like to try to avoid is having to rip out code and set up 'profiling' tests with production/development code each time to determine what is faster in the particular case - copying objects/assigning by value on the stack or picking certain classes to be put on the heap rather than having to transfer objects by value around the code base.

    Is there some sort of best practices advice that dictates this decision? Also, I have no idea, maybe there is a free tool like valgrind that could help. It really is just something to think about. I hope this isn't pre-mature optimization. Basically, I am concerned that instead of over-using heap objects (which is the worst), I now may be leaning towards under using heap objects.


  • Moderators

    bq. Thanks man. I am trying to avoid using the heap as using the ‘new’ construct has been shown to be slower and can be harder to debug.

    Ohhh, that's a bad philosophy. I would question your sources for the speed difference. I would suspect that any differences would be negligible in common usage. That operating system you're using, and your web browser, and pretty much every piece of software you use makes a LOT of use of the heap.

    One important thing to remember, is that you can think of the heap as random memory. That is, you can create things, and destroy them, and generally let the objects have independent lives without it affecting things. Items can be contiguous or far apart. In no particular order. Think of the heap as your "general purpose" memory.

    The stack, by definition, is a sequential block of memory. First in, last out. So, you're limited in the lifespan of objects. It serves a different purpose than the heap. It's there for items that are more limited in scope and lifespan, such as passing parameters, or having short-term elements in a method.

    Also, if you create an object on the stack, it is immediately scoped to the block in which it was created. As soon as you leave that block, the item is popped off the stack and disappears. If you try to work around this, then you will end up with a ton of objects down in your main() or in some class. That becomes very kludgy and inefficient. With heap-based memory, you can pass pointers around and the data lives independently of where it was allocated, until such time as you tell it to go away.

    Additionally, the QObject class hierarchy relies on heap-based objects, as objects need to be allocated on the heap for QObject's memory management routines to work.

    The rules of practice that you're looking for mainly consist of realizing what the two different items are for. It sounds, at first glance, like you're looking for a shortcut to get away from having to do memory management in C++. I'm assuming you come from a background of a language which manages memory for you. The stack is not designed for cheating that process.

    Debugging is simple with heap-based data if

    • you are careful with how you manage creation and deletion of objects -- this also entails understanding the difference between automatic (stack-based) and heap-based storage.
    • you're comfortable with your debugger and know how to use it
    • you're aware of tools which can help you, such as valgrind.

    Additionally, Qt has a nice suite of smart pointers which can help you manage the scope and deletion of heap-based items.

    Don't take short cuts. You need to learn the basics, then everything will make sense.



  • From my experience, people tend to overrate speed optimization. In most cases this is negligible. The process is quite clear for me:

    • make your application work correctly
    • if - and only if there seems to be a speed bottleneck, investigate
    • if you do have a bottleneck look for an optimization

    Everything else is a waste of time, IMHO.

    For the stack/heap decision - that's mostly (not always!) a matter of the live time of objects: stack for short term objects, heap for long living objects. As for every rule of thumb: there are exceptions!



  • I don't get what allocating on the heap vs. allocating on the stack (vs. allocating in the data segment, why not) has to do with pass by value. Are you saying that for the 99.99% of usage there's a speed penalty in doing

    @
    A a;
    foo(a);
    @

    instead of

    @
    A *a = new A;
    foo(*a);
    @

    ?

    Or are you talking about the fact that you would pass the pointer by value, which usually is much cheaper than making a full copy?



  • Yes, the information that I have (from searching and running a 'timing' test) is that:

    @A *a = new A();//creates as object on the heap using 'new'@

    is far slower than creating an object on the stack:
    @A a=A();@

    Therefore, there is no reason to create objects on the heap unless absolutely called for as it involves additional overhead and complexity... and will result in poorer execution speed of the code. Here are the only reasons why one would create an object on the heap using new:

    • The object is too big to be put on the stack (results in stack overflow or whatever)
    • The object on the stack would degrade the performance of the code due to passing or assigning the stack class object by value everywhere in the code.

    The question of this post is talking about point two above since we all know... it is a waste of time to allocate objects on the heap.

    To be clear, in many (if not some) cases, it is probably far faster to pass class object's by value instead of by class pointer value because the heap object that is being pointed to by the class pointer value slowed down the code when it was created with 'new' much more than if that object was not created on the heap. In other words, the use of 'new' has slowed down the stupid code way more than just passing around class objects by value.

    I am fairly confident that for 'SMALL' objects at least, using a class object by value is speedier (and also easier to use) than that of using a class object by pointer value since I assume that the -slow- heap allocator would not work if there was not a call to 'new'.

    A long, living, object could be handled by class object value. I am asserting that handling objects by class object value is not necessarily slower, and in fact often FASTER, if I am not incorrect.


  • Moderators

    No, we do not know that it's a "waste of time to allocate objects on the heap." I completely and totally disagree with that fundamental basis of your assertion. It's an absurd statement. And I've been doing this stuff for many, many years.

    Can you please describe your timing test? How many objects are you talking about creating? I'm concerned that you have done something wrong in the past that caused an inefficiency and that you're erroneously attributing that problem to the use of new and/or the heap.

    For all intents and purposes there is no difference in an object created on the heap and one created on the stack. They both physically reside in the same hardware. They both are in the same logical space. And they both are stored in the same way. The only difference is how they get placed there and the rules which pertain to how they're created and destroyed.

    I also think you're confusing two very separate topics: Creation of an object and usage of the object.

    Once an object is created, it's in memory... No matter whether it's in heapspace or stackspace. If you pass around references or pointers to that object, it's the same cost. A reference is a reference. However, if you want to pass objects around by copying them (like as parameters -- which uses the stack, by the way) then you can actually incur a greater overhead because of the cost of constructing new temporary objects.

    Are you aware that passing pointers around does not actually pass the objects that they point to? A pointer is in essence a 32-bit (or 64-bit) integer, for all intents and purposes.

    Copying a pointer is extremely fast. It's fast at the machine level... it's only passing a few bytes.

    I only mention these things because, in all honesty, you're making statements and asking questions based on a flawed line of logic. And, as such, there's no concise clear answer that anyone here can give you until such time as we are all in agreement with the fundamentals of how the language and the computer operate. Garbage in, garbage out, etc.

    Incidentally, you posted the code above: @ A a=A(); @

    This is an incorrect declaration of an automatic variable. It is sufficient to say @ A a; @

    What you are doing is:

    Instantiating an "A" on the stack. (That's the "A a" part.)

    Instantiating a second temporary "A" on the stack. (That's the "A()" part.)

    Copying the contents of the second A to the first A using the first A's "operator=" (That's the "=" part.)

    Destroying the the temporary A that was created.

    If you just use @ A a; @ you only have the first step.

    THAT is the kind of inefficiency that you need to be aware of. Not overhead from a call to new. I assert that a single call to new is substantially faster than this code.



  • Here is a 'toy' code test that gives credence to the fact (IMO) that using 'new' is a waste of time. There are two different test runs. On my machine, the test shows that just using 'new' followed by delete is 20 times slower than:

    • instantiating the class on the stack
    • instantiating a second temporary
    • copying that temporary to the class variable
    • then copying the stack object to a second class 'stack' variable
    • the first class variable goes out of scope
    • the second class variable goes out of scope

    Here are the numbers:
    stack allocation took 30000 clock ticks
    heap allocation took 610000 clock ticks

    For this test, allocating new/delete on the heap was 20 times slower than 6 things? that were done through the stack allocation. Maybe the results on different machines are less dramatic?

    Thanks for the clarification about pointers. I am fairly strong on using them except for pointer to pointer and reference to pointer which I haven't had to think too much about for now.

    As far as the inefficient and definitely blatant instantiation of automatic variables, I had a feeling it was bad to do, but was trying to be blatant. Thanks for the detailed clarification and care about how that impacts performance.

    Anyway, here is my test code if anybody is interest is 'shooting it down' and discounting my opinion (the zeitgeist of this post) - that 'new' is a waste of time:

    @
    /*

    • Note: It has to be run in debug mode without compiler optimizations.
      */
      #include <ctime>
      #include <iostream>
      using namespace std;
      namespace {
      class empty { }; // even empty classes take up 1 byte of space, minimum
      }

    int main()
    {

    std::clock_t start = std::clock();
    for (int i = 0; i < 10000000; ++i){
     {
      empty d=empty();
       empty e=d;
     }
    }
    std::clock_t duration = std::clock() - start;
    std::cout << "stack allocation took " << duration << " clock ticks\n";
    start = std::clock();
    for (int i = 0; i < 10000000; ++i) {
        empty* e = new empty;
        delete e;
    };
    duration = std::clock() - start;
    std::cout << "heap allocation took " << duration << " clock ticks\n";
    

    }
    @



  • Here is a second test. It looks like if the object is about 1 Kilobyte Or Less, then there is no actual need to create an object on the heap. Is all the data and test case wrong? Basically, copying an object of that size in the stack SEEMS to be faster than using an object of that size created with the 'new' allocator.

    @
    stack allocation took 720000 clock ticks
    heap allocation took 820000 clock ticks

    /*

    • For an object of about 1 Kilobyte AND LESS, on my computer, using 'new' is
    • a waste of time compared to using an object on the stack even when the
    • object on the stack is 'copied'. Like what I have been saying all along...
      */
      #include <ctime>
      #include <iostream>
      #include <string>
      using namespace std;

    string CopyString(string copystring){
    /passes string object by value and returns string object by value/
    return copystring;
    }
    string& ReferenceString(string& referencestring){
    /passes and returns string by reference/
    return referencestring;
    }
    int main(){
    string smallstring;
    const int kIterations=10000000;
    const int kSize=1000;
    //Put in about a kilobyte (kSize) of data into 'smallstring'.
    for(int i=0;i<kSize;++i)
    smallstring.append("1");

    std::clock_t start=std::clock();
    for(int i=0;i<kIterations;++i){
    string stackstring(smallstring);;
    stackstring=CopyString(stackstring);/It is copied twice and assigned./
    }
    std::clock_t duration=std::clock()-start;
    std::cout<<"stack allocation took "<<duration<<" clock ticks\n";
    start=std::clock();
    for(int i=0;i<kIterations;++i){
    string* heapstring=new string(smallstring);
    heapstring=&(ReferenceString(*heapstring));//It is passed back by reference.
    delete heapstring;
    };
    duration=std::clock()-start;
    std::cout<<"heap allocation took "<<duration<<" clock ticks\n";
    }
    @


  • Moderators

    Are you seriously contending that you go to great lengths to avoid heap allocation because creating an object on the stack takes like 1 gazillionth of a second, compared to 20 gazallionths of a second?

    Granted, there will always be a little bit of overhead using new and delete, because of memory management, etc. But, come on. It's not as if using new is blocking your program and hurting its performance. How many objects are you talking about creating in normal operation?

    At one point you asked about premature optimization. This definitely falls into that category.

    Listen to Volker's advice from above, which I agree with wholeheartedly:

    bq. For the stack/heap decision – that’s mostly (not always!) a matter of the live time of objects: stack for short term objects, heap for long living objects. As for every rule of thumb: there are exceptions!



  • Another rule to remember: test cases have to be drawn from life. Otherwise they are mostly useless.
    (And no, you won't allocate millions of objects in such a short timeframe).

    There is no real-life difference between heap and stack allocation, really.



  • OK, I can not resist giving my take on this discussion.

    I agree with many of the comments that suggest that the optimization Iama is trying to do is premature, and we all know that premature optimization is the road to badly designed, impossible to maintain software.

    There is a place for both heap and stack allocations, and there is no absolute clear line when to use what. I also agree with Volker's take on this.

    But to muddle the issue a bit more: if you want to seriously think about performance differences between using heap and stack memory, you can not ignore the option to create your own new and delete operators and the possibilities that that brings. There can be real benefits in doing so, especially if you find yourself newing and deleting large numbers of small objects. Optimizing the new and delete operators for such cases can bring real benefits, but the advice given earlier applies here just as well: only do this if you measured this to bring real benefit to your application.

    Edit:
    Anyway, to answer the question in the title, some guidelines (again):

    • Prefer stack for local, short lived objects
    • Prefer heap for objects that have a longer life span or a life span that is independent of the context where the object is created
    • Prefer heap for large objects (stack is limited in size)
    • Prefer heap if you need a more than trivial bit of memory in a function that might recurse deeply (again: stack is limited in size).


  • [quote author="Iama Hummingbird" date="1314924803"]@
    /*

    • Note: It has to be run in debug mode without compiler optimizations.
      */
      @[/quote]

    Using debug code to compare times is absolutly nonesense. The MSVC compiler for example does many things in debug mode, which slow down memory allocation which is not done in release mode. E.g. it has additional management overhead which can be used to identify memory leaks. Performance issues of such fine granularity MUST be checked in release mode. But there you have all optimizations...

    I also did such comparison things once and I know that heap allocation is a bit slower than stack allocation, but we are talking about some CPU cycles, not about milliseconds.



  • OK, thanks for the followup. I found an article that has somewhat of a rule about when to favor stack objects. It says that allocating on the heap for 'small objects with value semantics' is a major performance killer:
    http://www.jelovic.com/articles/why_java_is_slow.htm

    Then there are examples of what small objects should NOT be in the heap:
    "...? For me these are iterators. I use a lot of them in my designs. Someone else may use complex numbers. A 3D programmer may use a vector or a point class. People dealing with time series data will use a time class. Anybody using these will definitely hate trading a zero-time stack allocation for a constant-time heap allocation. Put that in a loop and that becomes O (n) vs. zero. Add another loop and you get O (n^2) vs. again, zero."



  • That comment is not really different from what people here have already told you, right? I mean: iterators are generally not long lived objects, and if you generate a bunch of small value-type objects in a calculation, go ahead and put them on the stack as long as you don't expect them to live after your method finishes. And again: if you really need to, new can be optimized also.



  • Andre. I am seriously considering avoiding the use of 'new' and that's it, whenever right. There are too many fans of 'new' here that don't seem to want to respect that 'new' is first of all dangerous to use, and second a possible performance handicap. Why will java never be faster than C++? It is said in the link above that that has to due with not using the stack.

    Most of the comments, other than trying to shoot down, have not supported the question. The question is about passing objects by value and when that is appropriate.

    I just read something that says that if the object is 4 bytes or less (like a primitive) then pass by value. However, I guess that would apply too in a recursive function, whereas the test I provided of passing an object of 1000 bytes would not be recommended there.

    Again, I am not asking when to prefer a heap object and I don't care about CPU cycles as much as what is faster and what is more bug free.

    By the way, I am not afraid of doing something like re-writing the 'new' allocator, but what I am working on is mult-threaded, so I would need the standard multi-threaded allocator. No idea



  • If the size of your object ~ size of pointer - use stack. If the size of your object >> the size of pointer - use heap.

    In any case it all depends from your task.

    In heap your object has its own life. In stack - only while the control inside the method where it was defined.

    Stock usually limited and set during compilation. It usually uses short references that makes it work faster.

    Heap could occupy all memory you have. Keep all data in memory, write changes in change log and you will have the best performance. With desktops 8 GB RAM we can afford that.



  • [quote author="Iama Hummingbird" date="1315225821"]Again, I am not asking when to prefer a heap object... [/quote]

    This is contradictory to

    bq. [thread title] Is there a general rule when to favor a heap object over a stack object if the stack object is passed by value a lot?

    [quote author="Iama Hummingbird" date="1315225821"]
    and I don't care about CPU cycles as much as what is faster....[/quote]

    Everyone else here understood your questions so far as if it was of a big concern for you, besides other considerations.

    [quote author="Iama Hummingbird" date="1315225821"]Andre. I am seriously considering avoiding the use of 'new' and that's it, whenever right. There are too many fans of 'new' here that don't seem to want to respect that 'new' is first of all dangerous to use[/quote]

    Everyone here knows about the dangers of using one tool or the other. You can shoot yourself into the foot with heap allocation as well as with stack allocation. Neither one is more dangerous over the other one. The statement "'new' is first of all dangerous to use" is just plain wrong, in my opinion.

    What we want to tell you is that there are no general rule, but at best rules of thumb for those categories of problems. This holds true for almost every questions that arise in the daily live of a software developer. Go on and read the "C++ FAQs":http://www.parashift.com/c++-faq-lite/, for example, you will stumble over that big but all over it.

    [quote author="Iama Hummingbird" date="1315225821"]...and second a possible performance handicap.[/quote]

    For the vast majority of application developers the speed impact of heap allocation compared to stack is just a plain no-problem. In most cases the bottlenecks caused by other subjects. This is one of the reasons why only few of them care about it. The decision about heap or stack is built upon other criteria, some of them were mentioned earlier.



  • [quote author="Iama Hummingbird" date="1315225821"] The question is about passing objects by value and when that is not appropriate.
    [/quote]

    I have found that parashift.com FAQ site helpful earlier and will get more into it. Basically, I am trying to ask if it would be acceptable in a situation or two. Thanks Volker.



  • [quote author="Iama Hummingbird" date="1315229264"]
    I have found that parashift.com FAQ site helpful earlier and will get more into it. Basically, I am trying to ask if it would be acceptable in a situation or two. Thanks Volker.[/quote]

    We'll be happy to help then. And for an actual problem, maybe with some code snippets, you will most probably get more valuable answers as the usual "it depends..." :-)



  • In that case, please explain these situations ("or two") instead of trying to pry out a general answer. That might foster a more constructive discussion. As Volker explained, people here are not so much fans of new, they just know that it has its merrits. If you find that nobody answered they question you would have liked answered, then perhaps the problem is in a not well articulated question. Please reprase, and make sure the actual question you want to ask is clear and at the top of your message. Further expansions, backgrounds, etc. can come below that. That makes it easier to understand your focus and goals, and thus provide you with answers better suited to those. Note that it was you who started about performance and benchmarks, by the way, not us. So forgive us if we focussed on that aspect a bit too much to your taste.

    Then, on what to prefer passing as function parameters:
    Personally, I prefer the form that most clearly communicates the purpose of the argument. That is: API design is my primary concern. For value-type parameters, I prefer:

    • const references or normal values for passing parameters that are only used, but not modified by the method.
    • non-const references for parameters that are modified (but try to avoid those, use the return value instead if you can)
    • pointers for optional parameters that can be modified (like a second return parameter) and have them be 0 by default. An example is @int QString toInt( bool *ok=0 , intbase=10 ) const@

    However, a downside to using references is that when you read the actual function call, there is no visible difference between a reference and a normal by-value call. So, the only way to know if an argument will be modified is to read the declaration of the method that was called (or have a clever enough IDE that shows you such things).



  • BUT:
    [quote author="Iama Hummingbird" date="1314914362"] ...
    What I would like to try to avoid is having to rip out code [/quote]



  • [quote author="Iama Hummingbird" date="1315225821"]... and second a possible performance handicap.

    Again, I am not asking when to prefer a heap object and I don't care about CPU cycles as much as what is faster and what is more bug free.[/quote]

    If you don't care about CPU cycles, why do you ask for performance? CPU cycles are the counter of performance...

    And on the other hand, the bug free stuff: a new needs a delete, that's right. And if people don't use it correctly you have a memory leak, thjat's the possible bug. To avoit that, there are smart pointers.



  • [quote author="Andre" date="1315230832"]That is: API design is my primary concern.[/quote]

    This can never be emphasized enough! The first and paramount commandment of software development is create readable, understandable, debugable and maintainable code - even at the cost of performance!



  • It all boils down to a few age old quotes again:

    "More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity." — W.A. Wulf

    "The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet." — Michael A. Jackson

    "Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you have proven that's where the bottleneck is." — Rob Pike

    "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified"[5] — Donald Knuth

    "The order in which the operations shall be performed in every particular case is a very interesting and curious question, on which our space does not permit us fully to enter. In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selection amongst them for the purposes of a Calculating Engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation." — Ada Byron's notes on the analytical engine 1842.


  • Moderators

    The most sound advice I can give to you, Iama Hummingbird, is to go read code.

    There are tons and tons and tons of great open-source projects out there with real-life code for you to look at, including the Qt sources themselves, or KDE (and the list goes on.) If you want to see common practices, pick a good-sized project with a good track record and just open some random .cpp files and their corresponding headers and dig in. The information you glean there will be priceless. Think of it as a do-it-yourself apprenticeship.

    Look at how seasoned developers are handling allocation, passing, copying, deletion, and so on. Assume that in a mature enough project, there has been substantial peer review of the code to eliminate a lot of boneheaded coding practices. (They will still be there, at times, though, but they will be the exception rather than the rule.)

    If you find concrete examples you are confused about, then a link to the code or a small pasted snippet gives us all a starting point for discussion. At that point, any questions you may have will have a solid foundation for us all to build our conversation on.



  • [quote author="mlong" date="1315319006"]The most sound advice I can give to you, Iama Hummingbird, is to go read code. (...)
    [/quote]
    Sound advice indeed.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.