Add constant time std::deque::splice()

[Adi Shavit]

Since deque is internally a doubly linked list of blocks, why not add a new method list std::splice that will concatenate one deque at the end of the other in constant time by splicing the internal lists?
This should be feasible to do in constant time regardless of the size of the containers.

Is there anything preventing this?

A more narrow definition would limit this to be done only at the beginning or the end of the deque (splice_back/splice_front).

--Adi

[Nicol Bolas]

On Monday, September 28, 2015 at 12:31:26 PM UTC-4, Adi Shavit wrote:

Since deque is internally a doubly linked list of blocks, why not add a new method list std::splice that will concatenate one deque at the end of the other in constant time by splicing the internal lists?
This should be feasible to do in constant time regardless of the size of the containers.

Is there anything preventing this?

Ignoring the fact that implementations are allowed to implement deque however they want, even in a linked-list implementation what you want simply can't happen.

The reason being that only the first and last blocks in a deque are allowed to be partially empty.

Let's say you have a deque with a block size of 10 elements. And the deque has 2 blocks, the first with 3 elements and the last with 9.

How do you splice that onto another deque? That would require that the receiving deque be able to handle empty blocks in the middle of the sequence. When getting to the new block, it would have to look at something that told it which elements in the block are valid.

This would only be necessary where "splice" exists. And it would needlessly take up performance from any `deque` user who doesn't use "splice", since every block access has to check the two indices to tell where the valid elements are.

At the end of the day, it's just not a good idea.

[Adi Shavit]

Ignoring the fact that implementations are allowed to implement deque however they want, even in a linked-list implementation what you want simply can't happen.
The reason being that only the first and last blocks in a deque are allowed to be partially empty.

AFAIK, the standard does not dictate that only the first and last blocks can be partially empty. 

 

This would only be necessary where "splice" exists. And it would needlessly take up performance from any `deque` user who doesn't use "splice", since every block access has to check the two indices to tell where the valid elements are.

Keeping 2 pointers instead of one is an O(1) overhead is not really a good reason to not do this.

Looking deeper into the standard, the problem would actually be the requirement for constant time random access. With fixed size blocks this is not a problem. However, allowing for empty slots means that finding a single element with O(1) would be tricky. 

Thanks,

Adi
 

--

---
You received this message because you are subscribed to a topic in the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this topic, visit https://groups.google.com/a/isocpp.org/d/topic/std-proposals/hPHs98Z7X-g/unsubscribe.
To unsubscribe from this group and all its topics, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[David Krauss]

> On 2015–09–29, at 12:31 AM, Adi Shavit <adis...@gmail.com> wrote:
>
> Since deque is internally a doubly linked list of blocks,

No, a deque is a table-of-contents array which links to various blocks.

> why not add a new method list std::splice that will concatenate one deque at the end of the other in constant time by splicing the internal lists?
> This should be feasible to do in constant time regardless of the size of the containers.

Given a spliced deque with gaps in the middle, finding the n'th element would not be constant-time.

[Howard Hinnant]

There is one very limited form of deque splice that I consider very important. The good news is that we don’t need a change in the standard for vendors to be able to supply it. But I don’t know if vendors actually do supply it.

When used as a FIFO queue, a std::deque should quickly reach equilibrium with regards to allocations/deallocations and no longer allocate as long as the average size() stabilizes. This can be accomplished by leaving an empty array on one end of the deque after a pop, and reusing it on the other end of the deque for a subsequent push.

Here is a test that should detect whether or not your implementation performs this conforming optimization:

#include <chrono>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <new>

void* operator new (size_t sz)
{
std::printf("allocating\n");
void* p = std::malloc(sz);
return p;
}

void operator delete(void* p) noexcept
{
std::printf("deallocating\n");
return std::free(p);
}

int
main()
{
using namespace std::literals;
std::deque<int> d(20, 0);
auto end = std::chrono::steady_clock::now() + 3s;
while (std::chrono::steady_clock::now() < end)
{
d.pop_front();
d.push_back(0);
}
}

Using libc++ this outputs:

allocating
allocating
allocating
allocating
deallocating
deallocating
deallocating
deallocating

On an implementation that does not perform this optimization I would expect orders of magnitudes more allocating/deallocating statements.

Howard

[Adi Shavit]

 

> why not add a new method list std::splice that will concatenate one deque at the end of the other in constant time by splicing the internal lists?
> This should be feasible to do in constant time regardless of the size of the containers.

Given a spliced deque with gaps in the middle, finding the n'th element would not be constant-time.

Yes, that is exactly what I meant.

 

[David Rodríguez Ibeas]

This messages is just a plain contradiction:

On Thu, Oct 1, 2015 at 7:48 AM, Adi Shavit <adis...@gmail.com> wrote:

> This should be feasible to do in constant time regardless of the size of the containers.

Given a spliced deque with gaps in the middle, finding the n'th element would not be constant-time.

Yes, that is exactly what I meant.

Line 1: Should be doable in constant time
Line 2: Cannot be done in constant time
Line 3: Exactly what I mean. !?!?!

   David 

[Adi Shavit]

Sorry for the confusion, the complexity statements were referring to 2 different things…

My first post asked about the possibility of adding a constant time splice. 

Implementing this would ass empty slots in the blocks

After further investigation, I posted a second post where I acknowledged that constant time random access, as required by the standard, would be problematic if constant time splice was added (because of the potential empty slots in each block) - this was David Krauss’s point too.

Adi

[Dietmar Kühl]

Neither `splice()` nor `push_back()` on a `std::deque<T>` can be done in worst case O(1) complexity. There are O(1) operations on `T` objects but the outer array contains O(n) pointers to inner arrays and upon appending it may require O(n) operations to move them to a new location.

The more inportant issue with `splice()`ing internal arrays of a `std::deque<T>` is that the size of these arrays is not defined and is highly unlikely coincide with any size reasonable for some application. Also, to move an inner array just to end of an existing object the last inner array of the object needs to be fully used. Allowing partially filled inner arrays would break existing complexity requirements, e.g., O(1) random access.

I can imagine specialized needs for a container moving blocks of objects but I don't think `std::deque<T>` is that container. However, the whole point of generic algorithms is support for creation of specialized containers.

[maurice barnum]

maybe the resistance you're encountering is due to the word "splice"?
appending a deque onto another deque should be doable in constant time.
a "push_front" api should work, too.

the generalized splice() might not work, but maybe we don't care?

[David Krauss]

On 2015–10–01, at 4:59 PM, Dietmar Kühl <dietma...@gmail.com> wrote:

Neither `splice()` nor `push_back()` on a `std::deque<T>` can be done in worst case O(1) complexity. There are O(1) operations on `T` objects but the outer array contains O(n) pointers to inner arrays and upon appending it may require O(n) operations to move them to a new location.

This isn’t necessary. Instead of making the blocks all equally sized, you can use a back-to-back pair of geometric series, like std::vector but without move-construction. Then there are only O(ln N) blocks in the worst case (using it as a vector), and exactly 2 blocks for a ring buffer of constant size (at equilibrium). In the 2-block case, an empty one can be kept around for Howard’s optimization.

For example, say I create a deque<int>(100, 0). Then I have an allocation block of size 100. (Let’s keep it simple.)

100(100 used)

Now I push_back.

100(100) 100(1)

After another 100 push_backs:

100(100) 100(100) 200(1)

Then push_front:

200(1) 100(100) 100(100) 200(1)

This is the worst-case utilization factor not resulting from removal, 1/3. Improving this would be tricky.

Now 201 pop_fronts:

200(1)

One push_front and the low utilization factor causes it to try a smaller block:

100(1) 200(1)

I’ve been meaning to implement this for a while. It needs to count leading bits during indexing, and C++ hasn’t standardized such a facility yet (and it’s not necessarily hardware-optimized even if it were). I call the idea “powerdeque.”

[Adi Shavit]

I used the term "splice" to imply that the source deque would lose its contents as this is not a copy, more like a moving push or insert. 

I have to particular love for the word. I borrowed it from std::list::splice().

Even a constant time "push_front"/"push_back" api would be of great value. 

How would you do this while keeping to the standard requirements?

[Adi Shavit]

Typo: "I have no particular love for the word"