Readonly
2004-10-29 22:22
偶是一个热爱学习的好小孩, 顺手去google一把, keyword是:
java "破坏结构"

很不幸, google告诉偶结果只有2页, 而且结果是风马牛不相及......

那么, "破坏结构"是你们自己翻译的吧? 不知道可否教育偶一下对应的英文术语是什么, 偶用英文google看看, 说不定能找到相关的资料来好好学习, 天天向上......

cafebabe
2004-10-29 23:55
写了一段程序,大概意思就是
主线程创建THREAD_COUNT个线程,这些线程等待主线程一声令下,
并发地往一个非同步的HashMap中put一对相同的键值对,主线程
等待这些线程都完成操作后,检查这个HashMap的size,如果size>1
那说明这个HashMap有问题了,否则重复进行以上过程。

我的P4 2.8 700M内存的机器过了大概不到10秒钟出现size=2

当然出现两个相同的键也许算不了什么,但你怎么保证不会出现更
糟糕的情况呢?
你不要说现实中不可能出现这么高的并发,那就没意思了。

import java.util.HashMap;
import java.util.Map;

public class BreakHashMap {

    private static final int THREAD_COUNT = 500;

    private static final BooleanLock startLock = new BooleanLock();

    private static final IntLock endLock = new IntLock();

    public static void main(String[] args) {

        while (true) {
            System.out.print(".");

            final Map map = new HashMap();
            //init locks
            endLock.count = THREAD_COUNT;
            startLock.locked = true;

            //construct THREAD_COUNT threads
            for (int i = 0; i < THREAD_COUNT; i++) {
                new Thread() {
                    public void run() {

                        //wait for main thread to kick off
                        synchronized (startLock) {
                            try {
                                while (startLock.locked) {
                                    startLock.wait();
                                }
                            } catch (InterruptedException ie) {
                                ie.printStackTrace();
                            }
                        }

                        //put the same key value pair
                        map.put("0", "1");

                        synchronized (endLock) {
                            endLock.count--;
                            if (endLock.count == 0) {
                                //notify main thread
                                endLock.notify();
                            }
                        }
                    }
                }.start();
            }

            //kick off
            synchronized (startLock) {
                startLock.locked = false;
                startLock.notifyAll();
            }

            //wait for all other thread to end
            try {
                synchronized (endLock) {
                    while (endLock.count > 0) {
                        endLock.wait();
                    }
                }
            } catch (InterruptedException ie) {
                ie.printStackTrace();
            }

            //check map size
            synchronized (map) {
                if (map.size() > 1) {
                    System.out.println("\nsize: " + map.size());
                    break;
                }
            }

            //failed, continue
        }
    }
}

class BooleanLock {
    boolean locked;
}

class IntLock {
    int count;
}
<p class="indent">

Readonly
2004-10-30 10:24
哇, 好cool的代码呀, 偶刚刚读大一, 是Java的初学者, 原来在Java里面测试多线程并发要写得这样复杂呀.....

闲话少说, 偶尝试着在你的代码
System.out.println("\nsize: " + map.size());
后面小心地加上一句
System.out.println(map.get("0"));
(嗯, 应该没有写错吧??)
就是想看看结果是什么? 难道不是1? 难道会出来一个异型?

偶的机器是amd2500 1G memory, 偶跑了很多次, 结果都是1......
偶上次对于你们所说的"破坏结构"所做的猜想后果一条也没有发生:

------
偶下次用map.get(key)获得的对象是null?
或者获得的对象是一个异型?
还是程序会抛出runtime exception?
甚至导致JVM crash?
------

cache照样work, 地球照样在转, size() changed? hey, who cares?

你们在第一页里面提到闻所未闻的cached object可能被"破坏结构"到底怎么才会发生呢??

cafebabe
2004-10-30 21:37
上面的程序我每次都可以成功使size>1

ok, another program

THREAD_COUNT个线程并发往一个非同步HashMap中分别写
Integer 0...THREAD_COUNT-1
写完后主线程检查是否Integer 0...THREAD_COUNT-1 都存在于这个HashMap中,并打印它的size()及toString()

这个应该很快出现,而且那时你可以看到size虽然==THREAD_COUNT,
但toString中却没有这么多值。

import java.util.HashMap;
import java.util.Map;

public class BreakHashMap4 {

    private static final int THREAD_COUNT = 500;

    private static final BooleanLock startLock = new BooleanLock();

    private static final IntLock endLock = new IntLock();

    public static void main(String[] args) {

        outer: while (true) {
            System.out.print(".");

            //init locks
            endLock.count = THREAD_COUNT;
            startLock.locked = true;

            Map map = new HashMap();
            //construct THREAD_COUNT threads
            for (int i = 0; i < THREAD_COUNT; i++) {
                new MyThread(map, i, startLock, endLock).start();
            }

            //kick off
            synchronized (startLock) {
                startLock.locked = false;
                startLock.notifyAll();
            }

            //wait for all other thread to end
            try {
                synchronized (endLock) {
                    while (endLock.count > 0) {
                        endLock.wait();
                    }
                }
            } catch (InterruptedException ie) {
                ie.printStackTrace();
            }

            //check Integers from 0 to THREAD_COUNT-1 all exist
            synchronized (map) {
                for (int i = 0; i < THREAD_COUNT; i++) {
                    if (map.get(new Integer(i)) == null) {
                        System.out.println(i + " not exists!");
                        System.out.println("size: " + map.size());
                        System.out.println(map);
                        break outer;
                    }
                }
            }
            //failed, continue
        }
    }
}

class MyThread extends Thread {

    private Map map;

    private Integer i;

    private BooleanLock startLock;

    private IntLock endLock;

    public MyThread(Map map, int i, BooleanLock startLock, IntLock endLock) {
        this.map = map;
        this.i = new Integer(i);
        this.startLock = startLock;
        this.endLock = endLock;
    }

    public void run() {

        //wait for main thread to kick off
        synchronized (startLock) {
            try {
                while (startLock.locked) {
                    startLock.wait();
                }
            } catch (InterruptedException ie) {
                ie.printStackTrace();
            }
        }

        map.put(i, "");

        synchronized (endLock) {
            endLock.count--;
            if (endLock.count == 0) {
                //notify main thread
                endLock.notify();
            }
        }
    }
}

class BooleanLock {
    boolean locked;
}

class IntLock {
    int count;
}
<p class="indent">

Readonly
2004-10-30 22:41
嘿, 偶没有说清楚, 还是你没有看清楚?

map.size() 变成了2, 是没错, but, who cares?

偶是建议你在后面加上一句
System.out.println(map.get("0"));
看看你们所说被破坏了结构的cached object是什么?

扔出一堆代码, 还不是证明了gigix最初的观点:
这种cache更本不用同步, 哪怕有并发冲突发生, 也不会对你的cache功能有任何影响.

cafebabe
2004-10-30 22:50
ok,那这一段程序呢?
有些数据没有被put到Map中算不算呢?

难道说:没有就没有嘛,再put一次不就好了!
不过我看其实也无所谓啦,不就是个cache嘛,大不了再到后台取一次得了,反正咱们的应用也不care,用户也看不到啦。

不争了,ok?

Readonly
2004-10-30 23:08
不争了? 累了?

证明了2点,
1. 破坏结构纯属虚构
2. 并发会影响hashmap cache的功能也纯属虚构

嗯, 这个好像gigix在第一页里面就讲过了......

OK, gigix唯一错误就是, cache应该是这样写的, 才是unbreakable:

private Map _tempCache;

public Long getTemperature(String city) {
Long result = (Long) _tempCache.get(city);
if(result == null){
result = calcTemperature(city);
_tempCache.put(city, result);
}
return result;
}

cafebabe
2004-10-31 09:01
那我就再争一争吧,我也是够无聊的:)
我们这些小人物也争不出啥结果来,还是请个权威来说两句吧。
昨天写了封email给Doug Lea,Doug Lea何许人也?不知道的就google一下吧。
其实这个问题本不该麻烦人家的。
如果你还是不信,那你就直接去请教java collection framework的作者
Joshua Bloch吧。

到此为止了!

hi,
I sorry for interrupting you, but I know that you are the authority in concurrent programming, and I have read your book <Concurrent Programming in Java>, it's a wonderful book. So I write this email to you and hope you can give me a hand.

Some one write the following program, he use HashMap to cache some values, I think because HashMap is not thread safe, so this program is not robust, concurrent putting may destroy the inner data structure of HashMap, and because of the memory model of java, the
reader threads may not see the lastest modification of other threads.

Am I right? People who write this program does not think so.
So I hope you can give us an authority answer.
Thanks in advance.

import java.util.HashMap;
import java.util.Map;
public class TemperatureService {
    private Map _tempCache = new HashMap();
    public Long getTemperature(String city) {
        Long result = (Long) _tempCache.get(city);
        if (result == null) {
            result = calcTemperature(city);
            _tempCache.put(city, result);
        }
        return result;
    }
    private Long calcTemperature(String city) {
        Long temp = null;
        //...calc temperature
        return temp;
    }
}

Best Regards
Cafebabe

发件人: "Doug Lea" <dl@cs.oswego.edu>  添加到地址簿 
日期: Sat, 30 Oct 2004 18:42:12 -0400 
收件人: <cafebabe2004@yahoo.com.cn> 
主题: Re: Would you please help me? Many thanks. 

    
>  
> Some one write the following program, he use HashMap to cache some 
values,

You are correct that this is not thread-safe. If this cache can
be accrssed by mulitple threads, you should use a thread-safe
Map such as the new java.util.concurrent.ConcurrentHashMap (or,
just java.util.Hashtable)

-Doug
<p class="indent">

newjoy
2004-10-31 09:44
gigix,看了你的主贴,你提到如果采用:

public static synchronized MyClass getInstance() {  ...}

采取保守的同步策略(将整个getInstance()方法同步),多个线程需要获得Singleton实例时就必须在getInstance()方法上排队等待。这就是传说中的“Singleton模式的性能问题”。而只有采用lazy initialization策略时才有性能问题。
<p class="indent">


当lazy initialization结束后,getInstance() 所要做的唯一的事只是返回一个对象的引用,这种性能问题在真实应用中
是否可以忽略不计?若产生性能问题,究竟到底在什么情况下才会发生。



banq
2004-10-31 18:36
大家都挺认真的,gigix的主贴我还是看得不够明白,可能我这人喜欢看平静理性的陈述,当然,有时我的言论让别人无法平静理性,这是我应该纠正的问题。

这件事情都震动了Dou Lee,真是不好意思,这个现象让更明白,有些事情好像确实争论不出结果来的。cafebabe 真是辛苦了。其实,HashMap不是线程安全是常识。

从newjoy 看出,好像说Singleton创建时有些性能误用区,这个只是小小的陷井,其实我觉得讨论方向有些问题。

那么,Singleton模式,究竟在怎样的情况下才有性能陷阱?
这个帖子说的案例才是有陷井的可能性:

http://www.jdon.com/jive/thread.jsp?forum=121&thread=16742

当多线程争用同一个共享资源对象时,才可能出现性能陷井,例如线程互锁。当然,你可以认为这不是Singleton的错,但是在多线程共享一个对象情况下,如果你对Singleton没有陷井认识,而且喜欢简单的话,总是会将这个对象做成Singleton(可以有其他做法),那么问题就来了。

具体案例代码我以后再碰到,会贴在这里。
Jdon讨论对事不对人,倡导理性讨论。

newjoy
2004-11-01 15:25
那现在应该基本观念达成一致了。我不知道我的理解是否正确:

1、Singleton 并不真正产生性能问题,只是需要注意使用Singleton 的时机,不要滥用。

2、只有当多线程争用同一个共享资源对象时,若要解决同步问题,才会产生性能问题,但这不是Singleton 对象的问题,任意对象都可能碰到。

BTW:
个人认为 Doug Lea 的邮件并没有帮助cafebabe 证明什么。他只是告诉你HashMap不是线程安全的。



Azure_2003
2004-11-01 20:08
同意

newjoy
2004-11-01 21:25
但是我的问题好像还是没有解决,
因为我并不认为当lazy initialization结束后,
getInstance() 由于使用了“synchronized”就影响了整体的性能,这在真实应用中是否可以忽略不计?

gigix指出的“若需要经常地获取Singleton实例,则Singleton模式中用于获取实例的方法有可能成为性能瓶颈;”,我觉得应该更夸张描述为“需要高频度并发的获取Singleton实例,则Singleton模式中用于获取实例的方法有可能成为性能瓶颈”,但这种情况在我们的实际应用中真的存在么?若真的存在,我们是否有别的办法可以解决?

具体何时该用Eager Initialization,何时该用lazy initialization应该看实际的应用需求进行评估。不存在好与不好之分,也没有统一的标准。

所以我同意gigix的观点,今后请不要一提Singleton就联想到性能有问题。它两之间没有必然联系。
synchronized产生的性能问题,是每一个涉及多线程操作的所有对象同样要面对的问题,而非Singleton一个。

看看 Hashtable 不也使用了大量的synchronized:

public synchronized Object get(Object key) {
	Entry tab[] = table;
	int hash = key.hashCode();
	int index = (hash & 0x7FFFFFFF) % tab.length;
	for (Entry e = tab[index] ; e != null ; e = e.next) {
	    if ((e.hash == hash) && e.key.equals(key)) {
		return e.value;
	    }
	}
	return null;
    }
<p class="indent">

banq
2004-11-02 10:04
to newjoy, lazy initalization在实际中可以不用,因此回避这个问题,主要带来的不只是一点性能问题,而是可能变成非单态。

“Singleton 并不真正产生性能问题,只是需要注意使用Singleton 的时机,不要滥用。”

是这样,这个问题就象以前ClassLoader问题一样,ClassLoader本身不复杂,甚至程序员名人都对其字节码分析过(个人觉得这是一种典型的向下思维,我推荐搞应用的要有向上思维,注重技术的应用场景,这也是设计模式的要点),其实ClassLoader复杂问题是在其应用场景,如Weblogic/Jboss的EJB、WEB和Ear打包处理中。

所以我说Singletong应用有性能陷井,也是指其应用场景,用的时候要小心,不是一点陷井没有,是有的。

其实,想起一个技术,就要立即想起它的应用场景,这才表面你已经有经验灵活运用它,(不同意:今后请不要一提Singleton就联想到性能有问题。它两之间没有必然联系。)因为任何技术都是有应用前提的。

“synchronized产生的性能问题,是每一个涉及多线程操作的所有对象同样要面对的问题,而非Singleton一个”
这个问题如果有我前面向上思维,那么就很容易注意到。并只有多线程操作同一个共享对象(读取没有问题,是写修改的情况)就会发生,一般如何做一个共享对象:无外乎将那个共享对象作为参数传进来,这是Jive源码中ForumFactory作为参数传来传去的原因;一般这种做法很麻烦,谁喜欢一个东西一直在所有方法参数中出现呢?那么简捷的方式就是使用Singleton。

最后,还是用外国人的说话有说服力,picocontainer的一篇文章:

http://www.picocontainer.org/Singleton+antipattern
picocontainer作者宣称Singleton其实是反模式,不能算模式!



newjoy
2004-11-02 16:42
那我想原先gigix提的:
“请不要简单地说一句“Singleton模式有性能问题”了事。”的观点咱们应该同意吧?

随口就说出一句“Singleton模式在多线程环境下存在性能问题。”咱们应该反对吧?

BANQ也指出“想起一个技术,就要立即想起它的应用场景”。那我们也应该针对具体的应用场景去评价使用一个技术的优劣,而不是在任意情况下简单总结一句话。

“所以我说Singletong应用有性能陷井,也是指其应用场景,用的时候要小心,不是一点陷井没有,是有的。”
这句话一点没错,但我一样也可以说:

“所以我也说 CopyOnWriteArrayList 应用有性能陷井,也是指其应用场景,用的时候要小心,不是一点陷井没有,是有的。”
“所以我也说 Hashtable 应用有性能陷井,也是指其应用场景,用的时候要小心,不是一点陷井没有,是有的。”

我只是一直想不通为啥会有人对Singleton有歧视,偏偏要针对Singleton?

说老实话,自从出现了Spring,我们已经很少自己去实现Singleton了。
您说的“谁喜欢一个东西一直在所有方法参数中出现呢”,Spring 倒是一个很好的解决方式对不?当时是注入方式,而非频繁的getBean("xxx")