Cyberax,

C>И используется такая фича достаточно редко, так как обычно надо
C>использовать монитор, отличный от самого объекта.

А вот моё _обычно_: обычно такие классы представляют обёртки над некоторой (одной) коллекцией, поэтому нет никакой разницы синхронизироваться по внутренней коллекции или по самой обёртке.

Второе _обычно_: обычно synchronized (любой) — это зло, и является первым кандидатом на удаление при проблемах с перфомансом.

Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>Куда приплыли? Этот "другой" просто будет ждать в очереди на захват монитора. В книжках об этом предупреждают уже на второй странице, сразу после примера про synchronized.

LCR>Да конечно, потенциальный bottleneck. Но это можно сказать про любое расшаренное состояние.

это потенциальный deadlock, вот куда приплыли.

Lazy Cjow Rhrr wrote:
> C>И используется такая фича достаточно редко, так как *обычно* надо
> C>использовать монитор, отличный от самого объекта.
> А вот моё _обычно_: обычно такие классы представляют обёртки над
> некоторой (одной) коллекцией, поэтому нет никакой разницы
> синхронизироваться по внутренней коллекции или по самой обёртке.
И часто это нужно? Обычно имеет смысл блокироваться по достаточно грубым
мьютексам, а не по отдельным членам классов.

Да и этот метод даже не подходит для защиты итерации по внешним итераторам:

SynchronizedList list;

public void someMethod()
{
    Iterator iter=list.iterate();
    while(iter.hasNext())
    {
        //А что если тут коллекцию поменяют??
        Object obj=iter.next();
    }
}

> Второе _обычно_: обычно synchronized (любой) — это зло, и является
> первым кандидатом на удаление при проблемах с перфомансом.
Ага.

Дарней,

Д>это потенциальный deadlock, вот куда приплыли.

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

Lazy Cjow Rhrr wrote:
> Д>это потенциальный deadlock, вот куда приплыли.
> JVM не даст залочиться (там какой-то эксепшн будет).
Еще как даст.

Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>Касаемо матриц. Здесь я буду говорить только про Эрланг, в других языках всё иначе.

LCR>Итак, зависит от представления. Векторы (mutable arrays) можно представлять в туплах, словаре, в ETS (Erlang Term Storage), и ещё в какой-то необычной форме (этот подход использован в HiPE), в которой я ещё не разобрался

LCR>Словарь и ETS — это модифицируемые хранилища, с ними всё понятно.
LCR>Hipe-овский подход позволяет достичь скорости ETS, при этом сохранив декларативность.

А можно пример перемножения матриц на каком-нибудь функциональном языке?

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

Здравствуйте, Lazy Cjow Rhrr, Вы писали:

E>>Когда одновременно работают 1000 потоков, какой квант времени выделается одному потоку?
E>>Какая многопоточность (кооперативная или конкурентная)? Что происходит, если один или несколько потоков начинают выполнять длительную операцию?

LCR>Процессы в Эрланге квантуются в зависимости от редукций. Одна редукция это в-общем эквивалент одному вызову фукнции. Процесс выполняется пока он не тормознётся для ожидания сообщения от другого процесса или пока он не выполнит 1000 редукций (кажется, раньше было 500).

LCR>Процессы могут иметь один из 4-х приоритетов (max, high, normal, low). Эрланг для мультипроцессорных систем (совсем новая версия) может использовать системные потоки, и системные приоритеты.

LCR>Многопоточность вытесняющая.

Предположим, что есть высокоприоритетный процесс, который спит на ожидании какого-то события. В это время работает низкоуровневый процесс, не успевший еще выполнить 1000 редукций. Событие высокоприоритетного процесс приходит, будет ли низкоприоритетный процесс остановлен, а высокоприоритетный процесс запущен?

Так что, что происходит, если процесс начинает выполнять длительную операцию ввода-вывода? Если многопоточность действительно вытесняющая, то, по идее, эта операция должна быть делегирована какой-то внутренней нити внутри Erlang-овской RunTime-системы. Чтобы зависла эта внутренняя нить, а сам Erlang смог бы диспетчировать другие нити.

Cyberax,

>> JVM не даст залочиться (там какой-то эксепшн будет).
C>Еще как даст.
Да, действительно, даёт.

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

eao197,

E>Предположим, что есть высокоприоритетный процесс, который спит на ожидании какого-то события. В это время работает низкоуровневый процесс, не успевший еще выполнить 1000 редукций. Событие высокоприоритетного процесс приходит, будет ли низкоприоритетный процесс остановлен, а высокоприоритетный процесс запущен?

Да, обязательно.

E>Так что, что происходит, если процесс начинает выполнять длительную операцию ввода-вывода? Если многопоточность действительно вытесняющая, то, по идее, эта операция должна быть делегирована какой-то внутренней нити внутри Erlang-овской RunTime-системы. Чтобы зависла эта внутренняя нить, а сам Erlang смог бы диспетчировать другие нити.

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

Здравствуйте, Lazy Cjow Rhrr, Вы писали:

E>>Предположим, что есть высокоприоритетный процесс, который спит на ожидании какого-то события. В это время работает низкоуровневый процесс, не успевший еще выполнить 1000 редукций. Событие высокоприоритетного процесс приходит, будет ли низкоприоритетный процесс остановлен, а высокоприоритетный процесс запущен?

LCR>Да, обязательно.

Круто. Т.е. они свой вытесняющий диспетчер внутрях залудили.
Надо полагать, что эффективность переключения потоков у них в нутри выше чем в самой OS за счет простоты самого переключения контекстов.

E>>Так что, что происходит, если процесс начинает выполнять длительную операцию ввода-вывода? Если многопоточность действительно вытесняющая, то, по идее, эта операция должна быть делегирована какой-то внутренней нити внутри Erlang-овской RunTime-системы. Чтобы зависла эта внутренняя нить, а сам Erlang смог бы диспетчировать другие нити.

LCR>Да, как-то эта проблема решается. Возможно рантайм использует асинхронный ввод-вывод, к сожалению подробностей не знаю.

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

Здравствуйте, eao197, Вы писали:

E>Круто. Т.е. они свой вытесняющий диспетчер внутрях залудили.
E>Надо полагать, что эффективность переключения потоков у них в нутри выше чем в самой OS за счет простоты самого переключения контекстов.

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

Здравствуйте, Трурль, Вы писали:

Т>Термин "вытесняющий" в данном случае вызывает нежелательные аберрации.

Вытесняющий он и есть вытесняющий. Смысл вытеснения в том, что низкоприоритетный поток (процесс) или просто процесс, исчерпавший свой квант, вытесняется ни смотря ни на что, а время выделяется другому процессу. Т.е. согласия у вытесненного потока никто не спрашивает.

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

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

eao197,


E>Кстати, я так и не понял, что же именно предлагается копировать для устранения побочных эфектов? Элементы результирующей матрицы или элементы исходной?
Теоретически можжно просто создать результирующую матрицу, и заполнить её ячейки нужными значениями. Но поскольку мы это делаем последовательно, то возникает задача модификации текущего промежуточного вектора.

Рассмотрим функцию:

func1({A1,A2,A3,A4,A5}) -> {A1,A2,A3+1,A4,A5}.

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

В Эрланге однако это приводит к копированию 5-элементного массива указателей (я выше писал, почему нужно копирование). В других же языках рантайм может просто модифицировать исходный тупл (думаю в Окамле с Хаскелем так и делается).

E>А можно пример перемножения матриц на каком-нибудь функциональном языке?
Перемножение матриц в окамле (m3 должна быть создана прежде чем вызвана функция mmult):

let rec inner_loop k v m1i m2 j =
  if k < 0 then v
  else inner_loop (k - 1) (v + m1i.(k) * m2.(k).(j)) m1i m2 j

let mmult rows cols m1 m2 m3 =
  let last_col = cols - 1
  and last_row = rows - 1 in
  for i = 0 to last_row do
    let m1i = m1.(i) and m3i = m3.(i) in
    for j = 0 to last_col do
      m3i.(j) <- inner_loop last_row 0 m1i m2 j (* modify here! *)
    done;
  done

Как видишь, чисто императивный код. Если заинтересовало, то вот ещё про численные вычисления в окамле: http://pauillac.inria.fr/ocaml/numerical.html

Перемножение матриц в эрланге без побочных эффектов:

mmult(M1, M2) -> 
    Inner = size(M2),
    NRows = size(M1), 
    mmult(Inner, NRows, NRows, [], M1, M2).

mmult(_, _, 0, MM, _, _) ->
    list_to_tuple(MM);
mmult(I, C, R, MM, M1, M2) ->
    NewRow = rowmult(I, C, R, [], M1, M2),
    mmult(I, C, R-1, [NewRow | MM], M1, M2).

rowmult(_, 0, _, L, _, _) ->
    list_to_tuple(L);
rowmult(I, C, R, L, M1, M2) -> 
    Sum = sumprod(I, C, R, 0, M1, M2),    % calculate c_{ij} = \sum_k a_{ik}b_{kj} 
    rowmult(I, C-1, R, [Sum | L], M1, M2).

sumprod(0, _, _, Sum, _, _) -> Sum;
sumprod(I, C, R, Sum, M1, M2) -> 
    Newsum = Sum + element(I, element(R,M1)) * element(C, element(I,M2)),
    sumprod(I-1, C, R, NewSum, M1, M2).

Здесь как видишь промежуточные результаты складываются в список, а потом список конвертируется в tuple с помощью list_to_tuple. Неудобно и не слишком эффективно, но вот так и происходит борьба с побочными эффектами

Есть ещё способ борьбы: это опустить матрицы на уровень языка и расширить операции. Тогда умножение матриц бы выглядело как M = M1 * M2, эффективно и никаких эффектов Но это автоматически делает * слишком дорогой атомарной операцией, и прощай, риал тайм. На текущий момент если что-то подобное встречается, в Эрланге используют порты (всё-таки 400 строк на C это не 4000 и тем более не 40000).

E> Что именно будут делать параллельные потоки и что конкретно будет передаваться в каждый из них?
Не знаю Ну как обычно параллелят умножение матрицы — вот так же и здесь.

eao197,

E>Не думаю, что переключение контекстов даже в интерпритаторе -- это простая операция. Она может быть проще, чем переключение контекстов в ОС. Но не тривиальной, имхо.

Особенно если на нескольких процессорах...

Здравствуйте, Сергей Губанов, Вы писали:

СГ>Кодеки не меняются. Они стандартизированы.
Да-да-да. Когда мне было 14 лет, отец моего друга (физик) сильно недоумевал по поводу моего хобби. Он считал, что все программы уже в общем-то написаны, и дело только за реализацией еще пары алгоритмов решения нелинейных уравнений. В связи с этим он пророчил скорую смерть программированию как профессии.

Уважаемый Сергей, стандартные кодеки действительно не меняются. Но вот новые кодеки появляются, и еще будут появляться. Будет еще много разных кодеков для всего подряд — кодеки, которые автоматически могут адаптироваться к выпадению пакетов (выпадение фрейма в современном видеокодеке приводит к артефактам различной степени чудовищности вместо плавного снижения качества картинки), кодеки, которые оптимизируют трафик для конкретного устройства воспроизведения, и т.п. Глупо ждать реализации каждой кодековой идеи в железе — железо, в отличие от программы, не скачаешь по интернету.