 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / November 2006NPE in PriorityQueue.poll()
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). > This is a strange one. App just recovered gracefully from: > [quoted text clipped - 3 lines] > 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. > This is a strange one. App just recovered gracefully from: > [quoted text clipped - 15 lines] > 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 > 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. >> 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 > This is a strange one. App just recovered gracefully from: > [quoted text clipped - 15 lines] > 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.]  SignatureMark Jeffcoat Austin, TX > [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). >> [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 [quoted text clipped - 8 lines] > 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)? SignatureMark Jeffcoat Austin, TX Preaching Western Civilization Since 2001 > 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've hypothesized that compareTo() is throwing an uncaught >> exception; you don't need an argument to prove me wrong, just [quoted text clipped - 4 lines] > ints. I don't see it throwing any exception, except NPE if it gets a > null argument. Convincing. Me. Does. Not. Solve. Your. Problem. SignatureMark Jeffcoat Austin, TX >> I've hypothesized that compareTo() is throwing an uncaught >> exception; you don't need an argument to prove me wrong, just [quoted text clipped - 18 lines] > 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 > 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.) SignatureMark Jeffcoat Austin, TX > (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. [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. > 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 > This would surprise me somewhat. > Either: the poll-attempt breaks with an exception and the queue [quoted text clipped - 4 lines] > 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? >> This would surprise me somewhat. >> Either: the poll-attempt breaks with an exception and the queue [quoted text clipped - 12 lines] > > Did I mention that I never saw NPEs here before updating to 1.6.0? That is consistent with either of two theories: 1. A bug in the 1.6 implementation of PriorityQueue that does not exist in the 1.5 version. 2. A bug in your code that does not produce any obvious errors in the pre-1.6 version of the code. For example, a compareTo change while an object is on the queue would be much more likely to produce an NPE with the 1.6 implementation of PriorityQueue than the 1.5 implementation. Patricia > For example, a compareTo change while an object is on the queue would be > much more likely to produce an NPE with the 1.6 implementation of > PriorityQueue than the 1.5 implementation. Highly unlikely to be the cause, since all of the fields in the object in question are final. :) >> For example, a compareTo change while an object is on the queue would be >> much more likely to produce an NPE with the 1.6 implementation of >> PriorityQueue than the 1.5 implementation. > > Highly unlikely to be the cause, since all of the fields in the object > in question are final. :) Unless these fields (those relevant to compareTo) are exclusively primitive types or immutable Objects (Integer, String, ...), the "final" doesn't help anything. So, perhaps not the enqueued items are changed, but any (even final) referenced Objects can change, and are relevant to sorting ? > Unless these fields (those relevant to compareTo) are exclusively > primitive types or immutable Objects (Integer, String, ...), > the "final" doesn't help anything. They are. Didn't I mention that the only things being used in compareTo() are booleans and integers? >> Unless these fields (those relevant to compareTo) are exclusively >> primitive types or immutable Objects (Integer, String, ...), >> the "final" doesn't help anything. > They are. Didn't I mention that the only things being used in > compareTo() are booleans and integers? Probably you did. But you can't expect anyone to remember all bits and bytes of all previous postings :-) Anyway, I think I'm through with my bag of tricks, so unless you take the effort to write some small app to reproduce the error, I'll end my participation in this thread. :-( Perhaps, posting just that one class (that gets enqueued) might help for further diagnosis without giving away too much "IP". > This is a strange one. App just recovered gracefully from: > [quoted text clipped - 15 lines] > 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. > 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). > 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) > 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. > > You have written, that you put the object into the queue > > immediately after creation - this may suggest that you might [quoted text clipped - 11 lines] > modified, and added back. (All while synchronizing on the queue.) In no > case is the object concurrently modified somewhere else. Give us an sscce (http://physci.org/codes/sscce/) and we'll give you the solution you ask for. > Give us an sscce I don't have one -- whatever it is. And what is that link you keep spamming in this newsgroup? > > Give us an sscce > > I don't have one -- whatever it is. > > And what is that link you keep spamming in this newsgroup? Try reading the link, as it tells you what an sscce is, and advice to creating one - Short, Self Contained, Correct (Compilable), Example. > > > Give us an sscce > > [quoted text clipped - 3 lines] > Try reading the link, as it tells you what an sscce is, and advice to > creating one - Short, Self Contained, Correct (Compilable), Example. Ah. Well, let that be a lesson to you then. When you write, try to avoid clever acronyms as a substitute for clarity of expression -- and don't rely on people following a link to get your message across, because people are way too leery of spam, spyware, and so forth to do anything but ignore links in Usenet posts except in a reply to a post where they specifically asked for a link, or links to well-known safe resources like Google and Wikipedia. > > > > Give us an sscce > > > [quoted text clipped - 11 lines] > where they specifically asked for a link, or links to well-known safe > resources like Google and Wikipedia. Sure can do, and let it be a lesson to you that when several people answer your questions the same way, perhaps you should investigate in understanding why. The link I provided is safe, and in any case, providing an example that allows us to reproduce your problem is the best route for help anyway. > Sure can do, and let it be a lesson to you that when several people > answer your questions the same way, perhaps you should investigate in > understanding why. If the answer is not actually an answer but another question, Web links, or whatever, then it is liable to get ignored. In any event, you posting the same thing to two or three different threads does not constitute "several people" doing *anything*. :P > The link I provided is safe And I'm supposed to just take your word for it? You may know it's safe, but all I know is it's an unsolicited(x) link to an unfamiliar(xx) site that somebody posted on usenet inside a post that is, at best, tangential to the topic(xxx) under discussion. That's three strikes, you're out, meaning I don't follow the link without a compelling reason of some kind. Certainly not just out of curiosity. > and in any case, > providing an example that allows us to reproduce your problem is the > best route for help anyway. Too bad it isn't always possible. The things I'm reporting are complex bugs that reproduce sporadically rather than systematically and basically to make them show up you just have to engage in extensive, normal use until it pops up. The simple, predictable bugs were easy to either fix (in my code) or work around as the case may be; for the most part, they never make it to being the subject of a Usenet posting. That leaves the complex ones. :) Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2008 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.