параллельные вычесления в haskell

yroslavasako

Наверное я сейчас выгляжу как тот человек, который поиграв в месяц в обливион задался вопросом, а не бывает ли похожей игры, но мультиплеера.
Вот поигрался я с хаскелем и подумал, что чистый ленивый функциональный язык удобен для организации параллельных вычислений. Мы можем упаковать вычисление в монаду, где помимо обычного бинда (ленивое вычисление) определить ещё несколько вариантов запуска: строгое вычисление, ленивое в отдельном потоке, строгое в отдельном потоке. Поскольку мы используем ленивые вычисления, мы можем ждать вычисления в других тредах максимально долго, работая в данном треде , а потом блокироваться до появления асинхронных результатов.
В императивных языка невозможно пользоваться стеков вызова, он работает в пределах одного треда. Потому результаты вычислений приходится передавать через параметры процедур, ссылающихся на общую область памяти, но нельзя через возвращение функцией значения.
В случае хаскеля наверное параллельность можно организовать почти незаметно, переопределив бинды.
Прав ли я и если прав где искать в хаскеле подобную функциональность?

Helga87

Хаскель пока не осилил, прокомментирую тот кусок текста, который понял:

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

кроме стека и общей памяти, активно используют передачу данных из одного треда в другой по pipe.

yroslavasako

кроме стека и общей памяти, активно используют передачу данных из одного треда в другой по pipe.

это понятно. Я имел в виду, что в нельзя записать sum(p1p2 где p1 и p2 запущены в разных тредах. придётся делать два пайпа, ждать результатов обоих и потом вызывать sum, это куча кода. Хаскель же как я подозреваю может в монаде сделать нечто такое
x<-p1
y<-p2
return x+y
и больше ничего писать не нужно. Ну может декораторы к p1, который будет говорить, что p1 - процедура в отдельном треде, что-то вроде:
x<-thread p1
y<-thread p2
return x+y

pitrik2

придётся делать два пайпа, ждать результатов обоих и потом вызывать sum, это куча кода

в С++ и Java для этого есть всякие хитрые штуки чтобы не было кучи кода
но все равно конечн онекий код будет, но вполне себе приемлемый

Helga87

Давай переходить на конкретику. У меня так (полный пример кода):

package main



import (

        "fmt"

)



func p1 int {

        // Тут долго считаем

        return 1

}



func p2 int {

        // Тут долго считаем

        return 2

}



func parallel(f func int) chan int {

        c := make(chan int)

        go func {

                c <- f

        }

        return c

}



func main {

        c1 := parallel(p1)

        c2 := parallel(p2)

        a1 := <- c1

        a2 := <- c2

        fmt.Printf("%v + %v: %v\n", a1, a2, a1+a2)

}

Выводит:

1 + 2: 3

yroslavasako

1) что за язык?
2) если у тебя p1 считается долго, p2 начинает считаться немедленно или по окончанию расчёта p1?

Helga87

1) Go
2) p2 начинает считаться мгновенно. Т.е. логика тут такая:

func main {

       // Запускаем "легкие" потоки (как в Erlang)

        c1 := parallel(p1) // Возвращает управление немедленно

        c2 := parallel(p2) // Возвращает управление немедленно

        a1 := <- c1 // Ждем завершение первой задачи и получаем результат

        a2 := <- c2 // Ждем завершение второй задачи и получаем результат

        fmt.Printf("%v + %v: %v\n", a1, a2, a1+a2)

}

yroslavasako

ясно.
но вопрос по-прежнему про хаскел.

alfadred

Control.Concurrent и Control.Parallel уже смотрел?

Katya19

http://research.microsoft.com/en-us/people/simonpj/
смотри секцию "Papers about parallelism in Haskell"

Andbar

Что-то не вижу принципиальной разницы с C++ (при использовании шаблонного класса).

Helga87

Что-то не вижу принципиальной разницы с C++ (при использовании шаблонного класса).

приведи свой пример кода.

Andbar

приведи свой пример кода.

Аналогичный тому, что ты писал? Пожалуйста:

#include<threadfunction.h>

#include<stdio.h>



int p1 {

        // Тут долго считаем

        return 1

}



int p2 {

        // Тут долго считаем

        return 2

}



int main

{

  ThreadFunction<int> c1(p1 c2(p2);

  int a1 = c1 a2 = c2;

  printf("%d + %d: %d\n", a1, a2, a1+a2);

}

threadfunction.h нужен?

Helga87

да, пожалуйста (сам в C++ не силен, поэтому сгенерить в уме не получается)

Andbar

Допустим, работа с потоками реализована через класс Thread (для каждой системы свой, если надо - напишу с использованием WinAPI у которого есть виртуальный абстрактный метод execute без параметров, метод Start для запуска потока и функция WaitFor, при вызове которой запускается ожидание окончания работы потока. Тогда threadfunction.h примерно такой:

#pragma once

#include<thread.h>



template<typename T>

class ThreadFunction

: protected Thread

{

  typedef T(*FuncType;

  T Result;

  FuncType _Function;

  ThreadFunction{}

protected:

  virtual void execute

  {

    Result = _Function;

  }

public:

  ThreadFunction(FuncType __func): _Function(__func)

  {

    Start;

  }

  ~ThreadFunction{}

  T operator 

  {

    WaitFor;

    return Result;

  }

};

Не раскрыты обработка исключений и возможность повторного получения значения... но, если нужно, не сложно исключение передать исключение в основной поток так, чтобы оно выскочило при попытке получить результат, а второе - не проблема (во всяком случае, в виндовой реализации Thread, которую я представляю).
upd: поправил немного

Helga87

У тебя пример работает не так, как мой. У тебя запускаются полноценные треды со стеком (что дорого а у меня так называемые goroutines, которых за секунду можно запустить хоть 10k. Они не настоящие треды, а отображаются на реальные системные. При 100k goroutines системных тредов будет не больше чем количество ядер + дельта.
Т.е. для получения сравнимой производительности при количестве задач порядка 1000-10000, каждая из которых работает 100 мс, тебе, похоже, придется еще мутить ThreadPool.
А если наши задачи делают блокирующие системные вызовы (например, скачивают wikipedia страницы тебе еще и многозадачность придется самому реализовывать. Иначе тредпул будет все время простаивать.

Andbar

Т.е. для получения сравнимой производительности при количестве задач порядка 1000-10000, каждая из которых работает 100 мс, тебе, похоже, придется еще мутить ThreadPool.
А если наши задачи делают блокирующие системные вызовы (например, скачивают wikipedia страницы тебе еще и многозадачность придется самому реализовывать. Иначе тредпул будет все время простаивать.

Синтаксически, на конечный код это вряд-ли заметно повлияет. Разве что добавится ещё один шаблонный параметр, определяющий, через что реализовывать класс Thread (который станет шаблонным).
То есть, если мы заговорили о реализации многопоточности, то конечно, C++ этого просто не предоставляет. Но это и без примеров кода понятно.

Helga87

Мое утверждение состоит в том, что ты заколебешься реализовывать эти легковесные треды. Если хочешь, я готов привести пример программы, которая скачивает 10k урлов из википедии по списку и проверить, сколько времени это займет. Если ты напишешь свой вариант, сравним и по скорости, и по коду.

kokoc88

Мое утверждение состоит в том, что ты заколебешься реализовывать эти легковесные треды. Если хочешь, я готов привести пример программы, которая скачивает 10k урлов из википедии по списку и проверить, сколько времени это займет. Если ты напишешь свой вариант, сравним и по скорости, и по коду.

Вообще у меня два замечания. Первое - надо использовать готовые решения, которые продвигают в стандарт. При этом кроссплатформенная реализация с поддержкой исключений выглядит так (я тоже давно не программировал на Си++ так что прошу простить):

#pragma once



#include <boost/thread.hpp>



template<class R>

class get_later

{

public:

	explicit get_later(const boost::shared_future<R>& f) : m_f(f)

	{

	}



	R get

	{

		f.wait;

		return f.get;

	}



	operator R

	{

		return get;

	}



private:

	boost::shared_future<R> m_f;

};



template<class R>

get_later<R> run(R (*pfunc

{

	boost::packaged_task<R> pt(pfunc);

	boost::shared_future<R> f = pt.get_future;

	boost::thread th(boost::move(pt;

	return get_later<R>(f);

}

Во-вторых, где и как реализовать расчёты - это не достоинства языка, а достоинства платформы. На Си++ можно написать легковесные потоки, просто весь ввод-вывод придётся делать через специальные библиотечные функции. (А в приведённом мною коде изменится только одна строка.) Язык-то тут при чём? С таким же успехом можно хвалить любой синтаксический сахар типа synchronized в Java.

Helga87

Практика — критерий истины. Ты готов написать ?

Andbar

Боюсь, многое будет зависеть от используемой библиотеки. А чисто архитектурно, это будет N одинаковых конвейеров, которые будут разбирать общий список ссылок. Так как делать N достаточно большим глупо, конвейеры можно и в отдельных потоках запустить (либо вообще в одном потоке всё сделать на неблокирующих вызовах). Короче, скачивание ссылок из вики - плохой пример.

Helga87

Короче, скачивание ссылок из вики - плохой пример.

1. Почему?
2. Предложи свой.

kokoc88

Практика — критерий истины. Ты готов написать прогу?

При чём тут твоё задание? Нельзя сравнивать платформу и язык программирования.

kokoc88

Боюсь, многое будет зависеть от используемой библиотеки. А чисто архитектурно, это будет N одинаковых конвейеров, которые будут разбирать общий список ссылок. Так как делать N достаточно большим глупо, конвейеры можно и в отдельных потоках запустить (либо вообще в одном потоке всё сделать на неблокирующих вызовах). Короче, скачивание ссылок из вики - плохой пример.

На отдельных потоках у Красина получится быстрый код, а у тебя - тормозной. На неблокирующих вызовах у Красина получится красивый код, а у тебя - лапша. И всё из-за того, что в Go ввод-вывод встроен в язык или платформа предоставляет библиотеку асинхронного ввода-вывода на легковесных потоках.

Helga87

Нельзя сравнивать платформу и язык программирования.

Если честно, я не понял этого утверждения.
Мои соображения следующие: я хочу решить указанную задачу. Как мне ее проще сделать? Ответом будет что-то типа "написать на C++ и boost" или "написать на go" или еще что-то.
Т.е. сравнивается не язык и не платформа, а то техническое решение, которое я предлагаю для решения задачи.
Есть ли у тебя решение лучше (по скорости выполнения и размеру кода)?

Andbar

1. Почему?
2. Предложи свой.

1. а) как я уже написал, многое будет зависить от реализации библиотеки работы с HTTP; б) скачивание 10к страниц с одного сервера - это не пример задачи, где следует устраивать 10к или даже 1к потоков, пусть даже легковесных;
2. я пока не понял, что ты хочешь сравнить.

kokoc88

Есть ли у тебя решение лучше (по скорости выполнения и размеру кода)?

Ну если есть готовая библиотека для Си++, то у меня есть такое же решение.
В boost легковесного ввода-вывода точно нету. (Не было в 2008 году.)

Helga87

1. а) как я уже написал, многое будет зависить от реализации библиотеки работы с HTTP; б) скачивание 10к страниц с одного сервера - это не пример задачи, где следует устраивать 10к или даже 1к потоков, пусть даже легковесных;

Не вопрос. Сколько там потоков запускать — это вопрос реализации, в который я не лезу. Задача скачать эти страницы за минимальное время и используя минимальное количество кода.
Реализацию библиотеки работы с http можешь выбирать как угодно, никаких ограничений не накладывается. В конце концов, C++ существует не один десяток лет, наверняка есть удачные библиотеки.

я пока не понял, что ты хочешь сравнить.

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

Helga87

Ну если есть готовая библиотека для Си++, то у меня есть такое же решение.
В boost легковесного ввода-вывода точно нету. (Не было в 2008 году.)

Т.е. предложить хорошего решения ты не можешь (кстати, совершенно необязательно завязываться на C++. Можно выбирать что угодно)?

kokoc88

Т.е. предложить хорошего решения ты не можешь (кстати, совершенно необязательно завязываться на C++. Можно выбирать что угодно)?

Я могу предложить хорошее решение, которое отнимет слишком много моего времени для реализации. Просто потому, что я не знаю готовых библиотек для ввода-вывода с переключением контекста/фиберов. В конце концов, если взять вычислительную задачу, то особых различий между реализацией на пуле и с легковесными потоками не будет. Ты заранее привёл условия, выгодные тебе (под что заточен выбранный тобой язык).

Helga87

Ты заранее привёл условия, выгодные тебе (под что заточен выбранный тобой язык).

Я выбрал задачу так, чтобы показать пример многопоточной программы, которую намного проще реализовать на go (там, где есть блокирующие системные вызовы). Это я и пытался показать. Т.е. если споров по этому поводу нет, то и замечательно.
Если хочешь, можешь привести свой пример многопоточной задачи. Попробуем сравнить. Хотя я склонен предполагать, что для чисто вычислительной задачи fibers и обычные потоки будут равнозначны.

yroslavasako

Обычно параллельные вычисления затевают, когда нужно много считать, а не когда нужно много выводить. Если много выводить - это называется асинхронный ИО. Меня больше интересует как следует из названия топика параллельное программирование.
Далее, любая задача должна иметь свой смысл. Посчитать число фибоначи через тысячи coprograms и рекурсию - это эзотерическая никому не нужная херня. То, что требуешь ты (массовый асинхронный IO) может быть и полезно для серверов и общения между ними, когда есть большие мощности и несколько каналов связи. Для обычного десктопа твоя задача бессмысленна.
То есть, помимо разных целей (parallel programming vs async IO ты предлагаешь использовать разные аппаратные платформы (single desktop vs multiple server). Так что я могу предложить тебе свой вариант, докажи, что go круче чем winavr для параллельной асинхронной обработки датчиков и приводов конвеера подачи гиповых плит

Helga87

Обычно параллельные вычисления затевают, когда нужно много считать, а не когда нужно много выводить. Если много выводить - это называется асинхронный ИО.

Я с тобой и согласен, и не согласен. Асинхронное ИО затевают, когда хотелось бы сделать параллельно, но из-за неэффективности стандартных средств параллелизации, приходится делать это асинхронным, что заметно запутывает код.
Кроме того, есть отличная жизненная задача web server-а, который должен обрабатывать много запросов. Однопоточным ты его все равно не сделаешь (только теоретически, и очень большой кровью)

kokoc88

Я выбрал задачу так, чтобы показать пример многопоточной программы, которую намного проще реализовать на go (там, где есть блокирующие системные вызовы). Это я и пытался показать. Т.е. если споров по этому поводу нет, то и замечательно.

Я не спорю. Но мне, наверное, будет одинаково трудно и на Go, потому что я его не знаю; и на Си++, потому что я не пользовался библиотеками для легковесного ввода-вывода и не знаю, существуют ли такие вообще. Я всё ещё не уверен, что при наличии такой библиотеки код на Си++ будет намного больше, чем на Go.

Helga87

Я всё ещё не уверен, что при наличии такой библиотеки код на Си++ будет намного больше, чем на Go.

Думаю, что вполне реально сделать "Go на С++". Т.е., может быть не очень просто (особенно, без GC но реально. Но, похоже, пока такого нет.

yroslavasako

Кроме того, есть отличная жизненная задача web server-а, который должен обрабатывать много запросов. Однопоточным ты его все равно не сделаешь (только теоретически, и очень большой кровью)

замечательно решается тредпулом. Пример можно посмотреть в апаче.

kokoc88

замечательно решается тредпулом. Пример можно посмотреть в апаче.

Статику давно отдают каким-нибудь nginx, потому что тредпулом задача решается плохо.

Andbar

На отдельных потоках у Красина получится быстрый код, а у тебя - тормозной. На неблокирующих вызовах у Красина получится красивый код, а у тебя - лапша. И всё из-за того, что в Go ввод-вывод встроен в язык или платформа предоставляет библиотеку асинхронного ввода-вывода на легковесных потоках.

Неужели в ситуации, когда большую часть времени потоки простаивают, на столько заметен оверхед от их переключения, что появляется необходимость в специальной реализации, отличной от обычных потоков или thread pool-ов?

Andbar

Статику давно отдают каким-нибудь nginx, потому что тредпулом задача решается плохо.

Я читал о тредпулах только из msdn-а, так что, возможно, не совсем понимаю, что это такое. Чем в nginx'е не тредпул?

kokoc88

Неужели в ситуации, когда большую часть времени потоки простаивают, на столько заметен оверхед от их переключения, что появляется необходимость в специальной реализации, отличной от обычных потоков или thread pool-ов?

Проблемы заметны, когда потоки не простаивают и активно занимаются I/O. А также когда они простаивают в ожидании завершения медленного I/O, тогда как быстрый I/O уже завершён, но ему не хватает потоков.
В задаче скачивания с википедии 10к страниц потоки простаивать не будут, если твой канал потянет нагрузку, которую ему может выдать процессор. Если канал тянет больше, чем ему может выдать процессор, то быстрее будет работать решение на асинхронном I/O. При грамотной реализации библиотеки асинхронного I/O ты пишешь свой код так, как будто он синхронный. В этом случае код получается красивым и простым, и нет проблем от того, что постоянно переключается контекст и процессор простаивает в ожидании I/O.