Double-ended vector – is it useful?

Re:Double-ended vector – is it useful? by jerf on Monday May 23, 2016 @10:39AM (#11754113)

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

[ Parent | on HN ]

Re:Double-ended vector – is it useful? by saalweachter on Monday May 23, 2016 @07:34PM (#11757841)

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

[ Parent | on HN ]

Re:Double-ended vector – is it useful? by nkurz on Monday May 23, 2016 @09:26PM (#11758347)

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.

[ Parent | on HN ]