Standard algorithms and boost::ptr_vector

I did something bad the other day.

OK, I can't tell if it was bad. In another environment, it would have been bad, but since this was C++, perhaps it was OK. I was in the situation where I had a boost::ptr_vector, and I wanted to use a standard algorithm on it. Specifically, I wanted to use std::partition to separate the objects that were still "alive" from those that were "dead" (where alive and dead are domain concepts in our application). The complexity here is that ptr_vector is a crazy container.

Most containers deal with a specific type T. You add Ts to the container. Dereferencing an iterator gives you a T&. It's generally assumed that a container operates on a single type, and the standard algorithms make this assumption.

The ptr_vector, on the other hand, appears to be two containers at once. Semantically, it's analogous to a std::vector<managed_ptr_type<T> >. It is intended that, by adding a pointer to the ptr_vector, the ptr_vector takes ownership of the lifetime of the memory at the end of the pointer. So, it is a container of pointers. On the other hand, when iterating a ptr_vector, it appears that it is a container of Ts.

In my case, I wanted to rearrange my ptr_vector. In particular, I wanted to partition the pointers into those whose object was still "alive", and those whose object was "dead". Since a ptr_vector is semantically a container of pointers, it made sense that I should apply std::partition to the ptr_vector. However, ptr_vector::iterator removes a level of indirection: instead of iterating T*, it iterates T&.

In fact, ptr_vector doesn't seem to provide any ways to rearrange the pointers once they are put into the container. Sure, you can mutate the object on the end of the pointer. You could operate at that level. But there doesn't appear to be a safe way to treat the ptr_vector as a container of pointers.

Fortunately, ptr_vector provides a back door. Its iterators support a base() method, which will return an iterator over T* (instead of an iterator over T&). This allows us to treat the ptr_vector as a container of pointers, and to use standard algorithms to manipulate those pointers. Now, this is not without peril. While it seems to be OK to rearrange the pointers, it wouldn't be safe to change the set of pointers. I wouldn't trust using something like std::remove_if, because it might leave garbage in the container after it is done. The container might contain duplicate pointers. Some pointers might get dropped completely. If the container then goes out of scope, it will try to delete these pointers multiple times, which would be a bad thing. It might also fail to delete some pointers, because they were overwritten (and not preserved elsewhere in the container).

This whole thing felt like the best solution possible, while at the same time leaving a lot to be desired. I felt like I was violating the encapsulation of the ptr_vector. I suppose this is one of those cases for which they put in the base() methods on the iterators. Additionally, I don't see any clear way that they could do better. For example, I think an assumption of ptr_vector is that a given pointer only occurs inside it at most once. The standard algorithms don't necessarily respect this assumption; see my commentary on remove_if in the previous paragraph. The standard algorithms, in some cases, expect more freedom than ptr_vector can provide. This disconnect is unfortunate, but not without reason.

An important first step to helping with this problem would be to add methods to ptr_vector (and its siblings) that allow you to treat it as a container of pointers. You could add, remove, and re-arrange the container using these methods. In addition, they could maybe provide specializations of some of the standard algorithms for each container. This is difficult for third party developers to do, since the actual type of a ptr_vector::iterator is implementation defined. The boost guys can cleanly provide a specialization of std::partition for this kind of iterator, but I can't. Now, this isn't perfect. It would help with the standard algorithms, but not third-party algorithms. Still, it would be a great step in the right direction.

So, did I do something bad, or did I do something necessary?

Why Google Experience phones are pretty awesome

As Android has grown, devices fall into one of two major classifications. Some devices are so-called "Google Experience" devices (featuring the phrase "with Google" somewhere on the device). Other devices are, well, not Google Experience devices. What is the difference? I've had a hard time figuring it out.

I think that Google Experience phones are updated by Google itself, while the rest of the devices are supported by the phone's manufacturer. I have an original G1 (a Google Experience phone), and I've gotten prompt updates as each new Android OS version has been released. This is similar to the experience that iPhone users enjoy.

Some devices, such as the HTC Hero and the Motorola Cliq (and the HTC Magic in certain regions), are not Google Experience phones. These phones were released with heavily customized software (such as HTC's Sense UI or Motorola's Motoblur). These customizations, while attractive to some users, also make it much harder for the phone manufacturer to update to a new version of the base Android OS. Both the Hero and the Cliq shipped with Android 1.5, and I don't believe that there are announced plans to update either to 1.6 (or 2.0, for that matter).

At first, I thought that the notion of a Google Experience phone was silly. At the time, the Magic was launching on Rogers with Exchange support, and that somehow disqualified the phone as being a Google Experience device. I now understand that Google Experience really means "unforked code base". In order to add Exchange support, I suspect that HTC had to fork and modify the standard Mail app. While they were able to add a feature that people wanted, it really just makes these phones into some sort of mutant Android device. No thank you. Google should really make it clear to users that the Google Experience is a feature in and of itself.

Android, at this point, is a rapidly evolving platform. Google Experience phones seem to be the best way to keep up with this evolution. I was pleased when I heard a Verizon rep say that the Droid will be a Google Experience phone. Now they just need to release a T-Mobile US GSM version, and I'll be happy. Over time, Android evolution will slow down, and then it might make sense for a manufacturer to fork the Android code base. Maybe they would even be willing to contribute back to the core distribution. But, until then, I'm sticking with Google Experience devices.

Fixing hard disk clicking / aggressive head parking on Mac OS X

I recently bought a Western Digital Scorpio notebook hard drive to put into my 2007-vintage Macbook Pro. Everything seemed fine at first. However, as I used my laptop, I noticed that it would frequently make a quiet clicking noise. At first, I thought that I had gotten a bad disk. However, after doing a little research, it became clear that this is a common problem. This clicking is a "normal" operational noise - it is the sound of the heads parking.

People say that you should just get used to the noise. However, this blog post makes the argument that every one of these clicks is killing your hard disk. Some people claim that this is related to the sudden motion sensor that's built into most (if not all) Apple portables. However, this is a red herring. The disk still clicks even if it is sitting on a table. It is the hard disk's own built-in power management that is causing the head parking. The disk's SMART statistics record the number of head parking cycles. If you want to see this for yourself, you can use either this menu extra or this command line tool (MacPorts). You are looking for the Load Cycle Count value.

To explain the problem (as I understand it), modern hard disks have some responsibility to manage their power consumption. One manifestation of this is to spin down the platters and to park the read/write heads. The operating system can influence the time before the heads are parked by setting the "APM Level" of the drive to a value between 0x00 and 0xfe. Each drive manufacturer is free to interpret this value as they see fit. Mac OS X seems to set a default APM Level for all disks, and I think this value is 0x80. This is fine with Apple-shipped disks, but not necessarily for third party disks.

But wait! Perhaps you have bought the same kind of drive that Apple ships in their laptops. Are you safe? Not necessarily. Allegedly, Apple flashes their own firmware onto the the hard disks that they install at the factory. That's right, you're not running stock disk firmware. My suspicion is that this firmware changes the drive's interpretation of the default APM level. Recently, there was a firmware update from Apple that fixed this problem on disks that were shipped by Apple. Unfortunately, you can't use this utility to flash the new firmware onto a non-Apple drive.

Right, so the two solutions that I see are either:

1. Write our own firmware
2. Set a different APM Level value

Obviously, option 2 looks much more attractive. Bryce McKinlay wrote a utility called hdapm for doing just that. He even includes a launchd configuration to run hdapm as the system starts. One thing not mentioned in the readme is that you need to get the permissions of the launchd config file correct. The file needs to be owned by root (preferably root:wheel), and must not be group- or world-writeable. I also changed the config file a little; here is my version:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
 <key>Label</key>
 <string>hdapm</string>
 <key>ProgramArguments</key>
 <array>
  <string>/usr/local/bin/hdapm</string>
  <string>disk0</string>
  <string>max</string>
 </array>
 <key>RunAtLoad</key>
 <true/>
</dict>
</plist>

The biggest change is that I removed the "LaunchOnlyOnce" and "ServiceDescription" keys. I didn't see a reason to load it only once, and ServiceDescription seemed undocumented. This solution isn't perfect, however. First of all, hdapm uses a seemingly undocumented back door to adjust the APM setting. Ideally, we would actually spawn a daemon that continuously monitors and adjusts the drive's APM level. I'm not yet convinced that Mac OS X won't override my setting. Still, I have been running with this configuration for a couple of days, and things seem to be working well.

I have an open support issue with Western Digital to see if they have a fix for this issue. If there were some way that we could change the way the disk behaves under OSX, we could forego the additional software, which would be great. I've also heard of a utility called wdidle, which allegedly lets you write new idle settings to the hard drive. However, I was unable to find any official site for this software, so I'm not using it.

Finally, I would like to thank two people. First, Doug Aghassi's post really explained the symptoms that he was experiencing and put me on the right track for solving the problem. Thanks, Doug. Also, Bryce McKinlay was kind enough not only to write the hdapm utility, but also to answer the questions that I emailed to him. Thanks, Bryce.