tag:blogger.com,1999:blog-8523046672726455213.post6164665296772570477..comments2022-03-26T19:01:31.406-07:00Comments on The Mailinator(tm) Blog: A Beautiful Race Conditionpaulhttp://www.blogger.com/profile/11412172362500455307noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-8523046672726455213.post-73445072858846091342013-05-22T17:36:15.561-07:002013-05-22T17:36:15.561-07:00Let's assume we have only one element in the b...Let's assume we have only one element in the bucket before reize(). <br /><br />Is the infinite loop still possible?<br /><br />I think yes. <br /><br />Thread1 : <br />elemA.next = newArray[newIndex];<br />newArray[newIndex] = elemA;<br /><br />Thread2 : <br />elemA.next = newArray[newIndex]; // what if the thread1 has already done the transferring...<br /><br />We will end-up with <br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-14780203534929636632013-04-18T04:36:54.564-07:002013-04-18T04:36:54.564-07:00Hi Paul,
After reading this wonderful post I woul...Hi Paul,<br /><br />After reading this wonderful post I would like to innocently mention you that your post has a bug. After non threaded 3rd iteration it should be <br /><br />3 -> C -> B -> A -> null<br /><br />but the image shows that C is not moved to the new bucket.<br /><br />Had it been true then it would have never found C after rehashing by a get(C) call. What do you think?Amitabha Royhttps://www.blogger.com/profile/08525221923361076568noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-33520070013463829562012-06-13T08:30:54.823-07:002012-06-13T08:30:54.823-07:00Thank you for the nice post. I have learned about ...Thank you for the nice post. I have learned about this feature of HashMap today because of a call from one of our clients (some big financial institution), where they had 99% of CPU servicing HashMap.get()s. Took quite a while to believe in the jstack output full of jdk methods :)Unknownhttps://www.blogger.com/profile/06872673561543697772noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-4418910635723959862011-06-05T03:48:21.391-07:002011-06-05T03:48:21.391-07:00Great article, I knew something about it but you m...Great article, I knew something about it but you make it so clear then I will always remember it. Thanks a lot.Javin @ hashmap in javahttp://javarevisited.blogspot.com/2010/10/difference-between-hashmap-and.htmlnoreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-14837447530056575502010-06-01T06:15:38.732-07:002010-06-01T06:15:38.732-07:00Years ago I encountered this "beautiful"...Years ago I encountered this "beautiful" situation. Reading the code, I came to the correct understanding.<br /><br />The post here describes the issue MUCH more clearly than I could - thank you.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-46242694861353654452009-08-14T07:05:58.756-07:002009-08-14T07:05:58.756-07:00It is just this race condition that makes JDOM so ...It is just this race condition that makes JDOM so broken when even different JDOM instances are accessed from different threads. At the root of JDOM is a static cache of namespaces.Steve Lakehttps://www.blogger.com/profile/16450008495890318156noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-82450225070183470082009-08-07T13:09:21.879-07:002009-08-07T13:09:21.879-07:00This happened in production code where I work. Som...This happened in production code where I work. Some genius had made their own connection pool (unsychronized). The app had crashed many times in production but was just restarted, and none of the system's developers could find the problem. It was located because we shared the same development machine with this piece of junk and occasionally it would eat all the CPU. A simple thread dump Unknownhttps://www.blogger.com/profile/14841515209304547220noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-46099892779057040232009-07-05T01:30:11.276-07:002009-07-05T01:30:11.276-07:00I was one of the first programmers on the NetBeans...I was one of the first programmers on the NetBeans team in Prague to have a multi-processor machine, and do a lot of coding at home.<br /><br />And, sure enough, I ran into this puzzling hang where every thread dump I pulled was inside HashMap.get(), scratched my head for a few minutes, figured out it what really was and laughed my ass off.<br /><br />It's my favorite race condition too, if Tim Boudreauhttps://www.blogger.com/profile/09178225575028777886noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-35063102221815007282009-06-19T00:18:21.121-07:002009-06-19T00:18:21.121-07:00Beautiful and not immediately apparent -- but it s...Beautiful and not immediately apparent -- but it seems the rc is dwarfed by the problems of the use of a global HashMap in the first place. Aren't you getting all the overhead of Java and all the round-in-the-chamber problems of c++?<br /><br />My rule of thumb is that if a coding idea of mine strikes me as "ooh, clever, what a neat unintended use that has!", to be deeply Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-35442196094231550862009-06-10T09:23:27.833-07:002009-06-10T09:23:27.833-07:00I've seen this happen in the wild. Fortunately...I've seen this happen in the wild. Fortunately we caught it before deploying to production.<br /><br />The bug was introduced after reworking some code to run in parallel where previously it had been single-threaded. IMHO this is one of the more difficult & dangerous refactorings to perform because it's so easy to miss issues exactly like this. Designing multithreaded code from the Chris Millernoreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-11264866861214511542009-06-10T02:22:15.199-07:002009-06-10T02:22:15.199-07:00Ah, SimpleDateFormat, how I love your crashes in t...Ah, SimpleDateFormat, how I love your crashes in third-party code just after midnight on Sunday morning.<br /><br />I haven't seen this with HashMap, but I've had to debug and fix two threads getting into infinite loops while each updated an unsynchronized TreeMap. With bonus points for it being hard to actually get a heap dump when you have more looping threads than CPU cores.Carey Evanshttps://www.blogger.com/profile/03868392542114468828noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-43270796949776873612009-06-10T01:44:30.062-07:002009-06-10T01:44:30.062-07:00Neat. One correction -- Thread2 needs to get to l...Neat. One correction -- Thread2 needs to get to line 5 before Thread1 gets to line 7, since otherwise Thread2's starting e will be null and it won't perform the resizing (leaving Thread1 to do the resizing correctly).sasmithhttps://www.blogger.com/profile/02662886624941879549noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-11897469586964866992009-06-10T00:40:44.182-07:002009-06-10T00:40:44.182-07:00Nice tale and presentation :)Nice tale and presentation :)Anonymoushttps://www.blogger.com/profile/07286834543482860937noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-69947228915102918002009-06-10T00:18:57.838-07:002009-06-10T00:18:57.838-07:00Great post!
My colleagues ran into this problem in...Great post!<br />My colleagues ran into this problem in practice and now we finally know why this happens :)<br /><br />BTW, there are rare conditions where one can ignore races. Hans Boehm has a paper about a sieve of erathostens implementation that has races, but still works. Can't find the reference at the moment it's also mentioned here: http://www.hpl.hp.com/personal/Hans_Boehm/Anonymoushttps://www.blogger.com/profile/06348916709650836506noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-85026939263734251802009-06-09T22:57:47.557-07:002009-06-09T22:57:47.557-07:00And that's just the basic single-core version ...And that's just the basic single-core version of the race condition. There's so many more fun ways for it to get corrupted as you start adding cores. I think I've used this one as an interview question before, though. It's a great way to take a senior candidate and figure out what they *really* know about the underlying implementation. The other one that a lot of people seem eyrieowlnoreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-55154594886290368842009-06-09T22:25:53.527-07:002009-06-09T22:25:53.527-07:00This is indeed beautifulThis is indeed beautifulUnknownhttps://www.blogger.com/profile/14743742369459516874noreply@blogger.comtag:blogger.com,1999:blog-8523046672726455213.post-16533229828269791672009-06-09T20:27:43.633-07:002009-06-09T20:27:43.633-07:00You shared an office with Josh Bloch? That's ...You shared an office with Josh Bloch? That's hot.Anonymousnoreply@blogger.com