6 ms·

Hidden Costs of Memory Allocation

111 points by ghusbands 12y ago

bluetomcat 12y ago
Does Windows really keep a pool of zero pages? With COW, a single zero page is sufficient -- any copying would be done when a write is attempted over the page.
- bartwe 12y ago
  Which makes it an ondemand cost with added latency instead of something that can be done ahead of time.
- BBlarat 12y ago
  From what I read in the linked msdn blog link (http://blogs.msdn.com/b/tims/archive/2010/10/29/pdc10-mysteries-of-windows-memory-management-revealed-part-two.aspx http://blogs.msdn.com/b/tims/archive/2010/10/29/pdc10-myster...) it sure seems like it's a list.
- ars 12y ago
  COW isn't free. You still have to spend the time doing the copy. Better to zero memory ahead of time.
  - fulafel 12y ago
    Windows-style ahead of time zeroing thread will typically take the cache misses and memory bandwidth for that page twice. (Assuming your code subsequently puts its own data on the pages, instead of just ordering up zeroed pages to sit on)
    - kevingadd 12y ago
      Are you certain it's not bypassing cache on the writes? It's been relatively straightforward to do this on x86 for ages now, especially if you're using SSE to fill many bytes at once. I would be shocked if the page zeroing thread did cached reads or writes.
      - brucedawson 12y ago
        The page-zeroing code may be able to minimize its effect on the cache, but it will then necessarily consume memory bandwidth -- 4 KB of bandwidth per page zeroed as it writes each page. So, it still affects overall performance. And it guarantees that when a process goes to use the pages they will not be in the cache. Ah, tradeoffs.
        ars 12y ago
        It does it when the system is otherwise idle. > And it guarantees that when a process goes to use the pages they will not be in the cache. There isn't much point in caching a page full of zeros. Let the cache fill when there is actual data.
        deleted 12y ago
        [deleted]
tehwalrus 12y ago
I know that in C it is relatively easy to define your own memory management functions (I have written my own, complete with very primitive garbage collector, in an attempt to track down memory leaks before I had heard about Valgrind). I believe Python essentially does this under the hood by allocating buffers and managing its own memory requests on them (allocating more when it needs more, obviously). I wonder if it is possible to do this kind of thing in C++? It occurs to me that it might be hard to write platform-independent code which mimics the behaviour of the `new` keyword on a preallocated buffer. A quick Google reveals some syntax[1] that I'd not seen before which allows one to do this, although it looks like your call would look something like: MyType* instance = new (my_malloc(sizeof(MyType))) MyType(); which is hardly concise. Perhaps a macro called my_new would allow you to text-transform your way there without as many parens or repeats of MyType. In any case, asking for all your RAM at the beginning, and then re-blanking and re-using it, is certainly much faster for certain problem types (3D games with physics emulation, some scientific problems.) [1] http://stackoverflow.com/questions/8301043/create-objects-in-pre-allocated-memory http://stackoverflow.com/questions/8301043/create-objects-in... disclaimer: This post is about reinventing too many wheels, and should be taken with a pinch of salt! Moving malloc calls out of loops (and replacing them with hand-written zeroing functions) is probably the most useful tip in practise.
- cdevfr 12y ago
  Sure it is possible. Just pass the constructor your type: my_type* t = New( MyType ) ; Where MyType passes information to New() of what to create. ... I don't know what I'm downvoted. This clearly works. The naive solution without macros would have MyType be a simple integer and New() has a switch statement. But it is easy to avoid that.
  - pmr_ 12y ago
    You are being downvoted because the language comes with well-defined and specifically designed ways to customize allocation/deallocation. Your approach choses to ignore those facilities and even adds a runtime decision to code that absolutely has no need for it. You are reinventing the wheel and it is not even round.
gargantian 12y ago
I'm actually surprised virtualized page-zeroing isn't a memory controller feature at this point. With all of the things modern CPUs do or you, it seems crazy that everyone is running CPU threads that waste time and voltage to pump a zero page queue.
- adwn 12y ago
  The Mill [1] does/will do that: When memory is allocated, it is served directly be the cache, which implicitly zeroes the respective cache line (without involving the main memory). A similar mechanism zeroes a stackframe upon a function call (and function return, I think), which eliminates most attacks that exploit buffer-overflows. [1] http://millcomputing.com/docs/memory/ http://millcomputing.com/docs/memory/
  - oso2k 12y ago
    So a Mill CPU can never do shared-memory process parallelization? Two or more processes accessing the same memory could be a hazard. Seems like it would suffer the same issue IA-64 has with parallelism. However, the conveyor belt analogy simplifies register spilling & related issues.
    - crest 12y ago
      Only if you are crazy enough to share stacks in which case you deserve what you get.
    - adwn 12y ago
      > So a Mill CPU can never do shared-memory process parallelization? Why not? The caches will still be coherent.
- peterfirefly 12y ago
  The Mill, if it ever gets built, does something like that. http://millcomputing.com/wiki/Memory#Implicit_Zero_and_Virtual_Zero http://millcomputing.com/wiki/Memory#Implicit_Zero_and_Virtu... "The big gain for this is that the OS doesn't have to explicitly zero out new pages, which would be a lot of bandwidth and time, and accesses to uninitialized memory only take the time of the cache and TLB lookups instead of having to do memory round trips."
deleted 12y ago
[deleted]
- cbd1984 12y ago
  > The article states that "relational databases" arose to conserve "rare" and "expensive" disk space. It seems that navigational databases, which relational databases largely replaced, would be even more sparing of disk space, which makes me think that claim is rather suspect. How about another explanation: Relational databases are to data what structured programming (using for loops and while loops and functions and local variables instead of, you know, not) is to code: It reduces the potential for error by, first, encouraging single-point-of-truth via normalization, and, second, encouraging people to make as many tables as possible automatically via queries which use relational algebra. In short, every table knows about one kind of thing. Everything your database knows about that kind of thing is in that one table. If you want to know more than one kind of thing at a time, you create a new table automatically with a query. Compare: Every function does one kind of thing. Everything your program knows about doing that kind of thing is in that function. If you want to do more than one kind of thing, you compose functions and let the details of flow control be handled automatically by the runtime.
- deleted 12y ago
  [deleted]

111 points by ghusbands 12y ago

Does Windows really keep a pool of zero pages? With COW, a single zero page is sufficient -- any copying would be done when a write is attempted over the page.

bartwe 12y ago
Which makes it an ondemand cost with added latency instead of something that can be done ahead of time.
BBlarat 12y ago
From what I read in the linked msdn blog link (http://blogs.msdn.com/b/tims/archive/2010/10/29/pdc10-mysteries-of-windows-memory-management-revealed-part-two.aspx http://blogs.msdn.com/b/tims/archive/2010/10/29/pdc10-myster...) it sure seems like it's a list.
ars 12y ago
COW isn't free. You still have to spend the time doing the copy. Better to zero memory ahead of time.
- fulafel 12y ago
  Windows-style ahead of time zeroing thread will typically take the cache misses and memory bandwidth for that page twice. (Assuming your code subsequently puts its own data on the pages, instead of just ordering up zeroed pages to sit on)
  - kevingadd 12y ago
    Are you certain it's not bypassing cache on the writes? It's been relatively straightforward to do this on x86 for ages now, especially if you're using SSE to fill many bytes at once. I would be shocked if the page zeroing thread did cached reads or writes.
    - brucedawson 12y ago
      The page-zeroing code may be able to minimize its effect on the cache, but it will then necessarily consume memory bandwidth -- 4 KB of bandwidth per page zeroed as it writes each page. So, it still affects overall performance. And it guarantees that when a process goes to use the pages they will not be in the cache. Ah, tradeoffs.
      - ars 12y ago
        It does it when the system is otherwise idle. > And it guarantees that when a process goes to use the pages they will not be in the cache. There isn't much point in caching a page full of zeros. Let the cache fill when there is actual data.
        deleted 12y ago
        [deleted]

tehwalrus 12y ago

I know that in C it is relatively easy to define your own memory management functions (I have written my own, complete with very primitive garbage collector, in an attempt to track down memory leaks before I had heard about Valgrind). I believe Python essentially does this under the hood by allocating buffers and managing its own memory requests on them (allocating more when it needs more, obviously). I wonder if it is possible to do this kind of thing in C++? It occurs to me that it might be hard to write platform-independent code which mimics the behaviour of the `new` keyword on a preallocated buffer. A quick Google reveals some syntax[1] that I'd not seen before which allows one to do this, although it looks like your call would look something like: MyType* instance = new (my_malloc(sizeof(MyType))) MyType(); which is hardly concise. Perhaps a macro called my_new would allow you to text-transform your way there without as many parens or repeats of MyType. In any case, asking for all your RAM at the beginning, and then re-blanking and re-using it, is certainly much faster for certain problem types (3D games with physics emulation, some scientific problems.) [1] http://stackoverflow.com/questions/8301043/create-objects-in-pre-allocated-memory http://stackoverflow.com/questions/8301043/create-objects-in... disclaimer: This post is about reinventing too many wheels, and should be taken with a pinch of salt! Moving malloc calls out of loops (and replacing them with hand-written zeroing functions) is probably the most useful tip in practise.

cdevfr 12y ago
Sure it is possible. Just pass the constructor your type: my_type* t = New( MyType ) ; Where MyType passes information to New() of what to create. ... I don't know what I'm downvoted. This clearly works. The naive solution without macros would have MyType be a simple integer and New() has a switch statement. But it is easy to avoid that.
- pmr_ 12y ago
  You are being downvoted because the language comes with well-defined and specifically designed ways to customize allocation/deallocation. Your approach choses to ignore those facilities and even adds a runtime decision to code that absolutely has no need for it. You are reinventing the wheel and it is not even round.

gargantian 12y ago

I'm actually surprised virtualized page-zeroing isn't a memory controller feature at this point. With all of the things modern CPUs do or you, it seems crazy that everyone is running CPU threads that waste time and voltage to pump a zero page queue.

adwn 12y ago
The Mill [1] does/will do that: When memory is allocated, it is served directly be the cache, which implicitly zeroes the respective cache line (without involving the main memory). A similar mechanism zeroes a stackframe upon a function call (and function return, I think), which eliminates most attacks that exploit buffer-overflows. [1] http://millcomputing.com/docs/memory/ http://millcomputing.com/docs/memory/
- oso2k 12y ago
  So a Mill CPU can never do shared-memory process parallelization? Two or more processes accessing the same memory could be a hazard. Seems like it would suffer the same issue IA-64 has with parallelism. However, the conveyor belt analogy simplifies register spilling & related issues.
  - crest 12y ago
    Only if you are crazy enough to share stacks in which case you deserve what you get.
  - adwn 12y ago
    > So a Mill CPU can never do shared-memory process parallelization? Why not? The caches will still be coherent.
peterfirefly 12y ago
The Mill, if it ever gets built, does something like that. http://millcomputing.com/wiki/Memory#Implicit_Zero_and_Virtual_Zero http://millcomputing.com/wiki/Memory#Implicit_Zero_and_Virtu... "The big gain for this is that the OS doesn't have to explicitly zero out new pages, which would be a lot of bandwidth and time, and accesses to uninitialized memory only take the time of the cache and TLB lookups instead of having to do memory round trips."

deleted 12y ago

[deleted]

cbd1984 12y ago
> The article states that "relational databases" arose to conserve "rare" and "expensive" disk space. It seems that navigational databases, which relational databases largely replaced, would be even more sparing of disk space, which makes me think that claim is rather suspect. How about another explanation: Relational databases are to data what structured programming (using for loops and while loops and functions and local variables instead of, you know, not) is to code: It reduces the potential for error by, first, encouraging single-point-of-truth via normalization, and, second, encouraging people to make as many tables as possible automatically via queries which use relational algebra. In short, every table knows about one kind of thing. Everything your database knows about that kind of thing is in that one table. If you want to know more than one kind of thing at a time, you create a new table automatically with a query. Compare: Every function does one kind of thing. Everything your program knows about doing that kind of thing is in that function. If you want to do more than one kind of thing, you compose functions and let the details of flow control be handled automatically by the runtime.
deleted 12y ago
[deleted]