<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Garbage Collection --> <!--X-From-R13: [vebfyni Evybivp <fvybivpNmrfbv.sre.ue> --> <!--X-Date: Thu, 09 Dec 1999 04:53:46 -0800 --> <!--X-Message-Id: 7eyab49txy.fsf@zesoi.fer.hr --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] Garbage Collection</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:silovic@zesoi.fer.hr"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00563.html">Previous</a> | <a href="msg00565.html">Next</a> ] Thread: [ <a href="msg00631.html">Previous</a> | <a href="msg00558.html">Next</a> ] Index: [ <A HREF="author.html#00564">Author</A> | <A HREF="#00564">Date</A> | <A HREF="thread.html#00564">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] Garbage Collection</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] Garbage Collection</LI> <LI><em>From</em>: Miroslav Silovic <<A HREF="mailto:silovic#zesoi,fer.hr">silovic#zesoi,fer.hr</A>></LI> <LI><em>Date</em>: 09 Dec 1999 13:31:37 +0100</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Sender</em>: <A HREF="mailto:mud-dev-admin#kanga,nu">mud-dev-admin#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> Cynbe ru Taren <cynbe#muq,org> writes: > In Muq, I'm currently using a plain-jane mark-and-sweep monolithic > gc I hacked together one weekend just to have something rather than > nothing. Hmm. :) Problem with mark&sweep is bad realtime performance. You can look to 1-2 seconds pause per 10MB allocated. Not too bad unless you have *lots* of active objects or are running realtime combat. See BattleTech MUSHes for realtime combat example (and the ammount of annoyance 1 second lag can cause). > I've been contemplating going to a two-generation system and/or > implementing Dijkstra's three-color incremental algorithm. Generational GC tends to require the same infrastructure as tricolor (i.e. write barrier). > Is there prior mud art with other approaches? Are there working > systems or good references I should be boning up on before proceeding? No MUD systems that I know of, but there are plenty of programming languages implementations that use good GC systems. Note that GC has one serious drawback: it tends to touch all the pages it scans. While it's possible to check whether the page is on swap (and then try and be clever about scanning the pointers from it), GCs in general don't do this, and so GC systems don't perform well when the machine begins to thrash. My favorite GC implementations are Hans Boehm's (major problem: uses VM tricks to handle generationality), rscheme's (check www.rscheme.org) and the one in TOM (incremental, nongenerational for now, and with very clean interface to the object system that allows objects a good degree of control over the way they get collected). So here are the MUD/GC issues: - Using well-implemented GC results in a code that doesn't have to worry at all about memory bugs - you probably want conservative stack scanning if you're doing *any* embedded C, but you can almost always scan heap exactly. Also, you can use circular datastructures without limits, work with graphs in a general manner (refcounting tends to break with general graphs) and keep all the memory issues separate from your object system (i.e. no worries where/when constructors/destructors get called). You also have symmetry between objects pointed from stack and the objects pointed from heap - this is VERY helpful for design. Note that GC may treat stack and heap pointers differently, the symmetry is in the GC interface. - Write barrier... This is problematic part. In C, calling write barrier for heap objects means you have to do GC_ASSIGN_POINTER(object->foo, another_object); or object->foo = another_object; GC_LINK(object, another object); (you need to know inter-generational pointers in gengc, that's what the second parameter is for). rather than just object->foo = another_object; This is easy to forget. C++ with some templates has trivial workaround (just implement write barrier into assignment operator) but will tend to call write barrier WAY too often. Alternatively one could probably program a lint-like utility to statically check for this problem. - swap interaction. This topic, to put it plainly, sucks. One way to treat this problem is to treat parts of your object tree as separate systems and collect them using distributed GC technique - it handles one hard problem by turning it into another hard (but more researched) problem. - one-bit refcounting: Some datastructures are VERY transient in nature - strings, for instance, or closures when you use them just to avoid enumerators. To handle them, you give them one bit refcount: You know when these will disappear from stack, so you can use a single-bit flag that checks whether this object is referenced from heap. If no, once it disappears from the local scope, you can kill it. This doesn't suffer from threading interactions typical for refcounting, and can drastically increase performance if you allocate your strings on a GC'ed heap. - distributed gc: This becomes relevant if you're running your mud on several servers. I haven't thought much about it, apart from noting that TOM supports somewhat limited form of it (read: VERY fault-intolerant). More information on this topic: <A HREF="ftp://ftp.cs.utexas.edu/pub/garbage/">ftp://ftp.cs.utexas.edu/pub/garbage/</A> -- How to eff the ineffable? _______________________________________________ MUD-Dev maillist - MUD-Dev#kanga,nu <A HREF="http://www.kanga.nu/lists/listinfo/mud-dev">http://www.kanga.nu/lists/listinfo/mud-dev</A> </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00563.html">Re: [MUD-Dev] ColdStore</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00565.html">Re: [MUD-Dev] Fair/Unfair? Scenarios (fwd)</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00631.html">[MUD-Dev] Re: Biosystems & simulation [RAMBLE]</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00558.html">[MUD-Dev] AI's in MUDS and Online Gaming</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00564"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00564"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><STRONG>Re: [MUD-Dev] Biosystems (was Fair/Unfair? Scenarios)</STRONG>, <EM>(continued)</EM> <ul compact> <ul compact> <LI><strong><A NAME="00584" HREF="msg00584.html">Re: [MUD-Dev] Biosystems (was Fair/Unfair? Scenarios)</A></strong>, Douglas Couch <a href="mailto:dscouch@purdue.edu">dscouch@purdue.edu</a>, Fri 10 Dec 1999, 17:04 GMT </LI> <LI><strong><A NAME="00587" HREF="msg00587.html">Re: [MUD-Dev] Biosystems (was Fair/Unfair? Scenarios)</A></strong>, Marc Hernandez <a href="mailto:marc@ias.jb.com">marc@ias.jb.com</a>, Fri 10 Dec 1999, 23:23 GMT <UL> <LI><strong><A NAME="00624" HREF="msg00624.html">Re: [MUD-Dev] Biosystems (was Fair/Unfair? Scenarios)</A></strong>, J C Lawrence <a href="mailto:claw@cp.net">claw@cp.net</a>, Fri 17 Dec 1999, 00:33 GMT <UL> <LI><strong><A NAME="00631" HREF="msg00631.html">[MUD-Dev] Re: Biosystems & simulation [RAMBLE]</A></strong>, Ben Greear <a href="mailto:greearb@candelatech.com">greearb@candelatech.com</a>, Fri 17 Dec 1999, 01:10 GMT </LI> </UL> </LI> </UL> </LI> </ul> </ul> </LI> <LI><strong><A NAME="00564" HREF="msg00564.html">[MUD-Dev] Garbage Collection</A></strong>, Miroslav Silovic <a href="mailto:silovic@zesoi.fer.hr">silovic@zesoi.fer.hr</a>, Thu 09 Dec 1999, 12:53 GMT <LI><strong><A NAME="00558" HREF="msg00558.html">[MUD-Dev] AI's in MUDS and Online Gaming</A></strong>, IronWolf <a href="mailto:ironwolf@ewa.net">ironwolf@ewa.net</a>, Thu 09 Dec 1999, 04:46 GMT <UL> <LI><strong><A NAME="00560" HREF="msg00560.html">Re: [MUD-Dev] AI's in MUDS and Online Gaming</A></strong>, Matthew Mihaly <a href="mailto:diablo@best.com">diablo@best.com</a>, Thu 09 Dec 1999, 05:11 GMT <UL> <LI><strong><A NAME="00561" HREF="msg00561.html">Re: [MUD-Dev] AI's in MUDS and Online Gaming</A></strong>, IronWolf <a href="mailto:ironwolf@ewa.net">ironwolf@ewa.net</a>, Thu 09 Dec 1999, 05:42 GMT </LI> </UL> </LI> </UL> <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="00589" HREF="msg00589.html">Re: [MUD-Dev] AI's in MUDS and Online Gaming</A></strong>, Ryan P. <a href="mailto:ixiterra@earthlink.net">ixiterra@earthlink.net</a>, Sat 11 Dec 1999, 05:37 GMT </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>