Re: Mid-term Update for Cycle Collector (Google Summer of Code Project)

On Wed, 11 Jul 2007 13:43:19 -0700, "David Wang" <planetbeing@gmail.com> wrote: > Hello, everyone. My name is David Wang and I am one of the students > participating in Google Summer of Code this year. As you may remember, > my project is to implement a garbage collector for circular references > in PHP. As the midterm for Summer of Code is coming up, my mentor, > Derick Rethans, thought it would be a good idea if I shared my > progress with the community. > > As you know, PHP uses reference counting as a simple garbage > collection system. One of the primary weaknesses of reference counting > systems is that objects that refer indirectly or directly to > themselves, i.e. reference cycles, are not collected. The accumulation > of unreferenced memory that is only deallocated at the end of a > request can be prohibitively expensive. The cycle collector I am > implementing directly addresses this problem. > > The cycle collector is, of necessity, a type of tracing garbage > collector. However, it uses reference count information to accelerate > the collection process. Essentially, it works by removing the internal > reference counts (that is, references from an object within the cycle > to another object within the cycles )from candidate cycles. In a cycle > that can be collected, after all internal reference counts have been > removed, the reference count of all objects within the cycle should be > 0. The particular algorithm that I am using is the synchronous cycle > collector described by David Bacon and V. T. Rajan in Concurrent Cycle > Collection in Reference Counted Systems (see the article for further > details). Various optimizations allow the cycle collector to be run > relatively infrequently and execute speedily when it does run. > > Note that because PHP is designed to be single-threaded, a synchronous > algorithm is used which does pause program execution for cycle > collection when cycle collection becomes necessary. If a program has > no reference cycles, the cycle collector does not run at all. > > The initial phase of implementation is complete, and I am currently > profiling, optimizing and trying the modified version of PHP on > various test programs in an effort to find bugs. Meanwhile, here are > some recent benchmarks. > > Some aspects of the eZ Components (http://ez.no/ezcomponents, > available from SVN with the instructions here: > > http://ez.no/community/articles/an_introduction_to_ez_components/installation% ¢¡ > ãfÆ\UM MY) > testing suite use reference cycles heavily. The Template test uses > circular references the most frequently, the Graph test also uses > circular references, albeit less heavily. > > On the Graph test, maximum memory usage with unmodified PHP was 133.9 > MB with an execution time of 8 seconds. > On the Graph test, maximum memory usage with gc was 51.6 MB with an > execution time of 9 seconds. > On the Template test, maxmium memory usage with unmodified PHP was 1.5 > GB with an execution time of 30 seconds. > On the Template test, maxmium memory usage with gc was 67.3 MB with an > execution time of 1 minute. > On the whole suite of tests (which includes the Graph and Template > tests), execution time with unmodified PHP was 12:03. With cycle > collection, it was 12:43. > These tests were conducted on my dual core AMD X2 4400+ desktop with > ./configure --with-gd --with-jpeg-dir --with-zlib. As you can see, > there is the classic time vs. memory trade-off. > > My project is currently being hosted on the xdebug CVS. You can get > the latest version with the following commands: > > cvs -d :pserver:srmread@cvs.xdebug.org:/repository login > CVS password: srmread > cvs -d :pserver:srmread@cvs.xdebug.org:/repository co circular > Note that I'm implementing my project on top of a CVS version of PHP > 5.2 that is a couple of weeks old. However, the cycle collector can be > ported into other versions of PHP fairly easily as it does not affect > the existing Zend engine code too much. > > If anyone has any questions, I'll be more than happy to answer them! > > Regards, > > Yiduo (David) Wang KUDOS! > > -- > PHP Internals - PHP Runtime Development Mailing List > To unsubscribe, visit: http://www.php.net/unsub.php ///////////////////////////////////////////////////// Service provided by hitOmeter.NET internet messaging! .