为什么这个并行算法的运行速度比顺序算法慢？ [英] Why does this parallel algorithm run more slowly than its sequential counterpart?

问题描述

顺序：

void do(List<D> d, final List<C> c) {
for (D datum : d)
    getChampoid(datum, c).tally(datum);

平行：

static final int procs = Runtime.getRuntime().availableProcessors();
static final ExecutorService pool = Executors.newFixedThreadPool(procs);
void do(List<D> d, final List<C> c) {
    List<Future> futures = new ArrayList<>();
    for (final D datum : d)
        futures.add(pool.submit(new Runnable() {

            @Override
            public void run() {
                getChampoid(datum, c).tally(datum);
            }

        }));
    for (Future f : futures)
        try {
            f.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }

我很难过，因为对我来说他们看起来像是做同样的事情，并行版本应该更快，但它要慢一个数量级。有什么想法吗？

I'm stumped because to me they look like they do the exact same thing, the parallel version should just be faster, but it's an order of magnitude slower. Any thoughts?

仅供参考，d和c都是巨大的列表，其中包含数千到数十万件物品。

FYI both d and c are huge lists with somewhere between thousands and hundreds of thousands of items.

推荐答案

并行版本应该更快，

the parallel version should just be faster,

这是一个常见的误解。

但它的速度要慢一个数量级。

but it's an order of magnitude slower.

常见结果

任何想法？

Any thoughts?

使用多个线程会产生一个线程没有的开销。开销可能比实际完成的工作高几个数量级，使得速度慢得多。如果完成的工作量远大于开销，则可以获得非常好的可伸缩性。

Using multiple threads has overhead which one thread doesn't have. The overhead can be orders of magnitude higher than the work actually done, making it much slower. If the work done is much larger than the overhead you can get very good scalability.

例如。说将任务传递给另一个线程需要大约10微秒。如果您的任务需要1微秒，那么开销会降低您的性能。但是，如果任务需要100微秒，您可以看到显着的性能提升并且值得支付开销的价格。

e.g. say it costs about 10 micro-seconds to pass a task to another thread. If your task takes 1 micro-second, the overhead can kill your performance. However, if the task takes 100 micro-seconds, you could see a significant performance improvement and worth paying the price of the overhead.

简而言之，没有什么是免费的esp not not多线程。

In short, nothing is free esp not multiple thread.

这篇关于为什么这个并行算法的运行速度比顺序算法慢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！