Mercurial > hg > xemacs-beta

comparison man/internals/internals.texi @ 4427:cff4ad0ab682

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Document "lifting to Lisp". <87tzjvx8lu.fsf@uwakimon.sk.tsukuba.ac.jp>
author Stephen J. Turnbull <stephen@xemacs.org>
date Wed, 27 Feb 2008 14:41:45 +0900
parents a78603f584d7
children 969a957a44ac
comparison
equal deleted inserted replaced
4426:515b91f904c1 4427:cff4ad0ab682
738 * Discussion -- Packages:: 738 * Discussion -- Packages::
739 * Discussion -- Distribution Layout:: 739 * Discussion -- Distribution Layout::
740 740
741 Discussion -- Garbage Collection 741 Discussion -- Garbage Collection
742 742
743 * Discussion -- KKCC::
744 * Discussion -- Incremental Collector::
743 * Discussion -- Pure Space:: 745 * Discussion -- Pure Space::
744 * Discussion -- Hashtable-Based Marking and Cleanup:: 746 * Discussion -- Hashtable-Based Marking and Cleanup::
745 * Discussion -- The Anti-Cons:: 747 * Discussion -- The Anti-Cons::
746 748
747 Old Future Work 749 Old Future Work
8549 @section lrecords 8551 @section lrecords
8550 @cindex lrecords 8552 @cindex lrecords
8551 8553
8552 [see @file{lrecord.h}] 8554 [see @file{lrecord.h}]
8553 8555
8556 @strong{This node needs updating for the ``new garbage collection
8557 algorithms'' (KKCC) and the ``incremental'' collector.}
8558
8554 All lrecords have at the beginning of their structure a @code{struct 8559 All lrecords have at the beginning of their structure a @code{struct
8555 lrecord_header}. This just contains a type number and some flags, 8560 lrecord_header}. This just contains a type number and some flags,
8556 including the mark bit. All builtin type numbers are defined as 8561 including the mark bit. All builtin type numbers are defined as
8557 constants in @code{enum lrecord_type}, to allow the compiler to generate 8562 constants in @code{enum lrecord_type}, to allow the compiler to generate
8558 more efficient code for @code{@var{type}P}. The type number, thru the 8563 more efficient code for @code{@var{type}P}. The type number, thru the
8568 lrecord_header} at its beginning, so sanity is preserved; but it also 8573 lrecord_header} at its beginning, so sanity is preserved; but it also
8569 has a pointer used to chain all lcrecords together, and a special ID 8574 has a pointer used to chain all lcrecords together, and a special ID
8570 field used to distinguish one lcrecord from another. (This field is used 8575 field used to distinguish one lcrecord from another. (This field is used
8571 only for debugging and could be removed, but the space gain is not 8576 only for debugging and could be removed, but the space gain is not
8572 significant.) 8577 significant.)
8578
8579 @strong{lcrecords are now obsolete when using the write-barrier-based
8580 collector.}
8573 8581
8574 Simple lrecords are created using @code{ALLOCATE_FIXED_TYPE()}, just 8582 Simple lrecords are created using @code{ALLOCATE_FIXED_TYPE()}, just
8575 like for other frob blocks. The only change is that the implementation 8583 like for other frob blocks. The only change is that the implementation
8576 pointer must be initialized correctly. (The implementation structure for 8584 pointer must be initialized correctly. (The implementation structure for
8577 an lrecord, or rather the pointer to it, is named @code{lrecord_float}, 8585 an lrecord, or rather the pointer to it, is named @code{lrecord_float},
28417 @section Discussion -- Garbage Collection 28425 @section Discussion -- Garbage Collection
28418 @cindex discussion, garbage collection 28426 @cindex discussion, garbage collection
28419 @cindex garbage collection, discussion 28427 @cindex garbage collection, discussion
28420 28428
28421 @menu 28429 @menu
28430 * Discussion -- KKCC::
28431 * Discussion -- Incremental Collector::
28422 * Discussion -- Pure Space:: 28432 * Discussion -- Pure Space::
28423 * Discussion -- Hashtable-Based Marking and Cleanup:: 28433 * Discussion -- Hashtable-Based Marking and Cleanup::
28424 * Discussion -- The Anti-Cons:: 28434 * Discussion -- The Anti-Cons::
28425 @end menu 28435 @end menu
28426 28436
28427 @node Discussion -- Pure Space, Discussion -- Hashtable-Based Marking and Cleanup, Discussion -- Garbage Collection, Discussion -- Garbage Collection 28437 @node Discussion -- KKCC, Discussion -- Incremental Collector, Discussion -- Garbage Collection, Discussion -- Garbage Collection
28438 @subsection Discussion -- KKCC
28439 @cindex discussion, KKCC
28440 @cindex KKCC, discussion
28441
28442 KKCC is the tag used for the ``new garbage collector algorithms,'' which
28443 are a refactoring of the garbage collector to make trying new collectors
28444 simpler.
28445
28446 @node Discussion -- Incremental Collector, Discussion -- Pure Space, Discussion -- KKCC, Discussion -- Garbage Collection
28447 @subsection Discussion -- Incremental Collector
28448 @cindex discussion, Incremental Collector
28449 @cindex Incremental Collector, discussion
28450
28451 The incremental collector is designed to allow better ``realtime''
28452 performance by not requiring a full mark and sweep pass. This also
28453 allows removal of most finalizers, as described in
28454 @samp{<vpd8x1fomdx.fsf@@informatik.uni-tuebingen.de>} by Marcus Crestani
28455 on xemacs-beta:
28456
28457 I was able to nuke many finalizers by transforming
28458 separately allocated data structures to Lisp objects. Some of the
28459 remaining finalizers are also likely to go away, as soon as I (or
28460 someone else) find the time to ``lift'' the remaining, separately allocated
28461 objects to Lisp objects.
28462
28463 Unfortunately, the current Lisp object layout leads to holes in the
28464 write barrier: Not all data structures that contain pointers to Lisp
28465 objects are allocated on the Lisp heap. Some Lisp objects do not carry
28466 all their information in the object itself. External parts are kept in
28467 separately allocated memory blocks that are not managed by the new Lisp
28468 allocator. Examples for these objects are hash tables and dynamic
28469 arrays, two objects that can dynamically grow and shrink. The separate
28470 memory blocks are not guaranteed to reside on page boundaries, and thus
28471 cannot be watched by the write barrier.
28472
28473 Moreover, the separate parts can contain live pointers to other Lisp
28474 objects. These pointers are not covered by the write barrier and
28475 modifications by the client during garbage collection do escape. In
28476 this case, the client changes the connectivity of the reachability
28477 graph behind the collector's back, which eventually leads to erroneous
28478 collection of live objects. To solve this problem, I transformed the
28479 separately allocated parts to fully qualified Lisp objects that are
28480 managed by the allocator and thus are covered by the write barrier.
28481 This also removes a lot of special allocation and removal code for the
28482 out-sourced parts. Generally, allocating all data structures that
28483 contain pointers to Lisp objects on one heap makes the whole memory
28484 layout more consistent.
28485
28486 A large part of the patch converts these data structures to Lisp
28487 objects. The conversion of an additionally allocated data structure to
28488 an Lisp objects includes:
28489 @itemize
28490 @item Add new object type to @samp{enum lrecord_type} in @file{lrecord.h}.
28491 @item Add @samp{lrecord_header} to the object's struct.
28492 @item Add @samp{DECLARE_RECORD()}/@samp{XFOO}/etc. below the struct definition.
28493 @item Add lrecord definition.
28494 @item Change allocation with malloc to allocation with new allocator.
28495 @item Add object to @samp{syms_of_*()}.
28496 @item Change memory description of parent object.
28497 @item Modify finalizer, free, or delete functions.
28498 @end itemize
28499
28500 The initial motivation for this is the write barrier and the consistent
28501 format for all objects that may contain Lisp pointers. That we can get
28502 rid of finalizers this way follows naturally.
28503
28504
28505 @node Discussion -- Pure Space, Discussion -- Hashtable-Based Marking and Cleanup, Discussion -- Incremental Collector, Discussion -- Garbage Collection
28428 @subsection Discussion -- Pure Space 28506 @subsection Discussion -- Pure Space
28429 @cindex discussion, pure space 28507 @cindex discussion, pure space
28430 @cindex pure space, discussion 28508 @cindex pure space, discussion
28431 28509
28432 On Tue, Oct 12, 1999 at 03:36:59AM -0700, Ben Wing wrote: 28510 On Tue, Oct 12, 1999 at 03:36:59AM -0700, Ben Wing wrote: