7 ms·
Borrow Checking, RC, GC, and the Eleven () Other Memory Safety Approaches
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- MarkMarine 3y agoThis is interesting but exhausting to read. I get the joke but come on, after the first few of these can I just read the information in line.
- deleted 3y ago[deleted]
- fwlr 3y agoThe explanation for the the chosen style is given near the end of the piece: the author says that they’ve found ‘imagining a better solution already exists and is just out of reach’ (my paraphrase) is an effective way to break the mental habit of assuming we’ve discovered everything there is to know about a problem.
- noelwelsh 3y agoAgreed. I don't really have time for informational articles that don't just present their information in a straight-forward way.
- fiddlerwoaroof 3y agoI think it’s better to view reference counting and gc as two kinds of garbage collection: https://courses.cs.washington.edu/courses/cse590p/05au/p50-bacon.pdf https://courses.cs.washington.edu/courses/cse590p/05au/p50-b...
- jdougan 3y agoThat is an excellent paper. One of those things that is obvious in hindsight, but no one wrote it down clearly before.
- _a_a_a_ 3y agoIMO it's not remotely obvious. Not to me anyway.
- vlovich123 3y agoIt’s obvious that is the same problem. It’s not obvious that it’s a more continuous linear tradeoff between the approaches
- dataflow 3y agoI have to disagree? Lumping them together is like lumping together formal verification with machine learning... Two fundamental characteristics of garbage collection (in pretty much every programmer's experience) are that (a) it can handle cycles (read: more general programs), and (b) it does not provide hard performance guarantees in the general case. Reference counting is literally the opposite, and that's exactly what people love about it.
- Animats 3y ago> "Linear reference counting is an elusive concept, where we can completely eliminate the counter integer, and do all of the reference counting at compile time." Right. I've occasionally thought about that for Rust, as a way to do back references. You can have an Rc owning an object, which can own another object, which can have a weak RC reference back to the original. This allows you to find an object's owner when needed, so you can do inheritance-like things when you need to. The single-ownership and dangling-pointer checks are made at run time and will panic if they fail. Now, the question is, can you statically check access behavior and determine that those panics will never occur? If you can, you can eliminate the reference counts and checks. That looks 1) possible, and 2) a PhD thesis sized problem.
- pirocks 3y agoYou may enjoy: https://docs.rs/static-rc/latest/static_rc/ https://docs.rs/static-rc/latest/static_rc/
- KRAKRISMOTT 3y agoMost of the fancier runtime-less non-GC techniques fail when it comes to graph data structures (or even linked lists) without a tremendous amount of upfront work from the programmer.
- hi-v-rocknroll 3y agoAre you just trying to throw shade on Rust? https://doc.rust-lang.org/std/collections/struct.LinkedList.html https://doc.rust-lang.org/std/collections/struct.LinkedList.... > NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache. https://docs.rs/petgraph https://docs.rs/petgraph 78 M downloads
- neonsunset 3y agoThe language the development of which this blog discusses is worth checking out too: https://www.uiua.org https://www.uiua.org It is an interesting APL successor I was planning to learn after getting current projects out of the way.
- dash2 3y agoI thought the language was https://vale.dev https://vale.dev?
- neonsunset 3y agoOh. You are, of course, right. Damn pattern recognition, the logo looks almost the same if you squint!
- deleted 3y ago[deleted]
- zozbot234 3y agoIt's weird to see no mention in this post of separation logic, which would seem to provide a basic, general foundation for most of these techniques if perhaps not all of them. For instance, the RustBelt paper gives a description of Rust borrow checking that can arguably be understood as relying on some form of separation logic.
- hi-v-rocknroll 3y agoNever free and periodically crashing by OOM killer is rarely used but can be useful in limited circumstances. There are some shops that arbitrarily kill any worker over X hours old under the hypothesis that a memory leak is present or probably present.
- littlestymaar 3y ago> Never free AFAIK it's how you get memory safety in missile guidance software: you just have to put enough RAM on the board so it never run out of memory before the end of its flight. Edit: TFA just talks about that in the “never free”
- swiftcoder 3y agoI'm aware of several Java service backends that just disable the GC entirely and take a once-a-day crash as a cost of doing business. As long as you have enough nodes that the crashes aren't correlated, your overall service can maintain decent uptime
- kibwen 3y ago> And as it turns out, reference counting can be blended with immutable region borrowing to greatly reduce its cache misses and make it data-race safe, something no language has done yet. Rust prevents data races, so I'm not sure what this is referring to.
- EricRiese 3y agoJava supports the never free strategy with Epsilon GC
- cryptonector 3y agoA compile-time reference counting and reference count ellision scheme would be awesome for jq. It could only happen with an escape hatch to reference counting. We had an interesting contribution that added a piece of this, but meant for libjq-using applications, not for jq itself.
- cryptonector 3y agoTFA is pretty awesome, not least because of all the links. I'm going to be reading for a while.
- habitue 3y agoI am surprised that call stacks aren't mentioned. The call stack is a great way to free up memory that's no longer being used by a function. Maybe it was too obvious to include?
- ReleaseCandidat 3y agoThat doesn't solve the "use after free" problem, so not memory safe (as long as not combined with something else).
- EVa5I7bHFq9mnYK 3y agoWhat is the "use after free" problem? A function leaves the computed result on the stack or modifies data higher in the stack. There are no pointers, nothing to free.
- deleted 3y ago[deleted]
- habitue 3y agoIf you return a pointer from a function that points to a stack local variable, it'll be invalid. Generally this is easy ish to detect though.
- EVa5I7bHFq9mnYK 3y agoIn this stack only scheme there are no pointers. Function leaves its returned data at the top of the stack.
- patrakov 3y agohttps://archive.md/uvwAC https://archive.md/uvwAC
- pizza234 3y agoIsn't the "regions" approach similar/same in principle, as Rust's memory model? A region's model is described as: > Pony's iso keyword: an iso'd object (and its contents) are only reachable from your pointer; nobody else points at that object or anything the object contains [...] we can "temporarily open" an isolated subgraph for a given scope, and afterward it would still be properly isolated. In Rust, AFAIR, one gets a mutable reference to an object, and the borrower can independently operate on its fields (subgraphs), while the root mutable reference can't be accessed from anything else other than the borrower.
- kovacs_x 3y agowhat about "self freeing" pointers? you allocate and must / are extending its lifetime all the time or else it frees itself! very predictable behaviour of memory collection. you get pointer and keep it allocated by "extending" its lifecycle.
- EVa5I7bHFq9mnYK 3y agoEarly Fortran worked in a way that every function was allocated a global static memory area for its arguments, variables and the result. No stack, no heap, no worries.
- kernal 3y agoBest part >I was once working with a customer who was producing on-board software for a missile. In my analysis of the code, I pointed out that they had a number of problems with storage leaks. Imagine my surprise when the customers chief software engineer said "Of course it leaks". He went on to point out that they had calculated the amount of memory the application would leak in the total possible flight time for the missile and then doubled that number. They added this much additional memory to the hardware to "support" the leaks. Since the missile will explode when it hits its target or at the end of its flight, the ultimate in garbage collection is performed without programmer intervention.