search

jankotek / elsa

Java serialization, faster and space efficient version of ObjectOutputStream
Apache License 2.0
45 stars 9 forks source link

Replace recursion with loop to dive into Object Graph #4

Open jankotek opened 8 years ago

jankotek commented 8 years ago

Elsa uses recursion to dive into object graph. That could generate long call stack and cause StackOverflow exception. Compared to Java serialization Elsa uses less stack frames and behaves better.

It should be possible to eliminate recursion and dive into object graph with simple loop. Some data structure needs to replace call stack (trie?). It should store path traversed on graph dive. Special care needs to be taken to preserve order of objects

dasbipulkumar commented 8 years ago

Should I look onto this issue?

jankotek commented 8 years ago

It is a bit of challenge, there is bug for JVM which was open since 2005. 

Stack is used to keep list of already traversed objects and their order. So you will need some knowledge of graph traversal. 

I would be happy to post more info, if you decide to do this.

dasbipulkumar commented 8 years ago

kryo also has the same issue logged since 2013 https://github.com/EsotericSoftware/kryo/issues/103

please post more details to start with the code related to this or any other enhancements.

jankotek commented 6 years ago

Update: Current version of Elsa uses non-recursive graph traversal at serialization. Object graph is traversed in for-loop and ArrayDeque is used to keep track of nested objects. No stack is expanded I tested it on linked list with graph depth of 1e7 entries.

Deserialization still uses recursion. Fix for that needs bigger code change, but I will do that as well.

reuschling commented 6 years ago

Is there a current status for the deserialization? Because of Kryo closed the related issue with 'we won't do it', Elsa would be the only serializing application that supports deep object graphs.

samoylenkodmitry commented 3 years ago

There is no solution in the entire internet that can handle large graph deserialization. It will be a good unique feature. Kryo, fst and others can't do this.

samoylenkodmitry commented 3 years ago

This feature needed for Android 4 with small stack overflow limit. Unfortunately these devices still in use.

jankotek commented 3 years ago

I think latest git snapshot already handles stack less serialization. I never released it.