为什么使用Java线程的速度要快得多？

Question

我有以下程序从字符串向量中删除偶数,当向量大小变大时,可能需要很长时间,所以我想到了线程,但使用10个线程并不比一个线程快,我的PC有6个内核和12个线程,为什么？

import java.util.*;

public class Test_Threads
{
  static boolean Use_Threads_To_Remove_Duplicates(Vector<String> Good_Email_Address_Vector,Vector<String> To_Be_Removed_Email_Address_Vector)
  {
    boolean Removed_Duplicates=false;
    int Threads_Count=10,Delay=5,Average_Size_For_Each_Thread=Good_Email_Address_Vector.size()/Threads_Count;

    Remove_Duplicate_From_Vector_Thread RDFVT[]=new Remove_Duplicate_From_Vector_Thread[Threads_Count];
    Remove_Duplicate_From_Vector_Thread.To_Be_Removed_Email_Address_Vector=To_Be_Removed_Email_Address_Vector;
    for (int i=0;i<Threads_Count;i++)
    {
      Vector<String> Target_Vector=new Vector<String>();
      if (i<Threads_Count-1) for (int j=i*Average_Size_For_Each_Thread;j<(i+1)*Average_Size_For_Each_Thread;j++) Target_Vector.add(Good_Email_Address_Vector.elementAt(j));
      else for (int j=i*Average_Size_For_Each_Thread;j<Good_Email_Address_Vector.size();j++) Target_Vector.add(Good_Email_Address_Vector.elementAt(j));
      RDFVT[i]=new Remove_Duplicate_From_Vector_Thread(Target_Vector,Delay);
    }

    try { for (int i=0;i<Threads_Count;i++) RDFVT[i].Remover_Thread.join(); }
    catch (Exception e) { e.printStackTrace(); }                                                   // Wait for all threads to finish

    for (int i=0;i<Threads_Count;i++) if (RDFVT[i].Changed) Removed_Duplicates=true;

    if (Removed_Duplicates)                                                                        // Collect results
    {
      Good_Email_Address_Vector.clear();
      for (int i=0;i<Threads_Count;i++) Good_Email_Address_Vector.addAll(RDFVT[i].Target_Vector);
    }

    return Removed_Duplicates;
  }

  public static void out(String message) { System.out.print(message); }
  public static void Out(String message) { System.out.println(message); }

  public static void main(String[] args)
  {
    long start=System.currentTimeMillis();

    Vector<String> Good_Email_Address_Vector=new Vector<String>(),To_Be_Removed_Email_Address_Vector=new Vector<String>();
    for (int i=0;i<1000;i++) Good_Email_Address_Vector.add(i+"");
    Out(Good_Email_Address_Vector.toString());
    for (int i=0;i<1500000;i++) To_Be_Removed_Email_Address_Vector.add(i*2+"");
    Out("=============================");

    Use_Threads_To_Remove_Duplicates(Good_Email_Address_Vector,To_Be_Removed_Email_Address_Vector);  // [ Approach 1 : Use 10 threads ] 
//    Good_Email_Address_Vector.removeAll(To_Be_Removed_Email_Address_Vector);                       // [ Approach 2 : just one thread ]
    Out(Good_Email_Address_Vector.toString());

    long end=System.currentTimeMillis();
    Out("Time taken for execution is " + (end - start));
  }
}

class Remove_Duplicate_From_Vector_Thread
{
  static Vector<String> To_Be_Removed_Email_Address_Vector;
  Vector<String> Target_Vector;
  Thread Remover_Thread;
  boolean Changed=false;

  public Remove_Duplicate_From_Vector_Thread(final Vector<String> Target_Vector,final int Delay)
  {
    this.Target_Vector=Target_Vector;

    Remover_Thread=new Thread(new Runnable()
    {
      public void run()
      {
        try
        {
          Thread.sleep(Delay);
          Changed=Target_Vector.removeAll(To_Be_Removed_Email_Address_Vector);
        }
        catch (InterruptedException e) { e.printStackTrace(); }
        finally { }
      }
    });
    Remover_Thread.start();
  }
}

在我的程序中,您可以尝试"[方法1:使用10个线程]"或"[方法2:只需一个线程]"速度方面没有太大差异,我将它的速度提高了几倍,为什么？

Answer 1

简单的答案是你的线程都试图访问调用synchronized方法的单个向量.synchronized这些方法的修饰符确保在任何给定时间只有一个线程可以执行该对象上的任何方法.因此,计算的并行部分的很大一部分涉及等待其他线程.

另一个问题是,对于O(N)输入列表,您有一个O(N)设置... Target_Vector对象的填充...这是在一个线程中完成的.加上线程创建的开销.

所有这些加起来并没有太大的加速.

如果使用ConcurrentHashMap单个Good_Email_Address_Vector对象而不是单个对象分割成多个Target_Vector对象,则应该获得显着的加速(使用多个线程):

• 删除操作O(1)不是O(n),
• 减少复制,
• 由于更好地处理争用,数据结构提供了更好的多线程性能
• 你不需要跳过篮球来避免ConcurrentModificationException.

此外,该To_Be_Removed_Email_Address_Vector对象应替换为未同步的对象List,并List.sublist(...)应用于创建可传递给线程的视图.

简而言之,您最好丢弃当前的代码并重新开始.并请使用遵循Java编码约定明智的标识符名称,并在包装线代码〜80,让人们可以阅读它!

Answer 2

矢量同步会产生争用

你已经拆分了要修改的向量,这避免了一些争用.但是多个线程正在访问static Vector To_Be_Removed_Email_Address_Vector,因此仍然存在很多争用(所有Vector方法都是同步的).

对共享的只读信息使用不同步的数据结构,以便线程之间不存在争用.在我的机器上,运行测试ArrayList代替Vector将执行时间减半.

即使没有争用,线程安全结构也会变慢,因此当只有一个线程可以访问对象时,不要使用它们.此外,VectorJava 5基本上已经过时了.除非您必须与遗留的API进行互操作,否则请避免使用它.

选择合适的数据结构

列表数据结构将为此任务提供较差的性能.由于电子邮件地址可能是唯一的,因此一组应该是合适的替代品,并且removeAll()在大型集合上会更快.在我的(8芯)机器上使用HashSet原始Vector切割执行时间从5秒到3毫秒左右.大约一半的改进是由于为工作使用正确的数据结构.

并发结构不合适

使用并发并发数据结构相对较慢,并且不会简化代码,因此我不推荐使用它.

使用更新的并发数据结构要比争用a快得多Vector,但这些数据结构的并发开销仍远高于单线程结构.例如,在我的机器上运行原始代码花了超过五秒钟,而一个ConcurrentSkipListSet花了半秒钟,而ConcurrentHashMap花了八分之一秒.但请记住,当每个线程都有自己HashSet的更新时,总时间只有3毫秒.

即使所有线程都在更新单个并发数据结构,分区工作负载所需的代码与用于为Vector原始代码中的每个线程创建单独代码的代码非常相似.从可读性和维护的角度来看,所有这些解决方案都具有同等的复杂性.

如果你的情况是异常地将"坏"电子邮件地址添加到集合中,并且你希望"好"列表的读者能够自动地看到这些更新,那么并发集将是一个不错的选择.但是,根据API的当前设计,"好"列表的使用者明确地调用阻塞过滤器方法来更新列表,并发数据结构可能是错误的选择.