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

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.

Thanks CornedBee,


1.

Quote:

---

Originally Posted by CornedBee

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

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

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.

Quote:

---

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.

http://cboard.cprogramming.com/showp...4&postcount=25

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

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

Quote:

---

Originally Posted by laserlight

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

2) It's a typo. I meant to write "no", not "to".

1) Yeah, sounds right.

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

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

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

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.

Quote:

---

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...

Thanks Mats,

Quote:

---

Originally Posted by matsp

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

Quote:

---

Originally Posted by laserlight

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

It would also need to keep track of the fill status of each block, which would make things quite complicated.

Quote:

---

Originally Posted by CornedBee

It would also need to keep track of the fill status of each block, which would make things quite complicated.

---

Naturally - but that's just a "used_size" and "block_size". Doesn't seem too complicated to me.

--
Mats

It's a first_index and a last_index, actually.

Quote:

---

Originally Posted by CornedBee

It's a first_index and a last_index, actually.

---

Of course, and "last_index - first_index" tells us how many items we have.

--
Mats

Thanks Mats,


1.

Quote:

---

Originally Posted by matsp

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.

---

Agree. Great!

2.

Quote:

---

Originally Posted by matsp

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.
Mats

---

Is (2) a new idea of a continue part of (1)? I feel it is a separate idea which is not a part of (1).

If it is a part of (1), I do not understand if you use continuous storage for deque, and how do you split one block into two continuous blocks in place, with each new block half full?


regards,
George

I think 1 and 2 are sort of separate, but you could concievably have a hybrid version of the two - the #2 concept is derived from laserlights comments (maybe misconstrued, but I think that's what laserlight implied).

And in 2, you wouldn't (as I see it) split a block as such, you would just make a link. Say we have this:

Code:

---

struct dqBlock
{
    int first, last;
    int blocksize;
    T *data;      // T is the data type stores.
    struct dqBlock *next; 
    // Other stuff may be here too.
};

---

Currently we have ONE block with ABCDMNOP
We want to insert E in order:

Code:

---

// Pseudo C++ code:
insertBlock(dqBlock &current, T newData, int insertPos)
  dqBlock p = new dqBlock;
  dqBlock n = new dqBlock;
 
  p->first = 0;
  p->last = current.last - insertPos;
  p->blocksize = current.blocksize - insertPos;
  current.last = insertPos-1;
  current.blocksize = insertPos;
 
  current.next = n;

  n->first = BLOCKSIZE/2;
  n->last = BLOCKSIZE/2+1;
  n->next = p;
  n->data = new T [BLOCKSIZE];
  n->blockSize = BLOCKSIZE;
  n->data[BLOCKSIZE/2] = newData;

---

This is just to give you an idea.

And as I said, it's probably not a good idea to ONLY do this inside a deque implementation - you will potentially end up with a linked list with one item per node - not a good situation for performance reasons, and you should probably use a list if that's what you actually want.

Also, I have not looked at the specifications for deque, nor have I looked inside anyones implementation to see what they actual internal data structure is.

--
Mats

Thanks Mats,


Great sample. Two questions,

1. why p->data is not assigned with any value?

2. What is the meaning of first and last member?

Quote:

---

Originally Posted by matsp

I think 1 and 2 are sort of separate, but you could concievably have a hybrid version of the two - the #2 concept is derived from laserlights comments (maybe misconstrued, but I think that's what laserlight implied).

And in 2, you wouldn't (as I see it) split a block as such, you would just make a link. Say we have this:

Code:

---

struct dqBlock
{
    int first, last;
    int blocksize;
    T *data;      // T is the data type stores.
    struct dqBlock *next; 
    // Other stuff may be here too.
};

---

Currently we have ONE block with ABCDMNOP
We want to insert E in order:

Code:

---

// Pseudo C++ code:
insertBlock(dqBlock &current, T newData, int insertPos)
  dqBlock p = new dqBlock;
  dqBlock n = new dqBlock;
 
  p->first = 0;
  p->last = current.last - insertPos;
  p->blocksize = current.blocksize - insertPos;
  current.last = insertPos-1;
  current.blocksize = insertPos;
 
  current.next = n;

  n->first = BLOCKSIZE/2;
  n->last = BLOCKSIZE/2+1;
  n->next = p;
  n->data = new T [BLOCKSIZE];
  n->blockSize = BLOCKSIZE;
  n->data[BLOCKSIZE/2] = newData;

---

This is just to give you an idea.

And as I said, it's probably not a good idea to ONLY do this inside a deque implementation - you will potentially end up with a linked list with one item per node - not a good situation for performance reasons, and you should probably use a list if that's what you actually want.

Also, I have not looked at the specifications for deque, nor have I looked inside anyones implementation to see what they actual internal data structure is.

--
Mats

---

regards,
George

1. That's a mistake. It should say "p->data = &current.data[insertPos]" somewhere in that code.

2. They indicate where in a particular block the data starts and end respectively.

Note that you could use the same technique of "splitting" for removing items.

--
Mats

Corrrect fix, thanks Mats!

Quote:

---

Originally Posted by matsp

1. That's a mistake. It should say "p->data = &current.data[insertPos]" somewhere in that code.

2. They indicate where in a particular block the data starts and end respectively.

Note that you could use the same technique of "splitting" for removing items.

--
Mats

---

regards,
George