Hacker News Reader

Comment by nkurz | Hacker News Reader

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?

View on HN

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.

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

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.

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.

Reply on news.ycombinator.com