7 ms·
Perceus: Garbage Free Reference Counting with Reuse [pdf]
- fwsgonzo 6y agoThat seems like quite the achievement! I'm actively looking for a high-level language to put on top of an enterprise product, but it has to either transpile to C or integrate well with a C standard library (unfortunately). It's not a 100% requirement, as Rust still works because I can override the global allocator. Right now I'm looking towards Nim, which has some pros and cons. I'm still not good enough to build complex APIs with it, but it's really easy to integrate. Nim feels like Python for systems programming.
- kitd 6y agoD has a similar feel to Nim, and excellent C integration. The GC is optional and it has good meta programming capabilities.
- RcouF1uZ4gsC 6y ago> The GC is optional A big issue is that while GC is technically optional, a lot of the standard library depends on GC (at least last time I checked) and using D without those parts of the standard library is much less ergonomic.
- mhh__ 6y agoThis is increasingly not the case but there is also mir, which is effectively a smaller standard library along with a lot of extremely fast numerical code
- idclip 6y agoD/haskell/nim are great
- iainctduncan 6y agoYou might want to check out the various Schemes that are designed to work well with C, either by compiling to it, or by being in an embedded interpreter. I'm doing that with S7 for computer music and loving it. Compile to C include Gambit, Gerbil, and Chicken, embed include Guile, S7, Gambit. (And others I'm forgetting).
- elcritch 6y ago+1 for Nim in that use case. The core system and std library is very flexible, so it “ports” easily. It’s been used in a few games too. I’m using it for embedded currently after a few months and while there are a few edge cases overall it’s been stable for me. With C interfaces you’ll want to add some code to make it more idiomatic, here’s my try for i2c code on esp-idf: https://github.com/elcritch/nesper/blob/e1d9f7ba13eebe45aea43c08fe839dd0544927c2/src/nesper/i2cs.nim#L65 https://github.com/elcritch/nesper/blob/e1d9f7ba13eebe45aea4...
- vnorilo 6y agoThis paper is worth reading; an implementation detail that may be useful to many is their use of reference counting: negative refcount is used to indicate thread-shared objects. Releasing objects goes fast path with a single branch when refcount > 1, performing a non-atomic decrement. The slow path handles freeing memory, atomic counter mutation, and a sticky object flag encoded as overflow-by-one.
- solarexplorer 6y agoVery nice, could this be used in Apple's ecosystem? (which is based on reference counting as well?)
- ramshanker 6y agoI imagine, even C compilers will soon start supporting automatic ref-counted version of compilation for old codes.
- pjmlp 6y agoFirst they would need to finally adopt one of the many available secure string libraries.
- Jweb_Guru 6y agoWhile it does depend on the C project, in general it's not the sort of language you can really retrofit pervasive refcounting into automatically. Even if it worked, I think the set of people currently using C who would be willing to switch to such a system, but hadn't already moved to another language or started using Bohm, must be quite small at this point.
- moonchild 6y agoTracing GC involves unpredictable pauses. RC does not (or, at least, has a much lower incidence rate).
- Jweb_Guru 6y agoYes, but (conservative) tracing GC doesn't require invasively updating the contents of all your data structures, in exchange for not actually capturing all pointer relationships. In C, it's often not really possible or even safe to do that, so I don't see how such a method could work automatically except in very restricted settings.
- yencabulator 6y agoReference counter drop can lead to an unpredictable amount of freeing. Consider dropping the last reference to the root of a varying-size large tree.
- parley 6y agoThis does seem very interesting, at first glance. One thought: > These “scoped life-time” reference counts are used by the C++ shared_ptr⟨T⟩(calling the destructor at the end of the scope), Rust’s Rc⟨T⟩(using the Drop trait), and Nim (using a finally block to call destroy) So Rust's non-lexical lifetimes doesn't remedy this? Meaning the actual drop of xs needing to occur at the end of the example in the beginning of section 2.2, as opposed to right after the map. I would have thought that ys borrows nothing from xs, and the drop can be inserted right after map? Perhaps it's too early in the morning for thinking for me.
- sanxiyn 6y agoNo, Rust's non-lexical lifetime does not change when things are dropped at all. It is purely a compile time feature with no run time effects.
- RobLach 6y agoThis is excellent work and Microsoft Research continues to leave a positive impression on me by reason of what they're focusing their energy on.
- hardwaresofton 6y agoMicrosoft Research has a great stable of researchers -- could you imagine just casually having Leslie Lamport being an email away while working on some distributed systems problem/design? Or being able to pull on This might be one of the only benefits to monopolistic presences -- the amount of great minds in the same place, set free to mingle and create can produce amazing results when a benevolent sponsor exists and it's tunnel-visioned on profit. I'm quite cynical towards Microsoft but I am very grateful that they publish at least some of their papers/insights and their links (to existing papers) generally don't die. [0]: https://www.microsoft.com/en-us/research/people/ https://www.microsoft.com/en-us/research/people/
- RcouF1uZ4gsC 6y agoIt seems rich monopolies are good at having great research labs. AT&T Bell Labs and Xerox PARC come to mind.
- Iv 6y agoI was surprised when reading Keynes texts where he criticized capitalism, seeing him counting the concentration of capital as one of the pros of the system: it allows efforts that no one else could take on.
- deleted 6y ago[deleted]
- pstch 6y agoJava being faster on nqueens shows an interesting result : GCs can actually make code "faster", by moving some work to another core. It's possible this could still be done with the described approach, but it looks much more difficult.
- djwatson24 6y agoUnless I am misreading their graph, Java beats neither c++ nor koka in time or rss.
- Bootvis 6y agoI read them the same. Now it is interesting that C++ is so much slower on cfold.
- pstch 6y agoOops, it was not on nqueens, but on deriv. > Finally,Java performs best on this benchmark; we can see whilerunning the benchmark that it can run the G1 collectorfully concurrent on another core.
- christophilus 6y agoThis is impressive. I wonder if any language that used these techniques would also have to use such a rigorous effect system. It seems so. Their implementation requires annotations on all functions which are effectful (throw exceptions, log to the console, etc). What wasn’t clear to me was whether or not the callers of those functions also need to be annotated, but I presume they do. If so, that’s a pretty tedious limitation. While I like explicitness, changing the signature of a deep, oft-called function (e.g. to add temporary debug logging) requires changing a lot of other code.
- jules 6y agoI don't think you need an effect system. You just need to take care to correctly fiddle with some reference counts when an exception traverses your stack frame. You already need to do that in other reference counted systems. After all, if an exception traverses your stack frame you need to decrement the reference counts of local variables. Whether or not you have checked exceptions or checked effects seems orthogonal to me. What matters is the implementation of those effects.
- com2kid 6y agoCould type inference be used to automatically propagate such annotations? And then potentially be hooked up to a prettier plugin to adf explicit annotations if desired.
- Jweb_Guru 6y agoI don't think an explicit effect system is required to implement most (maybe all?) of the optimizations. Actually I think these techniques are probably applicable to many strict, mostly-functional languages with few to no cycles or mutable references. In fact, they cite Lean as their inspiration for many of these techniques.
- Someone 6y agoI would think that, if the compiler can check that the annotations are correct, it also can generate them if none are given (one way to do that: ‘just’ generate any possible combination of annotations, check which are correct, and pick the minimal set. Of course, a production-level compiler would use a faster algorithm) If so, you still might have to annotate some library functions that are implemented outside the language, but that would be it. The annotations are there for the programmer as, without them, it would be hard to keep track of which of your functions are pure, which might throw, etc.
- djwatson24 6y agoCool to see explicit annotations for how to make rc fast when you have access to the ir. But doesn’t solve some major issues, like cycle collection: “ In practice, mutable references are the main way to con- struct cyclic data. Since mutable references are uncommon in our setting, we leave the responsibility to the programmer to break cycles by explicitly clearing a reference cell that may be part of a cycle. ”
- studius 6y agoconst is really popular in JS... (i.e. could they surreptitiously be taking on Orinoco?)
- djwatson24 6y agoI don’t think const or non const is the main issue- some data structures just require cycles like graphs or circular linked lists.
- studius 6y agoI supposed you could construct as dynamic and then make it constant? I wonder why that feature isn't seen in common languages, even though I know it sounds crazy.
- vnorilo 6y agoClojure has transient mutable collections that are designed to become persistent once "complete". [1] Some systems have made use of using reference count of one (unique owner) as permission to mutate, something that TFA generalizes as memory reuse. 1: https://clojure.org/reference/transients https://clojure.org/reference/transients
- Jweb_Guru 6y agoI don't disagree, but I also suspect that a very large number of real world JavaScript applications have few to no application-induced cycles. I might even go further and say this extends beyond JavaScript--the most common reason I even define recursive data structures in a language like Rust is for AST-like data that almost invariably forms a tree.