Как стать автором
Обновить

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

Java
Змей-горыныч от 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, в особенности — её десятую главу.
Теги:concurrencyмногопоточностьoptimizationоптимизация программ
Хабы: Java
Всего голосов 56: ↑37 и ↓19 +18
Просмотры8K

Похожие публикации

Разработчик C++
до 150 000 ₽НТЦ ПРОТЕЙСанкт-ПетербургМожно удаленно
Java разработчик
от 150 000 до 200 000 ₽KotelovСанкт-Петербург
Java developer
от 100 000 ₽ТФ «Николь»ОмскМожно удаленно

Лучшие публикации за сутки