Double-ended vector – is it useful? | Hacker News Reader

Double-ended vector – is it useful?

larshagencpp.github.io

63 pointsingve52 comments

Qt's QList is like what this describes: it tracks where the first and last used items are in the allocated region, so both prepends and appends are amortized constant time.

Peeking at the code, Qt's even using the same general approach described in the post ("When there is still a lot of room left in the buffer, we should move elements toward the middle, and not reallocate straight away."): it moves items into the middle if the backing array is under 1/3 full.

When QList first came out, I think the team said they got there by trying different implementations and measuring what worked best on average in the real app code they had. That at least suggests that to the author's question "is it useful?", somebody thought yes.

(The code I peeked at is at https://github.com/radekp/qt/blob/master/src/corelib/tools/q..., header at https://github.com/radekp/qt/blob/master/src/corelib/tools/q..., and docs (possibly for a newer version) at http://doc.qt.io/qt-5/qlist.html#prepend.)

This is an interesting article, and a "devector" is something I've never heard of or considered before, so I'll leave critique of the data structure itself to others. But I have some constructive criticism of how the data is presented. Since the graphs / performance comparisons are such a large part of the post, I think it's relevant.

First of all, and most simply, when presenting multiple charts please use the same colors for the same lines on each chart. Here, the charts without the "vector" line use a different color scheme, making it harder to compare them at a glance.

Second, absolute timings don't matter here, only relative timings do, so showing absolute time on the Y-axis doesn't really make sense. Instead, I would use percentage from a baseline of one of the data structures. I think choosing the "deque" line for that purpose would make the most sense, given that it's the standard data structure from double-ended access.

Here's a rough version of what that looks like for the first chart -- https://goo.gl/bg5mrN -- Hopefully it makes the relative speeds of the different solutions more clear (I only put in the data for "deque" and "devector").

> Second, absolute timings don't matter here, only relative timings do, so showing absolute time on the Y-axis doesn't really make sense. Instead, I would use percentage from a baseline of one of the data structures. I think choosing the "deque" line for that purpose would make the most sense, given that it's the standard data structure from double-ended access.

It's useful to measure the real asymptotic complexity.

Second, absolute timings don't matter here, only relative timings do, so showing absolute time on the Y-axis doesn't really make sense

I like to see the real timings, though. It helps me get a sense for how long real-world tasks take. In this one, we can see that things were happening on the order of nanoseconds.

Agreed - I tend to prefer absolute timings for similar reasons. Both are valid ways to present data, and I have chosen both for different reasons in the past.

The primary purpose of the graph is to show relative timings, so I think it's important to make that clear. A logarithmic Y-Axis makes that really hard to judge.

If you wanted to show absolute timings, then I would say a separate graph with time / N on they Y-axis would be the right way to do it -- you could see how the time per operation changed as you increased N.

A logarithmic Y-Axis makes that really hard to judge.

Come on, we're programmers, get good at math!

Thanks, I'm plenty good at math. The point of a graph is to display information visually -- minimal math should be required.

If what you want is the numbers, then a graph doesn't help you -- use a table instead.

Pretty clearly your "understand graphs with logarithmic axes" could use some work.

I feel like it would be possible to leave the heavy lifting to the underlying page tables. Presuming you are running a 64-bit system, you have a enormous practically unused address space. Until you access the allocated memory it doesn't actually occupy any physical RAM.

The virtual address gets associated with the physical RAM in 4KB pages. So if you just allocate an a region twice as large as you will ever need, and start writing in the middle, you will never be wasting more than 8KB of real RAM. No copying, no reallocation, just keep track somewhere of the head and tail.

Other than the momentary panic of those who notice how much memory is being "used", what are the downsides of this approach? The 8KB is unlikely to ever be a problem. I haven't seen many people taking this approach to memory management, and other than stigma, I'm not sure why. Is it that everyone still wants to support 32-bit systems?

Even further: allocate the same physical region twice. Please google what "virtual ring buffer" is ))

That's a really neat idea - hadn't seen that before. Link: http://vrb.sourceforge.net/

If only that were possible without a file...

It is completely possible without a file (on linux, winNT, osx). Syscall names might mislead you, but this is how it is...

For example here: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...

So if you have a million vectors then you have wasted 8GB. It only makes sense if you have a few large vectors.

Or if you have fewer than millions. You jumped from millions to few large. That's not what applications usually need. And even within one application, you may want to mix the storage strategies between different objects.

For a general-purpose container that is unacceptable. It must perform well from tiny to huge sizes. Also, syscalls in every constructor/destructor call? No thanks.

What you describe might make sense for some special cases, but adopting it as a default strategy is a bad idea IMO. (Edit: re-read your other post in this thread and realized that you are not really advocating this. Well then my reply goes mostly to nkurz :))

> even within one application, you may want to mix the storage strategies between different objects.

That's precisely what modern malloc implementations do.

> Also, syscalls in every constructor/destructor call? No thanks.

You can batch up operations just like with normal list and malloc/free. Instead of 1 page, allocate some bigger size in one go.

Familiarity / need I'd guess. I know this is possible. I also know how I'd do it on Linux, or where to start reading (mmap). But I have no idea how portable it is (does windows have mmap?) and unless I really need a structure that expands both ways, unless I know it's going to grow big, unless I can't estimate and preallocate it with some known capacity, unless I can't handle this using rebalancing tree, unless I really want to avoid copies, etc. I'm not going to implement it.

Even if all of those special cases apply, I'd first use dequeue or something ready and only reimplement it if it was too slow or take too much space in practice. We've got good-enough solutions for many cases. I'm ok with good-enough in many cases :)

Portable enough. I did this successfully on Windos and OSX (using mach calls)

I know it's possible to implement. By portable, I mean: is there a common interface for it. I'm guessing the answer is no if you mention specifically mach calls.

Between VirtualAlloc and MapViewOfFile, Windows has roughly equivalent functionality. Windows also separates out "reserve" and "commit" in the API.

If you are using virtual address space as your only method -- no reallocation when you hit certain boundaries -- don't you need to pick starting addresses way in the middle of nowhere? That could be problematic.

Imagine a work queue which is pushing items onto one end of the devector and popping them off the other. It pushes 1 item each nanosecond and pops at a similar rate, so the devector never actually grows large. You want the process to run for several years, so you allocate room for 3.16 x 10^17 items on either side of the starting address, and largest you want each item to be is 8 bytes.

Bam, you've want about 2^62 bytes for a single devector. You can fit 4 of those into your 64-bit address space before you run the risk of two of them overwriting each other and needing to add special handling to prevent that, which would eliminate the code benefits.

(Incidentally, this does answer a question that came up the other day: why would you need a 128-bit address space? If you had 128 bits of memory address space, you could give each container its own 64-bit address space, and never run out.)

"Imagine a work queue which is pushing items onto one end of the devector and popping them off the other. It pushes 1 item each nanosecond and pops at a similar rate, so the devector never actually grows large. You want the process to run for several years, so you allocate room for 3.16 x 10^17 items on either side of the starting address, and largest you want each item to be is 8 bytes."

When making this sort of argument, one wants to use numbers that are obviously sensible and practical and then show they lead to an nonsensical and/or impractical result. When using obviously silly and impractical numbers you basically prove the exact opposite of what you meant to prove. You provided evidence that this isn't a problem by showing how silly you have to get to have a problem, plus the part you didn't explicitly state which is that the programmer here has chosen a grossly incorrect data structure; with the workload you've described, the correct solution is a ring buffer.

It, uh, wasn't meant so much an argument as an absurd upper bound on how much address space you'd consume.

Are you familiar with the joke where the patient says about some awkward improbable activity, "Doctor, it hurts every time I do it" and the doctor responds "Then don't do that!"

The principle here is the same: then don't do that!

I will mention though that although pointers occupy 64 bits, the virtual address space on current x64 machines is limited to 48-bit (256 TB). This means that if you are careful, you can get away with stashing an extra 16-bits of data in the high two bytes of your pointers. Or if you are nefarious (as described in the recently discussed http://zinascii.com/2016/the-illumos-syscall-handler.html) you might figure out a way to utilize the "non-canonical" addresses for privilege escalation.

More restrictively, current CPUs have an even smaller range for physical RAM addresses. This varies by CPU, but the Skylake processor I just checked on (cat /proc/cpuinfo | grep address) shows that it only has 39 bits physical address space, which is only 512GB. There are servers with considerably more capacity, but I don't know if any actually get to the full 48 yet.

I mention these limits to say that if you are planning to handle 3.16 x 10^17 8B items on your system any time soon, I think you may hit some other blocking issues before you need to worry about the suitability of the double ended vector.

It might be of interest to mention that std::deque is implemented as a linked list of arrays: http://cpp-tip-of-the-day.blogspot.com/2013/11/how-is-stddeq...

Note that std::deque is not really implemented as a linked list, as it would prevent O(1) random access. The classical implementation is as a dynamic array of pointers to fixed size chunks.

That's what he just said...

"linked list of arrays"...

"Dynamic array of fixed size chunks..."

They don't look the same to me. They do to you?

Whoops. You are right!

I have already made this concept a year ago: https://github.com/orlp/devector.

I never finished the implementation though. Exception safe programming of standard containers is incredibly annoying (feel free to inspect the source code to see what I mean).

I have made a circular queue where data can be pushed or popped on either end of a vector of structs.

Adding an entry can be done on the end or the head without moving any other nodes. All that is required is to have an index for the head and one for the tail. Used as a queue, you would push nodes on the tail and pop nodes off the head. You could just as easily add nodes to the head and pop them off the tail or any combination that you like. You could iterate over the list by starting at the tail and moving backward toward the head. You could also start at the head and move forward toward the tail. If you try to move below the first element then set the index to the last entry. If you try to move above the last entry then continue on the front of the vector.

If the head and tail have the same number then no entries are in the vector.

If the buffer size (which determines how many entries you can have) is about to be exceeded then create a bigger buffer and copy the old entries to the new buffer.

Instead of creating a bigger buffer and copying all the entries, you could make a new "cluster" of the same size as the current buffer and then you could use an integer division and modulo to determine in which cluster and what offset any node might be at.

Using the cluster method, the whole struct could grow as needed, and never move any existing data entries while pushing/popping data at either the head or tail of the list of array nodes. The struct could be just a single number or any other sized structure. Memory allocations would be minimized by allocing a buffer of "n" times the size of each node.

Interesting. I needed a similar data structure once and ended up using linked list (but it had exactly $VERTICAL_RESOLUTION big elements so the memory cost for poitners was negligible, and the most common operation was moving all elements left(up) or right(down) and linked list is hard to beat at that).

This is definitely useful because it gives us a double ended queue with efficient random access. I can't think of a use case right now, but I'm sure there are some.

Interesting implementation. Given that it seems to perform more moves than a regular vector, I'm wondering how much more efficient this would be if it could just memmove the whole block around (AFAIK, the spec doesn't allow it because of constructors/destructors for complex structures).

Isn't that a std::deque (http://en.cppreference.com/w/cpp/container/deque)?

I don't think std::deque's implementation is specified in standard. It only needs to meet certain running times, and the data structure in the article — the author's "devector" — would satisfy the requirements of std::deque; i.e., the "devector" is a valid implementation of std::deque, I think. However, in practice, std::deque is not implemented this way — your link hints at this:

> As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

The usual implementation, I think, looks something like the image here[1].

[1]: http://stackoverflow.com/a/6292437/101999

> the "devector" is a valid implementation of std::deque, I think

It is not. std::deque has strict requirements that say appends/prepends may not invalidate references/iterators. A devector can not guarantee this.

Nitpick, the operation seems to be allowed to invalidate iterators, though not references. "An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque" [1] There might be some cases where it would be practical to simply not free the previously used memory, such that after N increases in size there are N copies of each element. This would only roughly double the space required.

[1] C++ working draft, 11 megabytes; http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n429...

Ah, I thought it was both, but was just working from the top of my memory. Good for looking it up :)

Wow, that's a really neat data structure!

This is known as a Circular Buffer https://en.m.wikipedia.org/wiki/Circular_buffer

In Java it is ArrayDeque https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeq...

I don't think this is a circular buffer. The strategy here is to shift the data inside the buffer to the middle once either the front or back pointer are at the front/end of the buffer respectively, rather than to wrap around.

My intuition is that a circular buffer would be better though, because it would not have to do any large scale moves of memory until it came time to reallocate.

There are many ways one might implement a circular buffer, that's not really important. The point is that you should use the standard names, so people may easily compare your "Double-ended vector" to the state of the art.

Yes, there are, but in my opinion, for it to be a circular buffer, it should wrap the end of the data back round to the front when the end of the queue reaches the end of the buffer.

Inserting 4 into:

    [x, x, x, 1, 2, 3]

Produces:

    [4, x, x, 1, 2, 3]

In a circular buffer, and:

    [x, 1, 2, 3, 4, x]

In the proposed "double-ended vector". The technique is different, the amortized complexity is also different. I think therefore, it warrants a different name, to avoid confusion.

It really is a double ended queue. A circular buffer is a particular data structure that share some properties with the double ended queue.

One of the difference is that a circular buffer has a fixed capacity. The double ended queue has no capacity limit.

Well, from what I remember from my data structures class, a queue/dequeue has to have O(1) worst case insertion, but otherwise, yeah, it's pretty much the same.

But your part made me think, indeed there's no inherent reason for a circular buffer to have a fixed capacity. You could use pretty much the same logic but implement reallocation when it's 100% full, and get most of the benefit of both.

A circular buffer can contain a number of nodes and get bigger when it runs out of space by making a larger buffer and copying the old data or clustering as I described above. It doesn't have a "fixed capacity".

My circular queue works without moving any elements on insertion (with cluster method) or just moving the nodes each time the buffer size is exceeded. It seems this "double ended queue" isn't as useful because it has to copy nodes, find a middle etc.

Even in the "cluster" version of my circular queue, you can quickly calculate the actual location of any node directly using it's "virtual" index number, even though the head and tail can "float" anywhere along each cluster array of structs.

I don't understand the phrase "Moving O(n) elements...".

As far as I know, Big O notation is used to compare growth rates of algorithms as their input size changes.

Can't you have a regular vector and place the place the appended items on the even indices and prepended items on the odd? If you keep count of how many prepended and appended items you have you have identical performance to a regular vector except a worst case doubling of memory.

Reply on news.ycombinator.com