深层图导致堆栈溢出:非递归序列化选项？

Question

我们从Java的序列化库中获取StackOverflowErrors.问题是默认的序列化实现是递归的,其深度仅受通过引用网络的最长路径的限制.

我们意识到我们可以覆盖默认方法,但是我们在项目中有数百个连接丰富的类,所以我们对覆盖方法并不热衷.如果存在非递归的通用解决方案(或者至少将递归从堆栈移动到堆),我们会更感兴趣.

我搜索了这个话题,发现只有很多人痛苦地抱怨同样的事情,但大多数这些抱怨来自很多年前.情况有所改善吗？如果没有,我们写一个通用的实现,你有什么建议吗？我们假设有一些原因(对我们来说还不明显)为什么没有人破解这个坚果.从理论上讲,做"正确"听起来应该是可行的.

Answer 1

不久前我遇到了这个问题。对于连接丰富的类，即使您能够在没有堆栈溢出的情况下完成序列化，序列化也会非常慢。当我们解决这个问题时，我们有一些类，所以我们只是创建了自己的序列化格式，将数据打包到一组整数对象 id 中，每个字段都有整数字段 id ，并通过一系列对象 id 描述它们的连接、字段 id、其他对象 id 映射。这种自定义方法非常快并且占用内存极少，但只有在您想要序列化一小组类时才真正有效。

一般情况要困难得多，并且对丰富连接的类的序列化的需求并不那么强烈，所以我猜这就是为什么没有人解决它的原因。

不过，您基本上已经解决了这个问题，您总是需要一个等于深度优先搜索树的最大高度的堆栈深度，因此只要您的图比该深度更深，您就会遇到堆栈溢出。从根本上来说，这是一个递归问题，因此您要么需要使用递归，要么需要通过将堆栈分配移动到放置在堆上的 Stack 对象来使用假递归。我会看一下 OpenJDK 的实现：

http://hg.openjdk.java.net/jdk6/jdk6-gate/jdk/file/tip/src/share/classes/java/io/ObjectOutputStream.java

您已经有一个 DebugTraceInfoStack，我将为您正在编写的当前对象创建第二个 Stack 字段，并更改 writeObject0 方法以将对象推入堆栈，如下所示：

stack.push(obj);
while(!stack.empty()) {
    obj = stack.pop();
    ...

然后你只需将所有调用更改为 writeObject0(x); 到 stack.push(x);。递归和迭代之间的简单、标准转换，除了该类几乎有 2500 行，并且可能存在大量陷阱。

如果你最终构建了它，我建议将 at 作为 java 的下一个版本的补丁提交，因为它会很有用，比如用于深度对象图的 IterativeObjectOutputStream。