Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > NPE in PriorityQueue.poll()

Reply
Thread Tools

NPE in PriorityQueue.poll()

 
 
Twisted
Guest
Posts: n/a
 
      11-16-2006
This is a strange one. App just recovered gracefully from:

java.lang.NullPointerException
at java.util.PriorityQueue.siftDownComparable(Priorit yQueue.java:627)
at java.util.PriorityQueue.siftDown(PriorityQueue.jav a:614)
at java.util.PriorityQueue.poll(PriorityQueue.java:52 3)
at com.sourceforge.sphaera.SThread.run(SThread.java:1 5

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).

 
Reply With Quote
 
 
 
 
Twisted
Guest
Posts: n/a
 
      11-16-2006
Twisted wrote:
> This is a strange one. App just recovered gracefully from:
>
> java.lang.NullPointerException
> at java.util.PriorityQueue.siftDownComparable(Priorit yQueue.java:627)
> at java.util.PriorityQueue.siftDown(PriorityQueue.jav a:614)
> at java.util.PriorityQueue.poll(PriorityQueue.java:52 3)
> at com.sourceforge.sphaera.SThread.run(SThread.java:1 5


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.

 
Reply With Quote
 
 
 
 
Patricia Shanahan
Guest
Posts: n/a
 
      11-16-2006
Twisted wrote:
> This is a strange one. App just recovered gracefully from:
>
> java.lang.NullPointerException
> at java.util.PriorityQueue.siftDownComparable(Priorit yQueue.java:627)
> at java.util.PriorityQueue.siftDown(PriorityQueue.jav a:614)
> at java.util.PriorityQueue.poll(PriorityQueue.java:52 3)
> at com.sourceforge.sphaera.SThread.run(SThread.java:1 5
>
> 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


 
Reply With Quote
 
Twisted
Guest
Posts: n/a
 
      11-16-2006
Patricia Shanahan wrote:
> 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.

 
Reply With Quote
 
Patricia Shanahan
Guest
Posts: n/a
 
      11-16-2006
Twisted wrote:
> Patricia Shanahan wrote:
>> 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).


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
 
Reply With Quote
 
Mark Jeffcoat
Guest
Posts: n/a
 
      11-16-2006
"Twisted" <(E-Mail Removed)> writes:

> This is a strange one. App just recovered gracefully from:
>
> java.lang.NullPointerException
> at java.util.PriorityQueue.siftDownComparable(Priorit yQueue.java:627)
> at java.util.PriorityQueue.siftDown(PriorityQueue.jav a:614)
> at java.util.PriorityQueue.poll(PriorityQueue.java:52 3)
> at com.sourceforge.sphaera.SThread.run(SThread.java:1 5
>
> 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.]

--
Mark Jeffcoat
Austin, TX
 
Reply With Quote
 
Daniel Pitts
Guest
Posts: n/a
 
      11-16-2006

Twisted wrote:
> This is a strange one. App just recovered gracefully from:
>
> java.lang.NullPointerException
> at java.util.PriorityQueue.siftDownComparable(Priorit yQueue.java:627)
> at java.util.PriorityQueue.siftDown(PriorityQueue.jav a:614)
> at java.util.PriorityQueue.poll(PriorityQueue.java:52 3)
> at com.sourceforge.sphaera.SThread.run(SThread.java:1 5
>
> 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.

 
Reply With Quote
 
Twisted
Guest
Posts: n/a
 
      11-16-2006
Mark Jeffcoat wrote:
> [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).

 
Reply With Quote
 
Twisted
Guest
Posts: n/a
 
      11-16-2006
Daniel Pitts wrote:
> 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).

 
Reply With Quote
 
Mark Jeffcoat
Guest
Posts: n/a
 
      11-16-2006
"Twisted" <(E-Mail Removed)> writes:

> Mark Jeffcoat wrote:
>> [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)?


--
Mark Jeffcoat
Austin, TX
Preaching Western Civilization Since 2001
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
NPE-G1 Daniel Skrzypkowski Cisco 1 04-07-2004 10:13 AM
FS Cisco 7206VXR/400 Router + NPE-G1 David Wenn Cisco 1 01-03-2004 04:58 AM
FS Cisco 7206VXR/400 Router + NPE-G1 David Wenn Cisco 0 12-19-2003 12:15 AM
FS Cisco 7206VXR Routers + NPE-G1 David Wenn Cisco 0 10-28-2003 11:08 PM
FS Cisco 7206VXR Routers + NPE-G1 David Wenn Cisco 0 10-21-2003 12:17 AM



Advertisments