In a multithreaded environment, where multiple threads are reading and writing to a ArrayList, what is the most efficient thread safe way of reading and writing from a ArrayList without incurring the cost of using synchronized keyword.
In simple words, have a thread safe arraylist, without using sychronized keyword.
> In a multithreaded environment, where multiple
> threads are reading and writing to a ArrayList, what
> is the most efficient thread safe way of reading and
> writing from a ArrayList without incurring the cost
> of using synchronized keyword.
> n simple words, have a thread safe arraylist, without
> using sychronized keyword.
No such thing.
ArrayList is, by default, not synchronized. It's your responsibility to make it safe.
%
> In a multithreaded environment, where multiple
> threads are reading and writing to a ArrayList, what
> is the most efficient thread safe way of reading and
> writing from a ArrayList without incurring the cost
> of using synchronized keyword.
> n simple words, have a thread safe arraylist, without
> using sychronized keyword.
In other words you want your ArrayList to be completely thread-safe without ever incurring any cost at all. We'd all love that, but in the real world that's not possible. Asking "What is the most efficient way to do this?" is fine, but when you start throwing things like "without using synchronized" I start to wonder. What if using synchronized is the most efficient? Why are you arbitrarily eliminating the language's built-in method for handling it?
There's more than a few ways to do this, I haven't the slightest idea what the most efficient is. If I were you I'd take a look at java.util.concurrent as minds far greater than my own have worked on this and there are List implementations that might suit your requirements there.
Okay, let say you have a class called ReadWriteLock. You have instance variable named arrayList. Then you have something like
readLock() and writeLock() methods. Now without making these methods sychronized, we need to be able to read from arrayList and write to arrayList.
What if you use boolean state flag when reading and writing from arrayList. Then you can use wait and notify mechanics to control when to read and write using a state flag.
I can implement that but I was wondering if there is a better approach to this scenario that some one out there may have a input on ?
> Okay, let say you have a class called ReadWriteLock.
> You have instance variable named arrayList. Then you
> have something like
> readLock() and writeLock() methods. Now without
> making these methods sychronized, we need to be able
> to read from arrayList and write to arrayList.
> What if you use boolean state flag when reading and
> writing from arrayList. Then you can use wait and
> notify mechanics to control when to read and write
> using a state flag.
You can implement that. It won't work, but you can certainly implement it.
The reason it won't work is because the thread switch might occur in the middle of where you are processing the if to check if the flag is set.
> You can implement that. It won't work, but you can
> certainly implement it.
>
> The reason it won't work is because the thread switch
> might occur in the middle of where you are processing
> the if to check if the flag is set.
It could be implemented if it were 1.5+ and the variable were volatile. The end result would be less easily understood semantics and slower performance.
> Okay, let say you have a class called ReadWriteLock.
What makes you think you can do this faster than synchronization already does?
> You have instance variable named arrayList. Then you
> have something like
> readLock() and writeLock() methods. Now without
> making these methods sychronized, we need to be able
> to read from arrayList and write to arrayList.
> What if you use boolean state flag when reading and
> writing from arrayList. Then you can use wait and
> notify mechanics to control when to read and write
> using a state flag.
> I can implement that but I was wondering if there is
> a better approach to this scenario that some one out
> there may have a input on ?
I'll bet the java.util.concurrent classes are better than anything you'll ever write. Why not use what's available to you?
%
Before spending time on trying to avoid synchronization please be aware that Java's synchronization is very fast. It's built in and hotspot knows how to optimize "synchronized" into a couple of machine instructions.
Try the test below. How many million synchronizations per seconds does your program need to do? Is synchronized really your bottleneck?
This test program does not test contended synchronization; the more contended your sync blocks are the slower they get. As always when concerned with speed run with "java -server". The difference between JDK 1.5 and the upcoming Java SE 6 may also be interesting.
public class SyncSpeed3
{
int count;
static final int LOOPS = 100000000;
public static void main(String args[])
{
System.out.println("Ignore the first few timings.");
System.out.println("They may include Hotspot compilation time.");
System.out.println("I hope you are running me with \"java -server\"!");
SyncSpeed3 x = new SyncSpeed3();
for (int n = 0; n < 5; n++) {
x.doit1();
x.doit2();
x.doit3();
}
}
void doit1()
{
long start = System.currentTimeMillis();
for (int n = 0; n < LOOPS; n++) {
synchronized (this) {
count /= 2;
}
}
long end = System.currentTimeMillis();
long time = end - start;
System.out.println("synchronized block: " + time + " ms, " +
(LOOPS * 1000 / time) + " operations/s");
}
void doit2()
{
long start = System.currentTimeMillis();
for (int n = 0; n < LOOPS; n++) {
doOperation();
}
long end = System.currentTimeMillis();
long time = end - start;
System.out.println("synchronized method: " + time + " ms, " +
(LOOPS * 1000 / time) + " operations/s");
}
synchronized void doOperation()
{
count /= 2;
}
void doit3()
{
long start = System.currentTimeMillis();
for (int n = 0; n < LOOPS; n++) {
count /= 2;
}
long end = System.currentTimeMillis();
long time = end - start;
System.out.println("no synchronization: " + time + " ms, " +
(LOOPS * 1000 / time) + " operations/s");
}
}
If you have bad experiences with C's synchronization here is a version using pthreads. Fortunately Java does much better.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <pthread.h>
#define LOOPS 100000000
static int count;
int main(int argc, char **argv)
{
pthread_mutex_t mutex;
time_t start, end, t;
int n;
pthread_mutex_init(&mutex, NULL);
start = time(NULL);
for (n = 0; n < LOOPS; n++) {
pthread_mutex_lock(&mutex);
count /= 2;
pthread_mutex_unlock(&mutex);
}
end = time(NULL);
t = end - start;
printf("time %d seconds, %d operations/s\n",
(int) t, (int) (LOOPS / t));
return 0;
}
> In a multithreaded environment, where multiple
> threads are reading and writing to a ArrayList, what
> is the most efficient thread safe way of reading and
> writing from a ArrayList without incurring the cost
> of using synchronized keyword.
> n simple words, have a thread safe arraylist, without
> using sychronized keyword.
The overhead of synchronization is generally negligible. The true cost of synchronization is caused by contention between threads. If you have little or no contention then stop worrying about this and synchronize.
Here are the results of running the program code mentioned above
Ignore the first few timings.
They may include Hotspot compilation time.
I hope you are running me with "java -server"!
synchronized block: 4750 ms, 255947 operations/s
synchronized method: 4610 ms, 263720 operations/s
no synchronization: 125 ms, 9726017 operations/s
synchronized block: 4625 ms, 262865 operations/s
synchronized method: 4594 ms, 264639 operations/s
no synchronization: 125 ms, 9726017 operations/s
synchronized block: 4625 ms, 262865 operations/s
synchronized method: 4625 ms, 262865 operations/s
no synchronization: 110 ms, 11052292 operations/s
synchronized block: 4765 ms, 255142 operations/s
synchronized method: 4954 ms, 245408 operations/s
no synchronization: 140 ms, 8683944 operations/s
synchronized block: 5000 ms, 243150 operations/s
synchronized method: 4594 ms, 264639 operations/s
no synchronization: 109 ms, 11153689 operations/s
> synchronized block: 5000 ms, 243150 operations/s
> synchronized method: 4594 ms, 264639 operations/s
> no synchronization: 109 ms, 11153689 operations/s
What JVM do you have? Those numbers are on the slow side.
The operations/s numbers are incorrect because this forum has a stupid bug: if you post the number 1000L inside [code] tags the forum strips the L away. I kid you not! So to get correct op/s figures you need to change 1000 to 1000L in three places in the program.
Here is what I get with Java SE 6 on a Windows laptop:
synchronized block: 741 ms, 134952766 operations/s
synchronized method: 701 ms, 142653352 operations/s
no synchronization: 260 ms, 384615384 operations/s
> Why is the synchronized block takes more time than
> synchronized method ?
Most likely because of the order the tests are running in.
Here's a version of my patented (not really) speed tester. I just modded it to randomize the order of the tests on the outer loop. If anyone sees an error in the code, please point it out as I just messed with it. I tested it and it runs without error. FYI, these are the kind of results I am getting:
Unsync: 2309 - 2.309E-5 millis per test
SyncMeth: 3159 - 3.159E-5 millis per test
Sync: 2625 - 2.625E-5 millis per test
import java.util.*;
import java.math.*;
public class SpeedTester
{
public static final long OUTER_ITERATIONS = 100;
public static final long INNER_ITERATIONS = 1000000;
public static void main(String[] args)
{
Data[] data = {};
Test[] tests = {new Sync(), new Unsync(), new SyncMeth()};
Map times = new HashMap();
for (int j = 0; j < OUTER_ITERATIONS; j++)
{
for (int k = 0; k < data.length; k++)
{
data[k].create();
}
Collections.shuffle(Arrays.asList(tests));
for (int k = 0; k < tests.length; k++)
{
//System.gc(); // uncomment if GC may affect results: slows down testing
Test test = tests[k];
Long total = (Long) times.get(test);
long time = test(test);
if (total == null) {
total = new Long(time);
} else {
total = new Long(total.longValue() + time);
}
times.put(test, total);
}
}
for (int j = 0; j < tests.length; j++)
{
Test test = tests[j];
long total = ((Long) times.get(test)).longValue();
System.out.println(test.getClass().getName() + ": " + total + " - "
+ ((double) total) / (OUTER_ITERATIONS * INNER_ITERATIONS)
+ " millis per test");
}
}
public static long test(Test test)
{
long start = System.currentTimeMillis();
for (int j = 0; j < INNER_ITERATIONS; j++) test.test();
return System.currentTimeMillis() - start;
}
}
interface Data
{
public void create();
}
interface Test
{
public void test();
}
class Unsync implements Test
{
int count = Integer.MAX_VALUE;
public void test()
{
count /= 2;
}
}
class Sync implements Test
{
int count = Integer.MAX_VALUE;
public void test()
{
synchronized (this) {
count /= 2;
}
}
}
class SyncMeth implements Test
{
int count = Integer.MAX_VALUE;
public void test()
{
doIt();
}
private synchronized void doIt()
{
count/= 2;
}
}
