CPISync Performance - A Breakdown of the Major Performance Issues in the System

  Figure 3 shows the performance of CPISync in the time required to synchronize with an increasing number of differences between the data sets. Each separate part of the system is colored differently, to show how much time each one takes out of the whole process. The breakdown is as follows (from least to most time consuming):

1) Misc. Tasks - These are the routine tasks that must be done in any programming environment. The cost of allocating and de-allocating heap memory as well as some informational calls to the PalmPilot are included here.

2) Characteristic Evaluations Transfer - This is the time it takes to transfer the sample points stored on the PalmPilot to the PC over the network (in this case, a 115k serial link).

3) CPISync - This is the time spent in actaul computation on the PC. Although the CPISync algorithm is cubic in the "number of differences", this really means that it is cubic in the upper bound on the number of differences (i.e. one less than the number of characteristic polynomial evaluations transferred). The algorithm is also only linear in the number of actual differences between the two data sets.

4) Missing Memo Transfer - This is the time spent in the actual transfer of the memo text both to the PalmPilot from the PC and from the PC to the PalmPilot, AND the time spent by the PalmPilot doing a lookup of the memo texts that the PC is missing (this time accounts for a majority of this block).

5) Missing Memo Incorporation - This is the time spent by the PC and PalmPilot to incorporate the new memo texts into their databases. This time block is dominated by the PalmPilot because it must update its characteristic polynomial for each new memo added, which is compuationally intensive, but still linear in the number of differences (while the PC doesn't need to maintain a characteristic polynomial).

Communication Performance

CPISync also is linear in the number of bytes required to synchronize, regardless of the upper bound on the differences and the data set size. In this figure, we can see that the naive synchronization method, Slowsync, is not scalable in the data set size.