Seeming Non-determinism in Java Programs

Hi,

I have a long-standing, oft vexatious problem in a large, complex Java
program and I would like to solicit feedback from advanced java-nauts.

The program involves heuristic search in a large, incrementally built
tree. As nodes are added to the tree, a heuristic figure-of-merit (FOM)
is computed and that FOM orders the priority queue from which
successive nodes are extracted, examined and expanded. The queue is
implemented using a heap, though alternatives such as Skip-Lists are
available as options (mostly implemented because of the issue I'm
writing about here).

The program makes extensive use of hashed sets. I've implemented an
option to allow different collection implementations to be used. E.g.,
one can choose Sun's HashSet, LinkedHashSet or Trove's hash set.

It's worth noting that it's often the case that there is relatively
little distinction between actual FOM values (they are very frequently
always small integers). While the priority queue may at any time hold
several thousand items, there may be only a relative handful of
distinct FOMs ordering that queue. Note, too, that the heap data
structure is not stable w.r.t. equal key (FOM) values.

Lastly, the problems, even when known to be solvable, are not always
solved within the user-specified resource limits (number of tree nodes
generated being the typical one).


So here is the symptom I seek to alleviate: The program's behavior on
some problems is highly variable. That is, I can invoke the same
problem repeatedly and get widely varying results. E.g., a given
problem may be solved in one case in under a thousand nodes, in another
in ten or twenty thousand and in others not at all (with a 100,000-node
limit).

This is perplexing to me. How can multiple independent (but identical)
invocations of the JVM produce highly varying executions?

My first question is this: What phenomenon / dynamics can cause this
sort of behavior? While I'm open to the possibility that it is a bug
(permit me to say a _subtle_ bug), I'm experienced enough to know the
proper implementation of equals() and hashCode(), e.g.


Has anyone else seen this sort of phenomenon? If so, how have you dealt
with it?

Thanks.

Randall Schulz

===================================
This list is hosted by DevelopMentor®  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com