New Garbage Collector
wiki.luajit.org
wiki.luajit.org
* A generational GC, preferably bump-allocating so that we can win on allocation-heavy workloads.
* A non-thread-safe GC, because all GC'd data is local to a single task in Rust (and we enforce this in the type system).
* A precise GC, because (a) we don't want accidental or malicious leaks due to misinterpreting non-pointers as pointers; and (b) because we need precise GC metadata to clean up shared data and run destructors when tasks fail.
* An incremental GC, because minimizing pause times is absolutely critical for browsers.
* A non-copying GC, because LLVM doesn't currently support copying GC satisfactorily (i.e. when allowing pointers to live in registers). Fixing this would require a significant portion of all target code to be rewritten.
Also of particular interest is the ability for individual allocation sites to choose to bump allocate only, in the interests of performance (but at the expense of fragmentation). This could potentially allow Rust programmers to fine-tune their allocation behavior and trade performance for fragmentation when it makes sense to do so.
Very cool, and I'll be sure to keep an eye on this.
This is a shame that this is so badly documented. I stumbled upon this way after having coded the whole code generator of my Z3 project (https://github.com/raph-amiard/Z3 - Ocaml bytecode -> LLVM compiler). The fact that you have to explicitly handle live roots with stacks instructions defeats a lot of the purpose of LLVM IR.
It just automatically roots live values that are pointers in a nonzero addrspace. Still doesn't support copying GC, and only works in the fast instruction selector at the moment, but it goes a long way toward making GC performant in LLVM.
This is just for now, as fast isel is much easier to work with. I have other branches that implement most of the SelectionDAG support needed as well, but they aren't updated to the most recent work.
It's the same algorithm used in SBCL (in non-incremental form), and in Dalvik. It's a good fit for LLVM because it's mostly precise. I.e. it scans the stack and registers conservatively, and prevents objects referred-to from those roots from moving, but scans everything else precisely.
It's also quite simple to implement, as far as garbage collectors go. I'm working on an extension of the algorithm to support local heaps that can be collected independently of each other. The flexibility of the mostly-copying algorithm is hard to beat for stuff like this.
The right solution is to have MachineInstr-level getelementptr instructions, so that we can discover all derived pointers and copies from a GC root after codegen passes are done. Right now, getelementptr instructions get lowered into "add"/"sub"/"mul"/"lea"/etc instructions too early and we can't track them.
What we can do relatively easily (with the series of patches I've been working on) is to track one instance of each GC root across a call (basically with a fake instruction after each call for each root that represents a virtual "use" of that root). That we can at least find the pointers.
Basically, mostly-copying collection allows you to perform copying collection in a situation where certain objects cannot be moved. The original use case was for conservative stack scanning. In that situation, you cannot move objects pointed-to by an ambiguous root because you cannot ensure it is an actual root. So while you're scanning the root set, you're "promoting" the target objects to to-space instead of copying them into to-space. But the mechanism is more general than just conservative root scanning. E.g. I'm using it because I need to keep potentially global objects from being moved during a local collection.
In your case, you would walk the stack/register roots precisely using maps, but promote target objects to-space rather than copying them, so derived pointers would not have to be updated. Then you could copy the remaining objects.
EDIT: David Detlef's PhD thesis contains a pretty good description of the algorithm (starting on pg. 16): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38....
I've been talking to them about re-licensing under something more liberal and there's hope that that might happen. (If others expressed a similar interest, it might help.)
It is in need of some love:
* Support x86_64
* Support ARM
* Support threads on OS X
* Compilation and/or crash issues on modern Linux
I'd personally like to see some other improvements to the build system and have started on a reworking of the documentation into something more cohesive ...
- May it be a good idea to create a KickStarter page ? I know LuaJit has its own donation mecanism, but it may help it gain further exposure. I know i'd be willing to donate for a better GC in either case.
- Mike mentions it has to be a non-moving collector, which is usually known for having worse performance than moving collectors. Also, a non-moving generational collector (and incremental, since this is also a requirement) is hard to get right.
I tried implementing a GC along the lines of this paper : http://www.pllab.riec.tohoku.ac.jp/papers/icfp2011UenoOhoriO... which presents a fast non moving collector. Incidentally it has ideas similar to those presented in this article. Maybe it could be a good source of inspiration ? I realize the ideas are maybe not as production grade since there is only one language implementation with a GC of this sort.
Alas, I'm not good at marketing and a garbage collector is a very technical and very unsexy project (for most people, anyway). I should make up a silly name for it, that bears no relation to what it does. Yeah, that would do ...
Thank you for the link to the paper! I'll check it out.
I have good evidence that it's possible to create a non-moving GC that doesn't suck. It's a bit like marrying the best-of-breed of malloc implementations with the best-of-breed of incremental mark & sweep collectors. Plus some crazy ideas I'll have to experiment with first ...
The main innovation consists basically of having separate heaps for different objects sizes. It starts with a size of i, and has heaps for sizes i^1, i^2, ..., i^n for bounded n. An object that has a size of m > i^n goes into the i^n+1 heap.
It does thus waste memory at the end of object blocks, but they seem to indicate this is on par with memory wasted by fragmentation (this of course needs to be proofed).
The very big advantage is basically costless deallocation and cheap maintenance of free lists (you just mark the block as unused). It does also trigger several optimizations idea regarding lost space at the end of objects.
I don't know if you'd consider it battle proofed enough though, but i really think it's an interresting idea ! And the benchmarks seem to indicate very good performance.
Anyway, congrats on the 4-colors algorithm, and thank you for this article, it is actually a quite thorough explanation of mark & sweep techniques, i enjoyed reading it !
Also, has anyone tried to pre-jit then load an image on iOS?
I guess this has to do with the way the gaming industry works. The smaller game companies have maybe two or three big hits until they go under and/or the talent is bought out. The bigger ones are just wrappers for financial purposes nowadays. Yes, there are a few exceptions (no point in listing them). But overall, there's little continuity.
Sponsoring is an investment into the future. Most game companies drown in their daily business and never get to look beyond that. Making the next deadline is all that counts. Après nous le déluge.
Ok, so maybe this is just my personal impression and I'm all wrong. In fact, I'd love to be corrected ...
It works quite differently from Kickstarter; I think it's more appropriate for Open Source software projects.
It's still a bit rough -- I even hesitate to mention it here on HN just yet -- but I think it's usable.
This also makes me wonder if a design that takes caching of the drive into account could make some small improvements on things.
EDIT: added small snippet about the arenas.
When hierarchical filesystems behave as pure trees, it's always possible to simply deallocate the storage of a deleted file, because the file cannot be pointed by more than one entry in the tree.
Unix filesystems, however, do have a way of creating several references to the same file, namely hard links. In order to handle these multiple references (like having a program with multiple variables pointing to the same object) a kind of GC algorithm is used, which is simply a "reference counting GC".
Reference counting is a simple technique which is appropriate in several cases but has it's drawbacks and it's One of these drawbacks can be illustrated by this quote:
"One day a student came to Moon and said: “I understand how to make a better garbage collector. We must keep a reference count of the pointers to each cons.”
Moon patiently told the student the following story:
“One day a student came to Moon and said: ‘I understand how to make a better garbage collector... ”"
When we all have persistent, solid state drives, your filesystem will be your heap and GC...
2.) Memristor Memory
Right now, there is a hundred-billion-dollar stampede going on for finding out it's successor. Players include:
MRAM (Toshiba, Hitachi, Hynix, IBM, Everspin(Freescale spinoff), Samsung, NEC)
FeRAM (Ramtron, IBM, TI, Fujitsu, Samsung, Matsushita, Oki, Toshiba, Infineon, Hynix, Symetrix)
ReRAM (HP, ITRI, IMEC, Panasonic, Rambus)
CBRAM (NEC, Sony, Axon, Micron)
PRAM (Intel, IBM, ST Micro, Samsung, Numoxys)
I might have missed a few backers. Also, all names after a technology are not working together, especially in FeRAM there are multiple competing approaches.
An interesting commonality about these technologies is that they all aim to be universal memories. That is, they intend to eventually replace both DRAM and Flash, and some are even aiming for the last cache levels in cpus. This will probably lead to some changes in system design. Although I think the people who are calling for the death of filesystems are going about it all wrong -- I expect the role of filesystems to expand, not shrink. All they need is new block layers.
Note that while everyone says memristors (ReRAM), they aren't even the most likely candidate (if I'd have to pick, I'd say PRAM), HP just has the best marketing.
Write amplification isn't much of an issue with smart firmware.
The new memory techs aren't market viable as we speak and it's questionable if first generation commercial devices featuring them will even be available within a few years and at what cost? Many of them also have drawbacks which hamper their viability or parallel the drawbacks of NAND.
I still think a real replacement for NAND is probably a decade out at least.
All 2-terminal non-volatile memory devices based on
resistance switching are memristors, regardless of the
device material and physical operating mechanisms.
Wouldn't surprise me if Oracle and HP also have something similar.
And they both have undesirable performance problems in certain regimes, the solution to which has been the unending quest of generations of incredibly smart programmers and academics. They have led to staggering complexity, weird bugs, huge near-unmaintainable codebases, and uncounted PhD theses. Whole careers have been aimed at this stuff.
And frankly it's been, from many perspectives, mostly a waste. ZFS/btrfs are, for 95% of problems, indistinguishable from FFS/ext2 implementations that are a tiny fraction of their size. Modern Java and .NET VMs still have latency issues under GC pressure that were equally visible in Emacs Lisp a quarter century ago.
Applications which have hard requirements that fly in the face of these systems don't use them. Serious storage servers don't use the filesystem except vestigially (i.e. they do manual sync on very large files, or they use a block device directly). Serious realtime apps don't do GC and manage memory themselves. And that's not going to change no matter how many PhD's we throw at the problem.
However, there are two little, minor things that file systems care about: performance and safety. FFS/ext2 have neither of things.
Neither ext2 nor FFS contain a journal nor do the copy-on-write metadata. Heck, if you "upgrade" to ext3, you get the journal but nothing that protects you from bit-rot.
If you look at most drives on the market, you will see devices capable of corrupting data for certain after three years. Your journal'd filesystem does jack in this case, all it can do is ensure proper ordering of writes to metadata, no guarantees that the data will be any good once written.
How about performance? Well, if you look at FFS/ext2 they are essentially terrible. Block-at-a-time allocators with no extent configuration. Good luck getting the most out of your storage media when you have your block tree data-structure. Granted, ZFS suffers from the same issue but btrfs's extent tree configuration certainly does not. IIRC, the state of the art ext[23] implementations use read ahead to ameliorate the problem but does not fundamentally cure it. If you look at ext4, they have adopted extent trees via their Htree structure.
A filesystem like zfs/btrfs is pretty imune to bitrot, they can easily mirror their metadata and avoid overwriting their metadata like FFS/ext[234] making torn writes non-issues. They avoid the many pathologies that your "simpler" filesystem and trades the complexity for not needing a fsck mechanism in the face of data-corruption, one should only be needed in the face of implementation bugs (you should note that ZFS has no fsck, btrfs just recently obtained one).
Oh, and if any of you think soft updates work, they don't. While it would be great if they really did work but in a world where drives actively reorder writes and do not respect SCSI/SATA/misc transport commands to flush their internal caches, then you do not get safety. This set of drives is considerably huge.
tl;dr You are oversimplifying the complex.
>If you define "95% of problems" to be "reading and writing data such that data is read and written"
Pretty much. You have a competing definition? With the added point that "95% of problems" are mostly I/O bound reads of unfragmented write-once files and won't see benefit from extent allocation. And of the remaining 5% most of them are database systems which are doing their own journaling and block allocation.
Does btrfs have nice features (I like snapshots myself)? Sure. Do I use it in preference to ext4? Yes. But be honest with yourself: it's only incrementally better than ext2 for pretty much everything you use a computer for. And yet it sits at the pinnacle of 40 years of concerted effort.
And garbage collection is much the same: a staggeringly huge amount of effort for comparatively little (but not zero, thus "worth it" by some metric) payout.
Edit: just to throw some gas on the^H^H^H^H point out the narrowness of vision that I think is endemic in this kind of thought:
> If you look at most drives on the market, you will see devices capable of corrupting data for certain after three years.
If you look at most actual filesystems on the market, you'll find they're embedded in devices which will be thrown out in two years when their contract expires. They'll also be lost or stolen with vastly higher frequency than that at which they will experience NAND failure. If you look at most high-value storage deployments in the real world, they have redundancy and backup regimes in place which make that filesystem feature merely a downtime/latency improvement.
Basically, if someone waved a magic wand and erased all fancy filesystems and GC implementations from the world... how much would really change? Apple has deployed a pretty good mobile OS without GC, after all. Oracle made a business out of shipping reliable databases over raw block devices 20 years ago. Try that same trick with other "difficult" software technologies (video compression, say) and things look much more grim.
Clearly either your or the ext[234] developers are mistaken as they have gone ahead and implemented extent based allocation and file management.
btrfs's design is inherently safe while ext2's design is inherently unsafe. To make the analogy work, I would say that ext2 does not fit the design spec for a file system; it would be like a garbage collector that does not actually collect garbage.
The payout for data integrity, which no filesystems really handled until the WAFL era, is huge. If you cannot see, this discussion has no point.
The only thing that I must be honest about is that I would not trust ext2 to store my data any more than I would trust you to implement a scheme to store my data.
To make the point again: without btrfs (or really "the last 30 years of filesystem research") we'd all be OK. Likewise if V8 or LuaJIT had to do mark & sweep, or if everyone had to write in a language with manual storage allocation, things would look mostly the same.
Without video compression probably two thirds of the market for semiconductor devices and half the internet would simply evaporate (I pulled those numbers out of you-know-where, but I frankly doubt they're all that wrong). That tells me something about the relative value of these three applications of software engineering talent.
You can't solve all (FS) problems for all people simultaneously. Custom FS solutions by Apple (recently), Oracle (20 years ago), and countless other vendors in the last 3 decades are about choosing different trade-offs, learning from mistakes, and growing the technology with the hardware (fat-12 -> fat-16 -> fat-32 was all about growing with increasing drive size). But if you truly believe that nothing substantial has been gained, why did you bother upgrading to btrfs?
Older filesystems suffered from a variety of problems that could and did ruin data for a lot of people. Modern filesystems like NTFS5, ZFS, btrfs, etc., make their best effort to ensure data can actually be consistently read and written, which while being outside of the most common path of reading non-fragmented files sequentially (I'd even say 99.99% of actual IO in non-server configurations), it is still a use-case that is important for the vast majority of computer users. You know, people who do business, homework, take pictures, ...
On the GC side of things, the Azul VM has shown to be quite effective at addressing many of the performance issues with garbage collection in Java (which gets even better when you stop doing stupid crap in Java). And there are garbage collected languages that are not Java that don't suffer the same stuttering problem of the Java GC (that have also been around for 20+ years, and have steadily gotten better over time).
ZFS also relies on drive write barriers for safety. There is no hope if your disk lies.
end point: ZFS packs a huge quantity of functionality into 80K lines of code (probably closer to 90 or 100 now), which is quite a bit smaller than the combined size of (less featureful) file system + volume manager implemenations that it replaces.
See [1] for a comparison of ZFS vs. UFS+SVM. See [2] for Jeff Bonwick's discussion of the complexity win in ZFS.
[1] http://www.mail-archive.com/zfs-discuss@opensolaris.org/msg0...
[2] https://blogs.oracle.com/bonwick/entry/rampant_layering_viol...
Aren't you jumping to conclusions a little bit too fast? That there are still issues in some applications means all the work on Garbage Collection was wasted? I would like to remind you that modern GC-ed Java programs are often close in performance to C++ code with hand-written memory management, this clearly was not "visible in Emacs Lisp a quarter century ago".
I don't see this. The Lua GC has to know what's visible from C, in order to avoid freeing those objects. If it knows what's visible from C, then it strictly just needs to avoid copying those objects. If it moves them to an uncollected area when C references them, and back when C dereferences them, then it can use a copying collector on the Lua-only objects.
This actually might work very well, if C-referenced objects are going to tend to be much longer lived. Of course, copying the objects into and out of the uncollected region will itself be some work.
I have no idea if the ideal algorithm is in this space, I just think that either they discarded copying collectors prematurely, or there's something I'm missing, so either I get to learn something or they do; is there a constraint I've missed?
Now ... the interesting objects, that benefit most from the defragmentation effects of a moving GC, are the variable-sized objects. Sadly, userdata cannot be moved at all and strings are the only other interesting object type. Well ... see above.
[Table objects are not variable-size. Only their array and hash parts are. But these are singly-linked from the table object and can easily be moved around, anyway. The addresses of these memory blocks are never exposed by the VM.]
Very readable and approachable. I read the entire book, which I almost never do with technical books.
I highly recommend the Jones/Hosking/Moss book, but it assumes familiarity with the basics. Pick it up if the Wilson paper intrigues you. The previous edition of the book (Jones & Lins) is good, too, but the new one adds a lot of important material on real-time GC, concurrent GC, and interactions between GC and runtime systems.
libgarbagecollector is a plug-in garbage collector library designed to be used by high level language implementors. It's used in the Io programming language.
As mentioned above, I'm regularly talking with Ravenbrook about liberalizing the license on MPS and doing some work on modernizing it. I've hopes that that might happen this year.
And some of the language specific ones are pretty good ... SGen in Mono seems interesting. The GC in ClozureCL is interesting as well.