Thread: redundant allocation

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    redundant allocation

    Hello everyone,


    Quoted from GotW #54 about redundant allocation in vector and deque. What makes me confused is "because none of the allocations are redundant". I think it means,

    The context is about adding new elements at the end, not about insert elements at any arbitrary location (e.g. in the middle), right?

    1. For deque, when allocating memory for new elements at the end, no need to reallocate, i.e. allocate new space, copy old elements to new space and free old memory -- so no redundant allocation for existing component again;

    2. For vector, when allocating memory for new elements at the end, when capacity == current size, need to reallocate, i.e. allocate new space, copy old elements to new space and free old memory -- so redundant allocation for existing components again.

    My understanding correct?

    http://www.gotw.ca/gotw/054.htm

    --------------------
    3. A deque is easier to use, and inherently more efficient for growth, than a vector. The only operations supplied by vector that deque doesn't have are capacity() and reserve() -- and that's because deque doesn't need them! For vector, calling reserve() before a large number of push_back()s can eliminate reallocating ever-larger versions of the same buffer every time it finds out that the current one isn't big enough after all. A deque has no such problem, and having a deque::reserve() before a large number of push_back()s would not eliminate any allocations (or any other work) because none of the allocations are redundant; the deque has to allocate the same number of extra pages whether it does it all at once or as elements are actually appended.
    --------------------


    thanks in advance,
    George

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    If you expand a vector element by element, it will reallocate now and then to accommodate the new elements. If you have a series of insertions during which the vector reallocates more than once, all but the last allocations have, in retrospect, been redundant: if the vector had allocated enough memory in the first place, only one reallocation would have been necessary.

    The way a deque is structured, it has to allocate a new block every so often no matter what, so the allocations aren't redundant.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks CornedBee,


    1.

    Quote Originally Posted by CornedBee View Post
    If you expand a vector element by element, it will reallocate now and then to accommodate the new elements. If you have a series of insertions during which the vector reallocates more than once, all but the last allocations have, in retrospect, been redundant: if the vector had allocated enough memory in the first place, only one reallocation would have been necessary.
    I think expand means push_back right?

    I do not agree that if you have allocated enough memory in the first place, only one rellocation would have been necessary. I think if you really reserved enough memory which exceeds the max possible size, no reallocations are needed. Right?

    2.

    Quote Originally Posted by CornedBee View Post
    The way a deque is structured, it has to allocate a new block every so often no matter what, so the allocations aren't redundant.
    If we insert elements in the middle of deque, reallocation is needed. Right?


    regards,
    George

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    1) push_back or insert(end()), or something like that.

    By "in the first place", I meant "at the first reallocation". That was unclear of me. True, if you really have enough memory from the start, you need to reallocations at all.

    2) No. By my definition, a deque absolutely never reallocates.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    2) No. By my definition, a deque absolutely never reallocates.
    What's your definition?

    EDIT:
    Oh, your definition is from capacity and reserve.

    It seems to me that insertion into the middle of a deque might cause reallocation, according to your definition, except that the reallocation is localised to the block. With a vector, the reallocation affects the entire vector.
    Last edited by laserlight; 03-06-2008 at 03:30 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Hi CornedBee,


    1.

    To be precise, at the first time, it should be called allcoation, since nothing before, should not be called reallocation, from 2nd time, it should be called reallocation. Any comments? :-)

    2.

    Is it a typo? "you need to reallocations at all" -- should be -- "you need not to reallocations at all"?

    Quote Originally Posted by CornedBee View Post
    1) push_back or insert(end()), or something like that.

    By "in the first place", I meant "at the first reallocation". That was unclear of me. True, if you really have enough memory from the start, you need to reallocations at all.

    regards,
    George

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by laserlight View Post
    What's your definition?
    Cornedbee previously stated that "reallocation" is "Allocate a new block of memory, fill it with the contents of an existing block of memory and free the existing block" - such as when a std::vector is being extended. Deque is specifically designed to avoid this situation.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    2) It's a typo. I meant to write "no", not "to".

    1) Yeah, sounds right.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Hi Mats,


    But insert elements in the middle of deque still involves a lot of elements' movement... if you do not want to keep empty slot in the middle. :-)

    Quote Originally Posted by matsp View Post
    Cornedbee previously stated that "reallocation" is "Allocate a new block of memory, fill it with the contents of an existing block of memory and free the existing block" - such as when a std::vector is being extended. Deque is specifically designed to avoid this situation.

    --
    Mats

    regards,
    George

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    True enough. Of course, it is much less of an issue than in the case of a (large) vector - because the deque isn't guaranteed to be contiguous, so we can "break a block in half", insert the new element at the start of this block, and then give a new block of memory to only the second half of the current block.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Ah, checking the C++ Standard on deque's insert/remove complexity made things clearer:
    Quote Originally Posted by deque insert()
    In the worst case, inserting a single element into a deque takes time linear in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque.
    Quote Originally Posted by deque erase()
    The number of calls to the destructor is the same as the number of elements erased, but the number of the calls to the assignment operator is at most equal to the minimum of the number of elements before the erased elements and the number of elements after the erased elements.
    Now, the question of whether Josuttis was wrong to call this reallocation depends on what leeway a std::deque implementer has. An implementation could just perform copies from the insertion/deletion point to the nearer of the beginning/end, upon which there is no reallocation at all, but only allocation.

    But this is the worst case. If it is acceptable to reallocate a block in the middle of the deque as an optimisation, then Josuttis would be correct. I have a feeling that this may not be a good optimisation, since the length of the blocks will then be variable, so one has to spend extra effort to keep track of them.

    because the deque isn't guaranteed to be contiguous, so we can "break a block in half", insert the new element at the start of this block, and then give a new block of memory to only the second half of the current block.
    Okay, then this defeats my "bad optimisation" theory, so Josuttis is correct.

    EDIT:
    ... or maybe not. Breaking the blocks and adding a new block in the middle will still not be reallocation. hmm...
    Last edited by laserlight; 03-06-2008 at 03:44 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks Mats,


    Quote Originally Posted by matsp View Post
    True enough. Of course, it is much less of an issue than in the case of a (large) vector - because the deque isn't guaranteed to be contiguous, so we can "break a block in half", insert the new element at the start of this block, and then give a new block of memory to only the second half of the current block.

    --
    Mats
    Good idea! Smart man!


    regards,
    George

  14. #14
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by laserlight View Post
    EDIT:
    ... or maybe not. Breaking the blocks and adding a new block in the middle will still not be reallocation. hmm...
    Depends on how you do that: I was thinking of something along the lines of:
    a block of data is a fixed size (say 256 items)
    each block is a member of a linked list [or such].
    When you need to insert into a block, if the block itself is full, we create a new block, and move "half" the data on to the new block.

    But you could also have blocks that are part of a larger contiguous block, so when you split something, it becomes a block of it's own [perhaps with some "spare" space], but the remaining parts of the block is just half of the original block. I have a feeling this would need some heuristics to prevent it from degrading into a linked list if you have lots of insertions in the middle.

    I have no idea how the std::deque is ACTUALLY implemented.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  15. #15
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    It would also need to keep track of the fill status of each block, which would make things quite complicated.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dynamic allocation from 1 instead of zero
    By cfdprogrammer in forum C Programming
    Replies: 27
    Last Post: 04-28-2009, 08:21 AM
  2. pointer to array with dynamic allocation
    By cfdprogrammer in forum C Programming
    Replies: 22
    Last Post: 04-07-2009, 09:56 AM
  3. Dynamic memory allocation.
    By HAssan in forum C Programming
    Replies: 3
    Last Post: 09-07-2006, 05:04 PM
  4. Parsing and Fwrite Help Please.
    By Freestyler in forum C Programming
    Replies: 11
    Last Post: 12-06-2005, 11:38 AM
  5. Dynamic allocation (I thought it would crash)
    By Baaaah! in forum C Programming
    Replies: 16
    Last Post: 11-30-2005, 05:10 PM