Многопоточность: в какую сторону думать

    Змей-горыныч от Sun
    Не так давно я по некоторому стечению обстоятельств принял участие в своеобразном соревновании, которое довольно быстро превратилось в исследование. Это исследование дало результаты, которые будут интересны читателям блогов Java и Алгоритмы в равной степени. По невозможности разместить сразу в двух местах, этот пост я решил разбить на две части. Как вам наверняка подсказывает Капитан, эта часть расскажет о результатах, касающихся Java.
    Кстати, из исследовательской команды не только я зарегестрирован на Хабре: если хотите выразить благодарность, то не забывайте о markiz и icekeeper.

    А о чём вообще речь?

    Речь пойдёт о том, что нужно держать в голове, распараллеливая некоторые вычисления или задачи. Я рассмотрю несколько вариантов реализации подобных вычислений и объясню, почему то или иное решение эффективнее. Итак, поехали.

    Ой, да ну эти ваши потоки!

    Начнём с самого простого: У нас есть компьютер с одним ядром, на котором требуется выпонять много задач. Создадим некий класс Task, у которого будет метод work, выполняющий некоторые действия в зависимости от идентификатора поданной задачи; а также некий класс, который будет выполнять много задач:
    public class Archiver {
        public static long count = 0;
        class Task {
            //...
            void work(String taskId) {
                count += something(taskId);
                count += somethingElse(taskId);
                count += commit(taskId);
            }
        }
        public static void main(String[] args) {
            for(String id : args)
                new Task().work(id);
            System.out.println(Task.count);
        }
    }


    До поры-до времени всё было прекрасно, но вот наш сервер проапгрейдили, и теперь у нас настоящий двухъядерный процессор! Разумеется, теперь нужно исправить этот код и заставить его работать в несколько потоков.

    Don't over-synchronize, young padawan

    Немного подумав, мы ринулись исполнять желаемое и написали вот такой вот код:
    public class Archiver {
        public static long count = 0;
        class Task implements Runnable {
            //...
            public void run() {
                timeout = 0;
                while(timeout < 10) {
                    if(haveMoreTasks()) {
                        taskId = getTask();
                        count += something(taskId);
                        count += somethingElse(taskId);
                        count += commit(taskId);
                    } else {
                        Thread.sleep(10);
                        timeout ++;
                    }
                }
            }
        }
     
        private static LinkedList<String> tasks;
     
        synchronized public static String getTask() {
            return tasks.pollLast();
        }
     
        synchronized public static boolean haveMoreTasks() {
            return tasks.size() > 0;
        }
     
        synchronized public static void addTask(String taskId) {
            tasks.add(task);
        }
     
        public static void main(String[] args) {
            for(String id : args)
                addTask(id);
            int threadNum = Runtime.getRuntime().availableProcessors();
     
            for (int i = 0; i < threadNum; i++) 
                (threads[i] = new Thread(new Task())).start();
     
            boolean finished = false;
            while (!finished) {
                finished = true;
                for (int i = 0; i < threadNum; i++)
                    finished &= !threads[i].isAlive();
                try {
                    Thread.sleep(10);
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            System.out.println(count);
        }
    }


    К нашему великому сожалению, у такого кода есть несколько недостатков. Во-первых, он может работать неверно:
    1. long — не атомарный тип. Нужно использовать AtomicLong;<Также доступ к count можно синхронизовать, причём таким вот образом:
      long delta = something(taskId);
      delta += somethingElse(taskId);
      delta += commit(taskId);
      synchronized(count) {
          count. += delta;
      }
      Выносить вычисление результата из синхронизованного блока следует потому, что оно может производится очень долго, блокируя тем самым работу других потоков;
    2. Пусть в очереди один элемент, и оба потока одновременно закончили свою работу. Тогда один из них получит true в ответ на haveMoreTasks(), затем второй получит тот же ответ, после чего первый заберёт значение, а второй обломается и швырнёт исключение.


    Но эти ошибки не так значительны, как ещё одна: если задач много, а выполняются они не так долго, то это будет работать дольше, чем однопоточный вариант. Почему? Ответ прост, но мы дойдём до него только написав решение так, как надо.

    Как сделать правильно

    К счастью, в Java есть множество средств для распараллеливания данных. В том числе — ExecutorService. Приведённый ниже код работает гораздо быстрее, чем все остальные придуманные варианты:
    public class Archiver implements Runnable {
        public static AtomicLong count = AtomicLong(0);
        public static String[] tasks;
        class Task implements Runnable {
            Task(String taskId) {
                this.taskId = taskId;
            }
            //...
            public void run() {
                long delta = something(taskId);
                delta += somethingElse(taskId);
                delta += commit(taskId);
                synchronized(count) {
                    count.addAndGet(delta);
                }
            }
        }
     
        public void run() {
            int processors = Runtime.getRuntime().availableProcessors();
            ExecutorService pool = Executors.newFixedThreadPool(processors);
            for(String id : tasks)
                pool.execute(new Task(id));
            pool.shutdown();
            try{
                if(!pool.awaitTermination(20, TimeUnit.MINUTES))
                    throw new InterruptedException("Time Limit Exceeded");
            } catch(InterruptedException e) {
                e.printStackTrace();
                pool.shutdownNow();
                System.exit(1);
            }
            System.out.println(count);
        }
     
        public static void main(String[] args) {
            tasks = args;
            new Thread(new Archiver()).start();
        }
    }


    Если заглянуть в исходники, то можно обнаружить лишь одно действительно серьёзное идеологическое различие: тут есть некоторая сущность, которая сама раздаёт задачи освободившимся потокам. Выигрыш во времени — только за счёт меньшей синхронизации.

    Синхронизация — это медленно. Её нужно обязательно минимизировать!


    Послесловие

    В Java есть много прекрасных встроенных средств для выполнения тех или иных задач, но люди продолжают изобретать велосипеды. В этой статье было показано, что это не только малоэффективно, но порой приводит к дополнительным трудноустранимым ошибкам. Тем, кто не слышал до этого про ExecutorService и всё прочее очень советую почитать прекрасную книгу Effective Java (2nd Edition) автора Joshua Blosh, в особенности — её десятую главу.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 29

      0
      А я бы посоветовал читать практиков: Implementation and Evaluation of Moderate Parallelism
      in the BIND9 DNS Server
        0
        Мне кажется, что байнд и приложения на Яве несколько отличаются по своим задачам и методикам воплощения задач. Что общего в данном аспекте между Явой и байндом судить не берусь. Книга Java Threads издательства O'Reilly когда-то помогла мне составить некоторое представление о мультипоточности в Яве. Если неохота покупать книги, можно почитать краткое описание от Sun. Часто начинающие программисты на Яве пишут свои модули по управлению распределением задач. Как правило, позже они все-таки переходят на использование вложенных средств.

        С уважением, S.
          0
          На Яве не пишут dns серверов? bind9 в своё время был отличным пособием для тех кому во сне почудилось о том что если они сейчас всё перепишут под «ExecutorService'ы», то заработает быстрее, а не наоборот.
          И не вижу ничего плохого в том что люди начинают писать свои велосипеды в жава. Одни только ScheduledExecutor'ы чего стоят, которые частенько используют для реализации таймеров: O(log n) — добавление, O(n) — удаление.
          +4
          для практиков (и не только) есть Java Concurrency in Practice, ставшее уже почти классикой
            0
            после этих классических трудов приходиться сталкиваться с людьми, которые путают concurrency и parallelism. Для изучения concurrency лучше посылать куда-нибудь в plan9 :)
          +9
          1. По AtomicLong не нужно синхронизироваться. На то он и атомик
          2. Какое отношение количество процессоров имеет к количеству рабочих потоков? Для двух потоков вам и десятой части процессора хватит
            0
            2. Наверное, то отношение, что в общем случае количество одновременно выполняемых потоков не превышает количество процессоров?
              0
              1. Воистину. Думал о другом. Исправил)
              2. Смотря что за процессор и как у него с HyperThreading'ом. Например, на одной из одноядерных машин, на которой проводили тесты, два потока работали дико медленно.
              +2
              Синхронизация при помощи ReentrantLock, если она происходит без проблем (потоки не столкнулись) — почти бесплатна.

              Фактически, на lock/unlock там изменяется одна int-переменная.

              Но если один Lock решили поменять две нитки одновременно — тогда проблемы, да — парковка нитки и прочие накладные расходы.
              • НЛО прилетело и опубликовало эту надпись здесь
                • НЛО прилетело и опубликовало эту надпись здесь
                    –1
                    С точки зрения jvm нет разницы, сколько ядер у вашего процессора
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        Что именно тут «трава»?
                        • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            А может это стринг? :)
                            • НЛО прилетело и опубликовало эту надпись здесь
                      • НЛО прилетело и опубликовало эту надпись здесь
                          –5
                          Не каждый поток постоянно дёргает очередь(синхронизованная операция), а потокам исполнитель раздаёт задания.
                          • НЛО прилетело и опубликовало эту надпись здесь
                          0
                          use erlang, luke
                            +1
                            > use scala, Luke

                            fixed. Мы же всё-таки о Java говорим.
                            +1
                            > Joshua Blosh
                            Joshua Bloch
                              0
                              Есть хорошая книга «Java Concurrency in Practice». www.javaconcurrencyinpractice.com/

                              Статья же больше напоминает предисловие к подобным книгам.

                                0
                                Атомарность доступа на значения типа long и double гарантируется, если описания переменных снабдить признаком volatile.
                                  0
                                  догоняясь =)
                                  начиная с java 1.5, но у слова волатайл есть более сильный момент — а именно синхронизация TLS с основной памятью! а это исключительно дорого! java.sun.com/docs/books/jls/second_edition/html/memory.doc.html#28330 Less formally: actions on the master copies of volatile variables on behalf of a thread are performed by the main memory in exactly the order that the thread requested.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • НЛО прилетело и опубликовало эту надпись здесь
                                      0
                                      Многопоточность… как много в этом слове особенно для тех кто работает в Java/.NET.
                                      www.amazon.com/Concurrent-Distributed-Computing-Java-Vijay/dp/047143230X (аккуратно — книгу можно стырить)

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое