Too Busy For Words - the PaulWay Blog

Since Tridge's talk in 2005 about the wonders of (among other things) talloc, and having Rusty give me a rundown on his own "use talloc or live in sin" talk at LCA 2006 (which I was going to be elsewhere for, unfortunately), I've been using talloc in my C programming for work. While those still into endless pointer maintenance and doing everything by hand might scoff at something that almost but not quite does garbage collection for you, it's been invaluable for saving me having to write and debug a lot of tedious memory clean-up code.

Unfortunately, I have a minor hassle. I'm creating a tree/array hybrid structure - each node has four pointers to subnodes (because I'm dealing with nucleotide bases - A, C, G and T), and rather than have a single root I allocate an array of nodes at the 'minimum tree level'. The structure isn't very complex - it's basically six pointers and an unsigned long count - and even with eight-byte pointers it takes about 56 bytes in memory.

So imagine my chagrin when I discover that the talloc structure that's invisibly maintained behind all that is over twice the size of my tree structure.

This is a problem because, even with 4GB in the machine, the tree structure can easily take up 1GB. Even with a relatively small sample of virus sequences - only 4MB or so of uncompressed data - the tree out to length 21 is 29 million nodes or 1,506MB. Triple that usage and we move to The Valley Of Eternal Disk Paging. It's a small comfort to find out that the internal tally of how much memory has been used by the structures directly is exactly what it should be according to the number of nodes actually allocated. And I'm aiming for much larger sequence sizes too - the shortest human gene is about 12MB in size. You can forget about trying to page that in, out and all about.

Of course, I need to consider moving beyond the bounds of RAM and into using disk - intelligently, not by creating a massive swap file. I can't expect 4GB to always be there, or for my requirements to always fit within the constraints of my memory limitations. So I need to do some research into alternative techniques.

The main avenue I'm working on is a 'slab' allocator, where 'slab' here means 'a chunk of 65536 structures'. Instead of each node having a pointer to its branches, it has an unsigned short slab number and unsigned short positition in that slab. Looking that up then requires a couple of relatively quick array lookups (depending on your implementation). Sure, it's not going to be as fast as direct pointer linking, but the talloc overhead goes way down because suddenly you only have an overhead per slab rather than per node.

And I think I need to find out how mmap works...