The following program is an example of balance between simplicity (synchronizing the entire method) and concurrency (synchronizing the shortest possible code path). By avoid holding locks during lengthy computation factors = factor(i); it gives chance to other threads to use the idled cores to execute other code blocks such as factors = factor(i); and encodeIntoResponse(resp, factors); in parallel, thus boost performance.
Notice interface Servlet is a mock of javax.servlet.Servlet, the method signature is public void service(StringBuilder req, StringBuilder resp); instead of public void service(ServletRequet req, ServletResponse resp);
Notice the StringBuilder is not threadSafe (Neither do ServletRequest and ServletResponse), however a new thread is created for each request, and for each thread, a new StringBuilder instance is created for req and another new StringBuilder instance is created for resp. Since req and resp didn't share across threads, we don't need to use thread-safe version StringBuffer here.
import java.math.BigInteger;
import java.util.Random;
import java.util.concurrent.CountDownLatch;
interface Servlet {
//mock the javax.servlet.Servlet
public void service(StringBuilder req, StringBuilder resp);
}
class CachedFactorizer implements Servlet {
private BigInteger lastNumber;
private BigInteger[] lastFactors;
private long hits;
private long cacheHits;
public synchronized long getHits() {
return hits;
}
public synchronized double getCacheHitRatio() {
return (double) cacheHits / (double) hits;
}
public void service(StringBuilder req, StringBuilder resp) {
BigInteger i = extractFromRequest(req);
BigInteger[] factors = null;
//synchronized (this) {
++hits;
if (i.equals(lastNumber)) {
++cacheHits;
factors = lastFactors.clone();
}
//}
if (factors == null) {
factors = factor(i);
//synchronized (this) {
lastNumber = i;
lastFactors = factors.clone();
//}
}
encodeIntoResponse(resp, factors);
}
public void service(StringBuilder req, StringBuilder resp) {
BigInteger i = extractFromRequest(req);
BigInteger[] factors = null;
synchronized (this) {
++hits;
if (i.equals(lastNumber)) {
++cacheHits;
factors = lastFactors.clone();
}
}
if (factors == null) {
factors = factor(i);
synchronized (this) {
lastNumber = i;
lastFactors = factors.clone();
}
}
encodeIntoResponse(resp, factors);
}
void encodeIntoResponse(StringBuilder resp, BigInteger[] factors) {
resp.append(factors[0]);
}
BigInteger extractFromRequest(StringBuilder req) {
return new BigInteger(req.toString());
}
BigInteger[] factor(BigInteger i) {
// Doesn't really factor
for(int j = 0; j < 100000000; j++) {}
return new BigInteger[]{i};
}
}
public class CachedFactorizerTest implements Runnable{
private static final int TOTALRUN = 200;
private static final int TOTALTHREAD = 2000;
private static final int DISCARDFIRSTFEW = 20;
private static Random rand = new Random();
private static CountDownLatch latch;
private static CachedFactorizer cachedFactorizer = new CachedFactorizer();
private void setCountDownLatch(CountDownLatch latch) {
this.latch = latch;
}
public static void main(String[] args) throws InterruptedException {
long totalTime = 0;
for (int i = 0; i < TOTALRUN; i++) {
long oneRoundTime = runMultiThread();
if (i >= DISCARDFIRSTFEW) {
totalTime += oneRoundTime;
}
}
System.out.println("average time per run: "
+ (double) totalTime / (double) (TOTALRUN - DISCARDFIRSTFEW)
+ " miliseconds.");
}
private static long runMultiThread()
throws InterruptedException {
long start = System.currentTimeMillis();
CountDownLatch latch = new CountDownLatch(TOTALTHREAD);
CachedFactorizerTest cachedFactorizerTest = new CachedFactorizerTest();
cachedFactorizerTest.setCountDownLatch(latch);
for (long i = 0; i < TOTALTHREAD; i++) {
Thread thread = new Thread(cachedFactorizerTest);
thread.start();
}
latch.await();
return System.currentTimeMillis() - start;
}
@Override
public void run() {
StringBuilder req = new StringBuilder().append(rand.nextInt(20));
StringBuilder resp = new StringBuilder();
//System.out.println(Thread.currentThread().getName() + " req=" + req.toString() + " resp=" + resp.toString());
cachedFactorizer.service(req, resp);
if(!req.toString().contains(resp.toString())) {
System.out.println("multi-threading race condition");
}
/*
System.out.println(Thread.currentThread().getName() + " req=" + req.toString() + " resp=" + resp.toString());
System.out.println(Thread.currentThread().getName() + " CacheHitRatio=" + cachedFactorizer.getCacheHitRatio() + " resp=" + resp.toString());
System.out.println(Thread.currentThread().getName() + " Hits=" + cachedFactorizer.getHits());
*/
latch.countDown();
}
}
concurrency>javac CachedFactorizerTest.java
concurrency>java CachedFactorizerTest
multi-threading race condition
multi-threading race condition
multi-threading race condition
multi-threading race condition
average time per run: 122.93333333333334 miliseconds.
concurrency>javac CachedFactorizerTest.java
concurrency>java CachedFactorizerTest
average time per run: 123.06111111111112 miliseconds.
