Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Double-ended vector – is it useful?

larshagencpp.github.io

Post reply on HN
Print view View original

11–20 of 53 posts

Re: Double-ended vector – is it useful?

#11

Post by viraptor »

poizan42 wrote: post #6
nkurz wrote: post #2

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…

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.

Re: Double-ended vector – is it useful?

#12

Post by viraptor »

nkurz wrote: post #2

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…

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 :)

Re: Double-ended vector – is it useful?

#13

Post by omgtehlion »

viraptor wrote: post #12
nkurz wrote: post #2

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…

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 rea…

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

Re: Double-ended vector – is it useful?

#15

Post by viraptor »

omgtehlion wrote: post #13
viraptor wrote: post #12

Earlier quoted context omitted.

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 rea…

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.

Re: Double-ended vector – is it useful?

#17

Post by deathanatos »

Someone wrote: post #14

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

Re: Double-ended vector – is it useful?

#18

Post by asQuirreL »

thomasahle wrote: post #16

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.

Re: Double-ended vector – is it useful?

#19

Post by xentronium »

agf wrote: post #4

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…

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

Re: Double-ended vector – is it useful?

#20

Post by nightcracker »

deathanatos wrote: post #17
Someone wrote: post #14

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 ele…

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

Post reply on HN