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

31–40 of 53 posts

Re: Double-ended vector – is it useful?

#31

Post by thomasahle »

asQuirreL wrote: post #18
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.

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.

Re: Double-ended vector – is it useful?

#32

Post by gpderetta »

chillacy wrote: post #7

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.

Re: Double-ended vector – is it useful?

#33

Post by IshKebab »

gpderetta wrote: post #32
chillacy wrote: post #7

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

Re: Double-ended vector – is it useful?

#34

Post by saalweachter »

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…

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

Re: Double-ended vector – is it useful?

#35

Post by jjnoakes »

IshKebab wrote: post #33
gpderetta wrote: post #32

Earlier quoted context omitted.

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?

Re: Double-ended vector – is it useful?

#36

Post by Kristine1975 »

omgtehlion wrote: post #5
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…

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

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

Re: Double-ended vector – is it useful?

#37

Post by asQuirreL »

thomasahle wrote: post #31
asQuirreL wrote: post #18

Earlier quoted context omitted.

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.

Re: Double-ended vector – is it useful?

#40

Post by chmike »

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

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.

Post reply on HN