Re: [Cdk-devel] Infinite loops

[Dr. C. S. <ste...@ic...>]

Toly,

thanks a lot for your thoughtful comments.
I will try to solve this problem soon, since the SDG is my special baby.
Unfortunately, on my side the code now even fails for our *connected* 
aliphatic test case for which it used to work. This is quite strange 
indeed.

First, I guess, we should incorporate your count-down patch, because it 
really seems quite reasonable. :-)

Cheers,

Chris

-- 
Dr. rer. nat. habil. Christoph Steinbeck (c.s...@un...)
Groupleader Junior Research Group for Applied Bioinformatics
Cologne University BioInformatics Center (http://www.cubic.uni-koeln.de)
Zülpicher Str. 47, 50674 Cologne
Tel: +49(0)221-470-7426   Fax: +49 (0) 221-470-7786

What is man but that lofty spirit - that sense of enterprise.
... Kirk, "I, Mudd," stardate 4513.3..


> Below are my observations and more concrete proposals.
> 
> ---------------------------------------
> 
> The principal source for layout infinite loops appear to be inside
> 
> StructureDiagramGenerator.generateCoordinates()
> do 
> {
> ...................
> } while(!atomPlacer.allPlaced(molecule));
> 
> The open-ended condition at the bottom means that if the layout engine fails
> to place even a single atom, then layout engine enters infinite loop. I do
> not believe it is possible to guarantee the any given structure could be
> successfully layouted. Therefore, there should be a deterministic "safety
> valve" condition.
> 
> For my purposes, I usually limit the number of iterations to number of
> atoms. I am not 100% sure this is entirely correct in all case - but it
> appears to work. 
> 
> int safetyCounter = molecule.getAtomCount(); 
> 
> do 
> {
>   safetyCounter --;
> ...................
> } while((!atomPlacer.allPlaced(molecule)) && (safetyCounter >0));
> 
> if (safetyCounter <= 0)
> {
>   throw new RuntimeException("Layout failed");
> }
> 
> The rationale is simple - if we cannot place at least one atom in every
> iteration loop, then something is going very-very wrong.
> 
> This is NOT a fix, nevertheless it is a sensible precaution and I would
> prefer to have it (or equivalent) kept in CDK codebase.
> 
> ----------------------------------
> 
> Now my observations, which might or might not be relevant to the issue. The
> observations below do not represent the only way to cause infinite loop, but
> this is the most straightforward to reproduce.
> 
> 1) CDK layout engine seems to have problems with disconnected structures
> 2) if the structure is disconnected AND it contains only aliphatics, then
> layout fails with NullPointerException (see the relevant bug I reported)
> 3) if the structure is disconnected AND it contains fused rings in both
> fragments, then we go into infinite loop (see the relevant bug I reported)
> 4) therefore I believe that rings layout algorithm incorrectly goes through
> the disconnected graph - probably it starts in a single fragments and never
> manages to "escape" it once layout of complete and handle the next fragment.
> 5) this is consistent with infinite loop manifestation - it never lays out
> the rings in the second fragment so atomPlacer.allPlaced() is always false
> 6) this is all the more frustrating since the layout correctly lays out the
> individual fragments
> 
> ----------------------------------
> 
> In terms of testing I had experience solving similar problems - confirming
> that a layout algorithm never enters infinite loop. Assuming that there
> going to be relatively few "problem" structures, the best course of action
> might be:
> 
> iterate through a big heterogeneous dataset (NCI is very good)
> for each entry starts a test in new thread synchronously - wait until
> completed
> 1) write a log message into log file and FLUSH logging output immediately
> 2) parse SMILES
> 3) layout structure
> 4) run few checks
> 5) [optional] convert back and forth between different formats several times
> and check that the data do not get corrupted
> 6) write a log message into log file and FLUSH logging output immediately
> 
> Have a Thread Killer running in parallel which will kill any testing thread
> which has run for longer then it should - write appropriate message into log
> if this happens and proceed to the next record.
> 
> Even if we enter infinite loop - we have a record about it.
> 
> This is also a very useful test to boost your confidence about CDK
> robustness and identify memory leaks. If CDK survives parsing/layout/format
> conversion on 250,000 different structures - it is a very good record of
> reliability.
> 
> Cheers,
>  Toly
> 
> -----Original Message-----
> From: Egon Willighagen [mailto:eg...@sc...] 
> Sent: 26 January 2004 22:49
> To: Anatoli Krassavine; cdk...@li...
> Subject: Re: [Cdk-devel] Infinite loops
> 
> On Monday 26 January 2004 21:15, Anatoli Krassavine wrote:
> 
>>I believe the general issue of infinite loops should be given a very high
>>priority. Presently, it is relatively easy to cause CDK to enter infinite
>>loop while doing relatively simple I/O and layout operations.
>>
>>This is an extremely serious, almost fatal issue from the point of view of
>>using CDK as a library. The severity of infinite loop is an order of
>>magnitude higher then any other bug or issue, even outright VM crash. VM
>>crash at its worst could take down a server - infinite loop in a wrong
>>server process could take down the whole local network.
> 
> 
> Good point.
> 
> 
>>Unfortunately, presently it means that CDK in the form it is distributed
>>cannot be used in serious server environment without custom modifications
>>to the codebase to insert custom safety checks.
> 
> 
> You might be quite right there... note that CDK *is* used on at least the 
> NMRShiftDB server... but I tend to agree...
> 
> Another problem with these infinate loop bugs, is that it is impossible to 
> make a JUnit test for it... because it will hang the whole testing... unless
> 
> one would use a thread that would stop it after some time...
> 
> 
>>I have attempted to identify and possibly fix the bugs - unfortunately
>>unsuccessfully. I know roughly the blocks of code responsible, but cannot
>>clearly identify the precise problems causing it.
> 
> 
> Please send the block you did identify as the cause... I will look at it 
> asap...
> 
> 
>>And being fair, they are
>>one of the most complicated pieces of functionality in CDK.
> 
> 
> Indeed, and therefore very hard to maintain and extend...
> 
> 
>>Proposals:
>>1) Add safety checks on all pieces of code which are known to cause
>>infinite loops.
>>2) Write a test harness, which will run through the whole NCI dataset,
>>parsing every single SMILES string and executing layout on it.
> 
> 
> Yes, that's something I wanted to do for some time now...
> 
> 
>>3) Identify and cap all the loops with open-ended finish conditions - a
>>standard cause of infinite loops. Rewrite the implementation to avoid
>>open-ended finish conditions or put safety-valves in.
> 
> 
> Toly,
> 
> thanx very much for writing this down. I'll see if I can find some time to 
> track down (and fix) the problem... to have it at least fail, instead of
> loop 
> endlessly...
> 
> Egon
> 
> 
> 
> 
> 
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004
> Premiere Conference on Open Tools Development and Integration
> See the breadth of Eclipse activity. February 3-5 in Anaheim, CA.
> http://www.eclipsecon.org/osdn
> _______________________________________________
> Cdk-devel mailing list
> Cdk...@li...
> https://lists.sourceforge.net/lists/listinfo/cdk-devel
> 
>