From the Canyon Edge -- :-Dustin

Sunday, June 21, 2009

Prime Numbers for the Win!

The Sieve of Eratosthenes

I minored in Mathematics in college. But as much as I have always loved math, I use it surprisingly little during my day-to-day computer programming. Perhaps this is why I'm excited about the latest Byobu releases.

Byobu-2.12 and 2.13 have introduced some tremendous performance enhancements, mostly surrounding the status gathering scripts.

I have gone over each of these with a fine-toothed comb, trying to make them as efficient as possible. I wrote a testing framework that ran these scripts millions of times to identify the most expensive operations. The improvements mostly involved reducing the number of shells and forks necessary to gather and print the information, and using files resident in memory, such as /var/run and /proc. In the long run, these scripts would probably perform better as compiled C programs. But I'm not yet willing to give up the simplicity and portability of the current shell scripts.

Aside from the scripts' contents, I also modified the intervals in which they run.

In Ubuntu 9.04, screen-profiles-1.44 ran the status scripts at the following intervals:
SECONDS   STATUS
2         cpu-freq
2         load-average
2         mem-used
2         network-down
2         network-up
2         processes
2         reboot-required
2         wifi-quality
10        updates-available
10        users
30        battery
60        uptime
600       ec2-cost
3600      hostname
3600      release
86400     arch
86400     cpu-count
86400     logo
86400     mem-available
86400     menu
86400     whoami


This means that:

  • Every 2 seconds, Byobu will run each of (cpu-freq, load-average, mem-used, network-down, network-up, processes, reboot-required, wifi-quality).

  • Every 10 seconds, Byobu will run (updates-available, users), plus all of the 2-second scripts.

  • Every 30 seconds, Byobu runs (battery), plus the 10-second scripts, plus the 2-second scripts.

  • Every 60 seconds, Byobu runs (uptime), plus the 30-second, 10-second, and 2-second scripts.
  • etc.


These particular intervals result in some unfortunate harmonics, which are not a good thing in terms of Byobu's responsiveness. The battery script, for instance, only runs twice a minute because it's relatively expensive. However, at that 30-second interval, the battery script must also share time with the 10- and 2-second scripts. As you can see, we're going to have a couple of standing waves, that periodically cause some rather expensive refreshes of Byobu's status bar.



This was reported as several bugs, noting that Byobu causes screen to "stutter" every 2 seconds or so, with an even longer "delay" at 10 seconds. In older versions of Byobu, if you toggle all status notifications "on", and then scroll through a rather long file, you'll see it pause or stutter every few seconds. Try, `find /lib | less`, and hold the down-arrow key.

How do we solve this problem? Prime numbers!

If we set the Byobu status updates to happen at prime intervals, rather than (2, 10, 30, 60, ...), we can greatly reduce the expensive, compounded updates. We can spread the updates out more evenly over time, without stacking them up as much and creating particularly expensive intervals.

Based on the automated testing and statistical analysis of each script, Byobu is now configured to run the status scripts at the following prime numbered intervals:
SECONDS   STATUS
2         cpu_freq
2         load_average
3         network
5         mail
5         reboot_required
7         processes
11        users
13        disk
13        mem_used
17        wifi_quality
19        temp_c
19        temp_f
29        uptime
61        battery
181       updates_available
599       release
601       ec2_cost
607       hostname
613       ip_address
86011     logo
86017     cpu_count
86027     mem_available
86029     whoami
86077     arch


Now, at any given time interval, we'll only run the status updates corresponding to the prime factors of that interval. So instead of a relatively expensive set of updates running at the 60-second mark, we only run 5 scripts (cpu_freq, load_average, network, mail, reboot_required), rather than 12 scripts in the old model!

The following chart shows time (in seconds) on the x-axis, and the number of scripts that need to run on the y-axis. In red, you have data from screen-profiles-1.44 (in Ubuntu 9.04), and in blue, you have current byobu-2.13 (in Karmic). We have reduced the average number of scripts that need to run per second. More importantly, we have tremendously reduced the harmonic spikes where previously we peaked running a dozen or more scripts at any one time.



In the latest Byobu release (2.13), responsiveness should be much better. The network status item is still the most expensive notification, but even it has improved. With the network item turned off, though, there should be no noticeable stutter in your Byobu sessions.

Prime numbers for the win!

:-Dustin

Printfriendly