NPE in PriorityQueue.poll()

Discussion in 'Java' started by Twisted, Nov 16, 2006.

  1. Twisted

    Twisted Guest

    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, Nov 16, 2006
    #1
    1. Advertising

  2. Twisted

    Twisted Guest

    Twisted wrote:
    > 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.
    Twisted, Nov 16, 2006
    #2
    1. Advertising

  3. Twisted wrote:
    > 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
    Patricia Shanahan, Nov 16, 2006
    #3
  4. Twisted

    Twisted Guest

    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.
    Twisted, Nov 16, 2006
    #4
  5. 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
    Patricia Shanahan, Nov 16, 2006
    #5
  6. "Twisted" <> writes:

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

    --
    Mark Jeffcoat
    Austin, TX
    Mark Jeffcoat, Nov 16, 2006
    #6
  7. Twisted

    Daniel Pitts Guest

    Twisted wrote:
    > 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.
    Daniel Pitts, Nov 16, 2006
    #7
  8. Twisted

    Twisted Guest

    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).
    Twisted, Nov 16, 2006
    #8
  9. Twisted

    Twisted Guest

    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).
    Twisted, Nov 16, 2006
    #9
  10. "Twisted" <> 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
    Mark Jeffcoat, Nov 16, 2006
    #10
  11. Twisted

    Twisted Guest

    Mark Jeffcoat wrote:
    > 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.
    Twisted, Nov 16, 2006
    #11
  12. "Twisted" <> writes:

    > Mark Jeffcoat wrote:
    >> 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.



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

    --
    Mark Jeffcoat
    Austin, TX
    Mark Jeffcoat, Nov 16, 2006
    #12
  13. Twisted wrote:
    > Mark Jeffcoat wrote:
    >> 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.
    >


    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
    Patricia Shanahan, Nov 17, 2006
    #13
  14. Patricia Shanahan <> writes:

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

    --
    Mark Jeffcoat
    Austin, TX
    Mark Jeffcoat, Nov 17, 2006
    #14
  15. Twisted

    Twisted Guest

    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, Nov 17, 2006
    #15
  16. Twisted

    Twisted Guest

    Mark Jeffcoat wrote:
    > (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.
    Twisted, Nov 17, 2006
    #16
  17. Twisted <> wrote:
    > 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, Nov 17, 2006
    #17
  18. Twisted <> wrote:
    > 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
    Andreas Leitgeb, Nov 17, 2006
    #18
  19. Twisted

    Twisted Guest

    Andreas Leitgeb wrote:
    > 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, Nov 17, 2006
    #19
  20. Twisted

    Twisted Guest

    Andreas Leitgeb wrote:
    > 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?
    Twisted, Nov 17, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Steve R. Burrus

    It's still about the NPE.

    Steve R. Burrus, Mar 25, 2005, in forum: Java
    Replies:
    5
    Views:
    319
    Ryan Stewart
    Mar 27, 2005
  2. Replies:
    4
    Views:
    2,229
    Chris Uppal
    Feb 16, 2006
  3. Twisted
    Replies:
    3
    Views:
    787
    cloud
    Oct 14, 2012
  4. birdsong

    select.poll.poll() never blocks

    birdsong, Feb 12, 2009, in forum: Python
    Replies:
    2
    Views:
    443
    birdsong
    Feb 12, 2009
  5. Jean-Paul Calderone

    Re: select.poll.poll() never blocks

    Jean-Paul Calderone, Feb 12, 2009, in forum: Python
    Replies:
    3
    Views:
    433
    birdsong
    Feb 12, 2009
Loading...

Share This Page