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

41–50 of 53 posts

Re: Double-ended vector – is it useful?

#41

Post by scott_s »

ktRolster wrote: post #21
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 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.

Re: Double-ended vector – is it useful?

#42

Post by jerf »

saalweachter wrote: post #34
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…

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

Re: Double-ended vector – is it useful?

#43

Post by bob8 »

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.

Re: Double-ended vector – is it useful?

#44

Post by agf »

ktRolster wrote: post #21
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 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.

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.

Re: Double-ended vector – is it useful?

#45

Post by falcor84 »

chmike wrote: post #40
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.

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.

Re: Double-ended vector – is it useful?

#46

Post by ktRolster »

agf wrote: post #44
ktRolster wrote: post #21

Earlier quoted context omitted.

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.

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!

Re: Double-ended vector – is it useful?

#47

Post by clarkd99 »

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.

Re: Double-ended vector – is it useful?

#48

Post by clarkd99 »

chmike wrote: post #40
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.

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.

Re: Double-ended vector – is it useful?

#49

Post by saalweachter »

jerf wrote: post #42
saalweachter wrote: post #34

Earlier quoted context omitted.

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…

"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 arg…

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

Re: Double-ended vector – is it useful?

#50

Post by nkurz »

saalweachter wrote: post #49
jerf wrote: post #42

Earlier quoted context omitted.

"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 arg…

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.

Post reply on HN