论坛首页 Java企业应用论坛

淘宝面试题:如何充分利用多核CPU,计算很大的List中所有整数的和

浏览 94737 次
该帖已经被评为良好帖
作者 正文
   发表时间:2010-07-13  
mercyblitz 写道
pengpeng99bill 写道
这还是 多线程的问题 啊 还是没有解决多CPU处理的问,你的多线程怎么能保证是多个CPU在处理呢 ,可能还是一个CPU在处理啊 。以前看到过报道好像说是 java7 支持多CPU处理任务。 等待中。。。



可能,你误会了。Java 1.2之后,使用的操作系统内核线程,操作系统还是会利用多CPU的,也就是说和Java无关了。
我的《Java内存模型》正在写,其中起到了这些东西,如果有需要的话,可以关注一下。


回帖里有好多说多CPU的,我不清楚说的是多个CPU,还是一个CPU多个核理解成多CPU了,我的题目是多核CPU,是一个CPU多个核,不知道是不是你们所理解的多CPU。

就像上面说的,操作系统内核线程由操作系统负责调配的,会充分的利用多核,CPU自己也会控制。
0 请登录后投票
   发表时间:2010-07-13  
搞个map-reduce就好了
0 请登录后投票
   发表时间:2010-07-13  
beneo 写道
hardPass 写道
package com.wl.test.concurrent.semaphore;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicLong;

/**
*
* 乍一看到题目“充分利用多核CPU”,
* 以为会根据CPU的核心数,计算出比较合理的任务线程的数目。
* 就题目的计算目标来说,实际上讲的主线程等待任务线程完成,
* 任务线程之间没有必要互相等待。
* 是不是可以考虑用信号来......
* 每次来看帖,都发现大家图画的很拉风……
*
* 我也帖个代码,虽然来晚了,大家不一定能看到……
*
* @author HardPass
......


java不是有Semaphore,为啥你非要自己写个lock


1、我的SemaphoreLock比较简单,从原理上大家一看就明白,我们注重讨论原理吗
2、咱SemaphoreLock和java.util.concurrent下的还是有点区别的
3、我不太会用那个Semaphore
0 请登录后投票
   发表时间:2010-07-13  
viei 写道
dilantaya 写道
viei 写道
个人觉的你的这些算法啊,线程操作可能都是白忙活,或者说对这种问题处理的很浅,还不深入。算法挺简单的实现起来也有很多办法,多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点,要是用多cpu充分发挥多cpu的优势,首先要把任务分发,你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行,只有可能时间片切的更小,在执行这些任务。
所以这个过程中考虑的重点应该是
1:操作系统(开多个jvm,规定每个jvm进程运行在指定cpu上,肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好)
2:jvm调整(大数据量必然涉及到垃圾回收)
3:程序编写
上面这些弄好了,再深入一点就考虑,同步消耗问题
cpu多了,同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。




怎么指定一个jvm对应单个cpu ,高手?



在linux下你看一下cpuinfo获取cpu信息,编号
然后启动的时候和运行的时候都可以通过taskset命令进行cpu绑定
如果开多进程处理,那么进程间数据如何共享,这个还要重新考虑
你现在的程序都是单进程下的


Hey, All:

首先viei同学的回答很深入, 我想这完全是按照大规模数据并行处理的理念来回答的. 正如上面有同学也提到 Map/Reduce的思想, 是的, 上面程序是单进程独力在一台机子上运行. (但对于这样的面试题目,个人觉得足矣.

其次, 只想补充一点, 大伙都在关注算法的优化, 但忽略了一点, 就是任务的控制. 这实际上在Concurrent中是很重要的一点. 原因是, java中我们不可能去控制时间片, 以及比线程更小级别的单元.  上述代码中, 按楼主最开始的实现, 确实有可能存在CPU切片分配不均的情况.

俺觉得需要两个闭锁, 一个“开始阀门”, 另一个是“结束阀门”.
原因是如果我们简单地创建并启动线程, 那么先启动的就比后启动的具有“领先优势”, 并且根据活动线程数量增加减少, 竞争度也在不断改变. 所以使用“开始阀门”让控制线程能够同时释放所有工作者线程.

0 请登录后投票
   发表时间:2010-07-13  
kakaluyi 写道
amigo 写道
dilantaya 写道
sunwenran 写道
赞一个。

问题是我用你的例子比较直接加
        long noCurrentSum=0L;  
        for(Integer i:list){  
            noCurrentSum+=i;  
        } 
发现时间差不多。而且有时候直接加更快。纠结了。。我的是双核。


可能是你给的数据量还不够大


调整到50000000
for (int i = 1; i <= 50000000; i++) {
list.add(i);
}


单线程时间比并发更快

呵呵其实这种纯粹的算术相加速度单线程和多线程是一样的(因为没有io读写,没有网络等待等等,),新建线程还要消耗资源,如何设计利用多核cpu就涉及到jvm的底层实现了,所以要我回答这个问题,我给出下面答案:
int sum=0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
}
return sum;


这个就是常规的求值啊
0 请登录后投票
   发表时间:2010-07-13  
viei 写道
个人觉的你的这些算法啊,线程操作可能都是白忙活,或者说对这种问题处理的很浅,还不深入。算法挺简单的实现起来也有很多办法,多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点,要是用多cpu充分发挥多cpu的优势,首先要把任务分发,你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行,只有可能时间片切的更小,在执行这些任务。
所以这个过程中考虑的重点应该是
1:操作系统(开多个jvm,规定每个jvm进程运行在指定cpu上,肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好)
2:jvm调整(大数据量必然涉及到垃圾回收)
3:程序编写
上面这些弄好了,再深入一点就考虑,同步消耗问题
cpu多了,同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。


你的说法容易误人子弟。

Java1.2之后,Java多线程依赖于操作系统的内核线程调度。操作系统会不会发挥多处理的优势呢?肯定会啊,操作系统作为基础设施,实时性是它最重视之一。
针对于你的观点,我进行反驳:
1.在进程之间,多个JVM的Heap不能相互共享。更谈不上制定那个CPU制定JVM进行,要知道主存是共享的,CPU的处理数据的。多核CPU不是多台机器,那个CPU负责,是由OS调度,用户进程没有办法控制内核进程。

2.List#sublist方法实现,当大List分离出多个小List,小List并没有放弃大的List,而是还是引用的大List。在计算之中,不会被GC掉。之后被GC掉,对计算没有影响。调整JVM需要是对的,但是调整是Java Heap的大小,而不是为了GC。如果要说GC的话,计算中虽然不会被GC,但是GC会停顿(Pause/Stop World操作),丧失了实时性。


0 请登录后投票
   发表时间:2010-07-13  
melody3 写道
kakaluyi 写道
amigo 写道
dilantaya 写道
sunwenran 写道
赞一个。

问题是我用你的例子比较直接加
        long noCurrentSum=0L;  
        for(Integer i:list){  
            noCurrentSum+=i;  
        } 
发现时间差不多。而且有时候直接加更快。纠结了。。我的是双核。


可能是你给的数据量还不够大


调整到50000000
for (int i = 1; i <= 50000000; i++) {
list.add(i);
}


单线程时间比并发更快

呵呵其实这种纯粹的算术相加速度单线程和多线程是一样的(因为没有io读写,没有网络等待等等,),新建线程还要消耗资源,如何设计利用多核cpu就涉及到jvm的底层实现了,所以要我回答这个问题,我给出下面答案:
int sum=0;
for(int i=0;i<list.size();i++)
{
sum+=list.get(i);
}
return sum;


这个就是常规的求值啊


同问
0 请登录后投票
   发表时间:2010-07-13  
mercyblitz 写道
viei 写道
个人觉的你的这些算法啊,线程操作可能都是白忙活,或者说对这种问题处理的很浅,还不深入。算法挺简单的实现起来也有很多办法,多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点,要是用多cpu充分发挥多cpu的优势,首先要把任务分发,你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行,只有可能时间片切的更小,在执行这些任务。
所以这个过程中考虑的重点应该是
1:操作系统(开多个jvm,规定每个jvm进程运行在指定cpu上,肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好)
2:jvm调整(大数据量必然涉及到垃圾回收)
3:程序编写
上面这些弄好了,再深入一点就考虑,同步消耗问题
cpu多了,同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。


你的说法容易误人子弟。

Java1.2之后,Java多线程依赖于操作系统的内核线程调度。操作系统会不会发挥多处理的优势呢?肯定会啊,操作系统作为基础设施,实时性是它最重视之一。
针对于你的观点,我进行反驳:
1.在进程之间,多个JVM的Heap不能相互共享。更谈不上制定那个CPU制定JVM进行,要知道主存是共享的,CPU的处理数据的。多核CPU不是多台机器,那个CPU负责,是由OS调度,用户进程没有办法控制内核进程。

2.List#sublist方法实现,当大List分离出多个小List,小List并没有放弃大的List,而是还是引用的大List。在计算之中,不会被GC掉。之后被GC掉,对计算没有影响。调整JVM需要是对的,但是调整是Java Heap的大小,而不是为了GC。如果要说GC的话,计算中虽然不会被GC,但是GC会停顿(Pause/Stop World操作),丧失了实时性。




那这个程序跑在windows和linux上会因为操作系统内核的调度不同,执行效率也不同了?
0 请登录后投票
   发表时间:2010-07-13  
david.org 写道
viei 写道
dilantaya 写道
viei 写道
个人觉的你的这些算法啊,线程操作可能都是白忙活,或者说对这种问题处理的很浅,还不深入。算法挺简单的实现起来也有很多办法,多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点,要是用多cpu充分发挥多cpu的优势,首先要把任务分发,你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行,只有可能时间片切的更小,在执行这些任务。
所以这个过程中考虑的重点应该是
1:操作系统(开多个jvm,规定每个jvm进程运行在指定cpu上,肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好)
2:jvm调整(大数据量必然涉及到垃圾回收)
3:程序编写
上面这些弄好了,再深入一点就考虑,同步消耗问题
cpu多了,同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。




怎么指定一个jvm对应单个cpu ,高手?



在linux下你看一下cpuinfo获取cpu信息,编号
然后启动的时候和运行的时候都可以通过taskset命令进行cpu绑定
如果开多进程处理,那么进程间数据如何共享,这个还要重新考虑
你现在的程序都是单进程下的


Hey, All:

首先viei同学的回答很深入, 我想这完全是按照大规模数据并行处理的理念来回答的. 正如上面有同学也提到 Map/Reduce的思想, 是的, 上面程序是单进程独力在一台机子上运行. (但对于这样的面试题目,个人觉得足矣.

其次, 只想补充一点, 大伙都在关注算法的优化, 但忽略了一点, 就是任务的控制. 这实际上在Concurrent中是很重要的一点. 原因是, java中我们不可能去控制时间片, 以及比线程更小级别的单元.  上述代码中, 按楼主最开始的实现, 确实有可能存在CPU切片分配不均的情况.

俺觉得需要两个闭锁, 一个“开始阀门”, 另一个是“结束阀门”.
原因是如果我们简单地创建并启动线程, 那么先启动的就比后启动的具有“领先优势”, 并且根据活动线程数量增加减少, 竞争度也在不断改变. 所以使用“开始阀门”让控制线程能够同时释放所有工作者线程.


同意。前面我也说了,这就是很深入的东西了,起码我的机器实现不了。再深入也可以从用分布式,不过这就不是我所能说的啦。。呵呵。。
0 请登录后投票
   发表时间:2010-07-13  
mercyblitz 写道
viei 写道
个人觉的你的这些算法啊,线程操作可能都是白忙活,或者说对这种问题处理的很浅,还不深入。算法挺简单的实现起来也有很多办法,多线程调度什么的也都是基本java知识。
我个人觉的的你要抓住问题的重点,要是用多cpu充分发挥多cpu的优势,首先要把任务分发,你只是起多个线程并不一定操作jvm和操作系统就会把任务分发到多cpu上执行,只有可能时间片切的更小,在执行这些任务。
所以这个过程中考虑的重点应该是
1:操作系统(开多个jvm,规定每个jvm进程运行在指定cpu上,肯定比一个进程下的多个线程只占用一个cpu对多cpu的压榨更好)
2:jvm调整(大数据量必然涉及到垃圾回收)
3:程序编写
上面这些弄好了,再深入一点就考虑,同步消耗问题
cpu多了,同步因素也是决定是否能把多cpu和性能转化率提高出来的一个重要环节。


你的说法容易误人子弟。

Java1.2之后,Java多线程依赖于操作系统的内核线程调度。操作系统会不会发挥多处理的优势呢?肯定会啊,操作系统作为基础设施,实时性是它最重视之一。
针对于你的观点,我进行反驳:
1.在进程之间,多个JVM的Heap不能相互共享。更谈不上制定那个CPU制定JVM进行,要知道主存是共享的,CPU的处理数据的。多核CPU不是多台机器,那个CPU负责,是由OS调度,用户进程没有办法控制内核进程。

2.List#sublist方法实现,当大List分离出多个小List,小List并没有放弃大的List,而是还是引用的大List。在计算之中,不会被GC掉。之后被GC掉,对计算没有影响。调整JVM需要是对的,但是调整是Java Heap的大小,而不是为了GC。如果要说GC的话,计算中虽然不会被GC,但是GC会停顿(Pause/Stop World操作),丧失了实时性。




两位说的都很有道理。
viei同学的观点是偏向于大规模数据, 高性能并行处理的需求. 可能用在这个算法题上不是太适合, 但关于JVM的调整确实是高性能程序需要注意的.

mercyblitz同学说的也很有道理, 可能viei的意思是把任务分割, 这个任务是通过独力于另外进程,或节点来提交的。之间可能会通过消息机制的方式来建立的.
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics