NPE in PriorityQueue.poll()

[Twisted]

This is a strange one. App just recovered gracefully from:

java.lang.NullPointerException
at java.util.PriorityQueue.siftDownComparable(PriorityQueue.java:627)
at java.util.PriorityQueue.siftDown(PriorityQueue.java:614)
at java.util.PriorityQueue.poll(PriorityQueue.java:523)
at com.sourceforge.sphaera.SThread.run(SThread.java:158)

The line of my own code that's involved is basically

Foo bar = baz.poll();

with baz an instance of PriorityQueue<Foo> and definitely not itself
null (and besides, the stack trace would have consisted of only the
last line if it were).

Looks like a library bug. JDK 1.6.0 -server -incgc -Xmx256 under WinXP
in case it matters, with the 1.6.0 standard library (including
PriorityQueue implementation).

 

[Twisted]

This is a strange one. App just recovered gracefully from:

java.lang.NullPointerException
at java.util.PriorityQueue.siftDownComparable(PriorityQueue.java:627)
at java.util.PriorityQueue.siftDown(PriorityQueue.java:614)
at java.util.PriorityQueue.poll(PriorityQueue.java:523)
at com.sourceforge.sphaera.SThread.run(SThread.java:158)

Eh. Should have mentioned that my comparator function can't possibly be
the culprit either, since it would otherwise be in the above stack
trace.

 

[Patricia Shanahan]

This is a strange one. App just recovered gracefully from:

java.lang.NullPointerException
at java.util.PriorityQueue.siftDownComparable(PriorityQueue.java:627)
at java.util.PriorityQueue.siftDown(PriorityQueue.java:614)
at java.util.PriorityQueue.poll(PriorityQueue.java:523)
at com.sourceforge.sphaera.SThread.run(SThread.java:158)

The line of my own code that's involved is basically

Foo bar = baz.poll();

with baz an instance of PriorityQueue<Foo> and definitely not itself
null (and besides, the stack trace would have consisted of only the
last line if it were).

Looks like a library bug. JDK 1.6.0 -server -incgc -Xmx256 under WinXP
in case it matters, with the 1.6.0 standard library (including
PriorityQueue implementation).

The failure appears to be in reorganizing code that would be very
vulnerable to synchronization problems.

I assume the PriorityQueue is either only used in a single thread, or is
supposed to be protected from simultaneous access by your own
synchronization.

However, it might still be worth replacing it with a
PriorityBlockingQueue, and verifying that the NPE still happens.

Patricia

 

[Twisted]

The failure appears to be in reorganizing code that would be very
vulnerable to synchronization problems.

I don't think so. It's definitely synchronizing on the queue every time
it accesses it (either to poll it or to put something in).

I've had two more similar NPEs. One looked identical. The other died in
my comparator, but I double-checked the comparator and there's only a
few accesses of fields of primitive type. The only reference type
variable that gets dereferenced is the parameter. If that's sometimes
null, it means the PriorityQueue is somehow getting nulls in it.

I've double checked that none of my own code is putting nulls in the
PriorityQueue. In fact, this particular one only gets added to in code
like this:

Foo myFoo = new Foo(params);
synchronized (queue) {
queue.add(myFoo);
}

myFoo can't be null, I think you'll agree. It's a local variable immune
to concurrent modification; it's assigned from "new" which never
produces null, only a proper reference or an exception; and if it threw
an exception (or the Foo constructor did) it would never reach the line
"queue.add(myFoo)".

This is damned odd.

 

[Patricia Shanahan]

I don't think so. It's definitely synchronizing on the queue every time
it accesses it (either to poll it or to put something in).

Pity - it would be an easy fix, and would explain the rest of the
symptoms. The queue could get nulls without them being added if it were
reorganizing itself in two threads at the same time, but if you are sure
all accesses to the queue are synchronized on the queue, that's out.

Patricia

 

[Mark Jeffcoat]

This is a strange one. App just recovered gracefully from:

java.lang.NullPointerException
at java.util.PriorityQueue.siftDownComparable(PriorityQueue.java:627)
at java.util.PriorityQueue.siftDown(PriorityQueue.java:614)
at java.util.PriorityQueue.poll(PriorityQueue.java:523)
at com.sourceforge.sphaera.SThread.run(SThread.java:158)

The line of my own code that's involved is basically

Foo bar = baz.poll();

with baz an instance of PriorityQueue<Foo> and definitely not itself
null (and besides, the stack trace would have consisted of only the
last line if it were).

Looks like a library bug. JDK 1.6.0 -server -incgc -Xmx256 under WinXP
in case it matters, with the 1.6.0 standard library (including
PriorityQueue implementation).

Some new programmers fall into the trap of blaming the
compiler (or library) just a little bit too quickly when
things go wrong. I remember some early C programs I wrote
where the compiler was actively malicious, insisting that
that log(2) really was -139433334749 ... eventually someone
explained to me that I was unlikely to ever get the right
answers without linking in the actual math library.

I call it a trap because when the problem is the compiler's
fault, you've given yourself implicit permission to stop
thinking about it yourself--after all, fixing Sun's libraries
isn't really your responsibility.

The best way I've found to make sure I haven't fallen into
that particular trap is to take my code, and cut it down
until I have the smallest program I can write that still
demonstrates the broken behavior.

If I finish the exercise, I'll have not only learned something,
but I'll have a demonstration that I can send to whoever's
really responsible for maintaining the problem code. More
often, I end up discovering that one of my original assumptions
about what was going on was quite false--but I win that way,
too, since I can go back and fix my code.






[In your case, I'd put a moderate amount of money on something
going wrong in compareTo(). Were I to go out on a limb, I'd say
you have an auto-boxing problem, but my full set of psychic powers
has not yet arrived.]

 

[Daniel Pitts]

This is a strange one. App just recovered gracefully from:

java.lang.NullPointerException
at java.util.PriorityQueue.siftDownComparable(PriorityQueue.java:627)
at java.util.PriorityQueue.siftDown(PriorityQueue.java:614)
at java.util.PriorityQueue.poll(PriorityQueue.java:523)
at com.sourceforge.sphaera.SThread.run(SThread.java:158)

The line of my own code that's involved is basically

Foo bar = baz.poll();

with baz an instance of PriorityQueue<Foo> and definitely not itself
null (and besides, the stack trace would have consisted of only the
last line if it were).

Looks like a library bug. JDK 1.6.0 -server -incgc -Xmx256 under WinXP
in case it matters, with the 1.6.0 standard library (including
PriorityQueue implementation).

Is the poll in a synchronized block like your add is?
Foo bar;
synchronized (queue) {
bar = baz.poll()
}

You need to make sure all access to baz is syncronized if it is access
in more than one thread.

BTW, from the Javadoc (in 1.5.0):
* <p> <strong>Note that this implementation is not
synchronized.</strong>
* Multiple threads should not access a <tt>PriorityQueue</tt>
* instance concurrently if any of the threads modifies the list
* structurally. Instead, use the thread-safe {@link
* java.util.concurrent.PriorityBlockingQueue} class.

 

[Twisted]

[In your case, I'd put a moderate amount of money on something
going wrong in compareTo(). Were I to go out on a limb, I'd say
you have an auto-boxing problem, but my full set of psychic powers
has not yet arrived.]

Seems unlikely to me. It's a custom class Foo implementing
Comparable<Foo>, whose compareTo accesses fields inside "this" and the
other Foo and performs some math and logic. The fields are of primitive
types (mainly ints), so nothing is being boxed or unboxed here. It is
NPEing either inside the PriorityQueue code or on the very first field
access of the other Foo in the compareTo, which tells me that there are
nulls creeping into the queue somehow.

As for the C compiler you had in the past -- if it merrily compiled
code that invoked log() and linked it even without anything to link
log() calls to, outputting unpredictably-behaving binaries instead of
an "unresolved symbol" error, then it looks like it was a rather broken
compiler (with the linker looking to be the specific culprit).

 

[Twisted]

Is the poll in a synchronized block like your add is?
Foo bar;
synchronized (queue) {
bar = baz.poll()
}

Of course, especially seeing as it can modify the queue (if the queue
isn't empty, it removes something).

 

[Mark Jeffcoat]

[In your case, I'd put a moderate amount of money on something
going wrong in compareTo(). Were I to go out on a limb, I'd say
you have an auto-boxing problem, but my full set of psychic powers
has not yet arrived.]

Seems unlikely to me. It's a custom class Foo implementing
Comparable<Foo>, whose compareTo accesses fields inside "this" and the
other Foo and performs some math and logic. The fields are of primitive
types (mainly ints), so nothing is being boxed or unboxed here. It is
NPEing either inside the PriorityQueue code or on the very first field
access of the other Foo in the compareTo, which tells me that there are
nulls creeping into the queue somehow.

It's likely that I'm wrong -- I mean, really, I'm speculating
from an exception trace and one paraphrased line of code.

My actual point, though, is that all this rhetoric, however
plausible sounding, is not moving you any closer to solving
the problem. You can't argue away an Exception, and the compiler
is remarkably resistant to persuasion.

I suppose with effort and luck, maybe you could convince me
that it's not your fault, but why bother? You'd still have a
broken program.

Make a hypothesis and test it. Repeat while useful.

I've hypothesized that compareTo() is throwing an uncaught
exception; you don't need an argument to prove me wrong, just
wrap the entire method in a block that catches everything,
and show that the behavior doesn't change.

Other posters have hypothesized that you have threading
problems. What happens when you wrap your PriorityQueue
with Collections.synchronizedCollection()? Any change?

You've hypothesized that nulls are being added to the
queue. What happens when you call PriorityQueue.add(null)?

 

[Twisted]

I've hypothesized that compareTo() is throwing an uncaught
exception; you don't need an argument to prove me wrong, just
wrap the entire method in a block that catches everything,
and show that the behavior doesn't change.

It doesn't do anything except test booleans and compare (with < and ==)
ints. I don't see it throwing any exception, except NPE if it gets a
null argument.

Other posters have hypothesized that you have threading
problems. What happens when you wrap your PriorityQueue
with Collections.synchronizedCollection()? Any change?

It's already synchronized.

You've hypothesized that nulls are being added to the
queue. What happens when you call PriorityQueue.add(null)?

I don't. There's only two places that add anything to the queue. One
adds the outcome of a new, and the other adds something back after it
had been removed and stored for a while, so if that one is adding a
null it's only because the queue already contained at least one null.

 

[Mark Jeffcoat]

It doesn't do anything except test booleans and compare (with < and ==)
ints. I don't see it throwing any exception, except NPE if it gets a
null argument.

Convincing. Me. Does. Not. Solve. Your. Problem.

 

[Patricia Shanahan]

It doesn't do anything except test booleans and compare (with < and ==)
ints. I don't see it throwing any exception, except NPE if it gets a
null argument.


It's already synchronized.


I don't. There's only two places that add anything to the queue. One
adds the outcome of a new, and the other adds something back after it
had been removed and stored for a while, so if that one is adding a
null it's only because the queue already contained at least one null.

I have a more indirect hypothesis to throw in the mix. JDK 1.6
PriorityQueue has a heap implementation. Is there any possibility of it
getting confused, and going off the end or creating gaps, if compareTo
is inconsistent?

I'm a bit more willing than Mark to consider library issues with a
non-final version such as 1.6.

However, I would work in any case on trying to strip down the minimal
case that reproduces the problem. You will need a minimal test case if
it is a library issue, and if it isn't trying to prepare one may bring
out the actual bug.

Patricia

 

[Mark Jeffcoat]

I have a more indirect hypothesis to throw in the mix. JDK 1.6
PriorityQueue has a heap implementation. Is there any possibility of it
getting confused, and going off the end or creating gaps, if compareTo
is inconsistent?

I pulled down the source for 1.6 after my first comment
in this thread; the stack trace made it clear that there's
been at least some significant changes since 1.5

From a brief skim, it looks to me like you can get away
with having a compareTo() that's inconsistent with equals().

If Twisted's Foo.compareTo() is inconsistent with any of
Comparable.compareTo()'s contract (anticommutative(ish),
transitive), then, yeah, I think you're exactly right--
I'd expect just the sort of bugs he's seeing.

I'm a bit more willing than Mark to consider library issues with a
non-final version such as 1.6.

I might be, too, were I not writing to the Poster Who Cried
Compiler Bug. This is what, the fourth in two days?


I guess I've stopped trying to be helpful, and moved on to a sort
of morbid curiousity: Are we ever going to get anything besides
defensive handwaving from the original poster? If he doesn't
go for your idea, that'll be answer enough for me.



(Not only do I not have your patience, but I find your
recent experience in comp.theory rather frightning. Declare
victory early and be home in time for dinner, that's my motto.)

 

[Twisted]

Patricia Shanahan wrote:
[snip]

The compareTo() here has been checked six ways to Sunday. It is
definitely imposing a total order -- no circularities of the rock,
paper, scissors sort. It doesn't have side effects. It shouldn't react
poorly except to a null passed in (even ints differing by more than
Integer.MAX_VALUE shouldn't faze it).

I'm equally certain that my code is not inserting nulls at any time.

The problem is minor, because the bug is only affecting daemon threads
and only rarely, and those threads are restarted automatically if they
die. It's a nuisance, that's all.

 

[Twisted]

(Not only do I not have your patience, but I find your
recent experience in comp.theory rather frightning. Declare
victory early and be home in time for dinner, that's my motto.)

Not a surprising sentiment from someone who apparently turns every
occasion into an excuse to wage a war, even when no-one else wants a
fight.

 

[Andreas Leitgeb]

Of course, especially seeing as it can modify the queue (if the queue
isn't empty, it removes something).

Is it possible that some fields of your Foo-instances
that are relevant to sorting can be modified while the
object is in the queue ?

You have written, that you put the object into the queue
immediately after creation - this may suggest that you might
"setup" the contents of the instance only afterwards.

I don't know if the contract for queues mentions this, but
my guts consider it dangerous to change the object's data
while the object is enqueued. (especially the data that is
relevant to sorting, of course)

 

[Andreas Leitgeb]

The problem is minor, because the bug is only affecting daemon threads
and only rarely, and those threads are restarted automatically if they
die. It's a nuisance, that's all.

This would surprise me somewhat.
Either: the poll-attempt breaks with an exception and the queue
remains unchanged, then why would the next attempt at poll()
suddenly work again?
Or: Some object is actually removed: then this object will
never be handled.
Its's hard to believe that this is not more than a minor nuissance
in the application.

I don't believe that any extra elements get added and that it's
these extra elements that disappear in the course of the NPE.

PS: have you tried running your application with java1.5 or
is your use of 1.6-features too widespread? This might also
help identify any pre-release-specific regressions in 1.6

 

[Twisted]

You have written, that you put the object into the queue
immediately after creation - this may suggest that you might
"setup" the contents of the instance only afterwards.

No, it's "setup" by the constructor and unchanged afterwards.

I don't know if the contract for queues mentions this, but
my guts consider it dangerous to change the object's data
while the object is enqueued. (especially the data that is
relevant to sorting, of course)

I have code elsewhere that does mutate objects in queues. Anytime the
change would affect compareTo() or equals() the object is removed,
modified, and added back. (All while synchronizing on the queue.) In no
case is the object concurrently modified somewhere else.

 

[Twisted]

This would surprise me somewhat.
Either: the poll-attempt breaks with an exception and the queue
remains unchanged, then why would the next attempt at poll()
suddenly work again?
Or: Some object is actually removed: then this object will
never be handled.
Its's hard to believe that this is not more than a minor nuissance
in the application.

Since the queue isn't being rendered unusable and the console isn't
being spammed with dozens in a row, it seems that some object is
actually removed -- the null. If the null remained in the queue for any
length of time, then yes there's be more than a minor nuisance.
Fortunately that does not seem to be happening.

Did I mention that I never saw NPEs here before updating to 1.6.0?