My project.
I m publishing my report earlier this week, because there was a lot to talk about. This week I started to make changes in the code going in the direction of what I want to do. I haven t started a final implementation, but I m studying about how what I want to do will affect the rest of the
Garbage Collection (GC). I noticed the code in
rts/sm/Sweep.c was simple and similar to what I m planning to do, so I started changing how it works.
Sweep in the
Glasgow Haskell Compiler (GHC) is done by a bitmap, which contains a bit for each word in a memory block, and is set to 1 when there s an object starting in the mapped area and 0 otherwise. When there s a block with no objects starting at it, that is, all bits of the bitmap are set to 0, the block is freed.
if (resid == 0)
freed++;
gen->n_old_blocks--;
if (prev == NULL)
gen->old_blocks = next;
else
prev->link = next;
freeGroup(bd);
The bits are analyzed in a group of
BITS_IN(W_), where
BITS_IN(W_) is the number of bits in a word.
for (i = 0; i < BLOCK_SIZE_W / BITS_IN(W_); i++)
if (bd->u.bitmap[i] != 0) resid++;
If more than of the groups are completely set to 0, the block is considered fragmented.
if (resid < (BLOCK_SIZE_W * 3) / (BITS_IN(W_) * 4))
fragd++;
bd->flags = BF_FRAGMENTED;
Immix, the GC algorithm I plan to implement in GHC, divides the blocks of memory in lines. My initial plan was to identify free lines. I decided to consider a the size of a line fixed in
BITS_IN(W_) words, because it will map to a word in the bitmap, and the code was already analyzing in groups of
BITS_IN(W_) words. This was very easy with the current code.
if (bd->u.bitmap[i] != 0) resid++;
else printf("DEBUG: line_found(%p)\n", bd->start + BITS_IN(W_) * i);
This worked, and showed some free lines. I m sure there are other ways of logging in GHC, but
printf was the simplest way I could thought of. I measured the occurrence of free lines using the
bernouilli program from
the NoFib benchmark suite, calling it with
500 +RTS -w, to make it uses sweep. In 782 calls to
GarbageCollect(),
sweep() was called 171 times, for 41704 blocks to be swept and found 230461 free lines. This gives us about 5.5 free lines per block, from the 8 lines in each block (on 64 bits systems).
The problem is that the bitmap is marked only in the start of the objects allocated, so even in a line that all bits are marked with 0 we can t assume that it s completely free, because there may be an object that starts in the previous line that is using the space of the line. Checking only for the previous line doesn t work either, because a big object can span several lines. What we can do here is a variation of conservative marking, as proposed in
the Immix paper, checking only the previous line and working only with objects smaller than a line.
To make sure I was working only with objects smaller than a line, I had to mark the blocks that contains medium objects and avoid them when seeking free lines. The block flags are defined in
includes/rts/storage/Block.h, so I included another flag in this file,
BF_MEDIUM.
/* Block contains objects evacuated during this GC */
#define BF_EVACUATED 1
/* Block is a large object */
#define BF_LARGE 2
/* Block is pinned */
#define BF_PINNED 4
/* Block is to be marked, not copied */
#define BF_MARKED 8
/* Block is free, and on the free list (TODO: is this used?) */
#define BF_FREE 16
/* Block is executable */
#define BF_EXEC 32
/* Block contains only a small amount of live data */
#define BF_FRAGMENTED 64
/* we know about this block (for finding leaks) */
#define BF_KNOWN 128
/* Block contains objects larger than a line */
#define BF_MEDIUM 256
The GHC GC is generational, there is, objects are allocated in a generation and, after a time, the ones that are still being used are moved the next generation. This idea assumes the death probability of younger objects is higher, so few objects are moved to the next generation. Sweep and Immix work only in the last generation so, to mark blocks with medium objects we have to check the size of the objects that are moved to the next generation.
This is done in the
copy_tag function of
rts/sm/Evac.c. I inserted a code that checks for the object size and marks the block when it s bigger than
BITS_IN(W_).
STATIC_INLINE GNUC_ATTR_HOT void
copy_tag(StgClosure **p, const StgInfoTable *info,
StgClosure *src, nat size, generation *gen, StgWord tag)
StgPtr to, from;
nat i;
to = alloc_for_copy(size,gen);
if(size > 8)
Bdescr(to)->flags = BF_MEDIUM;
So I updated the code in
rts/sm/Sweep.c to only inspect for free lines in blocks without BF_MEDIUM mark.
if (bd->u.bitmap[i] != 0) resid++;
else if(!(bd->flags & BF_MEDIUM))
printf("DEBUG: line_found(%p)\n", bd->start + BITS_IN(W_) * i);
This also worked. Now, in the 32012 blocks there were 189015 free lines, found in the same number of GCs, making about 5.9 free lines per block. We considered only blocks with small objects, but we didn t ignore the first line of each group of free lines. This can be achieved by checking if the previous line was also free.
if (bd->u.bitmap[i] != 0) resid++;
else if(!(bd->flags & BF_MEDIUM) && i > 0 && bd->u.bitmap[i] == 0)
printf("DEBUG: line_found(%p)\n", bd->start + BITS_IN(W_) * i);
Now, from the 32239 blocks, 165547 free lines were found, giving 5.1 free lines per block. But there are more things to improve. If the whole block is free, we want to free it, instead of marking it s lines as free. So it s better to mark the lines after we know that the blocks are not completely free. So I left the code that checks the bitmap as it was, and included a line check only for blocks that are not completely free. At this point, I also associated the fragmentation test with blocks with medium objects, because in blocks of small objects we plan to allocate in free lines, so fragmentation is not a (big) issue.
if (resid < (BLOCK_SIZE_W * 3) / (BITS_IN(W_) * 4) &&
(bd->flags & BF_MEDIUM))
fragd++;
printf("DEBUG: BF_FRAGMENTED\n");
bd->flags = BF_FRAGMENTED;
else if(!(bd->flags & BF_MEDIUM))
for(i = 1; i < BLOCK_SIZE_W / BITS_IN(W_); i++)
if(bd->u.bitmap[i] == 0 && bd->u.bitmap[i - 1] == 0)
printf("DEBUG: line_found(%p)\n", bd->start + BITS_IN(W_) * i);
The total ammount of blocks increased dramatically: the blocks that become fragmented and were not called again in sweep made a huge difference. From the 345143 blocks, 1633268 free lines were found, or about 4.7 free lines per block. 9434 blocks were free, so, from the remaining blocks, we have about 4.9 free lines per block.
Something we ll need then is a way to access these lines latter. The simplest way I thought to achieve it is constructing a list of lines, in each the first word of each free line is a pointer to the next free line, and the first word of the last free line is 0. It s useful to keep reporting the lines to stdout, so that we can then follow the list and check if we went to the same lines.
if(bd->u.bitmap[i] == 0 && bd->u.bitmap[i - 1] == 0)
StgPtr start = bd->start + BITS_IN(W_) * i;
printf("DEBUG: line_found(%p)\n", start);
if(line_first == NULL)
line_first = start;
if(line_last != NULL)
*line_last = (StgWord) start;
line_last = start;
*line_last = 0;
for(line_last = line_first; line_last; line_last = (StgPtr) *line_last)
fprintf(stderr, "DEBUG: line_found(%p)\n", line_last);
I printed the inclusion of the lines on the list to
stdout, and the walking on the list in stderr, so that it d be easy to diff. There was no difference between the lists.
There re another improvements that can be made, like using a list of groups of free lines, but I think it ll be better to think about this after studying how the allocation in the free lines will be done. That s where I m going to now.
There are some minor things I learned, and thought they worth blogging. The current GHC uses three strategies for collecting the last generation: copying, mark-compact and mark-sweep. Copying is the default until the memory reaches 30% of the maximum heap size; after that, mark-compact is used. Sweep can be chosen by a
Real Time System (RTS) flag,
-w. To use mark-compact always, the flag is
-c.
I ve been submitting small patches to the
cvs-ghc mailling list, mostly about outdated comments. Most of them were accepted, except for one which contained a lot of commentary, and that indeed was not completely correct. I corrected it and resend to the list, but the message is waiting for approval because the message header matched a filter rule. I believe this is because I replied the message generated from
darcs.
There s a very useful ghc option, specially for testing the compiler, because in this case you need to rebuild the source, even when there re no changes in it. It s
-fforce-recomp, and it makes only sense when used with
--make.
Having invested in some introspection into my reading habits, I made up my mind to dial down my consumption of bite-sized nuggets of online information, and finish a few books. That s where my bottleneck has been for the past year or so. Not in selecting books, not in acquiring books, and not in starting books either. I identify promising books, I buy them, I start reading them, and at some point, I put them down and never pick them back up again.
Until now. Over the weekend, I finished two books. I started reading both in 2009, and they each required my sustained attention for a period measured in hours in order to finish them.
Taking a tip from Dustin, I decided to try alternating between fiction and non-fiction.
Jitterbug Perfume by Tom Robbins
This was the first book I had read by Tom Robbins, and I am in no hurry to read any more. It certainly wasn t without merit: its themes were clever and artfully interwoven, and the prose elicited a silent chuckle now and again. It was mainly the characters which failed to earn my devotion. They spoke and behaved in ways I found awkward at best, and problematic at worst. Race, gender, sexuality and culture each endured some abuse on the wrong end of a pervasive white male heteronormative American gaze.
I really wanted to like Priscilla, who showed early promise as a smart, self-reliant individual, whose haplessness was balanced by a strong will and sense of adventure. Unfortunately, by the later chapters, she was revealed as yet another vacant vessel yearning to be filled by a man. She s even the steward of a symbolic, nearly empty perfume bottle throughout the book. Yes, really.
Managing Humans by Michael Lopp
Of the books I ve read on management, this one is perhaps the most outrageously reductionist. Many management books are like this, to a degree. They take the impossibly complex problem domain of getting people to work together, break it down into manageable problems with tidy labels, and prescribe methods for solving them (which are hopefully appropriate for at least some of the reader s circumstances).
Managing Humans takes this approach to a new level, drawing neat boxes around such gestalts as companies, roles, teams and people, and assigning them Proper Nouns. Many of these bear a similarity to concepts which have been defined, used and tested elsewhere, such as psychological types, but the text makes no effort to link them to his own. Despite being a self-described collection of tales , it s structured like a textbook, ostensibly imparting nuggets of managerial wisdom acquired through lessons learned in the Real World (so pay attention!). However, as far as I can tell, the author s experience is limited to a string of companies of a very specific type: Silicon Valley software startups in the dot com era.
Lopp (also known as Rands) does have substantial insight into this problem domain, though, and does an entertaining job of illustrating the patterns which have worked for him. If you can disregard the oracular tone, grit your teeth through the gender stereotyping, and add an implicit preface that this is (sometimes highly) context-sensitive advice, this book can be appreciated for what it actually is: a coherent, witty and thorough exposition of how one particular manager does their job.
I got some good ideas out of this book, and would recommend it to someone working in certain circumstances, but as with Robbins, I m not planning to track down further work by the same author.
The eSATA SheevaPlug is supported by the Debian installer and by Debian
now. I've updated the 
<rant>Recently I've adopted a package, mainly as Merkaartor uses it now. It made me sad to see in which bad condition the package was. Here are just a few things I had to do to bring it into shape:
Following the
After one year in France, there's still something I cannot completely
understand; I don't know if it is something common in Europe, or a artifact of
the French law, or if it is just that French people like to do things so
formally all the time...
I was taking a look at the website of the 
In the past, I ve used PCI cards providing telephony TDM for my Asterisk-based projects. I ve only worked with Digium s FXO/FXS and T1/E1 cards, both in PCI and PCI-x formats, until a client asked for a gateway solution with FXO, FXS and E1, where using the PCI cards in a 1U IPBX was simply out of the question.
Using Ethernet gateways has always been a problem in those cases, since entry-to-medium level solutions lack the processing power for massive call handling, and signalling is poor, making the architecture unfit for reporting purposes and specialized apps such as call centers. But hey, that s my experience with gateways.
Therefore, I looked into Xorcom s Astribank. They pack FXO, FXS and PRI/BRI ports inside a convenient 19 1U case, which can connect to an Asterisk-based IPBX server via USB and gets recognized as an integral DAHDI device in modern setups.
So I ordered a composite 8xFXO, 8xFXS and 1xE1 PRI from Astribank, labelled 
Sometimes help is just around the corner, and all you have to do is
ask.
Not so long ago, I