5 ms·

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 pract

by nkurz 10y ago

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?

omgtehlion 10y ago
Even further: allocate the same physical region twice. Please google what "virtual ring buffer" is ))
- mhandley 10y ago
  That's a really neat idea - hadn't seen that before. Link: http://vrb.sourceforge.net/ http://vrb.sourceforge.net/
- glandium 10y ago
  If only that were possible without a file...
  - omgtehlion 10y ago
    It is completely possible without a file (on linux, winNT, osx). Syscall names might mislead you, but this is how it is...
- Kristine1975 10y ago
  For example here: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...
poizan42 10y ago
So if you have a million vectors then you have wasted 8GB. It only makes sense if you have a few large vectors.
- viraptor 10y ago
  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.
  - dunkelheit 10y ago
    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.
    - viraptor 10y ago
      > 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.
viraptor 10y ago
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 :)
- omgtehlion 10y ago
  Portable enough. I did this successfully on Windos and OSX (using mach calls)
  - viraptor 10y ago
    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.
- pjc50 10y ago
  Between VirtualAlloc and MapViewOfFile, Windows has roughly equivalent functionality. Windows also separates out "reserve" and "commit" in the API.
saalweachter 10y ago
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.)
- jerf 10y ago
  "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.
  - saalweachter 10y ago
    It, uh, wasn't meant so much an argument as an absurd upper bound on how much address space you'd consume.

by nkurz 10y ago

omgtehlion 10y ago

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

mhandley 10y ago
That's a really neat idea - hadn't seen that before. Link: http://vrb.sourceforge.net/ http://vrb.sourceforge.net/
glandium 10y ago
If only that were possible without a file...
- omgtehlion 10y ago
  It is completely possible without a file (on linux, winNT, osx). Syscall names might mislead you, but this is how it is...
Kristine1975 10y ago
For example here: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff...

poizan42 10y ago

So if you have a million vectors then you have wasted 8GB. It only makes sense if you have a few large vectors.

viraptor 10y ago
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.
- dunkelheit 10y ago
  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.
  - viraptor 10y ago
    > 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.

viraptor 10y ago

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

omgtehlion 10y ago
Portable enough. I did this successfully on Windos and OSX (using mach calls)
- viraptor 10y ago
  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.
pjc50 10y ago
Between VirtualAlloc and MapViewOfFile, Windows has roughly equivalent functionality. Windows also separates out "reserve" and "commit" in the API.

saalweachter 10y ago

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

jerf 10y ago
"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.
- saalweachter 10y ago
  It, uh, wasn't meant so much an argument as an absurd upper bound on how much address space you'd consume.