Java 1.7: sync (is) faster than void sync
I am currently implementing a multi-threaded version of the Barnes-Hut algorithm for the N-body problem. Although the algorithm works, it is not very optimized and I am trying to reduce the execution time of my program.
I made sure there were multiple threads out there that precisely defined the boundaries of the space I was working with, and realized that the code of the highest level object in which I set the boundaries is rather unoptimized. It looks like this:
public synchronized void setBorders(float maxX, float minX, float maxY, float minY, int thread){
if(maxX > this.maxX){
this.maxX = maxX;
}
if(maxY > this.maxY){
this.maxY = maxY;
}
if(this.minX > minX){
this.minX = minX;
}
if(this.minY > minY){
this.minY = minY;
}
}
I have several threads trying to access this method when they figured out their respective values. Since a synchronized object can only be accessed by one thread at a time, this can be greatly improved.
About a possible solution I was thinking about was removing the "shared synchronized void" and rewriting the code:
public synchronized void setBorders(float maxX, float minX, float maxY, float minY, int thread){
Synchronize(this){
if(maxX > this.maxX){
this.maxX = maxX;
}
}
Synchronize(this){
if(maxY > this.maxY){
this.maxY = maxY;
}
}
Synchronize(this){
if(this.minX > minX){
this.minX = minX;
}
}
Synchronize(this){
if(this.minY > minY){
this.minY = minY;
}
}
}
}
If my understanding of a synchronized block is correct, then only one thread can access the code inside the Synchronize (this) block at any given time, this should speed up my code.
Will this work, or is there a reason I should avoid this that I missed?
Edit: Wow, I'm amazed at the speed and precision of the help you guys are giving. I am very grateful for all this!
source to share
This code needs to execute very quickly, so I doubt that splitting it up into more synchronized blocks would reduce contention. I would go with a single, the function level is synchronized.
However, if the code was doing more like
...
if(maxX > this.maxX){
this.maxX = maxX;
doSomeSlowerCalculation();
updateSomeComplexSharedDataStructure();
}
...
Then breaking it down into separate synchronized blocks can help
source to share
There are three options to prevent or reduce synchronization:
Use automatics
Using a class from Guava you can do
private final AtomicDouble maxX = new AtomicDouble(Double.MIN_VALUE);
and just
while (true) {
double currentMaxX = this.maxX.get();
if (currentMaxX >= maxX) break;
boolean ok = compareAndSet(currentMaxX, maxX);
if (ok) break;
}
If you really need to use float, write your own class, do multiple lines like this .
no sync, just CAS .
Double check blocking
FROM
private volatile float maxX;
and Java 1.5 or higher, follow these steps:
if (maxX > this.maxX) {
synchronized (this) {
if (maxX > this.maxX) {
this.maxX = maxX;
}
}
}
Minimize sharing
Calculate the local max / min and only after a few iterations update the overall state. This is the easiest way, but may not apply to your use case.
source to share
To optimize this more efficiently, you can split your setBorders procedure into 4 methods (1 for each parameter) and use 4 blocking objects to lock each setter method separately ... But that would be more efficient if your setters were (not always as a block) and / or not always called in the same order, or if you could quickly exit the setter when you define a value, it doesn't really change
source to share
First add sync to method definition like
synchronized void foo() {
...
}
is the same as
void foo() {
synchronized(this) {
...
}
}
If you are inserting synchronized blocks like your second example:
synchronized void foo() {
synchronized(this) {
...
}
synchronized(this) {
...
}
}
then internal blocks do not affect synchronization, the calling thread still has to get the object monitor when the method is entered and frees it on exit.
If you remove the synchronized method, so all you have is:
void foo() {
synchronized(this) {
...
}
synchronized(this) {
...
}
}
whereas threads execute this code, they will have to purchase each block separately. Therefore, if multiple threads are setting different variables, you might end up with an object that has some fields set by one thread and other fields set by another.
With smaller synchronized blocks, threads can spend more time on locks. For each of these blocks, the scheduler must decide which thread gets the next lock. Capturing a lock is not fair, there is no certainty about which thread will acquire the lock.
It is not obvious that a lower granularity approach will be faster, it might be better to turn on the flow, set all fields and exit. The second example might just make the scheduler work harder for no good reason. The only definite difference is that the second approach will allow mixing data from different streams.
source to share