elsa
elsa copied to clipboard
jankotek
Replace recursion with loop to dive into Object Graph
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
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.
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.
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.
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.
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.
This feature needed for Android 4 with small stack overflow limit. Unfortunately these devices still in use.
I think latest git snapshot already handles stack less serialization. I never released it.