ФЯП или ООП? - Священные войны - Страница 10

Psilon · 20.02.2015, 11:27

Студворк — интернет-сервис помощи студентам

korvin_, это был пример, никто не мешает взять сколь угодно больше N.

А в шарпе насколько я помню, он возьмет сколько-то потоков из пула, будет им пихать задачи, сумма будет считаться локально для каждого потока, после этого только в конце будет количество синхронизаций по количеству потоков при записи в итоговую переменную. В результате все плюсы параллелизации без минусов. Да, придется попросить тредпул выделить сколько-то потоков, но этот оверхед просто копеечный. На малых задачах на него пофиг, на средних и больше профит только, причем с размером задачи он растет.

@korvin_ · 20.02.2015, 14:27

Сообщение от Psilon

korvin_, это был пример, никто не мешает взять сколь угодно больше N

Ты, наверное, имел в виду не переменную N, в которую суммируются квадраты элементов массив/диапазона, а размер размер этого самого массива/диапазона?

Сообщение от Psilon

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

Из кода это не очень очевидно. Впрочем мои замечания относятся к плюсовому примеру, где N — внешняя по отношению к потокам переменная.

Psilon · 20.02.2015, 15:08

Сообщение от korvin_

Ты, наверное, имел в виду не переменную N, в которую суммируются квадраты элементов массив/диапазона, а размер размер этого самого массива/диапазона?

да, конечно

Сообщение от korvin_

Из кода это не очень очевидно. Впрочем мои замечания относятся к плюсовому примеру, где N — внешняя по отношению к потокам переменная.

ну в данном случае если мы даже вызовем Enumerable.Range(1, N), то N будет просто параметром метода, а если посмотреть на лямбду x => x*x очевидно, что она ни на что не замыкается => никаких внешних переменных.

Psilon · 20.02.2015, 15:16

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

@Curry · 20.02.2015, 15:17

Psilon, В этом выражении

C#
1
Enumerable.Range(1, 10).AsParallel().Select(x => x * x).Sum();

распараллеливается только Select, а Sum выполняется по завершении всех веток? Или частичные суммы могут вычисляться параллельно, а по их завершении вычисляется сумма из меньшего кол-ва чисел?
Из синтаксиса непонятно где граница распараллеливания.

@korvin_ · 20.02.2015, 15:28

Сообщение от Psilon

ну в данном случае если мы даже вызовем Enumerable.Range(1, N), то N будет просто параметром метода, а если посмотреть на лямбду x => x*x очевидно, что она ни на что не замыкается => никаких внешних переменных.

Нет, ты не понял, в плюсовом коде в N складывается сумма из диапазона, при этом сложение в неё вызывается из каждой итерации. =)

Сообщение от Psilon

Если вопрос про внутреннее устройство

Тут вопросов нет, я и сам могу нечто подобное изобразить.

Кликните здесь для просмотра всего текста

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package main
 
import (
    "fmt"
    "runtime"
    "time"
)
 
type sum uint64
 
func main() {
    runtime.GOMAXPROCS(runtime.NumCPU())
    fmt.Println(runtime.GOMAXPROCS(0))
    r := NewRange(1, 10000000)
    test("sequential:", r, sequential)
    test("concurrent:", r, concurrent)
}
 
func test(title string, r *Range, f func(*Range) sum) {
    start  := time.Now()
    result := f(r)
    fmt.Println(title, result, time.Since(start))
}
 
func sequential(r *Range) (result sum) {
    for i := r.Low; i <= r.High; i++ {
        result += sum((i*i - i)/i + (i*i + i)%i)
        //result += sum(i*i)
    }
    return result
}
 
func concurrent(r *Range) (result sum) {
    c := make(chan sum)
    s := func(r *Range) {
        c <- sequential(r)
    }
    ranges := r.Split(runtime.GOMAXPROCS(0))
    for _, r := range ranges {
        go s(r)
    }
    for range ranges {
        result += <-c
    }
    return result
}
 
 
 
type Range struct {
    Low  int
    High int
}
 
func NewRange(low, high int) *Range {
    return &Range{low, high}
}
 
func (r *Range) String() string {
    return fmt.Sprintf("%d..%d", r.Low, r.High)
}
 
func (r *Range) Size() int {
    return r.High - r.Low + 1
}
 
func (r *Range) Split(n int) []*Range {
    step, size := 1, r.Size()
    if n < size {
        step = size/n
    } else {
        n = size
    }
    ranges := make([]*Range, n)
    low := r.Low
    n1 := n-1
    for i := 0; i < n1; i++ {
        ranges[i] = &Range{low, low+step-1}
        low += step
    }
    ranges[n1] = &Range{low, r.High}
    return ranges
}

Bash
1
2
3
4
% go run ttest.go
8
sequential: 49999995000000 406.0232ms
concurrent: 49999995000000 125.0071ms

Просто из C# кода не совсем очевидно, что оно работает именно так.

Psilon · 20.02.2015, 15:29

KolodeznyDiver, метод AsParallel() возвращает обертку (ParallelQuery<T>) над коллекцией, которую ей передали. Все поледующие методы в цепочке будут вызваны параллельно. То есть и Select и Sum.

Немного об устройстве:

As of CLR 4.0, the CLR thread pool consists of several cooperating components. When a thread that doesn’t belong to the thread pool (such as the application’s main thread) dispatches work items to the thread pool, they are enqueued into a global FIFO (first-in-first-out) queue. Each thread pool thread has a local LIFO (last-in-first-out) queue, to which it will enqueue work items created on that thread (see Figure 6-5). When a thread pool thread is looking for work, it begins by consulting its own LIFO queue, and executes work items from it as long as they are available. If a thread’s LIFO queue is exhausted, it will attempt work stealing—consulting the local queues of other threads and taking work items from them, in FIFO order. Finally, if all the local queues are empty, threads will consult the global (FIFO) queue and execute work items from there.

Figure 6-5 . Thread #2 is currently executing work item #5; after completing its execution, it will borrow work from the global FIFO queue. Thread #1 will drain its local queue before tending to any other work

Possibly the highest level of abstraction for parallel computation is that where you declare: “I want this code to run in parallel”, and leave the rest for the framework to implement. This is what Parallel LINQ is about. But first, a short refresher on LINQ is due. LINQ (Language INtegrated Query) is a framework and a set of language extensions introduced in C# 3.0 and .NET 3.5, blurring the line between imperative and declarative programming where iterating over data is concerned. For example, the following LINQ query retrieves from a data source called customers—which might be an in-memory collection, a database table, or a more exotic origin—the names and ages of the Washington-based customers who have made at least three over $10 purchases over the last ten months, and prints them to the console:

C#
1
2
3
4
5
6
7
8
9
10
11
var results = from customer in customers
          where customer.State == "WA"
          let custOrders = (from order in orders
          where customer.ID == order.ID
          select new { order.Date, order.Amount })
          where custOrders.Count(co => co.Amount >= 10 &&
                   co.Date >= DateTime.Now.AddMonths(-10)) >= 3
          select new { customer.Name, customer.Age };
foreach (var result in results) {
  Console.WriteLine("{0} {1}", result.Name, result.Age);
}

The primary thing to note here is that most of the query is specified declaratively—quite like an SQL query. It doesn’t use loops to filter out objects or to group together objects from different data sources. Often enough, you shouldn’t worry about synchronizing different iterations of the query, because most LINQ queries are purely functional and have no side effects—they convert one collection (IEnumerable < T>) to another without modifying any additional objects in the process.
To parallelize the execution of the above query, the only code change required is to modify the source collection from a general IEnumerable < T > to a ParallelQuery < T>. The AsParallel extension method takes care of this, and allows the following elegant syntax:

C#
1
2
3
4
5
6
7
8
9
10
11
var results = from customer in customers.AsParallel()
    where customer.State == "WA"
    let custOrders = (from order in orders
    where customer.ID == order.ID
    select new { order.Date, order.Amount })
    where custOrders.Count(co => co.Amount >= 10 &&
    co.Date > = DateTime.Now.AddMonths(-10)) >= 3
    select new { customer.Name, customer.Age };
foreach (var result in results) {
  Console.WriteLine("{0} {1}", result.Name, result.Age);
}

PLINQ uses a three-stage processing pipeline to execute parallel queries, as illustrated in Figure 6-7. First, PLINQ decides how many threads should be used to parallelize the query’s execution. Next, the worker threads retrieve chunks of work from the source collection, ensuring that it is accessed under a lock. Each thread proceeds to execute its work items independently, and the results are queued locally within each thread. Finally, all the local results are buffered into a single result collection, which is polled by a foreach loop in the above example.

@Curry · 20.02.2015, 15:56

Psilon, Приведённый Вами материал очень интересен. Но, мне, по прежнему, непонятна ситуация с Sum(). Дело в том, что как распаралелить преобразование (или фильтрацию) каждого элемента контейнера - понятно. Может происходить автоматом. А преобразования вида "из многих в один" не очевидны для распарралеливания. К примеру. для Sum() (или среднего, или максимума или даже сортировки) мы можем, имея по несколько элементов обрабатываемого контейнера на трэд, их распараллелить, но для каждого по разному алгоритму. К примеру сумма частичных сумм равна сумме сразу всего, но нет так с арифметическим средним.
Тем, более, что получится для свёртки в которой промежуточный результат зависит от предыдущих и она может вообще не распараллеливаться?
Т.е. для некоторых ф-ий, типа Sum описаны свои алгоритмы распараллеливания, а если встретится ф-ия, стратегия распараллеливания которой неизвестна, то до её выполнения должны все треды сойтись в один?

Psilon · 20.02.2015, 16:06

KolodeznyDiver, ну как-то он всё-таки параллелит, учитывая трехкратное превосходство уже после 10 миллионов целых чисел (а тут чем сложнее задача, тем больше профит, потому что на создание потоков для примитивных чисел много сил уходит).

Я пробовал копаться в исходниках фреймворка - нихрена не понял

если вдруг интересно, можете сами поизучать

http://referencesource.microso... merable.cs

@Curry · 20.02.2015, 16:16

Сообщение от Psilon

ну как-то он всё-таки параллелит

А Вы попробуйте просто Sum() или Average() попараллелить, без всяких Select с лямбдами.
Будет видна разница?

Psilon · 20.02.2015, 16:21

KolodeznyDiver, будет. Пример же выше. Я же даже использовал обобщенный Aggregate (это так называется reduce в шарпе), чтобы не говорить, что в Sum() или Average() какие-то специализированные алгоритмы.

@Curry · 20.02.2015, 16:45

Сообщение от Psilon

Я же даже использовал обобщенный Aggregate

С распараллельвиаемой очевидно функцией. Оптимизирующий компилятор такой оптимизирующий.
А если попробовать что то типа Aggregate((acc,elm) => ((abs(acc) % 10)> 5)? acc*acc+elm : elm-acc) ?

Добавлено через 4 минуты
... хотя ... окводратуривание накапливаемого значения - это уж перебор - переполнится быстро
скажем

C#
1
Aggregate((acc,elm) => ((abs(acc) % 10)> 5)? (acc+elm)%11 : elm-acc)

Psilon · 20.02.2015, 16:53

KolodeznyDiver, всё, понял. Смысл в том, что присвоение как и инкремент в шарпе - это атомарная операция. Как только пытаемся сделать функцию сколько-нибудь сложной, тут же получаем расхождение из-за состояния гонки. Нужно четко указывать, что и как делать, тогда он сможет всё сделать правильно:

http://stackoverflow.com/quest... oing-wrong

http://blogs.msdn.com/b/pfxtea... 76194.aspx

Сообщение от KolodeznyDiver

Оптимизирующий компилятор такой оптимизирующий.

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

Добавлено через 6 минут
кстати по ссылке на мсдн как раз ваш случай про Average

@Dennis Ritchie · 20.02.2015, 17:07

Сообщение от Psilon

Ни о каких агрессивных оптимизациях тут не может быть и речи.

В D реализована агрессивная оптимизация.
Из статьи Функциональная обработка изображений в D:

Компиляторы D с более совершенным бекэндом могут проводить еще более агрессивные оптимизации: например, если определили функцию flipXY, которая инвертирует оси X и Y, и rotateCW (для поворота изображения на 90° против часовой стрелки) как src.flipXY().hflip(), тогда четыре удачных вызова rotateCW вырезаются при оптимизации.

Psilon · 20.02.2015, 17:11

Dennis Ritchie, я рад за него, но JIT != AOT

@Curry · 20.02.2015, 17:25

Сообщение от Psilon

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

Очень странно. Ожидал увеличение времени, но не ошибку расчёта. Предположу, что шарп полагает, что любую ф-ию в Aggregate можно выполнить параллельно в каждом трэдэ, а результаты опять объединить через Aggregate с той же функцией.
Если так, то кошмар - ведёт к трудно отлавливаемым багам.
Насчёт атомарности: а Вы попробуйте сложную ф-ию в Select, когда она просто применяется к каждому элементу массива. Думаю, в этом случае, всё правильно без дополнительных плясок получится.

И, проверьте, всё таки просто одни Sum() и Average() на больших массивах.

Добавлено через 5 минут

Сообщение от Dennis Ritchie

Компиляторы D с более совершенным бекэндом могут проводить еще более агрессивные оптимизации

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

И для оленьпиад удобно - как не напиши, компилятор в 1 секундк код утопчет.

@Dennis Ritchie · 20.02.2015, 17:40

Сообщение от KolodeznyDiver

И для оленьпиад удобно - как не напиши, компилятор в 1 секундк код утопчет.

Там чаще в 2 секунды нужно утоптать.

А почему так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
 
using namespace std;
 
int main() {
    
    int  a = 0, b = 1;
    
    if (a & b == 0)
        cout << (a & b) << " = " << 0 << endl;
    else
        cout << (a & b) << " != " << 0 << endl;
    
    return 0;
}

Output0 != 0

Psilon · 20.02.2015, 17:46

Сообщение от KolodeznyDiver

Очень странно. Ожидал увеличение времени, но не ошибку расчёта. Предположу, что шарп полагает, что любую ф-ию в Aggregate можно выполнить параллельно в каждом трэдэ, а результаты опять объединить через Aggregate с той же функцией.
Если так, то кошмар - ведёт к трудно отлавливаемым багам.
Насчёт атомарности: а Вы попробуйте сложную ф-ию в Select, когда она просто применяется к каждому элементу массива. Думаю, в этом случае, всё правильно без дополнительных плясок получится.

Естественно, он же в этом случае просто маппит. Трудноуловимые баги - да, есть такое, нужно очень тонко писать код ибо мутабельность в многопотоке - это много головной боли. Но вот простые маппинги и фильтры пишутся элементарно, а кроме этого редко что надо, честно говоря

А когда надо - не трудно и подумать чутка.

Сообщение от KolodeznyDiver

И, проверьте, всё таки просто одни Sum() и Average() на больших массивах.

Так уж и быть:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using System;
using System.Diagnostics;
using System.Linq;
 
class Program
{
    static void Main()
    {
        double[] array = Enumerable.Range(1, 128*1024*1024).Select(x => (double) x).ToArray(); // 1.5GB RAM
        var sw = Stopwatch.StartNew();
        var sum = array.Sum();
        sw.Stop();
        Console.WriteLine("Sum1 in {0}ms {1}", sw.Elapsed.TotalMilliseconds, sum);
 
        var sw2 = Stopwatch.StartNew();
        var sum2 = array.AsParallel().Sum();
        sw2.Stop();
        Console.WriteLine("Sum2 in {0}ms {1}", sw2.Elapsed.TotalMilliseconds, sum2);
    }
}

C#
1
2
3
Sum1 in 590,6115ms 9,00719932184986E+15
Sum2 in 102,3434ms 9,00719932184986E+15
Для продолжения нажмите любую клавишу . . .

Сообщение от KolodeznyDiver

Ещё одно преимущество Ди: дишник может пойти покурить пока большая прога, с глобальной оптимизацией компилируется.
И для оленьпиад удобно - как не напиши, компилятор в 1 секундк код утопчет.

ничего-ничего, майкрософт щас усилинно прикручивает С++ компилятор к шарпу, уже сейчас работает в бета-режиме для виндофонов, на десктопе обещает повяится в течение года-два, и тогда посмотрим, как шарп будет с /O3 летать...

@Curry · 20.02.2015, 17:47

Сообщение от Dennis Ritchie

А почему так?

Патамучто!

C++
1
if ((a & b) == 0)

@korvin_ · 20.02.2015, 17:49

Сообщение от Dennis Ritchie

А почему так?

Потому что у == приоритет выше, чем у &.

Новые блоги и статьи Все статьи Все блоги /
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.02.2015, 11:27
	korvin_, это был пример, никто не мешает взять сколь угодно больше N. А в шарпе насколько я помню, он возьмет сколько-то потоков из пула, будет им пихать задачи, сумма будет считаться локально для каждого потока, после этого только в конце будет количество синхронизаций по количеству потоков при записи в итоговую переменную. В результате все плюсы параллелизации без минусов. Да, придется попросить тредпул выделить сколько-то потоков, но этот оверхед просто копеечный. На малых задачах на него пофиг, на средних и больше профит только, причем с размером задачи он растет. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.02.2015, 15:16
	Если вопрос про внутреннее устройство, то там все очень умно параллелится с минимумом накладных расходов. Система автоматически определяет оптимальное количество потоков, хотя можно вручную задать, а можно оставить на откуп заложенной эвристике, после чего умно разбивает по ним. Если получится, найду еще картинку. Миниатюры 0

@Curry Модератор 5171 / 3537 / 536 Регистрация: 01.06.2013 Сообщений: 7,696 Записей в блоге: 9
	20.02.2015, 15:56
	Psilon, Приведённый Вами материал очень интересен. Но, мне, по прежнему, непонятна ситуация с Sum(). Дело в том, что как распаралелить преобразование (или фильтрацию) каждого элемента контейнера - понятно. Может происходить автоматом. А преобразования вида "из многих в один" не очевидны для распарралеливания. К примеру. для Sum() (или среднего, или максимума или даже сортировки) мы можем, имея по несколько элементов обрабатываемого контейнера на трэд, их распараллелить, но для каждого по разному алгоритму. К примеру сумма частичных сумм равна сумме сразу всего, но нет так с арифметическим средним. Тем, более, что получится для свёртки в которой промежуточный результат зависит от предыдущих и она может вообще не распараллеливаться? Т.е. для некоторых ф-ий, типа Sum описаны свои алгоритмы распараллеливания, а если встретится ф-ия, стратегия распараллеливания которой неизвестна, то до её выполнения должны все треды сойтись в один? 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.02.2015, 16:06
	KolodeznyDiver, ну как-то он всё-таки параллелит, учитывая трехкратное превосходство уже после 10 миллионов целых чисел (а тут чем сложнее задача, тем больше профит, потому что на создание потоков для примитивных чисел много сил уходит). Я пробовал копаться в исходниках фреймворка - нихрена не понял если вдруг интересно, можете сами поизучать http://referencesource.microso... merable.cs Миниатюры 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.02.2015, 16:21
	KolodeznyDiver, будет. Пример же выше. Я же даже использовал обобщенный Aggregate (это так называется reduce в шарпе), чтобы не говорить, что в Sum() или Average() какие-то специализированные алгоритмы. 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	20.02.2015, 17:11
	Dennis Ritchie, я рад за него, но JIT != AOT 0