Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
  • Search
  • Get Qt Extensions
  • Unsolved
Collapse
Brand Logo
  1. Home
  2. Special Interest Groups
  3. C++ Gurus
  4. Pre allocation of memory
QtWS25 Last Chance

Pre allocation of memory

Scheduled Pinned Locked Moved C++ Gurus
18 Posts 8 Posters 10.4k Views
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • C Offline
    C Offline
    cazador7907
    wrote on 14 Jan 2011, 17:08 last edited by
    #1

    In setting up vector or other data structures, is there really any benefit to pre-allocating the memory?

    Laurence -

    1 Reply Last reply
    0
    • T Offline
      T Offline
      tobias.hunger
      wrote on 14 Jan 2011, 17:15 last edited by
      #2

      Yes. It saves you some memory copy operations.

      1 Reply Last reply
      0
      • Z Offline
        Z Offline
        Zlatomir
        wrote on 14 Jan 2011, 17:22 last edited by
        #3

        Are you talking about "reserve()":http://doc.trolltech.com/latest/qvector.html#reserve member function of QVector or std::vector?

        If yes, then the answer is you could get some benefits in speed if you use reserve instead calling many times push_back() or any other way repeatedly resize the vector and cause multiple allocations (potentially copy data, deallocation of old memory)

        https://forum.qt.io/category/41/romanian

        1 Reply Last reply
        0
        • G Offline
          G Offline
          giesbert
          wrote on 14 Jan 2011, 21:31 last edited by
          #4

          not potentially, it serves some allocations.

          Not each push results in a new, ther is always some pre allocation, but ich you want to add many items, it definitly makes sense if you already know the amount of items.

          Otherwise you reallocate memory and free memory often, which fragemnts the memory more than needed. You have to move the elements of the vector on each reallocation.

          And if you call reserve, the memory is allocated en block and then placement new is used to create the object. placement new is used to call the constructor of a class on an already allocated block of memory. This is the way how STL does this pre allocation.

          The current vector implementations always grow (reserve) dependant on the current size if all allocated memory is in use, so they are already a bit optimized for multiple push operations, but reserve is always a good idea.

          Nokia Certified Qt Specialist.
          Programming Is Like Sex: One mistake and you have to support it for the rest of your life. (Michael Sinz)

          1 Reply Last reply
          0
          • F Offline
            F Offline
            fcrochik
            wrote on 15 Jan 2011, 02:17 last edited by
            #5

            Like Gerolf said the important question is if you know the amount of items. You don't want to "reserve" much more memory than you will need and avoiding reallocating memory can't hurt.

            from the "documentation":http://doc.qt.nokia.com/4.7/qvector.html#reserve:

            bq. Attempts to allocate memory for at least size elements. If you know in advance how large the vector will be, you can call this function, and if you call resize() often you are likely to get better performance. If size is an underestimate, the worst that will happen is that the QVector will be a bit slower. The sole purpose of this function is to provide a means of fine tuning QVector's memory usage. In general, you will rarely ever need to call this function. If you want to change the size of the vector, call resize().

            Certified Specialist & Qt Ambassador <a href="http://www.crochik.com">Maemo, Meego, Symbian, Playbook, RaspberryPi, Desktop... Qt everywhere!</a>

            1 Reply Last reply
            0
            • C Offline
              C Offline
              cazador7907
              wrote on 15 Jan 2011, 15:47 last edited by
              #6

              Ok! So this leads me into a slightly more involved question.

              I have created a graph data structure that holds pointers to the node and edge objects that make up the graph. I am wondering if perhaps my implementation is not as efficient as it could be. The data for the graph is read in from an XML file and as the reader comes to each new node the following code runs:

              @
              //Determine if the node already exists in the graph ... skip is yes.
              if( !NodeExists(name, heuristic) )
              nodeList.push_back(new GraphNode(name, heuristic, m_iNodeIndex));

              //Advance the Node index.
              m_iNodeIndex++;
              

              @

              NodeList is a vector of pointers. Based on your responses, it seems that each new graph node will be created on the heap in a random location. Is that correct? If so, would it be better to store the node itself rather than a pointer to the node in the NodeList vector?

              Edges are created in roughly the same manner except pointers to each edge are stored in a vector or edge pointers that are a part of each node.

              Or, is this a difference of programming style?

              Laurence -

              Laurence -

              1 Reply Last reply
              0
              • G Offline
                G Offline
                giesbert
                wrote on 15 Jan 2011, 19:48 last edited by
                #7

                It depends what you do with the objects later on.

                From pure creational view, It could be better to store objects than pointers. But that also leads to other implications. If you store the pointers (or use the pointers) somwhere else and the modify the vector, the pointer might be invalid.

                So it can't be answered generally.

                Nokia Certified Qt Specialist.
                Programming Is Like Sex: One mistake and you have to support it for the rest of your life. (Michael Sinz)

                1 Reply Last reply
                0
                • C Offline
                  C Offline
                  cazador7907
                  wrote on 16 Jan 2011, 01:56 last edited by
                  #8

                  How could an object be rendered invalid?!? That almost seems counter-intuitive. If I create and object and then pass a pointer reference to some other part of the program, even if the data in the object is changed, it should not invalidate the object itself.

                  After a little more reading, my question should be, are you referring the possibility that the vector may have to re-allocate and move the underlying objects around thus invalidating the pointers? If so, I am not sure that I have to worry about this possibility. The graph's nodes and edges are fixed in number.

                  Laurence -

                  1 Reply Last reply
                  0
                  • G Offline
                    G Offline
                    giesbert
                    wrote on 16 Jan 2011, 08:00 last edited by
                    #9

                    An std::vector (and also a QVector) is a C - array. SO if you have 20 elements in and need to reallocate the vector, the old content MUST be moved in memory, so pointers to the old (unchanged) array would definitly get invalid.

                    If you can preallocate the vector and do not resize it, than you can also give pointers out of it. Think of it like a C-style array. If you have no space left and want to add elements, you have to move all elements to a new array which is bigger.

                    Both vectors have just a bit more comfort, like moving, adding, preallocating, but in general, they are C-style arrays.

                    Nokia Certified Qt Specialist.
                    Programming Is Like Sex: One mistake and you have to support it for the rest of your life. (Michael Sinz)

                    1 Reply Last reply
                    0
                    • T Offline
                      T Offline
                      Taamalus
                      wrote on 16 Jan 2011, 08:58 last edited by
                      #10

                      Not sure if this helps, since I don't like arrays, never used them and would not know how they compare to a vector, just giving another angle to the discussion.

                      I think a std::vector is contiguous through out its life. When the allocated memory block for a vector is exhausted during a growth, the entire vector gets copied into a larger block, and whatever is contained gets copied with it. Any type of data can be accessed in this vector as before the copy took place.

                      The catch is when the vector is created at run time and is filled with a horde of pointers and needs to be destructed, than all those pointers in the vectors need to be destroyed as well and at programming time you don't know which one's will be created and where - you are stuck or it's time for smart pointers.

                      Bottom line? I practise and test stuff to the hilt. If the vector works the way I want it, it's end of story.

                      ... time waits for no one. - Henry

                      1 Reply Last reply
                      0
                      • P Offline
                        P Offline
                        Panke
                        wrote on 16 Jan 2011, 09:57 last edited by
                        #11

                        Preallocating may give you an advantage in writing exception save code.

                        1 Reply Last reply
                        0
                        • C Offline
                          C Offline
                          cazador7907
                          wrote on 16 Jan 2011, 12:17 last edited by
                          #12

                          I believe that I understand now. Coming from the Visual Basic and C# universes, I was shielded (to an extent) from this sort of thing. Is there a way to check if a pointer assignment is still valid?

                          Laurence -

                          Laurence -

                          1 Reply Last reply
                          0
                          • T Offline
                            T Offline
                            Taamalus
                            wrote on 16 Jan 2011, 16:19 last edited by
                            #13

                            @ cazador7907
                            That is more or less a save pointer.
                            Hopefully I will not get shot down showing a link to the competition, but I learned so much from those guys.

                            http://www.codeguru.com/cpp/cpp/article.php/c17775/The-Smart-Pointer-That-Makes-Your-C-Applications-Safer---stduniqueptr.htm

                            ... time waits for no one. - Henry

                            1 Reply Last reply
                            0
                            • P Offline
                              P Offline
                              Panke
                              wrote on 16 Jan 2011, 18:29 last edited by
                              #14

                              But unique_ptr ist no solution here. A unique_ptr implies that you own the object pointed to and
                              that the lifetime of the object and the unique_ptr are (more or less) identical. So you should know if its valid, regardless of the use of unique_ptr.

                              In fact there is no way no ensure, that a pointer points to an object that has not been deleted.

                              1 Reply Last reply
                              0
                              • T Offline
                                T Offline
                                Taamalus
                                wrote on 16 Jan 2011, 20:04 last edited by
                                #15

                                My humblest apologies.
                                The pointer style in my previous link does work in std::vectors, and those vectors that had been moved(copied). The topic is about effectively using vectors, and I added information to that.

                                And sure, no smart/save pointer is a direct answer to cazador7907 question, but the topic is about vectors; that's why I wrote 'That is more or less ...' , I assumed his/her question was in context to the topic, since we all agreed that to allocate space for a vector is a good idea, and what left to figgure out is what to do with its contents. :)

                                ... time waits for no one. - Henry

                                1 Reply Last reply
                                0
                                • G Offline
                                  G Offline
                                  giesbert
                                  wrote on 16 Jan 2011, 20:20 last edited by
                                  #16

                                  In general, there is no platform independant method to check, whether a pure pointer is valid or not.

                                  Nokia Certified Qt Specialist.
                                  Programming Is Like Sex: One mistake and you have to support it for the rest of your life. (Michael Sinz)

                                  1 Reply Last reply
                                  0
                                  • A Offline
                                    A Offline
                                    andre
                                    wrote on 16 Jan 2011, 20:27 last edited by
                                    #17

                                    Like Gerolf said: there is no general way. But, if you are dealing with a QObject you're pointing to, you can use a QPointer. That pointer will reset itself to 0 if the object is deleted.

                                    1 Reply Last reply
                                    0
                                    • G Offline
                                      G Offline
                                      giesbert
                                      wrote on 16 Jan 2011, 21:09 last edited by
                                      #18

                                      But that only helps if you are deleting the objects.

                                      I think the intention was:

                                      using a QVector which is storing objects and using pointers on those objects. And there it definitly does not work.

                                      Nokia Certified Qt Specialist.
                                      Programming Is Like Sex: One mistake and you have to support it for the rest of your life. (Michael Sinz)

                                      1 Reply Last reply
                                      0

                                      1/18

                                      14 Jan 2011, 17:08

                                      • Login

                                      • Login or register to search.
                                      1 out of 18
                                      • First post
                                        1/18
                                        Last post
                                      0
                                      • Categories
                                      • Recent
                                      • Tags
                                      • Popular
                                      • Users
                                      • Groups
                                      • Search
                                      • Get Qt Extensions
                                      • Unsolved