Ingo Molnar has developed a patch to the Linux kernel that is an advanced remake of the task scheduler. The new scheduler is claimed to have O(1) complexity; as the Big O notation suggests, this means that the time taken to switch between tasks stays roughly the same while the number of tasks, active or otherwise, grows. This can greatly reduce latency and boost overall performance under substantial workload.

Other improvements include better scalability on SMP systems, achieved with reduced interlocking between CPUs, and improved CPU affinity, such that the task that runs on a particular CPU and primes its cache is rarely rescheduled to other CPUs, lest this would cause a lot of cache misses.

The most notable effects of this patch are good interactive performance and higher tolerance to heavy load. I.e. users don't perceive delays in response to keyboard and mouse actions, regardless of the number of tasks running. Also, it endorses aggressively multithreaded patterns in program execution: one can throw a bunch of threads at a problem and get away without penalty for switching between significant number of tasks.

To round up, the O(1) scheduler is an amazing feat of software engineering. It's spectacular that it was developed in the free software community. Bravo, Ingo.