10 ms·

When the memory allocator works against you

89 points by bostik 10y ago

quickben 10y ago
>"I hadn’t optimized for memory use in the first place." It is git, it is made to grow and get into billions of string comparisons. Anyways... C/c++ would have probably been a better language for his problem. Simply prealocate as much as needed as a working buffer and eliminate the need to profile libc and patch your interpreter altogether.
- Kenji 10y ago
  I concur. If the memory allocator causes problems and you use a language with managed memory/a garbage collector, you're doing something wrong.
  - Filligree 10y ago
    An aggressive, copying garbage collector would have eliminated this problem from the start. People often argue that GCs have unavoidable overhead, but it's bounded overhead; they defragment your program with every GC cycle.
    - Kenji 10y ago
      GC does have unavoidable overhead, in particular, it makes the execution times of your binary extremely unstable and high-variance. Not to mention, it has no idea how your program uses memory, such that it is bound to use a generic approach while with manual management, you can get real and high performance.
      - pg314 10y ago
        > it makes the execution times of your binary extremely unstable and high-variance. Not necessarily, it depends on your allocation patterns. The same can be said for using malloc. > Not to mention, it has no idea how your program uses memory, such that it is bound to use a generic approach Ditto for malloc. > with manual management, you can get real and high performance. Using a GC does not mean you can't manually manage allocations. E.g. say you are allocating and deallocating a lot of Point objects. You keep a free list of Point objects that you can recycle. If you need a Point, you first see if there are any in the free list. If so, you pop the first one off the list and reuse it. Otherwise you allocate a new one. When you're done with a Point, you push it on the free list.
        jstimpfle 10y ago
        >> Not to mention, it has no idea how your program uses memory, such that it is bound to use a generic approach > Ditto for malloc. malloc != manual management > Using a GC does not mean you can't manually manage allocations. E.g. say you are allocating and deallocating a lot of Point objects... But that's not using a GC. It's manual memory management.
        buzzybee 10y ago
        That's aggressively missing the point. If you design the program architecture around manual memory techniques, the runtimes are stable even in a GC. If you use malloc willy-nilly throughout core algorithms, your runtimes become unpredictable.
        jstimpfle 10y ago
        But my point was simply that you can't defend GC by contrasting to manual management, if you do manual management. > If you use malloc willy-nilly throughout core algorithms, your runtimes become unpredictable. First, where did I say "use malloc willy-nilly"? Second, do you have experience with that? I haven't much, but I haven't heard your claim before. Of course "willy-nilly" should not be done with real-time constraints. But I have written a substantial algorithmic program (no RT constraints) in that style when I didn't know better, and it was very well performing. (probably glibc's malloc was optimized for my allocation patterns). The main problem I see with that style is that each malloc has memory overhead, and that it leads to unmaintainable code.
        Kenji 10y ago
        Actually, to address realtime constraints... In my job, I work on systems with realtime constraints and even in less critical parts (latency of ~100 microseconds is still acceptable) we had to eliminate all malloc calls. Mostly because malloc on our platform essentially acquires one big lock for memory operations and if some other process has that lock, you get nasty delays or even priority inversions. Allocate a big chunk beforehand, preferrably in the form of ring buffers, and then operate on these if you need precise timing and performance.
      - mgottein 10y ago
        I personally believe one of the biggest reasons for the popularity of managed code is GC. Manual memory management is pretty hard to get right, even the C++ stl offers reference counted pointers as a form of automatic memory management
        dbaupp 10y ago
        I think that is a rather common belief... "Managed" is exactly referring to automatic memory management meaning the defining feature of the category is literally GC.
        jstimpfle 10y ago
        Wikipedia disagrees. "Managed code is computer program source code that requires and will execute only under the management of a Common Language Runtime virtual machine, typically the .NET Framework, or Mono. The term was coined by Microsoft."
        dbaupp 10y ago
        Huh. By that definition Java isn't managed, which seems to be missing the point and not as nearly useful as a broad category like everyone outside the Microsoft ecosystem uses it. That said, even if "CLR" is sensibly replaced with "CLR, JVM or similar", it does seem like I have the etymology/definition wrong, thanks.
        jstimpfle 10y ago
        Yes, I also think of Java as "managed". But the common idea of "managed" seems to be more than only "garbage collected".
- glandium 10y ago
  Author here. FWIW, git-cinnabar is written in python because it uses the mercurial code to talk to mercurial servers, and the mercurial code is in python. Well, that was true when it was first released, but recent versions have gained "native" support to talk to mercurial servers (where a helper program written in C does the talking[1]), although the mercurial code is still used to read bundle2[2] data that comes from the mercurial server, even in that case (that is, only bundle1 is supported without using mercurial code). I'm moving more and more things to the helper with the ultimate goal of not having any python code left. 1. https://glandium.org/blog/?p=3648 https://glandium.org/blog/?p=3648 2. https://www.mercurial-scm.org/wiki/BundleFormat2 https://www.mercurial-scm.org/wiki/BundleFormat2
rini17 10y ago
How about trying pypy? It has different GC/memory allocator and the 2.7-compatible branch is pretty much drop-in replacement (Unless you need something like PyQt).
crististm 10y ago
People never learn. News at eleven. Just the other day was reading N. Wirth objecting on using a resource lavishly just because it was cheap. And just now, in the same front page of HN, some guy wants programmers to stop calling themselves engineers because they aren't. Well, let's build a bridge using all the iron we can get our hands on (iron is very cheap you know); or even better, let's use all the RAM in the computer with this program of ours.
- 0xcde4c3db 10y ago
  It's also a lot of fun when someone gets the bright idea of "oh, we'll allocate until we have 75% of RAM and then stop; that will keep us from swapping". Which isn't so terrible until somebody installs a second program using that strategy.
  - crististm 10y ago
    My favourite these days is Linux OOM killer. For some people it's just right to randomly kill a process instead of rejecting the current request. My mind gets a blue-screen every time I'm contemplating this issu.,....ds.fsd... :) edit: https://discuss.96boards.org/t/yocto/576 https://discuss.96boards.org/t/yocto/576
    - SomeStupidPoint 10y ago
      Wait, what? Memory allocation "doesn't fail" so they kill a random program? Can someone link me to an explanation of this?
      - cturner 10y ago
        "Memory allocation "doesn't fail"" That's not quite it. But it does deserve a double-take. When you request memory, it generally works out fine. But it doesn't actually give you a lock on the pages you need until you request those pages. This leads to weird situations where memory is oversubscribed. When this happens the OS casts one of your processes into the rift. Google for "oom killer". To me this sounds insane - a basic breach in the contract of malloc. However, it's possible that this is one of those situations that involves a complex tradeoff that you won't grok until you've been the guy building it. It would be interesting to know what other OSs do. Something that is annoying: as far as I know there is no signal that fires when this happens. Instead, you scrape logs to learn about it. Whereupon you will reboot the box, because you no longer trust its state. You can get a callback when this happens if you use systemtap. In practice it's less of a problem than you'd think. If you care about the thing you're building, you will have made it host-independent. From the perspective of production software, there's no difference between a rifted process and a motherboard death. If you're using sockets as your IPC mechanism, it doesn't matter why the process died, just that it did.
__s 10y ago
ITT: people being snide about scripting languages over a post digging into a glibc malloc mishap
- Kenji 10y ago
  Did he really find a bug in glibc malloc? He didn't write that. This sounds like a bug in the python runtime and possibly in the offending program itself.
  - malisper 10y ago
    I don't fully understand the post, but I don't think the author found a bug anywhere. The main discovery the author made was that CPython uses its own allocator on top of memory allocated by mmap. This leads to a difference between the reported allocated memory by malloc and the memory used by the program. The author still hasn't discovered a root cause for the large amounts of memory allocated.
    - glandium 10y ago
      Author here. The last graph actually shows that the problem still happens with CPython's allocator disabled. Also, to clarify, the amount of memory allocated is actually decreasing (in-use bytes), while the memory allocator requests more and more memory from the system (system bytes), presumably because of fragmentation.
      - malisper 10y ago
        I see. I thought system bytes included the mmaped block of memory (the docs for malloc_stats explicitly say it does not) and I thought the last graph was a demonstration of why the Python memory allocator was necessary.
      - Kenji 10y ago
        >The last graph actually shows that the problem still happens with CPython's allocator disabled. Excuse my ignorance, but couldn't it still be a problem of the python runtime? I.e. they use malloc wrong, etc?
draw_down 10y ago
Good thing you didn't optimize prematurely ;)
bogomipz 10y ago
The author states: >“Import manifest” phase (which, in fact, allocates and frees increasingly large buffers for each manifest, as manifests grow in size in the mozilla-central history)." I am not familiar with the reference of a "manifest" or importing them at least not in the context of memory allocation. Can someone shed some light on this? Also right after the author states? >"To put the theory at work, I patched the python interpreter again, making it use malloc() instead of mmap() for its arenas." If I understand correctly the author is trying to remove the possibility of entanglement but doesn't the malloc() glibc library routine translate into an mmap() system call? I am not sure how that would help disambiguate memory allocators then.
- eternalban 10y ago
  > "Import manifest" phase ... in the context of memory allocation [+]. +of git operations.
  - bogomipz 10y ago
    Sorry, I don't understand your reply. Could you elaborate?
    - eternalban 10y ago
      A manifest is an element of a Git repository. Importing a manifest is a git operation. So OP is looking at memory patterns per distinct git ops.
      - bogomipz 10y ago
        I see, that makes perfect sense. I'm not sure how I missed that, thanks.
- jwilk 10y ago
  https://www.mercurial-scm.org/wiki/Manifest https://www.mercurial-scm.org/wiki/Manifest

89 points by bostik 10y ago

>"I hadn’t optimized for memory use in the first place." It is git, it is made to grow and get into billions of string comparisons. Anyways... C/c++ would have probably been a better language for his problem. Simply prealocate as much as needed as a working buffer and eliminate the need to profile libc and patch your interpreter altogether.

Kenji 10y ago
I concur. If the memory allocator causes problems and you use a language with managed memory/a garbage collector, you're doing something wrong.
- Filligree 10y ago
  An aggressive, copying garbage collector would have eliminated this problem from the start. People often argue that GCs have unavoidable overhead, but it's bounded overhead; they defragment your program with every GC cycle.
  - Kenji 10y ago
    GC does have unavoidable overhead, in particular, it makes the execution times of your binary extremely unstable and high-variance. Not to mention, it has no idea how your program uses memory, such that it is bound to use a generic approach while with manual management, you can get real and high performance.
    - pg314 10y ago
      > it makes the execution times of your binary extremely unstable and high-variance. Not necessarily, it depends on your allocation patterns. The same can be said for using malloc. > Not to mention, it has no idea how your program uses memory, such that it is bound to use a generic approach Ditto for malloc. > with manual management, you can get real and high performance. Using a GC does not mean you can't manually manage allocations. E.g. say you are allocating and deallocating a lot of Point objects. You keep a free list of Point objects that you can recycle. If you need a Point, you first see if there are any in the free list. If so, you pop the first one off the list and reuse it. Otherwise you allocate a new one. When you're done with a Point, you push it on the free list.
      - jstimpfle 10y ago
        >> Not to mention, it has no idea how your program uses memory, such that it is bound to use a generic approach > Ditto for malloc. malloc != manual management > Using a GC does not mean you can't manually manage allocations. E.g. say you are allocating and deallocating a lot of Point objects... But that's not using a GC. It's manual memory management.
        buzzybee 10y ago
        That's aggressively missing the point. If you design the program architecture around manual memory techniques, the runtimes are stable even in a GC. If you use malloc willy-nilly throughout core algorithms, your runtimes become unpredictable.
        jstimpfle 10y ago
        But my point was simply that you can't defend GC by contrasting to manual management, if you do manual management. > If you use malloc willy-nilly throughout core algorithms, your runtimes become unpredictable. First, where did I say "use malloc willy-nilly"? Second, do you have experience with that? I haven't much, but I haven't heard your claim before. Of course "willy-nilly" should not be done with real-time constraints. But I have written a substantial algorithmic program (no RT constraints) in that style when I didn't know better, and it was very well performing. (probably glibc's malloc was optimized for my allocation patterns). The main problem I see with that style is that each malloc has memory overhead, and that it leads to unmaintainable code.
        Kenji 10y ago
        Actually, to address realtime constraints... In my job, I work on systems with realtime constraints and even in less critical parts (latency of ~100 microseconds is still acceptable) we had to eliminate all malloc calls. Mostly because malloc on our platform essentially acquires one big lock for memory operations and if some other process has that lock, you get nasty delays or even priority inversions. Allocate a big chunk beforehand, preferrably in the form of ring buffers, and then operate on these if you need precise timing and performance.
    - mgottein 10y ago
      I personally believe one of the biggest reasons for the popularity of managed code is GC. Manual memory management is pretty hard to get right, even the C++ stl offers reference counted pointers as a form of automatic memory management
      - dbaupp 10y ago
        I think that is a rather common belief... "Managed" is exactly referring to automatic memory management meaning the defining feature of the category is literally GC.
        jstimpfle 10y ago
        Wikipedia disagrees. "Managed code is computer program source code that requires and will execute only under the management of a Common Language Runtime virtual machine, typically the .NET Framework, or Mono. The term was coined by Microsoft."
        dbaupp 10y ago
        Huh. By that definition Java isn't managed, which seems to be missing the point and not as nearly useful as a broad category like everyone outside the Microsoft ecosystem uses it. That said, even if "CLR" is sensibly replaced with "CLR, JVM or similar", it does seem like I have the etymology/definition wrong, thanks.
        jstimpfle 10y ago
        Yes, I also think of Java as "managed". But the common idea of "managed" seems to be more than only "garbage collected".
glandium 10y ago
Author here. FWIW, git-cinnabar is written in python because it uses the mercurial code to talk to mercurial servers, and the mercurial code is in python. Well, that was true when it was first released, but recent versions have gained "native" support to talk to mercurial servers (where a helper program written in C does the talking[1]), although the mercurial code is still used to read bundle2[2] data that comes from the mercurial server, even in that case (that is, only bundle1 is supported without using mercurial code). I'm moving more and more things to the helper with the ultimate goal of not having any python code left. 1. https://glandium.org/blog/?p=3648 https://glandium.org/blog/?p=3648 2. https://www.mercurial-scm.org/wiki/BundleFormat2 https://www.mercurial-scm.org/wiki/BundleFormat2

rini17 10y ago

How about trying pypy? It has different GC/memory allocator and the 2.7-compatible branch is pretty much drop-in replacement (Unless you need something like PyQt).

crististm 10y ago

People never learn. News at eleven. Just the other day was reading N. Wirth objecting on using a resource lavishly just because it was cheap. And just now, in the same front page of HN, some guy wants programmers to stop calling themselves engineers because they aren't. Well, let's build a bridge using all the iron we can get our hands on (iron is very cheap you know); or even better, let's use all the RAM in the computer with this program of ours.

0xcde4c3db 10y ago
It's also a lot of fun when someone gets the bright idea of "oh, we'll allocate until we have 75% of RAM and then stop; that will keep us from swapping". Which isn't so terrible until somebody installs a second program using that strategy.
- crististm 10y ago
  My favourite these days is Linux OOM killer. For some people it's just right to randomly kill a process instead of rejecting the current request. My mind gets a blue-screen every time I'm contemplating this issu.,....ds.fsd... :) edit: https://discuss.96boards.org/t/yocto/576 https://discuss.96boards.org/t/yocto/576
  - SomeStupidPoint 10y ago
    Wait, what? Memory allocation "doesn't fail" so they kill a random program? Can someone link me to an explanation of this?
    - cturner 10y ago
      "Memory allocation "doesn't fail"" That's not quite it. But it does deserve a double-take. When you request memory, it generally works out fine. But it doesn't actually give you a lock on the pages you need until you request those pages. This leads to weird situations where memory is oversubscribed. When this happens the OS casts one of your processes into the rift. Google for "oom killer". To me this sounds insane - a basic breach in the contract of malloc. However, it's possible that this is one of those situations that involves a complex tradeoff that you won't grok until you've been the guy building it. It would be interesting to know what other OSs do. Something that is annoying: as far as I know there is no signal that fires when this happens. Instead, you scrape logs to learn about it. Whereupon you will reboot the box, because you no longer trust its state. You can get a callback when this happens if you use systemtap. In practice it's less of a problem than you'd think. If you care about the thing you're building, you will have made it host-independent. From the perspective of production software, there's no difference between a rifted process and a motherboard death. If you're using sockets as your IPC mechanism, it doesn't matter why the process died, just that it did.

__s 10y ago

ITT: people being snide about scripting languages over a post digging into a glibc malloc mishap

Kenji 10y ago
Did he really find a bug in glibc malloc? He didn't write that. This sounds like a bug in the python runtime and possibly in the offending program itself.
- malisper 10y ago
  I don't fully understand the post, but I don't think the author found a bug anywhere. The main discovery the author made was that CPython uses its own allocator on top of memory allocated by mmap. This leads to a difference between the reported allocated memory by malloc and the memory used by the program. The author still hasn't discovered a root cause for the large amounts of memory allocated.
  - glandium 10y ago
    Author here. The last graph actually shows that the problem still happens with CPython's allocator disabled. Also, to clarify, the amount of memory allocated is actually decreasing (in-use bytes), while the memory allocator requests more and more memory from the system (system bytes), presumably because of fragmentation.
    - malisper 10y ago
      I see. I thought system bytes included the mmaped block of memory (the docs for malloc_stats explicitly say it does not) and I thought the last graph was a demonstration of why the Python memory allocator was necessary.
    - Kenji 10y ago
      >The last graph actually shows that the problem still happens with CPython's allocator disabled. Excuse my ignorance, but couldn't it still be a problem of the python runtime? I.e. they use malloc wrong, etc?

draw_down 10y ago

Good thing you didn't optimize prematurely ;)

bogomipz 10y ago

The author states: >“Import manifest” phase (which, in fact, allocates and frees increasingly large buffers for each manifest, as manifests grow in size in the mozilla-central history)." I am not familiar with the reference of a "manifest" or importing them at least not in the context of memory allocation. Can someone shed some light on this? Also right after the author states? >"To put the theory at work, I patched the python interpreter again, making it use malloc() instead of mmap() for its arenas." If I understand correctly the author is trying to remove the possibility of entanglement but doesn't the malloc() glibc library routine translate into an mmap() system call? I am not sure how that would help disambiguate memory allocators then.

eternalban 10y ago
> "Import manifest" phase ... in the context of memory allocation [+]. +of git operations.
- bogomipz 10y ago
  Sorry, I don't understand your reply. Could you elaborate?
  - eternalban 10y ago
    A manifest is an element of a Git repository. Importing a manifest is a git operation. So OP is looking at memory patterns per distinct git ops.
    - bogomipz 10y ago
      I see, that makes perfect sense. I'm not sure how I missed that, thanks.
jwilk 10y ago
https://www.mercurial-scm.org/wiki/Manifest https://www.mercurial-scm.org/wiki/Manifest