Регаординация программы на параллельном HashMap

Question

В интервью собеседник спросил о параллельной Hash-карте и ее функциональности, о которой я подробно объяснил. Он сказал, что в случае одновременной операции обновления HashMap ConcurrentHashMap блокирует только часть Карты вместо всей Карты.

Поэтому он сказал мне написать простую программу, которая доказывает, что во время операции обновления ConcurrentHashMap блокирует только часть Карты, а не целую Карту. Я не мог этого сделать, поэтому, пожалуйста, сообщите мне, как этого добиться.

Answer 1

Интервьюер был, возможно, ожидая простой ответ, например:

• если вся карта синхронизирована GET/поместить операции, добавляя темы, не улучшит пропускную способность, потому что узкое место будут синхронизированные блоки. Вы можете написать кусок кода с synchronizedMap, который показывает, что добавление темы не поможет
• потому что карта использует несколько замков, и если у вас есть более одного ядра на вашей машине, добавив тему улучшит пропускную

в приведенном ниже примере выводит следующее:

Синхронных один поток: 30
синхронизированных нескольких потоков: 96
Параллельных один поток: 219
Параллельного MUL автовоз нить: 142

Таким образом, вы можете увидеть, что синхронизированная версия более чем в 3 раза медленнее при высокой конкуренции (16 нитей), тогда как параллельная версия почти в два раза быстрее с несколькими потоками, как с одной нитью.

Также интересно отметить, что ConcurrentMap имеет незначительные накладные расходы в однопоточной ситуации.

Это очень надуманный пример со всеми возможными проблемами из-за микро-бенчмаркинга (первые результаты должны быть отброшены в любом случае). Но это дает намек на то, что происходит.

public class Test1 { 
    static final int SIZE = 1000000; 
    static final int THREADS = 16; 
    static final ExecutorService executor = Executors.newFixedThreadPool(THREADS); 

    public static void main(String[] args) throws Exception{ 

     for (int i = 0; i < 10; i++) { 
      System.out.println("Concurrent one thread"); 
      addSingleThread(new ConcurrentHashMap<Integer, Integer>()); 
      System.out.println("Concurrent multiple threads"); 
      addMultipleThreads(new ConcurrentHashMap<Integer, Integer>()); 
      System.out.println("Synchronized one thread"); 
      addSingleThread(Collections.synchronizedMap(new HashMap<Integer, Integer>())); 
      System.out.println("Synchronized multiple threads"); 
      addMultipleThreads(Collections.synchronizedMap(new HashMap<Integer, Integer>())); 
     } 
     executor.shutdown(); 
    } 

    private static void addSingleThread(Map<Integer, Integer> map) { 
     long start = System.nanoTime(); 
     for (int i = 0; i < SIZE; i++) { 
      map.put(i, i); 
     } 
     System.out.println(map.size()); //use the result 
     long end = System.nanoTime(); 
     System.out.println("time with single thread: " + (end - start)/1000000); 
    } 

    private static void addMultipleThreads(final Map<Integer, Integer> map) throws Exception { 
     List<Runnable> runnables = new ArrayList<>(); 
     for (int i = 0; i < THREADS; i++) { 
      final int start = i; 
      runnables.add(new Runnable() { 

       @Override 
       public void run() { 
        //Trying to have one runnable by bucket 
        for (int j = start; j < SIZE; j += THREADS) { 
         map.put(j, j); 
        } 
       } 
      }); 
     } 
     List<Future> futures = new ArrayList<>(); 
     long start = System.nanoTime(); 
     for (Runnable r : runnables) { 
      futures.add(executor.submit(r)); 
     } 
     for (Future f : futures) { 
      f.get(); 
     } 
     System.out.println(map.size()); //use the result 
     long end = System.nanoTime(); 
     System.out.println("time with multiple threads: " + (end - start)/1000000); 
    } 
}