为什么使用Java线程不会更快？

Question

我有以下程序，用于从字符串向量中删除偶数，当向量大小增长时，可能需要很长时间，因此我想到使用线程，但使用10个线程并不比一个线程更快，我的电脑有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();
  }
}

在我的程序中，你可以尝试“[方法一：使用10个线程]”或“[方法二：只使用一个线程]”，速度上并没有太大的区别，我预计它会快几倍，为什么呢？

- Frank

---

线程具有成本，锁争用的成本非常高。 - Jonas

最初的向量有多大？ - David Weiser

在写作时，您应该遵循所使用语言的约定，不要自行发明。这段代码难以阅读，因为它使用了非常规的大写字母和下划线。 - erickson

我同意@erickson的观点。而且那些一行式的if/for组合让我的眼睛很疼。 - Mark

为什么每个线程都要调用sleep()函数？ - erickson

Answer 1

简单来说，您的所有线程都试图访问一个调用同步方法的单个向量。这些方法上的synchronized修饰符确保在任何给定时间只有一个线程可以执行该对象上的任何方法。因此，并行计算的重要部分涉及等待其他线程。

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

所有这些加起来并没有太大的加速效果。

如果您使用单个ConcurrentHashMap而不是一个单个的Good_Email_Address_Vector对象，它将被分成多个Target_Vector对象，则应该获得显着的加速（使用多个线程）：

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

此外，To_Be_Removed_Email_Address_Vector对象应替换为未同步的List，并且应使用List.sublist(...)创建可以传递给线程的视图。

简而言之，最好放弃当前的代码并重新开始。并且请使用符合Java编码规范的合理标识符名称，并将您的代码包装在第~80行以便人们阅读！

- Stephen C

---

或者 Set<String> set = Collections.setFromMap(new ConcurrentHashMap<String, Boolean>())。 - Peter Lawrey

他们没有更新同一个向量；每个线程都有自己的向量进行修改。 - erickson

@erikson - 但是所有线程都在使用单个向量来查找要删除的地址。 - Stephen C

是的，我的评论适用于您最初的答案，该答案说单个集合由多个线程更新。 - erickson

@erikson - 所以你的评论现在不再相关了。正确吗？ - Stephen C

不，我认为后续的评论使其仍然具有相关性。你的回答不够清晰；听起来你是在暗示Good_Email_Address_Vector应该是一个ConcurrentHashMap。这是正确的吗？ - erickson

Answer 2

向量同步会导致争用

您已将要修改的向量拆分，避免了一些争用。但是多个线程正在访问static Vector To_Be_Removed_Email_Address_Vector，因此仍然存在很多争用（所有Vector方法都是同步的）。

对于共享的只读信息，请使用非同步数据结构，以便线程之间没有争用。在我的机器上，将ArrayList替换为Vector后运行您的测试可以将执行时间减半。

即使没有争用，线程安全的结构也会更慢，因此当只有一个线程可以访问对象时不要使用它们。此外，Vector在Java 5中基本过时。除非必须与无法更改的遗留API进行交互，否则请避免使用它。

选择合适的数据结构

列表数据结构对于此任务的性能不佳。由于电子邮件地址可能是唯一的，因此集合应该是一个适当的替代，并且在大型集合上会更快地执行removeAll()操作。在原始Vector的位置使用HashSet可以将我的（8核）机器上的执行时间从超过5秒降至约3毫秒。其中大约一半的改进是由于使用了正确的数据结构。

并发结构不适合

使用并发数据结构相对较慢，而且不会简化代码，因此我不建议使用它。

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

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

如果您遇到异步添加“坏”电子邮件地址到集合中，并希望“好”列表的读者自动查看这些更新，则并发集合是一个不错的选择。但是，针对当前API的设计，在“好”列表的使用者显式调用阻塞过滤器方法来更新列表时，并发数据结构可能是错误的选择。

- erickson

Answer 3

你的所有线程都在同一向量上工作。你对向量的访问是串行化的（即一次只能有一个线程访问它），因此使用多个线程最多可能会达到相同的速度，但更有可能会慢得多。

当你有独立任务要执行时，多个线程的工作速度要快得多。

在这种情况下，最快的选项很可能是创建一个新列表，其中包含您想保留的所有元素，并用一个线程替换原始列表。这比使用多个线程的并发集合更快。

---

为了比较，以下是你可以使用一个线程完成的操作。由于集合相当小，JVM在仅一次运行中不会预热，因此有多个未打印的虚拟运行。

public static void main(String... args) throws IOException, InterruptedException, ParseException {
    for (int n = -50; n < 5; n++) {
        List<String> allIds = new ArrayList<String>();
        for (int i = 0; i < 1000; i++) allIds.add(String.valueOf(i));

        long start = System.nanoTime();
        List<String> oddIds = new ArrayList<String>();
        for (String id : allIds) {
            if ((id.charAt(id.length()-1) % 2) != 0)
                oddIds.add(id);
        }
        long time = System.nanoTime() - start;
        if (n >= 0)
            System.out.println("Time taken to filter " + allIds.size() + " entries was " + time / 1000 + " micro-seconds");
    }
}

打印

Time taken to filter 1000 entries was 136 micro-seconds
Time taken to filter 1000 entries was 141 micro-seconds
Time taken to filter 1000 entries was 136 micro-seconds
Time taken to filter 1000 entries was 137 micro-seconds
Time taken to filter 1000 entries was 138 micro-seconds

- Peter Lawrey