Big overhead when serializing object graphs with shared nodes

[GoogleCodeExporter]

I did some benchmarking and profiling of Kryo.
Kryo supports serialization of object graphs with sharing, but it introduces 
quite some overhead. 
Inspection of sources has shown that 3 different (identity) maps are used to 
implement this feature. Lookups and insertion in those maps plus usage of 
InstanceId wrapper for instance ids are the reasons for this overhead.

I sketched a possible solution here:
https://github.com/romix/kryo/commit/845ae6018c4f4adcae81269392f972275dff2a54

It gives a better performance on my tests. It seems to be faster for object 
graphs that are not very big, because it uses linear scan through entries and 
no hashing at all. For bigger graphs it will degrade to O(n^2). So, it is not 
ideal solution for all cases. 

It would be actually nice to introduce a GraphReferenceManager API or something 
like this. Then one could provide a custom implementation for it. For example, 
one could use my (or similar) approach for small graphs and/or current approach 
based on hashing for big graphs. 

Original issue reported on code.google.com by romixlev on 3 May 2012 at 11:07

[GoogleCodeExporter]

Forgot to mention: with this changes (plus array serialization improvements 
from the other issue), Kryo seems to beat protostuff-runtime in speed on my 
tests

Original comment by romixlev on 3 May 2012 at 11:08

[GoogleCodeExporter]

Agreed, this can definitely be improved.

Original comment by nathan.s...@gmail.com on 3 May 2012 at 9:58

• Changed state: Accepted

[GoogleCodeExporter]

This issue was closed by revision r252.

Original comment by nathan.s...@gmail.com on 23 May 2012 at 9:39

• Changed state: Fixed

[GoogleCodeExporter]

Your changes have been committed, thank you!

Original comment by nathan.s...@gmail.com on 23 May 2012 at 9:39