Older blog entries for pphaneuf (starting at number 318)

Saving what again?

As it turns out, this year's change in the implementation of daylight "savings" ended up not saving anything, and actually just causing extra annoyance. The US Congress seems completely taken by surprise by the fact that changing the time does not magically create more sunlight. That extra hour in the evening, scientists and the Department of Energy reminds them, is actually offset by an hour less in the morning! Imagine that!

Seems like there is not even a measurable energy savings. If anything, the biggest impact of the daylight savings change is that a bunch of computerized gadgets needed to be updated, and people with their Blackberry and Palm not being sure if the time was adjusted (some changed the time manually, only to have it change by another at the old switch-over date, for example).

Down with daylight savings! End the madness!

Syndicated 2007-05-21 05:41:05 (Updated 2007-05-21 05:44:15) from Pierre Phaneuf

My birthday is coming up, you know?

OMG, I so want one of these!

Syndicated 2007-05-16 06:59:38 from Pierre Phaneuf

Reboot

Last weekend, I got my residency permit turned down, which, to make a long story short, means that we'll be heading back to Canada. Seems like I was misdirected by the Consulat de France in Montreal, and from what I hear, it seems to be something they've done a few times ([info]azrhey worked in a place here where they hire a lot of foreigners, due to language skills).

So, it looks like I'm going to be looking for a job back in Montreal.

My weapons of choice are C++ and Perl, but being a Unix/Linux hacker, of course, I am not limited to those, they're just the ones I'm most deadly with. I am comfortable with meta-programming (mostly, but not limited to that of C++ templates), continuations/coroutines, closures, multithreading, as well as event-driven state machines. I am quite effective at code refactoring, particularly in strongly typed languages, where I can use the typing system to my advantage.

I am deeply intimate with Unix/Linux, mainly in the area of network programming (sockets, networking protocols, other forms of IPC). On Linux, I am quite familiar with a number of the high-performance APIs. I have a deep knowledge of the HTTP protocol (and some of its derivatives). I have experience writing Apache modules. I know the difference between bandwidth and latency (and wish more people did too). I have some experience with developing distributed software. I have a higher-than-average knowledge of ELF and Mach-O binary formats, particularly of how symbol resolution works. I know a good deal about component software (dynamically loading modules, for example), and ABI stability issues. While I am not a master at it, I have some Linux kernel development experience as well. I know what make is doing, and why.

Finally, I also have some experience doing project and release management, where I feel I did a pretty good job, and would certainly like to do more of it. I am familiar with the free and open source software community, belonging to a number of projects, including some that were part of my work.

Syndicated 2007-05-12 17:45:47 from Pierre Phaneuf

Down with the Daylight Savings!

Two PhD students in economics at Berkeley are studying the effect of daylight savings observance in Australia (which had a partially extended DST during the Olympics of 2000, thus providing useful data on the subject) and are making such shocking discoveries such as "the extra hour of light in the evening is at the cost of an extra hour of darkness in the morning"! No, really? Wow!

More seriously, it would seem that instead of saving anything, it could actually even have had a slight increase in power use. There are also some reports of increased car usage, but I'm finding that a bit sketchy (are people really that crazy? maybe I'm just too much of an optimist).

In any case, at worst, it generated this hilarious comment on good old Slashdot. Heh.

Syndicated 2007-03-12 15:57:38 from Pierre Phaneuf

10 Mar 2007 (updated 18 May 2008 at 07:14 UTC) »

Message passing? Yes!

[info] lkcl posted a reply to my previous post...

Oh, lkcl, you're a bit of a pessimistic, there. unlink is also atomic, not just rename. ;-)

But what I'm looking after right now isn't just a general message-passing operation (I already do that at a higher level, between various subsystems, using shared memory for local or sockets for remote recipients), more specifically the best way to take advantage of multiple cores as much as possible to process file descriptor events.

You have to cut the libc people some slack, though, they don't have locks around every single functions. I'd be amazingly appalled if strncmp() took a lock, for example! And as I described, I already used processes and shared-memory for higher-level concurrency, this threading is only for the very lowest level, when I have no choice and I'm pushed to the edge. Note that the code is already written as a state machines, using the threads to run more than one state machine at once (there is one state machine per connection or so, more or less). I'm planning on having a lock on the state machine instance, so that a single state machine cannot be executed on more than one thread at once, so that the code inside of it can make that assumption (that still allows me to handle multiple independent connections at once).

On Linux, epoll already does that in an atomic way, for me, in its edge-triggered mode. You can just have multiple threads call epoll_wait(), a given event will be sent to only one thread, until it is re-armed. But the specific requirement here is "compatibility layer for portability to other POSIX platforms", hence the use of crummy old select(). Of course, if I need high-load scalability on some big iron, I'll be sure to not use that layer, and go for epoll, kqueue() or something like that!

That said, I'd like a link to that message-passing work, it sounds interesting.

Syndicated 2007-03-10 18:49:00 (Updated 2008-05-16 18:47:53) from Pierre Phaneuf

Insight of the day

I must be very silly, but I just realized that a Unix pipe is a semaphore. It's better in some aspects (is select()able) and worse in others (SEM_VALUE_MAX is lower). Cool.

In that context, the "signal handler that writes to a pipe" trick makes a new kind of sense (the semaphore equivalent, sem_post(), is the only synchronization function that is safe to use in a signal handler).

Syndicated 2007-03-08 12:34:38 (Updated 2007-03-08 12:38:16) from Pierre Phaneuf

7 Mar 2007 (updated 8 Mar 2007 at 09:05 UTC) »

select() and a thread pool

Here's the challenge: a select()-based event dispatcher that can scale from single-threaded to multi-threaded efficiently, preferably as simple as possible and able to be effectively edge-triggered (even if select() itself is level-triggered).

Note that the point here is to run the event handlers concurrently. I've used threads in the past to work around deficiencies in select(), putting "quiet" file descriptors on one thread that would sleep most of the time, and "busy" file descriptors on another (since select() scales based on the number of file descriptors it watches, this made the active set more efficient), but it would still only use one thread for event handlers. It was just about sleeping more efficiently.

My first idea was that all threads would be symmetrical and would thus all sleep in select(). But that doesn't work, obviously, because as soon as one file descriptor is ready, all the threads wakes up, which is rather wasteful. Splitting the set of file descriptors between the threads isn't so good, because a scheduler would then be needed to balance the load between threads, and I prefer to leave scheduling to the kernel, as much as possible. On the other hand, this could allow better cache locality, handling the same file descriptor on the same thread (possibly bound to the processor) as often as possible, but on the third hand, let's not get ahead of ourselves.

It seems that the only way is to keep all the file descriptors together, with just one thread calling select(). When it returns, it should be examined and all the events put on a list. Then it goes into a loop of taking an event from the head of the list, posting the semaphore of the next thread (which could be itself in the single-threaded case), calling the event's handler, then waiting on the semaphore. If there was no event left, it goes back to select() instead.

There's a few good bits and a few bad bits about this design. A good bit is that the semaphores that keeps the other threads sleeping also protect the list at the same time (that's why it's posted after taking the next event). A bad bit is that at the end, we would be going into the select() before all the handlers are done, and they might want to add some file descriptors. This could be fixed by having a counter of threads busy running handlers, and the last thread that would be out of events would be the one going back into select(), but this would also make the load more "bursty" in a busy server, where there's really work all the time, but at every round of select(), all the threads but one would go to sleep, only to be reawakened.

I think, in the end, that the usual Unix solution comes to the rescue: add a file descriptor! Having the reading end of a pipe in the select() invocation, and adding a file descriptor from a handler would write to the writing end, waking up the select() as needed. A bit of a shame, since it would be unnecessary in the single-threaded case, but oh well, that's how it is sometimes...

Anyone has suggestions for improvements? They are most welcome!

Syndicated 2007-03-07 18:34:43 (Updated 2007-03-08 08:44:17) from Pierre Phaneuf

5 Mar 2007 (updated 18 May 2008 at 07:14 UTC) »

Edge- Versus Level-Triggered Events

A good while ago, I declared my preference for edge-triggered events (for I/O), because in my mind, it most closely paralleled the actual workings of the hardware (IRQs being triggered when new data arrives on network interfaces or when a read/write request to disk is completed). I also figured that since it was possible to emulate level-triggered efficiently on top of edge- (that's what happens when you use close-to-the-metal "abstractions"), it probably was the more flexible choice.

I then changed my mind, when I realized that what is very often needed is level-triggered, someone has to remember what file descriptor still has work to do. I figured that it might as well be the kernel, since it is in the best position to do that safely, simply and efficiently. Otherwise, you end up either having to remember myself (which isn't very safe if your framework is only providing the event delivery mechanism, a buggy user could easily "get lost"), or to re-arm the file descriptor (more system calls, less efficient). On the other hand, there were also some other relatively common usage where edge-triggered was preferable (specifically, when transferring data from one file descriptor to another, where you do not want to re-arm the source until you managed to write the data to the sink first.

But recently, I changed my mind again, and about a certain number of things. Many know me to be one who
dislikes threads, but it's not exactly true, I have a dislike of how it's haphazardly used as magic pixie dust by hordes of people who are apparently utterly confused by event-driven state machines. Now that we're seeing more and more multi-core systems, I feel something has to be done about it. And it turns out that level-triggered events are a bit of a pain to handle with multiple threads: a thread going into epoll_wait could get a notification that a file descriptor is readable while another thread is in the process of dealing with it. Adding a monitor to prevent re-entrance would just make it busy-wait instead, as it wouldn't sleep. Edge-triggered events deal with this neatly, and I think this combines with the existing cases where it was preferable to make them actually the better choice.

Now, I want to have a select()-based reference implementation, for portability, and it turns out it's kind of tricky to have multiple thread service a common set of file descriptors... I have some ideas, but that'll be for next time.

Syndicated 2007-03-05 19:21:21 (Updated 2008-05-16 18:44:27) from Pierre Phaneuf

309 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!