Fri, 18 Apr 2008
One of the freedoms I value is the freedom to choose what you spend your time on and who you spend it with. And while I’ve spent a lot of time arguing that people in key roles in Debian still have those freedoms (hey, 2.1(1), don’t you know), reality these days seems to be otherwise. But hey, solving that quandry just requires a mail to DSA.
To folks on the core teams I’ve been involved with: it’s been a pleasure and an honour working with you; if not always, at least mostly. Best of luck, and I hope y’all accept patches.
Tue, 15 Apr 2008
Last month we had a brief discussion on debian-devel about what images would be good to have for lenny – we’re apparently up to about 30 CDs or 4 DVDs per architecture, which over 12 architectures adds to about 430GB in total. That’s a lot, given it’s only one release, and meanwhile the entire Debian archive is only 324GB.
The obvious way to avoid that is to make use of jigdo – which lets you recreate an iso from a small template and the existing Debian mirror network. I’ve personally never used jigdo much, half because I don’t usually use isos anyway, but also because the few times I have tried jigdo it always seemed really unnecessarily slow. So the other day I tried writing my own jigdo download tool focussed on making sure it was as fast as possible.
The official jigdo download tool, ttbomk, is jigdo-lite – which you give a .jigdo file, and the url of a local mirror. It then downloads the first ten files using wget, and once they’re all downloaded, it calls jigdo-file to get them merged into the output image. This gets repeated until all the files have been downloaded.
By doing the download in sequence like this, you miss out on using your full network connection in two ways: one during the connection setup latency when starting to download the next package, and also while jigdo-lite stops downloading to run jigdo-file. And if you’ve got a fast download link, but a slower CPU or disk, you can also find yourself constrained in that you’re maxing those out while running jigdo-file, but leaving them more or less idle while downloading.
To avoid this, you want to do multiple things at once: most importantly, to be writing data to the image at the same time as you’re downloading more data. With jigdodl (the name I’ve given to my little program), I went a little bit overboard, and made it not only do that, but also manage four downloads and the decompression of the raw data from the template. That’s partly due to not being entirely sure what needed to be done to get a speedy jigdo program, and partly because the communicate module I’d just written to deal with this sort of parallelism making that somewhat natural.
In the end, it works: from wireless over ADSL to my ISP’s Debian mirror, I get the following output:
Jigsaw download: Filename: debian-40r3-amd64-CD-1.iso Length: 675477504 MD5sum: d3924cdaceeb6a3706a6e2136e5cfab2 Total: 679 s; d/l: 586 MB at 883 kB/s; dump: 57 MB at 57 MB/s Finished!
which is only slightly short of maxing out my downstream bandwidth, taking a total of about 11m20s. Running jigdodl with a closer mirror works pretty well too, though evidently some of my more recent changes weren’t so great, because I’ve gone from 9153 kB/s on a 100 Mbps link down to 7131 kB/s or lower. The CPU usage also seems a bit high, hovering at between five to ten percent at 900 kB/s.
For comparison, running jigdo-lite on the same file took 17m41s, which is about 566 kB/s, with the overhead being about 6m20s. What that means is if I doubled my bandwidth to about 20Mbps, jigdodl would halve its time for the download to about 5m50s, while jigdo-lite would still have about the same non-download overhead, and thus take 12m10, which is still 69% of its original speed. Going from 10Mbps ADSL speed to 100Mbps LAN gets jigdodl down to 1m31s (13% of the time, with optimal being 10%), while jigdo-lite would be expected to still be about 7m51s (43% of its original time).
I suspect the next thing to do is to rewrite the downloading code to use python-curl instead of running curl, and thus downloading multiple files with a single connection, and tweaking the code so that it writes the file in order, rather than updating whichever parts are ready first.
Anyway, debs are available for anyone who wants to try it out, along with source in the new git source package format.
In a couple of days, DPL-elect Steve McIntyre takes over as DPL, after being elected by around four hundred of his peers… Because I can’t help myself, I thought I might poke at election numbers and see if anything interesting fell out.
First the basics: I get the same results as the official ones when recounting the vote. Using first-past-the-post, Steve wins with 147 first preference votes against Raphael’s 124, Marc’s 90 and NOTA’s 19 (with votes that specify a tie for first dropped). Using instant-runoff / single transferable vote, the winner is also Steve, with NOTA elimited first and Marc collecting collecting 5 votes, Steve 4 and Raphael 2, followed by Marc getting eliminated with Steve collecting 50 votes, against Raphael’s 26.
So, as usual, different voting systems would have given the same result, presuming people voted in basically the same way.
NOTA really didn’t fare well at all in this election, with a majority of voters ranking it beneath all candidates (268 of 401, 53.5%). For comparison, only 18 voters ranked all candidates beneath NOTA, with 9 of those voters then ranking all candidates equally. (For comparison, in 2007, 312 of 482 voters (about 65%) ranked some candidate below NOTA, though that drops to 225 voters (47%) if you ignore voters that just left some candidates unranked. Only 98 voters (20%) voted every candidate above NOTA)
With NOTA excluded from consideration, things simplify considerably, with only 13 possible different votes remaining. Those come in four categories: ranking everyone equal (17 votes, 9 below NOTA as mentioned above, and 8 above NOTA), ranking one candidate below the others (13 votes total, 7 ranking Raphael last, 3 each for Steve and Marc), ranking one candidate above the others (66 votes; 30 ranking Steve first, 18 each ranking Raphael and Marc first), and the remainder with full preferences between the candidates:
70 V: 213
63 V: 123
56 V: 132
52 V: 231
38 V: 312
26 V: 321
The most interesting aspect of that I can see is that of the people who ranked Raphael first, there was a 1.8:1 split in preferring Steve to Marc, and for those who preferred Marc first, there was a 2:1 split preferring Steve to Raphael. For those who preferred Steve, there was only a 1.1:1 split favouring Raphael over Marc.
I think it’s fair to infer from that that not only was Steve the preferred candidate overall, but that he’s considered a good compromise canidate for supporters of both the alternative candidates (though if all the people who ended up supporting Steve hadn’t been voting, Raphael would have won by something like 26 votes (129:103) with a 1.25:1 majority; if they had been voting, but Steve hadn’t been a candidate, Raphael’s margin would’ve increased absolutely to 33 votes (192:159) but decreased in ratio to a 1:1.2 majority.
Thu, 10 Apr 2008
One of the loveliest things about Unix is the select() function (or its replacement, poll()), and the way it lets a single thread handle a host of concurrent tasks efficiently by just using file descriptors as work queues.
Unfortunately, it can be a nuisance to use – you end up having to structure your program as a state machine around the select() invocation, rather than the actual procedure you want to have happen. You can avoid that by not using select() and instead just having a separate thread/process for every task you want to do – but that creates a bunch of tedious overhead for the OS (and admin) to worry about.
But magically making state machines is what Python’s generators are all about; so for my little pet project that involves forking a bunch of subprocesses to do the interesting computational work my python program wants done, I thought I’d see if I could use that to make my code more obvious.
What I want to achieve is to have a bunch of subprocesses accepting some setup data, then a bunch of two byte ids, terminated by two bytes of 0xFF, and for each of the two byte inputs to output a line of text giving the calculation result. For the time being at least, I want the IO to be asynchronous: so I’ll give it as many inputs as I can, rather than waiting for the result before sending the next input.
So basically, I want to write something like:
def send_inputs(f, s, n): f.write(s) # write setup data for i in xrange(n): f.write(struct.pack("!H", i)) f.write(struct.pack("!H", 0xFFFF)) def read_output(f): for line in f: if is_interesting(line): print line
Except of course, that doesn’t work directly because writing some data or reading a line can block, and when it does, I want it to be doing something else (reading instead of writing or vice-versa, or paying attention to another process).
Generators are the way to do that in Python, with the “yield” keyword passing control flow and some information back somewhere else, so adopting the theory that: (a) I’ll only resume from a “yield” when it’s okay to write some more data, (b) if I “yield None” there’s probably no point coming back to me unless you’ve got some more data for me to read, and (c) I’ll provide a single parameter which is an iterator that will give me input when it’s available and None when it’s not, I can code the above as:
def send_inputs(_): # s, n declared in enclosing scope yield s for i in xrange(n): yield struct.pack("!H", i)) yield struct.pack("!H", 0xFFFF) def read_output(f): for line in f: if line is None: yield None; continue if is_interesting(line): print line
There’s a few complications there. For one, I could be yielding more data than can actually be written, so I might want to buffer there to avoid blocking. (I haven’t bothered; just as I haven’t worried about “print” possibly blocking) Likewise, I might only receive part of a line, or I might receive more than one line at once, and afaics a buffer there is unavoidable. If I were doing fixed size reads (instead of line at a time), that might be different.
So far, the above seems pretty pleasant to me – those functions describe what I want to have happen in a nice procedural manner (almost as if they had a thread all to themselves) with the only extra bit the “None, None, continue” line, which I’m willing to accept in order not to use threads.
Making that actually function does need a little grunging around, but happily we can hide that away in a module – so my API looks like:
p = subprocess.Popen(["./helper"], stdin=PIPE, stdout=PIPE, close_fds=True) comm = communicate.Communication() comm.add(send_inputs, p.stdin, None) comm.add(read_output, None, p.stdout, communicate.ByLine()) comm.communicate()
The comm.add() function takes a generator function, an output fd (ie, the subprocess’s stdin), an input fd (the subprocess’s output), and an (optional) iterator. The generator gets created when communication starts, with the iterator passed as the argument. The iterator needs to have an “add” function (which gets given the bytes received), a “waiting” function, which returns True or False depending on whether it can provide any more input for the generator, and a “finish” function that gets called once EOF is hit on the input. (Actually, it doesn’t strictly need to be an iterator, though it’s convenient for the generator if it is)
The generator functions once “executed” return an object with a next() method that’ll run the function you defined until the next “yield” (in which case next() will return the value yielded), or a “return” is hit (in which case the StopIteration exception is raised).
So what we then want to do to have this all work then, is this: (a) do a select() on all the files we’ve been given; (b) for the ones we can read from, read them and add() to the corresponding iterators; (c) for the generators that don’t have an output file, or whose output file we can write to, invoke next() until either: they raise StopIteration, they yield a value for us to output, or they yield None and their iterator reports that it’s waiting. Add in some code to ensure that reads from the file descriptors don’t block, and you get:
def communicate(self): readable, writable = [], [] for g,o,i,iter in self.coroutines: if i is not None: fcntl.fcntl(i, fcntl.F_SETFL, fcntl.fcntl(i, fcntl.F_GETFL) | os.O_NONBLOCK) readable.append(i) if o is not None: writable.append(o) while readable != [] or writable != []: read, write, exc = select.select(readable, writable, []) for g,o,i,iter in self.coroutines: if i in read: x = i.read() if x == "": # eof iter.finish() readable.remove(i) else: iter.add(x) if o is None or o in write: x = None try: while x is None and not iter.waiting(): x = g.next() if x is not None: o.write(x) except StopIteration: if o is not None: writable.remove(o) return
You can break it by: (a) yielding more than you can write without blocking (it’ll block rather than buffer, and you might get a deadlock), (b) yielding a value from a generator that doesn’t have a file associated with it (None.write(x) won’t work), (c) having generators that don’t actually yield, and (d) probably some other ways. And it would’ve been nice if I could have somehow moved the “yield None” into the iterator so that it was implicit in the “for line in f”, rather than explicit.
But even so, I quite like it.