Object reference graphs containing cycles can be serialized??

[gov kur]

Hi all...
I'm still new to Serialization and have read someplace that "Object reference graphs containing cycles can be serialized".

However my Serialization attempts throw a StackOverflowError for which Stuart and David asked me to check if the objects refer recursively to one another.

I don't get this part... is it absolutely necessary to be aware of the object graph?


I've already tried to increase the stack size but that also did'nt help..

Please advice

[Amol Fuke]

Hi,

PLease make sure that your object ref is not involved in any cyclic classpath.That means if porject A is referering to project B and project B is again refering to project A then this condition may arise. or if you are storing any object in database or if any object travelling over the network then that object may not be serialised.You can solve this problem by extending the particular object by serilizable interface.

Thanks,
Amol

[gov kur]

Amol ... i have extended all my classes with the Serializable Interface.

My question is "Should'nt cyclic references be handled by the Serialization mechanism ?"

The code that i am trying to Serialize is a couple of years old and no longer maintained. it works perfectly in an application but when i try to Serialize it ... it throws a StackOverflow Error .. Any Ideas

[Joe Ess]

Please don't start new topics for what is essentially the same question. We will end up having to cover the same ground that has already been covered in this topic and this topic. I'm going to lock the previous topics and direct the conversation here.

[Ernest Friedman-Hill]

Originally posted by gov kur:

My question is "Should'nt cyclic references be handled by the Serialization mechanism ?"

Yes they are. As is well-known, Java serialization keeps a record of every object written to a stream. If the same object is encountered a second time, only a reference to it is written to the stream, and not a second copy of the object; so circular references aren't the problem here.

But serialization is vulnerable to stack overflow for certain kinds of structures; for example, a long linked list with no special writeObject() methods will be serialized by recursively writing each link. If you've got a 100,000 links, you're going to try to use 100,000 stack frames, and quite likely fail with a StackOverflowError.

It's possible to define a writeObject() method for such a list class that, when the first link is serialized, simply walks the list and serializes each link iteratively; this will prevent the default recursive mechanism from being used.

And folks: if you don't know something (and here I'm thinking of the suggestions about circular references being bad), it's not really helpful to inject it into a discussion as if it were a confirmed fact. It just confuses the original poster, and wastes people's time. If you must guess, than please state that you don't know the answer, but you have a theory, and then state your theory.

[gov kur]

Thanks for the info and also sorry for starting a new post. :roll:

quote:
----------------------------------------------------------------------------
Originally posted by Ernest Friedman-Hill

It's possible to define a writeObject() method for such a list class that, when the first link is serialized, simply walks the list and serializes each link iteratively; this will prevent the default recursive mechanism from being used.
----------------------------------------------------------------------------

I'm not quite sure what you mean or rather how to implement that in my code ...

here's an example that gives me a StackOverflowError. Could you please point out the changes that need to be done to avoid the error


import java.io.*;
public class Obj implements Externalizable //Serializable
{

private Obj innerObject;

public static int count = 0;
public int temp=100;
public String str="asdf";

public Obj(){
count ++;
if(count<500){
System.out.println("Creating new Object :"+count);
innerObject = new Obj();

}
}

public void writeExternal(ObjectOutput out)
{
try
{
System.out.println("Coming into the writeExternal :");
out.writeInt(temp);
out.writeObject(str);
out.writeObject(innerObject);
}
catch(Exception e)
{
e.printStackTrace();
}
}


public void readExternal(ObjectInput in)
{
try
{
System.out.println("Coming into the readExternal :");

temp=(int)in.readInt();
str=(String)in.readObject();
innerObject=(Obj)in.readObject();
}
catch(Exception e)
{
e.printStackTrace();
}
}


public static void main(String args[])
{
try
{

Obj o1=new Obj();
o1.temp=189;
o1.str=o1.str+" KURUP";
FileOutputStream ostream = new FileOutputStream("C:\\files\\obj_new1.txt");
BufferedOutputStream bout = new BufferedOutputStream(ostream);
ObjectOutputStream p = new ObjectOutputStream(bout);

p.writeObject(o1);
p.flush();
p.close();
}
catch(Exception e)
{
e.printStackTrace();
}
}


}

[gov kur]

Sorry the count should be greater that 900

[David Harkness]

In writeExternal(), when innerObject is not null, you call writeObject which results in another call to writeExternal() without returning from the first call. This continues on, creating two stack frames (at least) per contained object, until you get a StackOverflowError.

The way to avoid the problem is to change writeExternal() from a recursive method to one that isn't. This means you cannot call writeObject() from within writeExternal(). You need to devise another method of writing out your objects.

One way would be to use a loop that follows the change of innerObjects, writing the fields of each. When you hit the end, you'll need to write a marker so that your new readExternal() method can detect when it should stop its loop.

This is a good general exercise, so I won't give you the code just yet. Try it out first. Here's an example of turning a recursive method into a non-recursive one: the good ol' factorial.

public static int recursiveFactorial ( int n )
{
    if ( n <= 2 )
        return n;
    
    return n * recursiveFactorial(n-1);
}
 
public static int factorial ( int n )
{
    int fact = 1;
    for ( int i = 2; i <= n; i++ ) {
        fact *= i;
    }
 
    return fact;
}

Not compiled. Not tested. Guaranteed to only 300 meters.

[gov kur]

Crossed one hurdle ..... or.. atleast i think i did

But now on DeSerializing it gives a EOF Exception after just 2 cycles...

---------------------------------------------------------------------

import java.io.*;
public class Obj implements Externalizable //Serializable
{

private Obj innerObject;

public static int count = 0;
public int temp=100;
public String str="govind";

public static final long serialVersionUID=3L;

public Obj()
{
}

public Obj(int total){
count ++;
if(count<total){
System.out.println("Creating new Object before Serialization :"+count);
innerObject = new Obj(total);

}
}




public void readExternal(ObjectInput in)
{
try
{
System.out.println("Coming into the readExternal :");
count++;
System.out.println("ReCreating object after DESerialization :"+count);
temp=(int)in.readInt();
str=(String)in.readObject();

create(in,this);
}
catch(Exception e)
{
System.out.println("***************************new**************************");
e.printStackTrace();
System.out.println("*****************************************************");
}

}



public void create(ObjectInput in,Obj loopObj)
{
try
{
while(in.readBoolean()!=true)
{
System.out.println("ReCreating object after DESerialization :"+ ++count);
loopObj.innerObject=new Obj();
loopObj.innerObject.temp=(int)in.readInt();
loopObj.innerObject.str=(String)in.readObject();
loopObj=loopObj.innerObject;

}
}
catch(Exception e)
{
e.printStackTrace();
}


}


public void writeExternal(ObjectOutput out)
{
try
{
System.out.println("Coming into the writeExternal :");
out.writeInt(temp);
out.writeObject(str);

if(innerObject !=null)
{
//System.out.println("inner if :"+count--);
//out.writeObject(innerObject);
call(out,this);
System.out.println("Wrote object :"+ --count);
}
}
catch(Exception e)
{
System.out.println("************************new*****************************");
e.printStackTrace();
System.out.println("*****************************************************");
}
}


public void call(ObjectOutput out,Obj loopObj)
{

boolean flag=true;
try
{
do
{
loopObj=loopObj.innerObject;
out.writeInt(loopObj.temp);
out.writeObject(loopObj.str);
System.out.println("Wrote object :"+ --count);

}while(loopObj.innerObject!=null);


out.writeBoolean(flag);

}
catch(Exception e)
{
e.printStackTrace();
}


}

public static void main(String args[])
{
try
{


Obj o1=new Obj(900);
o1.temp=189;
o1.str=o1.str+" KURUP";
FileOutputStream ostream = new FileOutputStream("C:\\files\\serial.txt");
BufferedOutputStream bout = new BufferedOutputStream(ostream);
ObjectOutputStream p = new ObjectOutputStream(bout);

p.writeObject(o1);
p.flush();
p.close();



FileInputStream istream= new FileInputStream("C:\\files\\serial.txt");
BufferedInputStream bin=new BufferedInputStream(istream);
ObjectInputStream p1=new ObjectInputStream(bin);

Obj o2=null;

o2=(Obj)p1.readObject();
p1.close();
}
catch(Exception e)
{
e.printStackTrace();
}
}


}


---------------------------------------------------------------------


is this ok ? or did u have something else in mind...

[David Harkness]

That will work, but you need to move the writing of the boolean inside the while loop because your reading method -- call() -- expects a boolean true value before every Obj in the chain after the first. Do that and make sure you still write a false boolean after the chain, and this should work.

There are ways to shrink the amount of bytes to be written by removing the need for the boolean for each Obj. The methods depend on ensuring certain aspects of the data in the Objs.

If you know every chain will be at most Integer.MAX_VALUE, you could first write out the number of Objs in the chain before writing each Obj. If not, try for Long.MAX_VALUE. This requires walking the chain twice each time it's written or tracking the length in the root Obj.

If you can ensure that temp will never hold a particular value, for example -1, then you could write all Objs in the chain and finish by writing a single -1. When reading, read the int first, and only create a new Obj for the chain if you read something other than -1.

[gov kur]

Hey... it works Thanks a million!!!

One FAQ had listed that the deserialization process does not use the object's no argument constructor and it's only the first non Serializable SuperClass that needs to have one.

However in my code if i have a no argument constructor it's called during the DeSerialization process.. could you please explain this

Is this because i have implemented Externalizable rather than Serializable ?

[David Harkness]

Originally posted by gov kur:
Thanks a million!!!

...

However in my code if i have a no argument constructor it's called during the DeSerialization process.

Glad to help. From Externalizable's JavaDocs:

When an Externalizable object is reconstructed, an instance is created using the public no-arg constructor, then the readExternal method called.

So yes, it's because you use Externalizable rather than Serializable.

[gov kur]

Hello again...

I've encountered a bigger problem and it's for a class like

public class data implements java.io.Externalizable
{
public int age=0;
public String name="abc xyz";

data childL;
data childR;
}

Serializing this class I guess would involve traversal of some sort...

Similar to the solution that was given earlier i thought of assigning

0 - left child null
1 - right child null
2 - left exists
3 - right exists

So the serialized file would be something like

age name 2 3 age name 0 1 age name 0 1

but somehow i feel that the code would then be quite unreadable..

could you suggest something? .... some links or algos would certainly help

[David Harkness]

I'd check out how TreeSet or TreeMap handle serialization for hints.

Okay, scratch that; bad idea. TreeSet uses a TreeMap underneath (just the Set of keys), and TreeMap simply writes out the size and all the entries in the Map. It doesn't maintain any of the internal structure. In the end, it's just like a List.

Do you need to maintain the structure of the tree, or can you do the same thing as TreeMap: write out the objects and rebuild a new structure upon reading?

Assuming you must write out the same structure, you're pretty hard-pressed to change a tree traversal from recursive to non-recursive without references from each child to its parent. If you do have back references, then you can traverse non-recursively.

By the way, are you trying to solve a real problem or just playing with serialization? I often find that the problems I face in real work are rarely as restricted or unbounded. My point is that you're unlikely to face the same issues in real-world situations, so feel free to alter the problem if you must.
[ April 27, 2005: Message edited by: David Harkness ]

[gov kur]

quote: from previous post
----------------------------------------------------------------------
The actual code that i am working on is a legacy piece of C/C++ code that had been ported to java some years ago .It's actually responsible for conversions from English to the local Languages of my region.There are 2 stages to the conversion.

the first is where the rule files, the dictionay files etc(which are basically flat files) are read into instances of my own classes which are loaded by the Converter class.

the second stage is when i actually convert data using the Converter class which now has access to the above rules.

I've been trying to serialize my object after the first stage.
-----------------------------------------------------------------------



I hope that explains it ..

I tried to use the default Serialization mechanism on the original code but that resulted in the StackOverflowError.
Since then i have just tried to simulate the errors...in small chunks of code ...and the next level is Serializing the structure given above since some classes that load some Rule/Dictionary files have that kind of structure.

It's not possible to change the structure because no one really understands it anymore ...

So i am pretty much stuck with it..

Yeah... i guess i do have to maintain the tree structure..

now i'm just trying to fit some tree traversal algo into the approach u suggested above.

[David Harkness]

Okay, do you have some idea of how large (depth and breadth and total number of nodes) these trees will get, on average and worst case?

The basic problem you have is that with a recursive algorithm, the stack keeps track of the traversal path for you, allowing back tracking, but it takes up too much space. One method that pops into my mind is to create your own stack on the heap -- not a program stack but a simpler traversal stack.

You could use a LinkedList for this pretty easily. It's doubly-linked and should provide decent performance. Don't use Stack as it extends Vector, bringing with it synchronization that will just be useless drag.

A simple encoding method just occurred to me. Start at the root node of the tree. Now, each step of the way, serialize the data members of the node (age and name) and next serialize a byte that denotes which direction you're traversing next: 0 = done, 1 = up, 2 = left, 3 = right. Traverse to that node and continue.

Obviously, go left only if you can, then go right if you can, otherwise go up. This is a preorder traversal which will be good for reconstructing the tree.

Here's an example:

  A
 / \
B   C
 \
  D
 
A 2 B 3 D 1 1 3 C 1 0

Okay, that didn't work so well. Navigating up doesn't go so smoothly. You could compress a string of up navigations into a single one if they are all coming from a right subtree, but that still leaves you with cases where you must navigate multiple times before writing out the next node.

For it to work, however, you must know when reading whether you are reading a navigation or a node before you read it. You could write a marker first, and that would work, but it will bloat the files. I bet with some more trickery you can find a way to encode it.

Hmm, one simple solution is to have two versions of navigation: 0 = done, 1..3 = navigate and node follows, 4..6 = navigate and another navigation follows. This is looking mighty kludgy!

[ Added... ]

The reason I went this way versus what you initially proposed was so that the reading code would only have to maintain the traversal path and not remember whether each node along the way has a right side while it's navigating the left side, but perhaps that's not worth it.

Regardless, if you choose your method, you can combine the two numbers into a single byte:

0 = no children

1 = left only

2 = right only

3 = both children

More simply, 0x10 = left and 0x01 = right and use them as bit patterns for a bitset of two bits in a single byte.
[ April 27, 2005: Message edited by: David Harkness ]

[gov kur]

thanks for the info

I was looking at pre-order traversal myself and was planning to associate numbers which would indicate whether it had children or not ... your numbring scheme is certainly better...

I was also trying to note all checks that i would have to follow while coding
I'll also try out your idea on paper...
Thanks once again

[gov kur]

ok.... finally have something workable....

public void readExternal(ObjectInput in)
{
try
{
System.out.println("Coming into the readExternal of data:");
readAgain(in,this);
System.out.println("Finishing readExternal of data:");
}
catch(Exception e)
{
e.printStackTrace();
}

}

public void readAgain(ObjectInput in,data current)
{

System.out.println("Coming into the readAgain of data:");
LinkedList traversal=new LinkedList();
int nodeCount=0;
int childValue=0;
try
{
nodeCount=(int)in.readInt();
System.out.println("The node count is :"+nodeCount);
traversal.add(new String("START"));
while(nodeCount>0)
{
nodeCount--;
childValue=(int)in.readInt();
System.out.println("The child value is :"+childValue+" for the node "+nodeCount);
if(childValue==3)
{
System.out.println("Coming into the loop for childValue "+childValue);

current.age=(int)in.readInt();
current.name=(String)in.readObject();

current.childL=new data();
current.childR=new data();

traversal.add(current.childR);

current=current.childL;
}

else if(childValue==1)
{
System.out.println("Coming into the loop for childValue "+childValue);

current.age=(int)in.readInt();
current.name=(String)in.readObject();

current.childL=new data();

current=current.childL;
}
else if (childValue==2)
{
System.out.println("Coming into the loop for childValue "+childValue);

current.age=(int)in.readInt();
current.name=(String)in.readObject();

current.childR=new data();

current=current.childR;
}
else
{
System.out.println("Coming into the loop for childValue "+childValue);

current.age=(int)in.readInt();
current.name=(String)in.readObject();
if(traversal.size()>1)
{
current=(data)traversal.removeLast();
}
else
{
traversal.clear();
}
}

}

}
catch(Exception e)
{
e.printStackTrace();
}

System.out.println("Coming out of readAgain of data:");
}


public void writeExternal(ObjectOutput out)
{
try
{
System.out.println("Coming into the writeExternal of data:");
writeAgain(out,this);

System.out.println("finishing the writeExternal of data:");
}
catch(Exception e)
{
e.printStackTrace();
}
}

public void writeAgain(ObjectOutput out,data current_node)
{
data current=current_node;
int nodeCount=0;
LinkedList traversal=new LinkedList();

System.out.println("Loop to get the count of nodes.....");
try
{
traversal.add(new String("START"));

while(traversal.size()>0)
{
if ( current.childL!=null && current.childR!=null )
{
System.out.println("both children");
nodeCount++;
traversal.add(current.childR);
current=current.childL;
}
else
{
if (current.childL!=null)
{
System.out.println("left child");
nodeCount++;
current=current.childL;
}
else if (current.childR!=null)
{
System.out.println("right child");
nodeCount++;
current=current.childR;
}
else
{
System.out.println("no child");
nodeCount++;
if(traversal.size()>1)
{
current=(data)traversal.removeLast();
}
else
{
traversal.clear();

}

}
}
}

System.out.println("The no of nodes is : "+nodeCount);

traversal=new LinkedList();;
current=current_node;

traversal.add(new String("START"));
out.writeInt(nodeCount);

while(traversal.size()>0)
{
if ( current.childL!=null && current.childR!=null )
{
System.out.println("The childValue written is : "+3);
out.writeInt(3);

out.writeInt(current.age);
out.writeObject(current.name);

traversal.add(current.childR);
current=current.childL;
}
else
{
if (current.childL!=null)
{
System.out.println("The childValue written is : "+1);
out.writeInt(1);

out.writeInt(current.age);
out.writeObject(current.name);

current=current.childL;
}
else if (current.childR!=null)
{
System.out.println("The childValue written is : "+2);
out.writeInt(2);

out.writeInt(current.age);
out.writeObject(current.name);

current=current.childR;
}
else
{
System.out.println("The childValue written is : "+0);
out.writeInt(0);

out.writeInt(current.age);
out.writeObject(current.name);

if(traversal.size()>1)
{
current=(data)traversal.removeLast();
}
else
{
traversal.clear();

}

}
}

}

}
catch(Exception e)
{
e.printStackTrace();
}
}



// this works...






By the way the real code has about 6 similar classes having some primitive variables and string objects.

Three of the these classes have 2 references to themselves
.Two of them generate about 24,000 and 33,000 nodes respectively.

The others generate about 1500 nodes between them

Keeping this in mind could you suggest any improvements in the code ...

[gov kur]

sorry wrong smiley...

[David Harkness]

You can always edit your posts (the pencil and paper icon at the top of your post). Also, please wrap your code in CODE tags to maintain indentation and line breaks. It makes it much easier to read. You can type the tags or insert them with the "Instant UBB Code" CODE button below the edit box. Make sure to put your code between the tags, just like HTML tags but with square brackets.

To your question, how big are the serialized files? Does the performance meet your needs? If it works well enough, it may be best to focus elsewhere. Perhaps you might want to rethink the data structure, but again only if runtime needs aren't met.

If you can post some specific issues you have with it, I'd be glad to check it out. Otherwise, I'll check out the code when I'm a bit more fresh. That's quite a bit of code to grok so late at night.

[gov kur]

hmm.. never noticed them..

I'm yet to insert the sample code into the actual implementation.. lets see how it turns out.will keep you updated