Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (482)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  double-checked locking... in the JDK core?!  (Read 6084 times)
0 Members and 1 Guest are viewing this topic.
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Posted 2012-09-04 11:19:47 »

While doing something completely unrelated, I ended up inadvertently browsing java.util.Random src, and noticed....

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
    private static Random randomNumberGenerator;

    private static synchronized Random initRNG() {
        Random rnd = randomNumberGenerator;
        return (rnd == null) ? (randomNumberGenerator = new Random()) : rnd;
    }

    public static double random() {
        Random rnd = randomNumberGenerator;
        if (rnd == null) rnd = initRNG();
        return rnd.nextDouble();
    }


Isn't that an obtuse implementation of double-checked locking?

I thought out of order writes made the double-checked locking idiom all kinds of bad?

No doubt if it is a bug it'd be hideously complicated to detect it in any kind of unit test.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline nsigma
« Reply #1 - Posted 2012-09-04 11:30:47 »

Wasn't double-checked locking fixed in Java 5 anyway?

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Roquen
« Reply #2 - Posted 2012-09-04 11:34:09 »

Wasn't that usage fixed in the second memory model?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #3 - Posted 2012-09-04 11:41:02 »

yeah i think it was "fixed" in java 5 if you made the variable volatile... i.e.
1  
private static volatile Random randomNumberGenerator;


so it does seem like a bug
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #4 - Posted 2012-09-04 12:01:23 »

http://bugs.sun.com/view_bug.do?bug_id=6633229

Found it in the bug database.
Reported 5 years ago....... Still not fixed.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline moogie

JGO Knight


Medals: 12
Projects: 6
Exp: 10 years


Java games rock!


« Reply #5 - Posted 2012-09-04 12:24:40 »

granted that their rationale for not fixing is pretty convincing... I would have thought that the fix was low impact/risk
Offline Damocles
« Reply #6 - Posted 2012-09-04 12:25:32 »

That should work
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
  private static Random randomNumberGenerator;
  private static boolean randomNumberGeneratorCreated=false;

    private static synchronized Random initRNG() {
       
      if(!randomNumberGeneratorCreated)
      {
      randomNumberGenerator = new Random();
      randomNumberGeneratorCreated=true;
      }
      return randomNumberGenerator;
    }

    public static double random() {
        Random rnd = randomNumberGenerator;
        if (!randomNumberGeneratorCreated) rnd = initRNG();
        return rnd.nextDouble();
    }

Offline Roquen
« Reply #7 - Posted 2012-09-04 13:18:32 »

The thing is, in this case, it doesn't matter if more than one end up getting created.
Offline Damocles
« Reply #8 - Posted 2012-09-04 13:40:04 »

Maybe in some special cryptographic algorythm setup it may matter.

Offline Roquen
« Reply #9 - Posted 2012-09-04 13:47:10 »

If you need serious random numbers you shouldn't use java.util.Random.  That aside, worst case situation is a given caller might see two values that are slightly less decollerated than if this potential defect didn't exist, but it cannot effect any meaningful computation.  I promise, this isn't a problem.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline delt0r

JGO Knight


Medals: 27
Exp: 18 years


Computers can do that?


« Reply #10 - Posted 2012-09-04 14:53:36 »

java.util.Random is a LCG which is by definition *not* a cryptographic strength source of random numbers. Hell it doesn't even pass the die hard tests and its not all that fast.

Its good enough for most things.. But even my scientific code uses a far better implementation (yea and better than MT too). 

Also does anything use these static things? I always create a random for each thread.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Roquen
« Reply #11 - Posted 2012-09-04 15:03:25 »

You really should never use the same generator on more than one thread.  Which generator? WELL?
Offline ra4king

JGO Kernel


Medals: 345
Projects: 2
Exp: 5 years


I'm the King!


« Reply #12 - Posted 2012-09-04 15:20:40 »

It may just be my slow mind today.....but what exactly is the 'bug' here? What's wrong with this double-checked locking?

EDIT: I could probably envision some race conditions, so that might be what the problem is here. Damocle's code is even worse, because the boolean is set after the object is created, with a greater chance of a race condition.

The only fix I can see for this is to initialize the 'rng' in a static initialization block.

Offline nsigma
« Reply #13 - Posted 2012-09-04 15:58:15 »

What's wrong with this double-checked locking?

Try this - http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

Damocle's code is even worse, because the boolean is set after the object is created, with a greater chance of a race condition.

After the object is created may be just what the doctor ordered!  Wink 

The only fix I can see for this is to initialize the 'rng' in a static initialization block.

I much prefer this myself, and if done properly the class isn't initialized until it's needed anyway.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline sproingie

JGO Kernel


Medals: 202



« Reply #14 - Posted 2012-09-04 16:07:42 »

The source I have for java.util.Random in JDK7 looks nothing like that and has no public static methods at all.
Offline Abuse

JGO Knight


Medals: 12


falling into the abyss of reality


« Reply #15 - Posted 2012-09-04 16:11:17 »

The source I have for java.util.Random in JDK7 looks nothing like that and has no public static methods at all.


Sorry, Math.

Make Elite IV:Dangerous happen! Pledge your backing at KICKSTARTER here! https://dl.dropbox.com/u/54785909/EliteIVsmaller.png
Offline sproingie

JGO Kernel


Medals: 202



« Reply #16 - Posted 2012-09-04 16:18:50 »

The usage is safe -- the RNG instance is private, and the reference never escapes, and the second check that does the actual creation synchronizes on it.  You'll notice that the second check returns the instance if had lost a race and another thread created it inbetween -- this is an addition to the double-checked idiom that isn't in the standard example.  Since there is no other path that can create the RNG, there is no other race condition.

I prefer the static inner class idiom over that double-checking foofrah anyway.

Offline nsigma
« Reply #17 - Posted 2012-09-04 16:50:49 »

You'll notice that the second check returns the instance if had lost a race and another thread created it inbetween -- this is an addition to the double-checked idiom that isn't in the standard example.

You sure?  Looks like the standard example with the second if changed for a ternary operation to me.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline sproingie

JGO Kernel


Medals: 202



« Reply #18 - Posted 2012-09-04 16:59:51 »

The standard double-checked locking is "if the reference is null, create it, and do nothing if it's not null, then grab the reference again and return it".  This one is "if the reference is null, create it, and return it if it's not null, then return that".  It's subtly different, but in the latter case, the reference being returned is properly synchronized.

This stuff is subtle and tricky, and I'm by no means a concurrency guru, so I'm wrong, do point it out with a counterexample.  Though like I mentioned before, I don't bother with double-checked locking anyway, so it's more academic curiosity.

At any rate, since you can't control the seeding of the static RNG instance in Math, it's not like a race condition would have much observable effect anyway.
Offline nsigma
« Reply #19 - Posted 2012-09-04 17:19:23 »

It's subtly different, but in the latter case, the reference being returned is properly synchronized.
...
At any rate, since you can't control the seeding of the static RNG instance in Math, it's not like a race condition would have much observable effect anyway.

I now see the difference you mean, but I'm not sure it protects against out-of-order writes in the constructor.  See this bug linked from one above - the random could potentially be used before the seed is initialised (AtomicLong) causing a NPE.  The evaluation of that bug seems to suggest it can't happen with the Sun JVM so who knows?

I don't bother with double-checked locking anyway, so it's more academic curiosity.

+1

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline sproingie

JGO Kernel


Medals: 202



« Reply #20 - Posted 2012-09-04 17:28:01 »

If the seed is an AtomicLong, doesn't that mean the seed is initialized, er, atomically?
Offline nsigma
« Reply #21 - Posted 2012-09-04 17:31:45 »

If the seed is an AtomicLong, doesn't that mean the seed is initialized, er, atomically?

Yes, but it doesn't mean it's been initialised at all by the time another thread sees the Random object.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline sproingie

JGO Kernel


Medals: 202



« Reply #22 - Posted 2012-09-04 17:50:15 »

Ah, I see your point about that, and there's the whole other possibility of working with an incompletely initialized class in general, something I don't know all the rules about... another reason shared state is the devil's playground I suppose.
Offline Danny02
« Reply #23 - Posted 2012-09-05 05:17:20 »

when I need to initialize some static resource lazyly I do this, its easy and thread safe

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
public class X
{
  private static class StaticStuff
  {
     public static MyObject lazyObject = new MyObject();
  }

  public void someMethod()
  {
    Object something = useResource(StaticStuff.lazyObject);
  }


just let the classloader handle everything Wink
Offline Roquen
« Reply #24 - Posted 2012-09-05 05:47:29 »

If the seed is an AtomicLong, doesn't that mean the seed is initialized, er, atomically?

Yes, but it doesn't mean it's been initialised at all by the time another thread sees the Random object.
Unless I'm on drugs, the second memory model requires the constructor to be completed before reference is visible anywhere.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #25 - Posted 2012-09-05 06:02:20 »

Unless I'm on drugs, the second memory model requires the constructor to be completed before reference is visible anywhere.
Maybe I'm on drugs (too?), but how could that possibly be enforced?



1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
public class X {
   public final int x, y;
   public X() {
      this.x = 5;

      // expose instance, before constructor is complete, where final 'y' is still zero
     Registry.register(this);

      this.y = 6;
   }
}

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline nsigma
« Reply #26 - Posted 2012-09-05 06:29:28 »

@Roquen - that's what I thought too, hence my first reply. However, from further reading I think moogie may be right about the need for the reference to be marked volatile.

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Roquen
« Reply #27 - Posted 2012-09-05 09:42:34 »

@Riven: well sure.  A determine programmer can break about anything and in your example indeed the reference will be visible before the constructor has completed.  But I'm sure we can agree that an object making itself visible in its constructor is very naughty.  I was referring to:

x = new WhatEver();

The constructor is insured to be completed before the value of 'x' changes.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #28 - Posted 2012-09-05 10:09:17 »

I have to admit I was not aware of the fact that it behaved differently in the 'first' Java Memory Model.

I thought it had to do with the order of bytecode operations. persecutioncomplex


1  
2  
3  
4  
ANEW some/Clazz // create instance
DUP
INVOKESPECIAL <init> // run constructor
ASTORE n // assign to local variable
Do I understand correctly that the above code would expose the instance to the local variable (line 4), before line 3 was fully executed? Possibly due to the JIT reordering the operations?

Like:
1  
2  
3  
4  
ANEW some/Clazz // create instance
ASTORE n // assign to local variable
ALOAD n // grab from local variable
INVOKESPECIAL <init> // run constructor

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline nsigma
« Reply #29 - Posted 2012-09-05 10:52:18 »

I was referring to:

x = new WhatEver();

The constructor is insured to be completed before the value of 'x' changes.

I think this is only the case where x is volatile (unless all accesses are in synchronized blocks).

I thought it had to do with the order of bytecode operations. persecutioncomplex

Yes, though I think your example is wrong in the sense that we've got to be talking about non-local variables?  The variable has to be visible from two different threads - it was a memory model change in the sense of when operations on one thread are visible to another.

But I'm sure we can agree that an object making itself visible in its constructor is very naughty.

And unfortunately, and very occasionally, necessary.  I've sometimes wondered about the ability to have two-stage construction here actually, where all assignments (particularly final ones) happen in a first stage where 'this' is invalid (including all subclass constructors), then an optional second stage for registering 'this' with other things, etc.  Probably a bad idea!  Wink

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

CopyableCougar4 (14 views)
2014-08-22 19:31:30

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (37 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!