[HN Gopher] Memory Management Reference
___________________________________________________________________
Memory Management Reference
Author : medo-bear
Score : 68 points
Date : 2022-07-12 09:37 UTC (13 hours ago)
(HTM) web link (www.memorymanagement.org)
(TXT) w3m dump (www.memorymanagement.org)
| anewpersonality wrote:
| recently had to implement malloc in an interview, this would be
| handy
| Hirrolot wrote:
| Nice reference but with some strange bits:
|
| > Algebraic data types are usually represented using a heap.
| Because of their non-uniformity, algebraic data types are more
| difficult to scan.
|
| Using a heap??? We can represent ADTs using stack as well, that's
| what we usually do in C and Rust.
|
| Shameless plug: https://github.com/Hirrolot/datatype99 (a library
| of mine that generates type-safe ADTs for pure C99).
| whizzter wrote:
| This post seems related to the authors of MPS (1) that seems to
| be a general garbage-collector to use with various languages.
|
| Many GC'd languages really didn't bother with stack-allocating
| variable-size entities, and regardless of if they did then
| _precicely_ scanning the stack would be complicated without
| compiler help.
|
| If the compiler doesn't leave any info to the GC, then it can't
| know if it's scanning a pointer or a float and if your GC
| strategy relies on compacting memory (ie moving objects) then
| trying to guess between a float or a pointer can become fatal.
|
| (1) https://github.com/Ravenbrook/mps
| tomp wrote:
| The most depressing thing about memory management is that there's
| been 0 innovation in the past 10+ years, _and_ it seems like we
| 're fundamentally at a dead end where only tradeoffs exist.
|
| There are basically 3 options going forward:
|
| - manual memory management (C++, Rust) _" I can verify your code
| but you need to `unsafe` to do anything interesting"_
|
| - reference counting (Swift) _" I leak memory through cycles"_
|
| - tracing GC (Java, Go) _" I stop the world and trash your swap"_
|
| The rest is engineering (e.g. Go reduced the "stop-the-world"
| phase to _O(1)_ from _O(n)_ where _n_ is the size of memory)
| WJW wrote:
| Well first of all there is tons of research being done right
| now into linear type systems, which have the potential to
| statically verify a whole bunch of things that Rusts borrow
| checking still struggles with. It's a very hot field of CS
| research atm.
|
| I also think that you discount the amount of advancement that
| has been done in the development of pauseless GC. It's a shame
| that many of these are only available on the JVM (and sometimes
| only at a steep price), but I have no doubt the main ideas will
| eventually get adopted by other languages.
|
| But really there are so many unexplored niches. AFAIK no
| current architecture has hardware support for read/write
| barriers, having that would make pauseless GC much more
| feasible. Zig has been experimenting with letting people use
| custom memory allocators, but there are many more avenues there
| that have not been explored. Why not have a language feature
| for "this value lives outside GC management" similar to
| Haskells compact regions but more powerful? Nim has some cool
| ideas about mixing reference counting for most values and a
| more general GC for cycle breaking. Mixing GC and non-GC values
| is also still a seriously underexplored field IMO.
| cb321 wrote:
| Nim has for a long time had automatically managed `ref` as
| well as manually managed `ptr` which is similar to (perhaps
| directly inspired?) your last comment, and has several
| options for Auto Mem Mgmt.
| Hirrolot wrote:
| There's also an interesting programming language called Neut
| [1]:
|
| > A dependently-typed programming language with compile-time
| malloc/free determination.
|
| Also related "ASAP: As Static As Possible memory management"
| [2].
|
| I think most of the "innovation" you're talking about is
| happening in the programming language design field.
|
| [1] https://github.com/vekatze/neut [2]
| https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-908.pdf
| verdagon wrote:
| (Disclaimer: Vale lead here!)
|
| You might be interested in what we're working on with Vale, its
| core innovations happen to be around memory management.
|
| Some off the top of my head:
|
| * Generational references, for single-ownership memory safety
| without garbage collection, ref counting, or borrow checking.
| [0]
|
| * Higher RAII, a form of "linear typing" that lets us add
| parameters and returns to destructors, to enforce that if you
| do X, you won't forget to do Y. [1]
|
| * Regions, which could make it so we can eliminate most
| generation checks in Vale. If it catches on, it could also help
| other paradigms and get reference counting back into the fight.
| (Note, we aren't done with this one yet, it's about 3-8 weeks
| out) [2]
|
| Those are just a few off the top of my head, there are a lot of
| crazy ideas floating around there. I'm hoping they'll combine
| to form something like an easier more flexible Rust, because
| that's the holy grail of language design, to me at least.
|
| A few years ago, I was also pretty down about the state of
| memory innovation... it felt like not much had been discovered
| since borrow checking. I knew there _had_ to be something with
| its speed, but the flexibility of C++. Perhaps we found it!
|
| [0] https://verdagon.dev/blog/generational-references
|
| [1] https://verdagon.dev/blog/higher-raii-7drl
|
| [2] https://verdagon.dev/blog/zero-cost-refs-regions
| tomp wrote:
| I've been following Vale's progress with interest but AFAIK
| as of a few months ago, it's still vapourware.
|
| Excited to learn you're nearing an actual implementation
| though! Let's hope it's practical!
| verdagon wrote:
| If talking about regions and HGM, that's fair to say.
| Regions are further behind where I hoped because the latter
| stages are blocked on generics, and I had to take 8 months
| off a year ago because of some PTSD from work (long story).
|
| I acknowledge that these are excuses, and that these two
| features of Vale can reasonably be regarded as vaporware
| until we get them finished. We're over halfway done with
| regions, fingers crossed for September!
|
| For what it's worth, most of our innovations are actually
| complete and released. Generational References, Fearless
| FFI (minus sandboxing), and Higher RAII are all done and
| usable, and the Perfect Replayability proof-of-concept is
| finished as well. All these are in version 0.2, which can
| be downloaded at [0].
|
| And if you ever want to see what we're working on, we have
| a "What's been happening recently" on the roadmap page [1].
|
| Thanks for following along!
|
| [0] https://vale.dev/download
|
| [1] https://vale.dev/roadmap
| zozbot234 wrote:
| The real disclaimer should perhaps be that this stuff is
| something that's still being worked on wrt. production use,
| just like many other kinds of PL research. Once it's ready,
| Rust will probably be in a very good position to adopt these
| features.
| verdagon wrote:
| That would be pretty cool! I'm not sure Rust can support
| these features, though.
|
| * Generational References involve some pretty deep compiler
| support. One can implement something like it in Rust with a
| thread-local side table, but with >3x overhead compared to
| language-supported generational references.
|
| * Higher RAII requires that a language not treat
| destructors and panic handlers as the same thing.
| Unfortunately, Rust uses one function (drop) for both.
| Additionally, it would be a backwards-incompatible change;
| Rust generic parameters already assume a zero-arg drop() is
| available for all parameters, even though there's no trait
| bound declared for them.
|
| * Regions get most of the borrow checker's optimizing power
| with a fraction of the user complexity. Having both borrow
| checking and regions would just be adding complexity
| though, which defeats the purpose a bit.
|
| Still, there are a few other features of Vale that we're
| thinking of proposing to Rust, especially around
| concurrency, determinism, and better memory safety
| guarantees.
| avgcorrection wrote:
| Don't save the disclaimer for last.
| verdagon wrote:
| Happy to oblige, edited it upward. Hope your day is going
| well =)
| avgcorrection wrote:
| It is, and thanks!
| oddity wrote:
| Depends on how you define innovation.
|
| The hard truth is that there is no free lunch. We like to
| pretend we're using a Turing machine, but the moment you start
| caring about performance or memory limits, the abstraction
| breaks down and you realize that physics dictates that we have
| a finite state machine instead. This was "solved" about as well
| as it could be many years ago with however many billions were
| poured into GC R&D for all the people who don't care deeply
| about the limits, but nothing is going to magic away that
| fundamental trade-off unless we discover new physics.
|
| Every innovation since then has been about developing
| workarounds to deal with that trade-off in more or less
| sophisticated ways.
| kevin_thibedeau wrote:
| Nim has GC with controllable max time slices.
| olliej wrote:
| By your definition of what is "engineering" I feel like all
| improvements or changes are just engineering.
|
| Because you've described three classes:
|
| * No explicit runtime knowledge of whether a given object is
| alive
|
| * Explicitly tracking how many references there are to an
| object
|
| * Searching the program memory to see if there are references
| to an object that make it live
|
| I'm not sure there is another class of memory management that
| isn't one of these three?
|
| It's also somewhat unfair to rust - the static and parametric
| lifetime management _is_ new, and doesn't "need unsafe" to do
| anything interesting; and to tracing GCs modern GCs have
| developed ever more techniques to not be "stop the world"
| including parallel, iterative, lock free tracing, etc.
| tomp wrote:
| All of the ones you mentioned above still involve a stop-the-
| world phase, however brief.
|
| The keywords you're looking for are "fullya-concurrent" or
| "on-the-fly" GC, but I'm not aware of any production runtime
| with those.
| WJW wrote:
| Doesn't the JVM ecosystem have fully concurrent GC with the
| Azul C4 collector? It's not my favorite set of languages
| but I don't think we can realistically claim the JVM is not
| a production-ready runtime.
| tomp wrote:
| Yes, "pauseless" is another keyword I forgot to mention.
|
| Azul uses a read barrier which I guess makes it so slow
| that noone uses it (and the same ideas haven't made their
| way into JDK collectors). The previous version required
| hardware-supported read barrier, now AFAIK they _only_
| require a Linux kernel extension.
| vitiral wrote:
| I'm doing some pretty different things with civboot.org and
| http://github.com/vitiral/fngi, but most would consider them
| regressions instead of advancements.
|
| The goal is to have fragmentation-free memory managers that can
| work with minimal hardware support. This has limitations like
| block size (only 4k blocks allowed), but forces me to innovate.
| For instance, I'm planning on an "arena stack", where most
| functions simply use the arena on the top of the stack.
| Functions can reserve an arena on the arena-stack, call a
| function, then copy essential data and drop the arena, reducing
| fragmentation.
|
| Might not be the kind of ideas you were thinking, but I
| consider this simpler than the current abstractions which hide
| complexity.
| dang wrote:
| Related:
|
| _Memory Management Reference (2018)_ -
| https://news.ycombinator.com/item?id=22145544 - Jan 2020 (3
| comments)
|
| _Introduction to Memory Management (2018)_ -
| https://news.ycombinator.com/item?id=19354465 - March 2019 (30
| comments)
|
| _Memory Management Reference_ -
| https://news.ycombinator.com/item?id=16087689 - Jan 2018 (8
| comments)
|
| _The Memory Management Reference_ -
| https://news.ycombinator.com/item?id=8256469 - Sept 2014 (9
| comments)
|
| _Good stuff: memory management dot org_ -
| https://news.ycombinator.com/item?id=1223785 - March 2010 (9
| comments)
| bsedlm wrote:
| I've seen this website before but I forgot about it...
| hyperman1 wrote:
| I've always wondered why there is no API to tell the memory
| allocator to take some time to reorganize itself.
|
| E.g. a http server just processed a request and sent a response.
| Before it sits in the queue to pick up a next request, it could
| tell: Now is a great time to stop this thread if you really need
| to. Ditto a GUI processed an event.
|
| GC could do a minor collection there. Malloc/free could take or
| give back some chunks to a lower level or the OS.
|
| Java had System.gc() but it was more a 'take as much time as you
| want on every thread and go deep'. I am thinking more of 'Here is
| avtime limit of a few ms, reorganize this thread only'.
| williamcotton wrote:
| There's a concept of a memory arena... allocate a bunch of
| memory per frame/request ahead of time and the just increase a
| pointer when you need memory and then release everything at the
| end of the frame/request.
| vitiral wrote:
| You are confounding two subjects: a bump allocator and an
| arena.
|
| "just increase the pointer" is a bump allocator.
|
| An arena can be used with any allocator, not just bump
| allocators.
| foota wrote:
| I think there's two common usages of the term arena, I
| might call them homogenous and non homogenous. Is there
| much reason to use a non homogenous arena with something
| other than a bump allocator?
| oddity wrote:
| Most people just want an allocator that works reasonably well,
| and maintaining that expectation means not exposing too many
| details that you might be held accountable to. If you care
| deeply, there are usually alternatives.
|
| There's nothing really stopping systems from exposing a hint
| for controlling this, but usually the people who might care
| about it don't just want hints, but actual guarantees, and then
| you have to consider all the users who hint incorrectly (or
| correctly, but for a different system/version). So, the
| benefit/cost ratio is low.
|
| Integration of GC with thread scheduling was once an active
| area of research, but the world has mostly moved on (perhaps
| prematurely, but so goes).
| xenadu02 wrote:
| Thread-local compacting GCs already handle this. Requests tend
| to be served by a single thread and the GC dishes out memory
| from a thread-local pool to avoid contention. Server-side GCs
| can also be concurrent and avoid suspending threads as much as
| possible. If you aren't generating garbage that escapes the
| nursery generation they may basically never suspend threads or
| block at all.
|
| Arenas are a similar concept that work well in non-GC
| environments if you don't let objects allocated during a
| request escape to live beyond the request.
|
| Thread-local pools to satisfy allocations are also a well-known
| technique used in various allocators so your system's malloc
| might be doing this for you. It might also be able to
| efficiently collapse free lists which more or less behaves like
| an arena allocator when your request pipeline doesn't let
| allocations escape.
|
| In practical terms: most approaches generalize well enough that
| if you follow the rules you'd need to follow anyway you get the
| benefits without the drawbacks. In most of the remaining edge
| cases you get even better benefits by adopting other
| strategies. For example Unity uses C# which has a GC... but
| games shouldn't allocate on the game loop _anyway_ so GC vs ref
| counts vs malloc isn't very important compared to avoiding
| allocations altogether. Or if you already obey the rules you'd
| need for an arena allocator in your server then letting the GC
| or allocator deal with it might mean you can coalesce cleanup
| across multiple requests which may actually be better for
| performance anyway. And without manual arena management you
| don't risk problems if some esoteric edge case in the code
| needs to allocate something that will outlive that specific
| request.
| DonBarredora wrote:
| Amazing, thanks for sharing.
___________________________________________________________________
(page generated 2022-07-12 23:01 UTC)