Opened 16 years ago

Closed 15 years ago

#169 closed defect (fixed)

Patch creation performance is bad

Reported by: Bernhard Haumacher (haui at haumacher dot de) Owned by:
Priority: normal Milestone: 2.0
Component: uka.karo Version: 1.08a
Severity: normal Keywords:


Creating a patch for a large graph of small objects takes incredible long. A graph of approximately 1024 objects takes on an AMD Athlon XP1900+ with JDK-1.4.2_01-b06 4227.679us +- 16.926us for patch creation, if the graph was not modified. If a single double value was modified at half the objects, patch creation takes 4405.714us +- 47.754us. Therefore, only 4% of the time is spent for productive work. Simply traversing the graph takes 2709.444us +- 10.123us, which is 60% of the time to create an empty patch. Because each graph node in the benchmark graph has approximately 4 neighbors, the rest of the time seems to be spent checking whether the graph references have been modified.


Profiling the patch creation process shows that most of the time is spent resolving object references in hash tables. Such hash table lookups are required at two steps during the patch creation process. First, during each patch creation the object graph is traversed completely to find all currently referenced objects. For each object reference encountered, its object identifier must be searched through a hash table lookup. This identifier is required for finding the backup copy of the current object and for labeling the patch record that is potentially created. The second source of hash table lookups is the change detection of object references. The original and the backup graph are isomorphic. Nodes of the original graph point to objects in the original graph and nodes in the backup graph point to corresponding objects in the backup graph. When comparing an original object with its backup copy, references can not be compared directly. Instead, the object identifier for the referenced object must be found to discover its backup copy. This backup copy can then be compared with the object referenced from the backup of the original object.


Instead of traversing the graph during patch creation, the object space can be iterated. This may create patch records for objects that were removed from the replicated graph. But the changes in the reference structure of the graph are detected during the reference comparison of the patch creation phase. Structure changes can now trigger a garbage collection phase that traverses the graph. This optimizes patch creation of graphs whose structure never or only slowly changes.


Reference comparison can be sped up by changing the structure of backup objects. Instead of pointing to objects in the backup graph, those objects could point to the corresponding original objects. With this modification, a value comparison of references is sufficient. In exchange, creating the backup copies becomes slightly more complicated. An original object can not simply be clone()d, because the corresponding method in java.lang.Object is protected. One way is to invoke this method reflectively and relying on the convention to declare a public clone() method, when declaring a class Cloneable. Another way would be a deep clone process that resolves all references to their corresponding original values. A deep clone process might be preferably, because all object in the original graph have to be cloned anyway, no reflection is required, and deep clone through serialization/deserialization provides automatic reference traversal for non-transportable objects.

todo since 1.08a.

Attachments (0)

Change History (1)

comment:1 Changed 15 years ago by hauma

  • Milestone set to 2.00
  • Resolution set to fixed
  • Status changed from new to closed

This issue is resolved in changeset:1930.

Add Comment

Modify Ticket

Change Properties
Set your email in Preferences
as closed The ticket will remain with no owner.
The resolution will be deleted. Next status will be 'reopened'.

E-mail address and user name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.