Installing iPhone Apps: Apple Doesn’t Care About Average Completion Time

Having recently spent some time outside the US, I found, upon my return, that many of the Apps on my iPhone needed to be updated. No big deal: I clicked “Update all”, typed in my password, and let the operating system finish the job. After watching the update process for a minute or so, I noticed one interesting fact: Apps were updated (i.e. downloaded+installed) in the order the updates became available (chronologically increasing), rather than by increasing order of the size of the update (in bytes). If you’re asking “why does it matter?”, read on.

During my grad school years at Carnegie Mellon, I had the pleasure of taking the Sequencing and Scheduling class with Egon Balas (I later sat in the class again as his TA, and finally taught it to the MBA students in 2004). So let’s start with some terminology: given a machine (the iPhone) and a set of tasks (Apps) to be executed (updated) on the machine, the completion time of a task is the time at which it is finished. For example, let’s assume the Concorde TSP App needs an update. If time zero is the moment I enter my iTunes password, the completion time of task “Concorde TSP” is the earliest time at which this App’s latest version is ready to run on my iPhone. The total completion time of a set of tasks is simply the sum of the completion times of all tasks, and the makespan is the completion time of the task that gets updated last.

The App update process has no release dates (all outdated Apps are ready to be updated at time zero), is non-preemptive (once started, the update of an App continues until it’s finished; ignoring crashes and other issues), and doesn’t involve sequence-dependent setup times (as soon as an App finishes updating, the next App in line can start its update right away). Under these circumstances, the makespan of a group of outdated Apps is always the same, regardless of the order in which they get updated. For example, if App A takes 15 seconds to download and install, and App B takes 10 seconds to download and install, it will take me 25 seconds to update both of them, regardless of which one is updated first. So far, so good. But let’s see what happens with the total (or average) completion time.

Continuing with the two-App example above, if I update the Apps in the order A, B, the completion time of A is 15, and the completion time of B is 25. The total completion time is 15+25=40, and the average completion time is 40/2=20 seconds. If the Apps are updated in the reverse order B, A, the completion time of B is 10, and the completion time of A is 25. The total completion time now is 10+25=35, and the average completion time decreases to 35/2=17.5 seconds. If there were other Apps being updated before or after the pair A, B, swapping them to make sure that B goes before A (because B takes less time) would have the same effect (the A, B swap doesn’t change the completion time of other Apps). What I just explained is called an exchange argument. It proves that whenever two Apps are out of order (in the sense that a smaller one is placed after a larger one), swapping them reduces the total/average completion time. Therefore, the minimum total/average completion time is obtained when the Apps are sorted by increasing order of duration. In the scheduling literature, this is called the SPT rule (Shortest Processing Time first).

I still haven’t answered the question of whether all of this matters because the makespan doesn’t depend on the order of Apps (updating A and B always takes 25 seconds). The answer is I don’t know! It’s a psychological effect. Shorter completion times may give the user the impression that the update process is going fast because a bunch of small Apps get updated quickly. By updating larger Apps first, the user may have the impression that the process is taking longer because, after a while, there are still many Apps to go. Should Apple worry about this? I’ll leave that question to my colleagues in the Marketing department who specialize in Consumer Behavior. If the answer turns out to be “yes”, then you now know what to do.

P.S. I’d like to know what other mobile operating systems do. Do they use SPT? Please let me know in the comments.


Filed under Applications, iPhone

5 responses to “Installing iPhone Apps: Apple Doesn’t Care About Average Completion Time

  1. prubin73

    I don’t know if this applies to an iPhone (don’t have one), but if it’s impossible/unsafe to use an app when its update is queued, then SPT makes the most apps available soonest. If size/complexity is positively correlated to importance, though, LPT might be best (get that huge and really important app ready first).

  2. The OS could actually start to download B while installing A, this would speed things up just a bit. Amd make the scheduling hard, since even though times are somewhat proportional to size, network speed has a huge influence. And also, what other things you do while installing has an impact on the install speed.

    From a security standpoint, it makes sense to install the oldest update first, after all, that is the one you are least up-to-date on.

    On the other hand, if the network fails, then what do you prefer, the big one installed first, to get it out of the way, or several smaller ones?

    At the end of the day, you install all of your updates anyways, so it really doesn’t matter. MS seems to be the same with windows, ie, just install in the order they are released in.

  3. “I still haven’t answered the question of whether all of this matters”

    I hadn’t thought about it before, but I think it does matter. If you’re updating a lot of apps then *all* of them switch to “waiting” status, and slowly become usable again one by one as they are updated. If they ordered the updates by completion time then I would have access to more of my apps for more of the time.

  4. Also, updates can depend on each other (not very likely with apps, but possible), so it is safer to install oldest first.

  5. orbythebeach

    Thank you all for your comments. They touch on important issues that I did not talk about. Imre: as you pointed out, I’m assuming that it’s rare for Apps to depend on each other (maybe this is more likely in Android or a jailbroken iPhone). But I think we all agree that perhaps oldest-first isn’t always the best way to go.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s