Slashdot Mirror

Jim Gettys (rock!) sent us some good news from the DEC/Compaq camp. Itsy, the ARM/Linux/PDA that has been under development for some time now, and is chock full of nifty little features, has had its schematics and software updated for you industrious do-it-your-selfers wanting to contribute to pocket computing.

Date: Mon, 7 Feb 2000 16:53:48 -0800
From: Deborah Wallach [kerr@pa.dec.com]
To: sa1100-linux@pa.dec.com, linux-arm-kernel@lists.arm.linux.org.uk
Subject: Itsy schematics and updated Linux software available

In order to promote collaboration and to advance the state of pocket computing research, Compaq Computer Corporation's Research Laboratories are making available the schematics and manufacturing information for the Itsy V1.5 Pocket Computer. The Itsy is a flexible research platform, based on the StrongARM 1100, intended to enable hardware and software research in pocket computing. It is a small, low-power handheld device with a highly flexible interface, designed to encourage the development of innovative research projects, such as novel user interfaces, new applications, power management techniques, hardware extensions, etc. The information we are making available includes the hardware specifications, a low level monitor, and the Linux source code for the Itsy.

Information about the project

More information on the distribution

Deborah Wallach
Western Research Laboratory
Compaq Computer Corporation

waite writes "The Compaq Testdrive program is now making available a Beowulf cluster of XP1000s running Alpha Linux. If you sign up for the testdrive program you can register for an account on the cluster to try out your applications in this cluster environment. There is no charge for this program. Compaq is making this available to Open Source developers. No strings, catches, or hooks of any type."

A.M. Kuchling is back again, this time with a review of Richard Jones and Rafael Lins' oddly named Garbage Collection. This book is not actually about Waste Management Inc, but is "A highly detailed survey of garbage collection algorithms, and the research literature surrounding them. Interesting, if at times very dry.". Click below for more information. Garbage Collection author Richard Jones and Rafael Lins pages publisher Wiley & Sons rating 6 reviewer A.M. Kuchling ISBN summary A highly detailed survey of garbage collection algorithms, and the research literature surrounding them. Interesting, if at times very dry.

The first time you encounter garbage collection (GC, for short) is often by using Lisp or Scheme in an introductory computer science course, where it can seem an almost magical technology. How does the interpreter determine that a variable has become garbage, and can safely be deallocated? This book explains how GC works, in great detail, and interest people implementing garbage collectors or who've wondered how it's done. There are 3 approaches to GC, all of which are covered in this book:

1. Reference counting:
   Every object keeps a count of the references pointing to it. When new references are created, the counter must be increased; when references are destroyed, the counter is decremented, and, if the count is zero, the object has become garbage and can be reclaimed. Reference counting unfortunately exacts the most overhead from constantly incrementing and decrementing the counters, and in its simplest form it can't collect cyclic data structures, because their count will never reach zero.
2. Mark-sweep:
   Traverse the graph of object references, starting from the roots of the computation; roots might be the program's global variables, the contents of the C stack, static class variables, or a main namespace of some sort. Each object that's traversed is marked as being reachable; when the traversal is complete, any unmarked objects are unreachable because they can't be reached by the program any longer, and can be reclaimed as garbage.
3. Copying:
   Divide memory into two halves, called "Fromspace" and "Tospace". Memory for new objects is always allocated out of Fromspace. When Fromspace fills up, a traversal similar to the one used by mark-sweep is done, but instead of just marking objects as reachable, they're copied into Tospace. Once the traversal is done, all the live objects are now in Tospace, and Fromspace no longer contains any live data; only garbage objects can be left in Fromspace. Tospace is now declared the new Fromspace, and new objects are allocated until it fills up; the algorithm is then repeated.

This book covers the above 3 algorithms for GC in great detail; there's a chapter for each algorithm, examining its limitations, common implementation techniques, and historical notes on the its development. Later chapters cover more advanced collectors that extend the basic algorithms in various ways. Generational collectors are based on the observation that many objects are temporary and have short lifetimes, while some few objects may last for the entire lifetime of the program. A generational garbage collector concentrates on young objects, because they will occupy the most recyclable space, and spends less time examining old objects that probably won't be reclaimed. Incremental and concurrent collectors don't bring the whole program to a halt while they scavenge through memory doing a collection, making them more suited for interactive or even real-time applications.

Chapter 9 is an interesting examination of the implementation of GC in an unfriendly environment, namely C programs. The Boehm-Demer-Weiser collector implements a mark-sweep garbage collector that can replace C's malloc() function, scanning stack frames and registers for potential pointers, and managing to do it fairly efficiently. One study found the Boehm-Demer-Weiser collector added 20% more execution time overhead than malloc() did -- that is, the time spent in memory allocation was 20% longer. (That doesn't mean it made programs 20% slower, because most programs spend more time computing results than they spend allocating memory). A garbage collector for C is a tricky job, complicated by the lack of type information, data values that may mimic pointers, and compiler optimizations that may render objects invisible to the collector. Barlett's Mostly Copying Garbage Collector, also described in this chapter, is more liberal and requires some assistance from the C programmer in exchange for greater accuracy.

The remaining 3 chapters consider suggestions for adding garbage collection to C++, the interaction of GC with cache memory, and distributed garbage collection. The topics of these chapters are still subjects of active research, so the final chapters are lighter on implementation details and heavy on references to research papers, making them a lot less interesting.

The authors are computer scientists specializing in GC (Richard Jones maintains a garbage collection page), and their coverage is quite complete, which at times makes for exceedingly dry reading as the authors enumerate what seems like every minor implementation variation and every relevant paper. On the other hand, if you're actually faced with implementing a garbage collector, the pointers into the research literature will be very useful. A casual reader (like me) can simply skim, or even skip, pages until the next interesting section arrives.

Excerpt

However, the matter is more subtle than this. The collectors described in this chapter are very simple and inefficient. The behaviour of these collectors cannot be automatically ascribed to their more sophisticated variants. The cost of copying an object is likely to be more expensive than simply testing and setting a mark-bit, particularly if the object is large. Although mark-sweep must sweep the entire heap, in practice its real cost is dominated by the mark phase. Linearly scanning the heap will generally be less expensive than tracing data structures even using the simple technique shown above. ... Furthermore, more sophisticated methods can substantially reduce the cost of the sweep. Although copying collectors have predominated in the past, recent studies suggest that the choice between mark-sweep and copying garbage collection may well depend as much on the behaviour of the client program as on the inherent properties of the garbage collection algorithm.
-- From section 2.4 of the book.

To purchase this book, head over to Fatbrain.

Table of Contents

1. Introduction
2. The Classical Algorithms
3. Reference Counting
4. Mark-Sweep Garbage Collection
5. Mark-Compact Garbage Collection
6. Copying Garbage Collection
7. Generational Garbage Collection
8. Incremental and Concurrent Garbage Collection
9. Garbage Collection for C
10. Garbage Collection for C++
11. Cache-Conscious Garbage Collection
12. Distributed Garbage Collection

David Dula writes "Compaq has put something up official about alpha hardware for linux with prices and everything. No compaq software support yet but there is hardware support offered. "

Leaky writes "Well some of us think the Linux market is valuable. Digital will be rolling out a Linux ready version of its low end uniprocessor Alphaserver aimed at the education market place later this month. The product is based on the Alphaserver 800 and will ship with no OS but marketed as Linux ready. Digital will begin rolling this program out to its resellers and distributors this week. Leaky ". I think this is a great start - assuming it's true. Can anyone confirm this, though? We'll keep our eyes out, but faucet.mail.dec.com isn't resolving over here (though the leaky and faucet thing does sound like a pun of sorts to me) ....

Larry Smith wrote in to tell us that its official. DEC is now taking the name of its new owner:Compaq. Too bad- I always thought that Digital had a better logo :)

In more PalmPilot news, Wired News reports that 3Com may sue Microsoft over the use of the term "PalmPC", sighting its likeness to an upcoming PalmOS product. The article also states that 3Com may be bringing out a "Pilot Killer" of their own.

In perhaps more exciting news, the San Jose Mercury reports that the Federal Trade Comission may postpone or prevent the sale of Digital Equipment Corp.'s semiconductor operations, and it may do the same with Intel's already long postponed acquistion of Chips & Technologies.