RVM

Improvements to Random number generation

Details

  • Number of attachments :
    1

Description

Just to remember some inefficiencies of what will be warm code:

1) java.lang.Math.rand isn't final when it could be
2) java.util.Random is using synchronized where atomic longs would be more optimal

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Andrew John Hughes added a comment -

I've been looking into these issues further:

1. Making rand final would mean also losing the lazy initialization of this object. For most classes, this wouldn't be too much of an issue but most of Math's methods are orthogonal, so the result of changing this would mean the creation (and possible subsequent garbage collection) of an unused Random object. Is the cost of this worth the gain in making this field final?

2. I agree this can be patched to use AtomicLongs though I'm not sure how much the performance gain will be. I'd be interested to know if splitting the lock in the gaussian computation would be worthwhile – does the computation take a significant amount of time to compensate the additional overhead and complexity of doing this?

Show
Andrew John Hughes added a comment - I've been looking into these issues further: 1. Making rand final would mean also losing the lazy initialization of this object. For most classes, this wouldn't be too much of an issue but most of Math's methods are orthogonal, so the result of changing this would mean the creation (and possible subsequent garbage collection) of an unused Random object. Is the cost of this worth the gain in making this field final? 2. I agree this can be patched to use AtomicLongs though I'm not sure how much the performance gain will be. I'd be interested to know if splitting the lock in the gaussian computation would be worthwhile – does the computation take a significant amount of time to compensate the additional overhead and complexity of doing this?
Hide
Permalink
Andrew John Hughes added a comment -

Here's the patch. Let me know what effect it has.

Show
Andrew John Hughes added a comment - Here's the patch. Let me know what effect it has.
Hide
Permalink
Ian Rogers added a comment -

Cool, I'll have a play with the patch. Is caching unsafe necessary? We always inline Unsafe.getUnsafe so the overhead in calling it each time isn't really there.

<quote>
Making rand final would mean also losing the lazy initialization of this object. For most classes, this wouldn't be too much of an issue but most of Math's methods are orthogonal, so the result of changing this would mean the creation (and possible subsequent garbage collection) of an unused Random object. Is the cost of this worth the gain in making this field final?
</quote>

It's hard to say, it depends on whether programs are using Math.random or creating Random classes of their own. Making it final will lose one indirection per call of Math.random when this method gets inlined, this could have a small performance impact. If the field weren't static, making it final would also mean we don't need to scan the field when we scan the boot image references held in the root map. I'd tend to make it final anyway as it looks to me there's a hypothetical race. 2 threads could call Math.random() in the same millisecond time causing its construction as rand is null. The 2 created Randoms will have the same seed and return the same random value, whereas they should return two different values if the field weren't lazily initialized. There either needs to be a synchronize to avoid this, or don't lazily initialize. I'd favor the latter to avoid introducing unnecessary locking code (in which case the field might as well be final).

Show
Ian Rogers added a comment - Cool, I'll have a play with the patch. Is caching unsafe necessary? We always inline Unsafe.getUnsafe so the overhead in calling it each time isn't really there. <quote> Making rand final would mean also losing the lazy initialization of this object. For most classes, this wouldn't be too much of an issue but most of Math's methods are orthogonal, so the result of changing this would mean the creation (and possible subsequent garbage collection) of an unused Random object. Is the cost of this worth the gain in making this field final? </quote> It's hard to say, it depends on whether programs are using Math.random or creating Random classes of their own. Making it final will lose one indirection per call of Math.random when this method gets inlined, this could have a small performance impact. If the field weren't static, making it final would also mean we don't need to scan the field when we scan the boot image references held in the root map. I'd tend to make it final anyway as it looks to me there's a hypothetical race. 2 threads could call Math.random() in the same millisecond time causing its construction as rand is null. The 2 created Randoms will have the same seed and return the same random value, whereas they should return two different values if the field weren't lazily initialized. There either needs to be a synchronize to avoid this, or don't lazily initialize. I'd favor the latter to avoid introducing unnecessary locking code (in which case the field might as well be final).
Hide
Permalink
Andrew John Hughes added a comment -

Sorry for the delay in reply, didn't realise you had replied so quickly

I was in two minds about caching Unsafe. When I was concerned about the serialisation, I noticed that the Javadocs for the API now specified readObject/writeObject so I checked the OpenJDK code and sure enough they've also switched to using an AtomicLong and cache the Unsafe needed to change it. I think caching is the safest bet across all VMs, although referencing the class is probably enough to do most of the work, based on the reference implementation (IIRC it's in the class initialisation).

With random, the method is already synchronised avoiding the race condition. Such a lock on the Class object's monitor is costly, I agree, but my concern was more that invoking e.g. Math.sin() or Math.floor() would instantiate a Random object which may never be used. Flicking through the JSR166 book again today, I see they provide what may be a desirable intermediate object (if a bit of a hack); they construct an inner class which holds the reference and which is then initialised lazily by the method. This avoids the synchronisation (as the VM gets a lock on the new class during initialisation anyway) but also means that the Random isn't created until needed e.g.

private final class RandomHelper
{
static final Random randomInstance;
}

Let me know what you think.

Show
Andrew John Hughes added a comment - Sorry for the delay in reply, didn't realise you had replied so quickly I was in two minds about caching Unsafe. When I was concerned about the serialisation, I noticed that the Javadocs for the API now specified readObject/writeObject so I checked the OpenJDK code and sure enough they've also switched to using an AtomicLong and cache the Unsafe needed to change it. I think caching is the safest bet across all VMs, although referencing the class is probably enough to do most of the work, based on the reference implementation (IIRC it's in the class initialisation). With random, the method is already synchronised avoiding the race condition. Such a lock on the Class object's monitor is costly, I agree, but my concern was more that invoking e.g. Math.sin() or Math.floor() would instantiate a Random object which may never be used. Flicking through the JSR166 book again today, I see they provide what may be a desirable intermediate object (if a bit of a hack); they construct an inner class which holds the reference and which is then initialised lazily by the method. This avoids the synchronisation (as the VM gets a lock on the new class during initialisation anyway) but also means that the Random isn't created until needed e.g. private final class RandomHelper { static final Random randomInstance; } Let me know what you think.
Hide
Permalink
Ian Rogers added a comment -

Using lazy initialization is fine, it will cost some space in the statics/class loader. Any progress with this Andrew?

Show
Ian Rogers added a comment - Using lazy initialization is fine, it will cost some space in the statics/class loader. Any progress with this Andrew?

People

  • Assignee:
    Unassigned
    Reporter:
    Ian Rogers
Vote (0)
Watch (0)

Dates

  • Created:
    Updated: