Как можно обойти фон Неймана?
От: Курилка Россия http://kirya.narod.ru/
Дата: 25.03.06 10:04
Оценка: 6 (1)
Набрёл на довольно интересный пост, спорный конечно, но основная мысль даже не вынесенная в заголовок, а в том, что архитектура фон Неймана — не единственная возможная схема, но на неё завязаны большинство современных языков программирования.
Но возникает вопрос — а что можно противопоставить им? Какие языки будут хорошо ложиться на архитектуру Cell?
(в статье приводится Erlang, насколько он подходит не берусь утверджать, а с другой стороны 1 язык это маловато)
Re: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 25.03.06 14:33
Оценка: 12 (1) +1 -3
Здравствуйте, Курилка, Вы писали:

К>Набрёл на довольно интересный пост, спорный конечно, но основная мысль даже не вынесенная в заголовок, а в том, что архитектура фон Неймана — не единственная возможная схема, но на неё завязаны большинство современных языков программирования.

К>Но возникает вопрос — а что можно противопоставить им? Какие языки будут хорошо ложиться на архитектуру Cell?
К>(в статье приводится Erlang, насколько он подходит не берусь утверджать, а с другой стороны 1 язык это маловато)

Я так часто слышал мнения, что архитектура фон Неймана (которую правдолюбы называют все же архитектурой фон Цузе) плоха, что стал в этом сомневаться.
Вот крамольный вопрос: так ли она плоха?
И каковы пределы роста эффективности за счет распараллеливания? Ведь есть такие ограничители, связанные с самой задачей, как, например, "критический путь".
Вот, навскидку, три источника роста производительности:
1) более эффективные алгоритмы;
2) распараллеливание;
3) конвейеризация (для потока однотипных задач; наподобие конвейеризации в RISC-процессорах).
И в чем их принципиально ограничивает архитектура фон Неймана?
Предполагаю, что проблема не в ней, а в ограничениях роста, связанных с алгоритмами.

Другой миф (IMHO) — о каких-то небывалых преимуществах функционального программирования перед императивным.
Может быть, я и правда ретроград, но использование АТД и классов кажется мне вполне естественным, удобным и эффективным, а ограничение себя одними функциями — нет.
Не так давно на RSDN обсуждалась статья Вирта в недавнем номере IEEE Computer.
Там он назвал потенциальную распараллеливаемость, свойственную функциональным языкам, "маргинальным преимуществом".
Это вызвало возмущение.
Но Вирт указал причину, по которой он считает это преимущество маргинальным. На его взгляд активные объекты (владеющие собственым потоком) еще лучше, нет надобности переходить на функциональные языки.

Конечно, все высказанное — сугубое IMHO.
Но мне (лично) кажется несколько нездоровым, что на RSDN такой популярностью пользуются:
1) фантастика (функциональное программирование);
2) чрезмерное увлечение мелкими деталями кодирования, взгляд "с высоты птичьего помета". Достаточно сослаться на огромное число форумов, посвященных, по сути, кодированию на Си++. До сих пор идут бои местного значения в форуме "Плохой язык C++".
Как мне кажется, этим два пунктам, могущих интересовать юношей, уделяется чрезмерное внимание.
Что указывают на некоторую незрелость наших обсуждений.

Все это, повторюсь, IMHO, и не следует мое ворчание принимать чрезмерно всерьез или на свой счет.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[2]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 27.03.06 01:52
Оценка: 1 (1) +2
Здравствуйте, AVC, Вы писали:

AVC>Другой миф (IMHO) — о каких-то небывалых преимуществах функционального программирования перед императивным.


нет здесь такого мифа

AVC>Но Вирт указал причину, по которой он считает это преимущество маргинальным. На его взгляд активные объекты (владеющие собственым потоком) еще лучше, нет надобности переходить на функциональные языки.


Каким образом эти самые активные объекты могут помочь распараллеливать задачу? Давай рассмотрим это на примере задачи умножения матриц.

AVC>1) фантастика (функциональное программирование);


фантастика — это то, чем занимается сам Вирт. А на функциональных языках пишут вполне даже production системы.
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[3]: Как можно обойти фон Неймана?
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 27.03.06 08:28
Оценка: -1
Здравствуйте, Дарней, Вы писали:

Д>Каким образом эти самые активные объекты могут помочь распараллеливать задачу? Давай рассмотрим это на примере задачи умножения матриц.


Умножение матриц и есть
AVC> взгляд "с высоты птичьего помета".
Вы ещё про сортировку и поиск вспомните...

Активные объекты — это элементы архитектуры программы, т.е. это из области крупномасштабного программирования. Они решают общую задачу преобразования информации. Информация получается, обрабатывается и выдаётся разными объектами асинхронно.
Re[4]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 27.03.06 08:56
Оценка: +2
Здравствуйте, Сергей Губанов, Вы писали:

СГ>Умножение матриц и есть

AVC>> взгляд "с высоты птичьего помета".
СГ>Вы ещё про сортировку и поиск вспомните...

можно ещё вспомнить про потоковое кодирование/декодирование данных, рендеринг изображений. Это как раз те задачи, где распараллеливание действительно востребовано.
А как распараллеливать задачи, где распараллеливание не особо то и нужно — это мало кого интересует. Кроме Вирта, конечно.

СГ>Активные объекты — это элементы архитектуры программы, т.е. это из области крупномасштабного программирования. Они решают общую задачу преобразования информации. Информация получается, обрабатывается и выдаётся разными объектами асинхронно.


На таком уровне задача прекрасно решается на C#, Java, Erlang, С++ и многих других языках. И даже не надо ни менять ОС, ни переписывать всю программу на оберон.
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[5]: Как можно обойти фон Неймана?
От: minorlogic Украина  
Дата: 27.03.06 09:12
Оценка:
Попытался представить распаралеленый рендеринг изображения на функциональном языке...
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[6]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 27.03.06 09:22
Оценка:
Здравствуйте, minorlogic, Вы писали:

M>Попытался представить распаралеленый рендеринг изображения на функциональном языке...


не вижу здесь приципиальных проблем, кроме (возможно) некоторого снижения эффективности вычислений. Но это всё равно будет компенсироваться общим ускорением за счет разделения по процессорам.
А ты видишь?
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[6]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 27.03.06 09:26
Оценка:
minorlogic,

M>Попытался представить распаралеленый рендеринг изображения на функциональном языке...


Не стоит перенапрягать своё воображение.

render_spawn(1) ->
    ok.
render_spawn(N) when is_integer(N) ->
    spawn(render_module, render, []),
    render_spawn(N - 1).

% в модуле render_module    
render() ->
    % чего-то тут рендерим...
    ok.


Как видишь, ничего сверхъестественного.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[5]: Как можно обойти фон Неймана?
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 27.03.06 10:34
Оценка: -1
Здравствуйте, Дарней, Вы писали:

Д>можно ещё вспомнить про потоковое кодирование/декодирование данных, рендеринг изображений. Это как раз те задачи, где распараллеливание действительно востребовано.


Там востребована аппаратная реализация: графические акселераторы, аппаратные кодеры/декодеры,...

Д>...Кроме Вирта, конечно...

Д>...на оберон...

Совершенно на ровном месте, ни с того ни с сего вдруг Вирту и Оберону за что-то досталось... При чём тут они?
Re[6]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 27.03.06 11:18
Оценка: +2
Здравствуйте, Сергей Губанов, Вы писали:

СГ>Там востребована аппаратная реализация: графические акселераторы, аппаратные кодеры/декодеры,...


чтобы выпускать новое железо каждый раз, когда обновляется версия кодека?

СГ>Совершенно на ровном месте, ни с того ни с сего вдруг Вирту и Оберону за что-то досталось... При чём тут они?


Re: Как можно обойти фон Неймана?
Автор: AVC
Дата: 25.03.06
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[7]: Как можно обойти фон Неймана?
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 27.03.06 11:27
Оценка: :))) :)))
Здравствуйте, Дарней, Вы писали:

Д>чтобы выпускать новое железо каждый раз, когда обновляется версия кодека?


Кодеки не меняются. Они стандартизированы.
Re[3]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 27.03.06 16:17
Оценка:
Здравствуйте, Дарней, Вы писали:

AVC>>Другой миф (IMHO) — о каких-то небывалых преимуществах функционального программирования перед императивным.

Д>нет здесь такого мифа

Тем лучше.
Просто у меня сложилось такое впечатление.
Уточни, что ты имеешь в виду:
1) что на RSDN никто не утверждает, что функциональные языки лучше императивных;
2) что принципиальные (не 'маргинальные' ) преимущества функциональных языков не являются мифом?
Интересно, тебе не понравилось только высказвание Вирта о функциональных языках?
Или ты также уверен, что архитектура Неймана плоха?

AVC>>Но Вирт указал причину, по которой он считает это преимущество маргинальным. На его взгляд активные объекты (владеющие собственым потоком) еще лучше, нет надобности переходить на функциональные языки.

Д>Каким образом эти самые активные объекты могут помочь распараллеливать задачу? Давай рассмотрим это на примере задачи умножения матриц.

Активный объект — это поток + собственные локальные переменные объекта.
В определенном смысле, это развитие идеи монитора.

А что уж такого страшного в задаче умножения матриц?
Пусть у нас есть на входе матрицу A (размерностью mxt) и матрицу B (размерностью txn).
На выходе надо получить матрицу C размерностью mxn.
Т.к. элементы матрицы C не зависят друг от друга, то в принципе вычисление матрицы можно разбить на mxn потоков.
Добавляю в библиотеку процедуру умножения матриц с использованием многопоточности. И пользуюсь ей.
Ты хочешь сказать, что в случае функционального языка компилятору проще распараллелить код.
Но, в принципе, отсутствие побочных эффектов у функции компилятор может установить и для императивного языка, со всеми вытекающими последствиями.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[4]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 27.03.06 17:39
Оценка: +1
Здравствуйте, AVC, Вы писали:

AVC>1) что на RSDN никто не утверждает, что функциональные языки лучше императивных;


Таки утверждают. Ты только забыл добавить — "для некоторых задач"

AVC>2) что принципиальные (не 'маргинальные' ) преимущества функциональных языков не являются мифом?


именно так — не являются. Их подтверждают вполне конкретными делами и проектами. В отличие от.

AVC>Интересно, тебе не понравилось только высказвание Вирта о функциональных языках?

AVC>Или ты также уверен, что архитектура Неймана плоха?

Текущая архитектура мне тоже не очень нравится. Но как программиста меня это практически не беспокоит

AVC>А что уж такого страшного в задаче умножения матриц?

AVC>Пусть у нас есть на входе матрицу A (размерностью mxt) и матрицу B (размерностью txn).
AVC>На выходе надо получить матрицу C размерностью mxn.
AVC>Т.к. элементы матрицы C не зависят друг от друга, то в принципе вычисление матрицы можно разбить на mxn потоков.
AVC>Добавляю в библиотеку процедуру умножения матриц с использованием многопоточности. И пользуюсь ей.

А теперь — внимание — вопрос на миллион. Каким образом активные объекты должны упростить эту задачу, по сравнению с существующими языками, например — C#?

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


Теоретически — да. Только для того, чтобы извлечь из этого реальную пользу, придется писать довольно специфический код — без изменяемых переменных, с активным применением рекурсий и т.д.
Тебе это ничего не напоминает?
Это был пункт раз. А пункт два — где ты видел такие компиляторы?
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[5]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 27.03.06 18:07
Оценка:
Здравствуйте, Дарней, Вы писали:

AVC>>А что уж такого страшного в задаче умножения матриц?

AVC>>Пусть у нас есть на входе матрицу A (размерностью mxt) и матрицу B (размерностью txn).
AVC>>На выходе надо получить матрицу C размерностью mxn.
AVC>>Т.к. элементы матрицы C не зависят друг от друга, то в принципе вычисление матрицы можно разбить на mxn потоков.
AVC>>Добавляю в библиотеку процедуру умножения матриц с использованием многопоточности. И пользуюсь ей.
Д>А теперь — внимание — вопрос на миллион. Каким образом активные объекты должны упростить эту задачу, по сравнению с существующими языками, например — C#?

Здесь, как мне кажется, и активные объекты как таковые не нужны.
Достаточно принципа локальности.
Если я напишу что-то вроде
matrix operator*(const matrix &a, const matrix &b) /* здесь можно добавить какое-нибудь ключевое слово вроде nosideeffect */
{
  matrix c;
  int i, j, k;
  for (i = 0; i < m; ++i)
    for (j = 0; j < n; ++j) {
      c[i][j]  = 0;
      for (k = 0; k < t; ++k)
        c[i][j] += a[i][k] * b[k][j];
    }
  return c;
}

то, IMHO, распараллеливание может быть добавлено компилятором как вполне рядовая оптимизация.
И не надо забивать голову специфическими проблемами ФЯ.

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


Д>Теоретически — да. Только для того, чтобы извлечь из этого реальную пользу, придется писать довольно специфический код — без изменяемых переменных, с активным применением рекурсий и т.д.

Д>Тебе это ничего не напоминает?


Необязательно избегать использования переменных.
Достаточно, если это будут локальные переменные.
Если функция меняет только свои локальные (имеющие одно с ней время жизни и недоступные из других функций) переменные, то она не приводит к побочным эффектам. А разве не это главное?
IMHO, здесь важна локальность переменных, а не их полное отсутствие.

Д>Это был пункт раз. А пункт два — где ты видел такие компиляторы?


Просто это было не так актуально, IMHO.
Точно так же и функциональные языки (до последнего времени?) обещали эффективность и распараллеливание только в потенции.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re: Никуда мы от от фон Неймана не денемся
От: Геннадий Васильев Россия http://www.livejournal.com/users/gesha_x
Дата: 28.03.06 03:32
Оценка: 6 (1) +2 -2
Здравствуйте, Курилка, Вы писали:

К>Набрёл на довольно интересный пост, спорный конечно, но основная мысль даже не вынесенная в заголовок, а в том, что архитектура фон Неймана — не единственная возможная схема, но на неё завязаны большинство современных языков программирования.

К>Но возникает вопрос — а что можно противопоставить им? Какие языки будут хорошо ложиться на архитектуру Cell?
К>(в статье приводится Erlang, насколько он подходит не берусь утверджать, а с другой стороны 1 язык это маловато)

Ну он, вообще-то, не столько о компьютерах, сколько о том, что "you'll just have to find an approach that works for you personally" (найдите, мол, подход к обучению, который будет работать персонально для вас). Да и вообще — have a fun! Фон Нейманом он иллюстрирует влияние привычки на положение дел.

Притом рассуждает иной раз так, что мама, не горюй. Как архитектура Cell принципиально противоречит фон Нейману? Или в более общем смысле — машине Тьюринга? Там что, процессор процессором не является? Или память — это не память? AFAIK, основное отличие от x86 — в явном прицеле на параллельные вычисления и развитые коммуникации. Но всё равно это никак не отрицает того, что набор инструкций а) имеет место быть и это ключевое понятие, и б) набор инструкций будет тем быстрее пройден процессором, чем меньше потребуется операций с внешними по отношению к процессору устройствами (общей памятью, синхронизациями, коммуникациями и т.п.). Вуаля, для достижения наивысшей производительности снова вспоминаем об архитектурных особенностях, т.е., читай, о фон Неймане.

Так что, вопрос о языках для Cell, это вопрос о языках с поддержкой параллелизма, а никакой не contra-von Neuman. Кстати, "в лоб" параллелизм можно и на обычном C поддержать. Набор инструкций, это что? Правильно, это — процедура.

create_thread_for_cpu(cpu_index, thread_func);
// Поехали!


Исключение здесь, конечно, массивная параллельность:

apply_as_simd(array_pointer, array_size, applied_function);


Или — не исключение даже?

PS.: Вот, всё-таки, русскую интеллигенцию погубит привычка читать между строк, даже если ничего там не написано.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Re[6]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 04:44
Оценка: 18 (2)
AVC,

AVC>
AVC>matrix operator*(const matrix &a, const matrix &b) 
AVC>/* здесь можно добавить какое-нибудь ключевое слово вроде nosideeffect */
AVC>{
AVC>  matrix c;
AVC>  int i, j, k;
AVC>  for (i = 0; i < m; ++i)
AVC>    for (j = 0; j < n; ++j) {
AVC>      c[ i ][j]  = 0;
AVC>      for (k = 0; k < t; ++k)
AVC>        c[ i ][j] += a[ i ][k] * b[k][j];
AVC>    }
AVC>  return c;
AVC>}
AVC>

AVC>то, IMHO, распараллеливание может быть добавлено компилятором как вполне рядовая оптимизация.
AVC>И не надо забивать голову специфическими проблемами ФЯ.

Ну да, создание копии. И никаких проблем.

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

Пример такого предположения — отсутствие побочных эффектов. Позволяет, например, выкинуть локи, мьютексы и прочие семафоры, и облегчить threading model. Пример языков с лёгковесными потоками (процессами): Erlang, GHC Haskell, GForth.

На этой диаграммке всё видно, в частности отрыв "лёгкой" многопоточности от "тяжёлой".

                       time     space  prog.size
1.0    Erlang HiPE #2  5.18     4,996    263    
1.1    Haskell GHC     5.86     2,696    236    
1.4    Forth GForth    7.00     1,052    305    
4.9    Smalltalk GST   25.32    8,676    435    
5.3    SML MLton #2    27.24    5,892    319    
5.6    Lua #2          29.00    1,664    229    
6.1    C++ g++         31.35    4,948    1086
...

(В этом тесте запускается 500 потоков, что для Эрланга — просто детский лепет — для него и 50000 по зубам, если интересно могу привести рекорд).

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


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

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

Функциональные языки называются таковыми не потому, что запрещают побочные эффекты (это вообще неверно для Erlang и Ocaml), а потому, что они позволяют скрыть сложность при реализации функций без побочных эффектов за счёт удобной нотации. (хотя в ФЯ ещё много чего есть кроме этого )

AVC>Просто это было не так актуально, IMHO.

AVC>Точно так же и функциональные языки (до последнего времени?) обещали эффективность и распараллеливание только в потенции.

Насколько велика область задач, где нужен массивный параллелизм? Скорее мала, чем велика. Это одна из "стратосфер человеческой мысли", и туда с обычными молотками и гвоздями не суются. Там нужны более тонкие инструменты
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[7]: Как можно обойти фон Неймана?
От: FR  
Дата: 28.03.06 05:18
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:


LCR>Пример такого предположения — отсутствие побочных эффектов. Позволяет, например, выкинуть локи, мьютексы и прочие семафоры, и облегчить threading model. Пример языков с лёгковесными потоками (процессами): Erlang, GHC Haskell, GForth.


Как я понял под легкими потоками имеются в виду потоки не преключающие контекст (фиберы в Win32), так это хак, аппаратно не распаралеливается, к тому же легко реализуется и на C++ и на C# и на питоне(10000 потоков тоже не проблема на интерпретаторе).
Re[7]: Как можно обойти фон Неймана?
От: Трурль  
Дата: 28.03.06 05:18
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:


LCR>
LCR>render_spawn(1) ->
LCR>    ok.
LCR>render_spawn(N) when is_integer(N) ->
LCR>    spawn(render_module, render, []),
LCR>    render_spawn(N - 1).

LCR>% в модуле render_module    
LCR>render() ->
LCR>    % чего-то тут рендерим... 
... а вот здесь самое интересное
LCR>    ok.
LCR>
Re[8]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 05:48
Оценка: +1 :)
Трурль,

LCR>>    % чего-то тут рендерим... 
Т>... а вот здесь самое интересное
LCR>>    ok.


А там посылается сообщение порту
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[8]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 05:48
Оценка:
FR,

LCR>>Пример такого предположения — отсутствие побочных эффектов. Позволяет, например, выкинуть локи, мьютексы и прочие семафоры, и облегчить threading model. Пример языков с лёгковесными потоками (процессами): Erlang, GHC Haskell, GForth.


FR>Как я понял под легкими потоками имеются в виду потоки не преключающие контекст (фиберы в Win32), так это хак, аппаратно не распаралеливается, к тому же легко реализуется и на C++ и на C# и на питоне(10000 потоков тоже не проблема на интерпретаторе).


Не обязательно — это может быть что-то своё. В Erlang RTS процессы не зависят от существования/несуществования фиберов/потоков в конкретной ОС. Главное — обеспечение параллелизма без накладных расходов.

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

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

Кроме того, фиберы есть не на многих осях. Тогда в чём прикол фиберов? В том, что иногда кое-где их полезно ввернуть вместо потоков, дабы тормоза снять. Гапертон как-то рассказывал о таком случае — в его случае это было что доктор прописал. Универсален ли этот подход? Думаю, что нет.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[9]: Как можно обойти фон Неймана?
От: FR  
Дата: 28.03.06 06:05
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:


LCR>Кроме того, фиберы есть не на многих осях. Тогда в чём прикол фиберов? В том, что иногда кое-где их полезно ввернуть вместо потоков, дабы тормоза снять. Гапертон как-то рассказывал о таком случае — в его случае это было что доктор прописал. Универсален ли этот подход? Думаю, что нет.


Я не про фиберы конкретно(они были как пример), я именно про легкие (не OS и не аппаратные) потоки, например в том же питоне они без всяких фиберов реализуются, хотя по сути это тоже самое, реализация корпоративной многозадачности. Так вот такие потоки не паралелятся на многопроцессорных системах, поэтому в контексте данной темы мало полезны, а так в общем удобная и хорошая вещь.
Re[10]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 06:07
Оценка:
FR,

FR>Я не про фиберы конкретно(они были как пример), я именно про легкие (не OS и не аппаратные) потоки, например в том же питоне они без всяких фиберов реализуются, хотя по сути это тоже самое, реализация корпоративной многозадачности. Так вот такие потоки не паралелятся на многопроцессорных системах, поэтому в контексте данной темы мало полезны, а так в общем удобная и хорошая вещь.


В Эрланге параллелятся. Про GHC и GForth не могу сказать.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[7]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 28.03.06 07:34
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>Ну да, создание копии. И никаких проблем.

LCR>Проблемы с concurrency так или иначе решаются, но дело в том, что при некоторых консервативных предположениях, можно _существественно_ разгрузить накладные расходы на обеспечение параллелизма.
LCR>Пример такого предположения — отсутствие побочных эффектов. Позволяет, например, выкинуть локи, мьютексы и прочие семафоры, и облегчить threading model. Пример языков с лёгковесными потоками (процессами): Erlang, GHC Haskell, GForth.

Здесь у меня возник "технический" вопрос (скорее всего, наивный).
В функциональных языках "переменные" создаются и уничтожаются неявно. В частности, по этой причине необходим сборщик мусора (по крайней мере, так было раньше).
Как в ФЯ разруливается вопрос о доступе потоков к общим ресурсам (например, куче) без мьютексов или мониторов?
Есть общий ресурс (память), есть разные потоки, но нет синхронизации.
(Я догадываюсь, что мой вопрос наивный и чисто познавательный, так что это, конечно, не "критика".)
Обычный поток не требует специальных средств синхронизации до тех пор, пока он не обращается к разделяемым ресурсам.
Например, скромно вычисляет что-то в своем стеке с помощью реентерабельных функций без побочных эффектов.

LCR>На этой диаграммке всё видно, в частности отрыв "лёгкой" многопоточности от "тяжёлой".


LCR>
LCR>                       time     space  prog.size
LCR>1.0    Erlang HiPE #2  5.18     4,996    263    
LCR>1.1    Haskell GHC     5.86     2,696    236    
LCR>1.4    Forth GForth    7.00     1,052    305    
LCR>4.9    Smalltalk GST   25.32    8,676    435    
LCR>5.3    SML MLton #2    27.24    5,892    319    
LCR>5.6    Lua #2          29.00    1,664    229    
LCR>6.1    C++ g++         31.35    4,948    1086
LCR>...
LCR>

LCR>(В этом тесте запускается 500 потоков, что для Эрланга — просто детский лепет — для него и 50000 по зубам, если интересно могу привести рекорд).

Создается впечатление, что отрыв не так уж и велик.
Например Си побыстрее, чем Си++:

35 C gcc 181.46 3,876 519

А Ада еще быстрее:

13 Ada 95 GNAT 69.64 6,960 452

IMHO, заметно, что дело не только в императивности.

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


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


Вот с этим и помогают бороться активные объекты.
Для потока активного объекта поле этого объекта также является "локальной переменной".
Ведь это поле принадлежит только активному объекту. Поэтому не требуются (за исключением особых случаев) средства синхронизации.

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


А эмуляция императивного стиля на ФЯ?
А использование рекурсии там, где итеративное решение очевиднее и эффективнее?
И разве сложно эмулировать функциональный стиль на императивных языках?
Допустим, введем ключевое слово, означающее отсутствие у функции побочных эффектов.
Компилятор проверит это свойство и выдаст ошибку, если оно не выполняется.
Затем этот факт отсутствия побочных эффектов можно использовать при компиляции других функций.

LCR>Насколько велика область задач, где нужен массивный параллелизм? Скорее мала, чем велика. Это одна из "стратосфер человеческой мысли", и туда с обычными молотками и гвоздями не суются. Там нужны более тонкие инструменты


Это, скорее всего, верно.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[7]: Как можно обойти фон Неймана?
От: FR  
Дата: 28.03.06 07:50
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:


LCR>На этой диаграммке всё видно, в частности отрыв "лёгкой" многопоточности от "тяжёлой".


Извиняюсь сразу ссылку не заметил, раньше я просто не доверял этому ресурсу, теперь же мое мнение о нем стало ниже плинтуса.
Уровень этих "тестов" c потоками такой же как и сравнение разных языков на разных алгоритмах(что у них уже было).
Re[2]: Никуда мы от от фон Неймана не денемся
От: Курилка Россия http://kirya.narod.ru/
Дата: 28.03.06 07:54
Оценка: +1
Здравствуйте, Геннадий Васильев, Вы писали:


ГВ>Ну он, вообще-то, не столько о компьютерах, сколько о том, что "you'll just have to find an approach that works for you personally" (найдите, мол, подход к обучению, который будет работать персонально для вас). Да и вообще — have a fun! Фон Нейманом он иллюстрирует влияние привычки на положение дел.

Про эту иллюстрацию и речь

ГВ>Притом рассуждает иной раз так, что мама, не горюй. Как архитектура Cell принципиально противоречит фон Нейману?

Если говорить строго — да, не противоречит (как ты вообще себе что-либо противоречащее фон Неймановской модели представляешь?), но это не машина фоннеймоновской модели, где есть процессор, память и операции выполняются строго последовательно
ГВ>Или в более общем смысле — машине Тьюринга? Там что, процессор процессором не является? Или память — это не память?
AFAIK, основное отличие от x86 — в явном прицеле на параллельные вычисления и развитые коммуникации.
(выделено мной)
Видимо ты не улавливаешь мысли, которую уже твердят давно и на RSDN в том числе, что стандартные языки (аля C и т.п.) не дают удобных концепций для описания свободно распараллеливаемых алгоритмов. Часто ФЯ упоминаются, но там далеко не всё так гладко как хотелось бы

ГВ>Так что, вопрос о языках для Cell, это вопрос о языках с поддержкой параллелизма, а никакой не contra-von Neuman. Кстати, "в лоб" параллелизм можно и на обычном C поддержать. Набор инструкций, это что? Правильно, это — процедура.

...
Много чего можно, можно и на ассемблере GUI-приложения писать и ещё много чего. Вопрос — насколько просто и удобно
Как раз на эту тему и мысль того поста — программисты ленивы, им лень изучать новые парадигмы, языки и т.п.
because they like to minimize the amount of crap they have to learn. Because learning is painful
Я лично имею привычку бороться с ленью, но это личный выбор каждого
Re[7]: Как можно обойти фон Неймана?
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 28.03.06 07:57
Оценка: +2
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>...Как только метод какого-нибудь класса обращается к своему полю с целью модификации — появляется побочный эффект...


Вот-вот именно отсюда и "растут ноги" активных объектов. Активный объект — это не просто сумма пассивного объекта и потока, а нечто большее — новая идеология, парадигма. Если ООП провозгласила, что все данные должны быть инкапсулированы в объектах, а поля объектов должны меняться только с помощью его методов, то парадигма активных объектов идёт дальше и говорит, что код методов зависящий от состояния объекта надо делать эксклюзивным (для данного объекта). В язык добавляется специальное служебное слово EXCLUSIVE ну, а дальше дело техники — компилятор сам разберётся...
Re[6]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 28.03.06 08:15
Оценка: +1
Здравствуйте, AVC, Вы писали:

AVC>Здесь, как мне кажется, и активные объекты как таковые не нужны.


А где они тогда вообще нужны?

AVC>Необязательно избегать использования переменных.

AVC>Достаточно, если это будут локальные переменные.
AVC>Если функция меняет только свои локальные (имеющие одно с ней время жизни и недоступные из других функций) переменные, то она не приводит к побочным эффектам. А разве не это главное?
AVC>IMHO, здесь важна локальность переменных, а не их полное отсутствие.

императивные циклы только усложняют работу компилятора.
А вообще у тебя уже получился гибридный язык, только ты сам не хочешь это признавать
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[8]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 28.03.06 08:16
Оценка:
Здравствуйте, AVC, Вы писали:

AVC>Создается впечатление, что отрыв не так уж и велик.

AVC>Например Си побыстрее, чем Си++:
AVC>

AVC>35 C gcc 181.46 3,876 519

AVC>А Ада еще быстрее:
AVC>

AVC>13 Ada 95 GNAT 69.64 6,960 452

AVC>IMHO, заметно, что дело не только в императивности.

Здесь я ошибся: перепутал поля.
Оказывается, все наоборот, и Си++ быстрее, чем Си в 6 (!) раз.
Что, IMHO, уже кажется весьма странным.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[8]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 08:31
Оценка: +1
FR,

FR>Извиняюсь сразу ссылку не заметил, раньше я просто не доверял этому ресурсу, теперь же мое мнение о нем стало ниже плинтуса. Уровень этих "тестов" c потоками такой же как и сравнение разных языков на разных алгоритмах(что у них уже было).




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

Я придерживаюсь промежуточной точки зрения: эти тесты определённо не супер-мега-рулез, однако по их результатам можно более-менее судить о задачах, которые благоприятны для того или иного языка (вкупе с прочей информацией из других источников).
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[7]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 28.03.06 08:33
Оценка:
Здравствуйте, Дарней, Вы писали:

AVC>>Здесь, как мне кажется, и активные объекты как таковые не нужны.


Д>А где они тогда вообще нужны?


Там же, где нужны потоки, мониторы и т.п.

AVC>>Необязательно избегать использования переменных.

AVC>>Достаточно, если это будут локальные переменные.
AVC>>Если функция меняет только свои локальные (имеющие одно с ней время жизни и недоступные из других функций) переменные, то она не приводит к побочным эффектам. А разве не это главное?
AVC>>IMHO, здесь важна локальность переменных, а не их полное отсутствие.

Д>императивные циклы только усложняют работу компилятора.


Зато как облегчают работу программиста!
Защитим операторы присваивания от посягательств функциональщиков!! (лозунг )

Д>А вообще у тебя уже получился гибридный язык, только ты сам не хочешь это признавать


Пусть гибридный.
Даже нелюбимый тобой Вирт не отрицает влияния, которое ФЯ оказывают на императивные языки: рекурсия, исключение побочных эффектов и т.д.
Но ведь главная идея функционального программирования — как раз в "чистоте".
Которой, как раз, что-то нигде не видно.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[8]: Как можно обойти фон Неймана?
От: Курилка Россия http://kirya.narod.ru/
Дата: 28.03.06 08:39
Оценка:
Здравствуйте, AVC, Вы писали:

AVC>Но ведь главная идея функционального программирования — как раз в "чистоте".

Это ты откуда такое взял, расскажи?
AVC>Которой, как раз, что-то нигде не видно.
Haskell вроде как чистофункциональный, но большинство языков реализуют много парадигм.
Re[8]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 28.03.06 08:53
Оценка: 1 (1)
Здравствуйте, AVC, Вы писали:

AVC>Там же, где нужны потоки, мониторы и т.п.


это всё и без них прекрасно реализуется в любом из современных языков. Овчинка не стоит выделки.

AVC>Зато как облегчают работу программиста!


не вижу никакого особого облегчения

AVC>Даже нелюбимый тобой Вирт не отрицает влияния, которое ФЯ оказывают на императивные языки: рекурсия, исключение побочных эффектов и т.д.


не видел, где он про этого пишет

AVC>Но ведь главная идея функционального программирования — как раз в "чистоте".


с чего ты взял? Истина, как всегда, не в крайностях. Истина — она где-то посредине.
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[9]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 28.03.06 08:55
Оценка:
Здравствуйте, Курилка, Вы писали:

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


AVC>>Но ведь главная идея функционального программирования — как раз в "чистоте".

К>Это ты откуда такое взял, расскажи?

Из книжки по функциональному программированию. (Кажется, Field и Harrison.)
Мол, главное — исключить программирование с помощью побочных эффектов (принцип "прозрачности по ссылкам").
Но если я неправильно это понимаю, буду благодарен за критику (можно даже с ругательствами, лишь бы по делу ).

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[11]: Как можно обойти фон Неймана?
От: А почему вы спрашиваете Беларусь  
Дата: 28.03.06 09:01
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>FR,


FR>>Я не про фиберы конкретно(они были как пример), я именно про легкие (не OS и не аппаратные) потоки, например в том же питоне они без всяких фиберов реализуются, хотя по сути это тоже самое, реализация корпоративной многозадачности. Так вот такие потоки не паралелятся на многопроцессорных системах, поэтому в контексте данной темы мало полезны, а так в общем удобная и хорошая вещь.


LCR>В Эрланге параллелятся. Про GHC и GForth не могу сказать.


В эрланге только в самом распоследнем снапшоте, который еще далеко не production ready и не скоро им станет.
Re[10]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 28.03.06 09:05
Оценка: +2
Здравствуйте, AVC, Вы писали:

AVC>Из книжки по функциональному программированию. (Кажется, Field и Harrison.)

AVC>Мол, главное — исключить программирование с помощью побочных эффектов (принцип "прозрачности по ссылкам").
AVC>Но если я неправильно это понимаю, буду благодарен за критику (можно даже с ругательствами, лишь бы по делу ).

некоторые задачи принципиально не решаются без побочных эффектов, что вполне очевидно. Но исключать побочные эффекты, где без них можно обойтись — дело конечно благое.
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[10]: Как можно обойти фон Неймана?
От: EXO Россия http://www.az.inural.ru
Дата: 28.03.06 09:06
Оценка: 6 (1) +1
Здравствуйте, AVC, Вы писали:
AVC> Мол, главное — исключить программирование с помощью побочных эффектов (принцип "прозрачности по ссылкам").

Это излишне экстремистский подход. Реально в практике используется много смешанных решений.
Например в Erlang есть такая штука, как "словарь процесса".
По сути — это те самые:
AVC> Активный объект — это поток + собственные локальные переменные объекта.
Что называется "один в один". То есть переменные "словаря процесса" меняются в Erlang так же как и в императивных языках. (Имнно меняются!) И этот словарь всегда локален для процесса, что здесь уже и предлагалось...
Другое дело, что используют его далеко не на каждом шагу — много других удобных абстакций.
Re[9]: Как можно обойти фон Неймана?
От: marat321  
Дата: 28.03.06 09:42
Оценка:
Здравствуйте, AVC, Вы писали:

AVC>Здесь я ошибся: перепутал поля.

AVC>Оказывается, все наоборот, и Си++ быстрее, чем Си в 6 (!) раз.
AVC>Что, IMHO, уже кажется весьма странным.

Видимо, libstdc++.so собирался с NPTL-версией glibc.

А программы на C компилялись с помощью LinuxThreads-версией glibc
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
silent
Re[9]: Как можно обойти фон Неймана?
От: FR  
Дата: 28.03.06 09:55
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>FR,


FR>>Извиняюсь сразу ссылку не заметил, раньше я просто не доверял этому ресурсу, теперь же мое мнение о нем стало ниже плинтуса. Уровень этих "тестов" c потоками такой же как и сравнение разных языков на разных алгоритмах(что у них уже было).


LCR>


LCR>Критикуя, попробуй предложить другую методику (тем более, что в разных языках совершенно разные базовые абстракции, и я вообще не понимаю, как сделать "одинаковый алгоритм").


Угу сравнивать хеш с дервом очень "полезно".

LCR>Я придерживаюсь промежуточной точки зрения: эти тесты определённо не супер-мега-рулез, однако по их результатам можно более-менее судить о задачах, которые благоприятны для того или иного языка (вкупе с прочей информацией из других источников).


Нельзя по ним ни о чем судить, если этот тестировщик несколько лет ни может например настроить нормальный запуск питона с psyco из-за чего результаты тестов занижены на порядок, и если у меня на машине результаты сильно расходятся с ихними и если подправив пару строк получается намного быстрее, то все доверия нет.
Re[8]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 10:06
Оценка: 6 (1)
AVC,

AVC>Здесь у меня возник "технический" вопрос (скорее всего, наивный). В функциональных языках "переменные" создаются и уничтожаются неявно. В частности, по этой причине необходим сборщик мусора (по крайней мере, так было раньше). Как в ФЯ разруливается вопрос о доступе потоков к общим ресурсам (например, куче) без мьютексов или мониторов?


Синхронизация обеспечивается внутренними средствами RTS (вполне вероятно, что это могут быть системные мьютексы). Там для модифицируемых данных применяется реал-тайм менеджер памяти, а для обычных данных one-pass real-time mark-and-sweep:

Armstrong and Virding have proposed a one-pass mark-and-sweep garbage collector [AV95]. The collector is designed for languages that prohibit destructive operations (i.e. values can not be overwritten), and is used in a Erlang implementation. Since destructive operations are not allowed, references can only refer to older objects. The collector marks the objects from the youngest to the oldest. If no other object has referred to an object that is being marked, it can be reclaimed immediately (since only younger objects can refer to it.) All objects are kept in a singly linked list to keep the objects in order. All GC operations have predictable runtime
behavior. Thus, it can be used for real-time systems if it is scheduled to guarantee memory availability.

Опять же консервативные предположения и здесь позволяют неможечко подкрутить...

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

Просто чудесно. Мне только интересно, как это будет выглядеть.

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

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

Возможно запутал, но вкратце будет так: чтобы смоделировать изменяющуюся сущность, мы отображаем эту сущность на язык (в виде объекта) и изменение этой сущности во времени моделируется с помощью изменения состояния объекта во времени. Есть альтернативный подход: изменение этой сущности во времени моделируется дискретной функцией (у которой значения меняются в зависимости от аргумента t, сама же функция является константной). Это подход ФЯ.

AVC>Для потока активного объекта поле этого объекта также является "локальной переменной".

AVC>Ведь это поле принадлежит только активному объекту. Поэтому не требуются (за исключением особых случаев) средства синхронизации.
Если один объект вызывает метод другого объекта и этот метод возвращает значение?
class A { public X meth(); }

class B
{
  private X x;
  public void fun(A a)
    {
        this.x = a.meth(); // здесь лок нужно захватить, а?
    }
}

Вопрос там, в комментарии...

AVC>А эмуляция императивного стиля на ФЯ?

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

AVC>А использование рекурсии там, где итеративное решение очевиднее и эффективнее?

Если рекурсия выглядит некрасиво, то я использую foreach(Fun, List) -> void().
Если этого мало, то я использую порт.
Правда, в случае побочных эффектов нужно смотреть в оба, чтобы они не вылезли за пределы функции, ну или процесса, если иначе никак. Обычная идеология скажем в Эрланге: каркас с побочными эффектами, наполнение — чистое.

AVC>И разве сложно эмулировать функциональный стиль на императивных языках?

AVC>Допустим, введем ключевое слово, означающее отсутствие у функции побочных эффектов.
AVC>Компилятор проверит это свойство и выдаст ошибку, если оно не выполняется.
AVC>Затем этот факт отсутствия побочных эффектов можно использовать при компиляции других функций.
Это неэффективно (и программиста напрягает, и вынуждает копировать объекты там, где бы компилятор ФЯ соптимизировал копирование).

State1 = modify(State), % ниже переменная State не используется

Выглядит, как будто копирование, а на самом деле модификация существующего объекта.

PS:
[AV95] Joe Armstrong and Robert Virding. One-pass real-time generational mark-sweep garbage collection.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[12]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 10:08
Оценка:
А почему вы спрашиваете,

LCR>>В Эрланге параллелятся. Про GHC и GForth не могу сказать.


АПВ>В эрланге только в самом распоследнем снапшоте, который еще далеко не production ready и не скоро им станет.


Ну ладно, _уже_ параллелятся.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[10]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 28.03.06 10:10
Оценка:
FR,

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


Ну так я же сказал, это неединственный источник информации.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re: Как можно обойти фон Неймана?
От: FR  
Дата: 28.03.06 11:13
Оценка: :)
Здравствуйте, Курилка, Вы писали:

К>Набрёл на довольно интересный пост, спорный конечно, но основная мысль даже не вынесенная в заголовок, а в том, что архитектура фон Неймана — не единственная возможная схема, но на неё завязаны большинство современных языков программирования.

К>Но возникает вопрос — а что можно противопоставить им? Какие языки будут хорошо ложиться на архитектуру Cell?
К>(в статье приводится Erlang, насколько он подходит не берусь утверджать, а с другой стороны 1 язык это маловато)

Пока мы тут спорим о языках, производители аппаратуры рождают настоящих монстров:

http://www.ixbt.com/news/news.php?id=58202
Re[9]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 28.03.06 12:01
Оценка: 7 (1)
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

AVC>>Как в ФЯ разруливается вопрос о доступе потоков к общим ресурсам (например, куче) без мьютексов или мониторов?

LCR>Синхронизация обеспечивается внутренними средствами RTS (вполне вероятно, что это могут быть системные мьютексы).

Или мониторы (если грубо определить монитор = доступ к разделяемому ресурсу + мьютекс).
Наверное, так и есть. Все как у людей.
Только одно непонятно: в чем же тогда особая 'легкость потоков', если мы как обычно пользуемся мьютексами?

LCR>Там для модифицируемых данных применяется реал-тайм менеджер памяти, а для обычных данных one-pass real-time mark-and-sweep:


LCR>

LCR>Armstrong and Virding have proposed a one-pass mark-and-sweep garbage collector [AV95]. The collector is designed for languages that prohibit destructive operations (i.e. values can not be overwritten), and is used in a Erlang implementation. Since destructive operations are not allowed, references can only refer to older objects. The collector marks the objects from the youngest to the oldest. If no other object has referred to an object that is being marked, it can be reclaimed immediately (since only younger objects can refer to it.) All objects are kept in a singly linked list to keep the objects in order. All GC operations have predictable runtime
LCR>behavior. Thus, it can be used for real-time systems if it is scheduled to guarantee memory availability.

LCR>Опять же консервативные предположения и здесь позволяют неможечко подкрутить...

Идея, что из ограничений можно извлекать большую пользу, мне близка.
Например, некоторые ограничения в синтаксисе императивного языка (хотя бы исключение goto) облегчают оптимизацию кода и повышают читабельность.
Type-safe языки могут обеспечить безопасность даже на машине без аппаратной защиты памяти.
И т.д. и т.п.
Вот и идея Армстронга и Вирдинга мне понравилась. Раз ссылки возможны только от младших к старшим, то сборка мусора, по идее, должна требовать всего лишь O(n), т.е. имеет место линейная зависимость (если я не ошибаюсь).
Но вопрос о 'цене ФЯ' остается (по крайней мере, для меня).
Локальные переменные в стеке по прежнему гораздо легче, чем объекты в любой куче, а их 'сборка' вообще не требует времени — достаточно выйти из подпрограммы.

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

LCR>Просто чудесно. Мне только интересно, как это будет выглядеть.

LCR>1. При передаче объекта в функцию, мы должны копировать его, или

LCR>2. При передаче объекта в функцию, позволяется вызывать только немодифицирующие методы.

Например, 2.
В Си++ есть модификатор const для метода.

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


Именно! Изменение состояния — основа моделирования, это одна из причин, почему мне не слишком нравятся ФЯ.
Слишком неестественно отображение понятия состояние на ФЯ.
Тот же автоматный подход гораздо естественнее.

LCR>Возможно запутал, но вкратце будет так: чтобы смоделировать изменяющуюся сущность, мы отображаем эту сущность на язык (в виде объекта) и изменение этой сущности во времени моделируется с помощью изменения состояния объекта во времени. Есть альтернативный подход: изменение этой сущности во времени моделируется дискретной функцией (у которой значения меняются в зависимости от аргумента t, сама же функция является константной). Это подход ФЯ.


Вот, IMHO, пример такой неестественности.

AVC>>Для потока активного объекта поле этого объекта также является "локальной переменной".

AVC>>Ведь это поле принадлежит только активному объекту. Поэтому не требуются (за исключением особых случаев) средства синхронизации.
LCR>Если один объект вызывает метод другого объекта и этот метод возвращает значение?
LCR>
LCR>class A { public X meth(); }

LCR>class B
LCR>{
LCR>  private X x;
LCR>  public void fun(A a)
LCR>    {
LCR>        this.x = a.meth(); // здесь лок нужно захватить, а?
LCR>    }
LCR>}
LCR>

LCR>Вопрос там, в комментарии...

Скорее, лок захватывается в методе A::meth() и там же освобождается.
Т.е. используется мьютекс.
Такой мьютекс может быть объявлен как поле в классе A, превращая любой экземпляр этого класса в монитор.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[9]: Как можно обойти фон Неймана?
От: Сергей Губанов Россия http://sergey-gubanov.livejournal.com/
Дата: 28.03.06 12:11
Оценка: +1
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>
LCR>class A { public X meth(); }

LCR>class B
LCR>{
LCR>  private X x;
LCR>  public void fun(A a)
LCR>    {
LCR>        this.x = a.meth(); // здесь лок нужно захватить, а?
LCR>    }
LCR>}
LCR>

LCR>Вопрос там, в комментарии...

Нужно или не нужно — никого кроме самого A не касается. Поэтому смело пишите просто a.meth().
Другое дело, что реализация этого метода может быть, например, такой:

C#:
public X Meth ()
{  
  System.Monitor.Enter(this);
  try
  {
    X x = ...
    return x;
  }
  finally
  {
    System.Monitor.PulseAll(this);
    System.Monitor.Exit(this);
  }
}

то же самое на Active Oberon:
PROCEDURE Meth (): X;
  VAR x: X;
BEGIN {EXCLUSIVE}
  x := ...
  RETURN x
END Meth;
Re[10]: Как можно обойти фон Неймана?
От: AVC Россия  
Дата: 28.03.06 12:11
Оценка:
Здравствуйте, marat321, Вы писали:

AVC>>Оказывается, все наоборот, и Си++ быстрее, чем Си в 6 (!) раз.

AVC>>Что, IMHO, уже кажется весьма странным.

M>Видимо, libstdc++.so собирался с NPTL-версией glibc.

M>А программы на C компилялись с помощью LinuxThreads-версией glibc

Возможно.
Тогда получается, что в данном тесте сравниваются вовсе не языки.
Поэтому и рассматривать его как аргумент в "споре языков", IMHO, нельзя.

Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.

Хоар
Re[7]: Как можно обойти фон Неймана?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 28.03.06 12:18
Оценка: 6 (1) +1
Здравствуйте, Lazy Cjow Rhrr

Хочется уточнить пару моментов.

AVC>>И не надо забивать голову специфическими проблемами ФЯ.


LCR>Ну да, создание копии. И никаких проблем.


Какие накладные расходы будут на создание отдельных копий данных при перемножении, например матриц 500x500?
Какие здесь вообще предполагается создавать копии?

LCR>На этой диаграммке всё видно, в частности отрыв "лёгкой" многопоточности от "тяжёлой".

LCR>(В этом тесте запускается 500 потоков, что для Эрланга — просто детский лепет — для него и 50000 по зубам, если интересно могу привести рекорд).

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


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[11]: Как можно обойти фон Неймана?
От: Шахтер Интернет  
Дата: 28.03.06 12:25
Оценка: +2 :))
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>FR,


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


LCR>Ну так я же сказал, это неединственный источник информации.


Это источник дезынформации.
В XXI век с CCore.
Копай Нео, копай -- летать научишься. © Matrix. Парадоксы
Re[8]: ошибочка вышла
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 28.03.06 12:35
Оценка:
Здравствуйте, eao197, Вы писали:

E>Какая многопоточность (кооперативная или конкурентная)?


Хотел написать кооперативная или вытесняющая.


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[3]: Никуда мы от от фон Неймана не денемся
От: Геннадий Васильев Россия http://www.livejournal.com/users/gesha_x
Дата: 28.03.06 13:13
Оценка: 4 (3)
Здравствуйте, Курилка, Вы писали:

ГВ>>Притом рассуждает иной раз так, что мама, не горюй. Как архитектура Cell принципиально противоречит фон Нейману?

К>Если говорить строго — да, не противоречит (как ты вообще себе что-либо противоречащее фон Неймановской модели представляешь?), но это не машина фоннеймоновской модели, где есть процессор, память и операции выполняются строго последовательно

Если не противоречит, то почему "не машина фоннеймоновской модели"? Просто у нас появляется много машин фон Неймана в одном флаконе с теми или иными особенностями межпроцессного обмена и своей спецификой процессора.

ГВ>>Или в более общем смысле — машине Тьюринга? Там что, процессор процессором не является? Или память — это не память?

К>AFAIK, основное отличие от x86 — в явном прицеле на параллельные вычисления и развитые коммуникации.
К>(выделено мной)
К>Видимо ты не улавливаешь мысли, которую уже твердят давно и на RSDN в том числе, что стандартные языки (аля C и т.п.) не дают удобных концепций для описания свободно распараллеливаемых алгоритмов. Часто ФЯ упоминаются, но там далеко не всё так гладко как хотелось бы

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

ГВ>>Так что, вопрос о языках для Cell, это вопрос о языках с поддержкой параллелизма, а никакой не contra-von Neuman. Кстати, "в лоб" параллелизм можно и на обычном C поддержать. Набор инструкций, это что? Правильно, это — процедура.

К>...
К>Много чего можно, можно и на ассемблере GUI-приложения писать и ещё много чего. Вопрос — насколько просто и удобно

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

Собственно, "новопарадигматологи" как раз и бодаются вокруг того, чтобы сохранить язык по возможности последовательным, а программу при том сделать распараллеливаемой. Поскольку автоматически это сделать нелегко (часто и невозможно), то начинается свистопляска вокруг очередной серебряной парадигматической пули и "лени" программистов. Как дети, прямо. Если 100 функций завязаны в цепочку результатами друг друга, то такую программу никакой компилятор не распараллелит при всём желании.

К>Как раз на эту тему и мысль того поста — программисты ленивы, им лень изучать новые парадигмы, языки и т.п.


Конечно, ленивы. Особенно когда вместо твёрдой алгоритмо-методической базы подсовывают обёртку "новой парадигмы". Угу, восьмой подход к снаряду, но уже в синем костюме. Серебряной пулей-с попахивает. Да-с.

К>because they like to minimize the amount of crap(Довыделено мной. — ГВ.) they have to learn. Because learning is painful

К>Я лично имею привычку бороться с ленью, но это личный выбор каждого

Лень и работоспособность бывают разными. Бывает трудоспособность, которая мешает понимать простые вещи объективной реальности.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Re[10]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 28.03.06 13:15
Оценка:
Здравствуйте, Сергей Губанов, Вы писали:

СГ>Нужно или не нужно — никого кроме самого A не касается. Поэтому смело пишите просто a.meth().


То есть лок делается при вызове любого метода, если он находится в другом объекте?

СГ>Другое дело, что реализация этого метода может быть, например, такой:


СГ>C#:

СГ>[c#]
СГ>public X Meth ()
СГ>{
СГ> System.Monitor.Enter(this);
СГ> try
СГ> {
СГ> X x = ...
СГ> return x;
СГ> }
СГ> finally
СГ> {
СГ> System.Monitor.PulseAll(this);
СГ> System.Monitor.Exit(this);
СГ> }

очень интересно. На работе ты вот прямо так и пишешь?
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[4]: Никуда мы от от фон Неймана не денемся
От: Курилка Россия http://kirya.narod.ru/
Дата: 28.03.06 13:17
Оценка:
Здравствуйте, Геннадий Васильев, Вы писали:

ГВ>Конечно, ленивы. Особенно когда вместо твёрдой алгоритмо-методической базы подсовывают обёртку "новой парадигмы". Угу, восьмой подход к снаряду, но уже в синем костюме. Серебряной пулей-с попахивает. Да-с.


Где ты её конкретно увидел? Не надо с ветряными мельницами бороться, Геннадий.
Re[5]: Никуда мы от от фон Неймана не денемся
От: Геннадий Васильев Россия http://www.livejournal.com/users/gesha_x
Дата: 28.03.06 13:22
Оценка: :))) :))
Здравствуйте, Курилка, Вы писали:

ГВ>>Конечно, ленивы. Особенно когда вместо твёрдой алгоритмо-методической базы подсовывают обёртку "новой парадигмы". Угу, восьмой подход к снаряду, но уже в синем костюме. Серебряной пулей-с попахивает. Да-с.


К>Где ты её конкретно увидел? Не надо с ветряными мельницами бороться, Геннадий.


У меня профессиональное чутьё. Разговоров о пуле ещё нет, но я их уже чую.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Re[10]: Как можно обойти фон Неймана?
От: Геннадий Васильев Россия http://www.livejournal.com/users/gesha_x
Дата: 28.03.06 13:26
Оценка:
Здравствуйте, Сергей Губанов, Вы писали:

Знаешь, что такое Очень Плохая Вещь?

Это вот она:

СГ>C#:

СГ>
СГ>  System.Monitor.Enter(this);
СГ>
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Re[6]: Никуда мы от от фон Неймана не денемся
От: Курилка Россия http://kirya.narod.ru/
Дата: 28.03.06 13:27
Оценка: :)
Здравствуйте, Геннадий Васильев, Вы писали:

ГВ>Здравствуйте, Курилка, Вы писали:


ГВ>>>Конечно, ленивы. Особенно когда вместо твёрдой алгоритмо-методической базы подсовывают обёртку "новой парадигмы". Угу, восьмой подход к снаряду, но уже в синем костюме. Серебряной пулей-с попахивает. Да-с.


К>>Где ты её конкретно увидел? Не надо с ветряными мельницами бороться, Геннадий.


ГВ>У меня профессиональное чутьё. Разговоров о пуле ещё нет, но я их уже чую.


Извини, но паранойей попахивает
Re[10]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.03.06 02:15
Оценка: +1
AVC

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


AVC>Именно! Изменение состояния — основа моделирования, это одна из причин, почему мне не слишком нравятся ФЯ. Cлишком неестественно отображение понятия состояние на ФЯ.

AVC>Тот же автоматный подход гораздо естественнее.

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

Ну а с эффективностью боремся помаленьку...

Полагаю, на этом можно свернуться, если вы не против. Спасибо за интересную беседу.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[11]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.03.06 03:45
Оценка:
Геннадий Васильев,

СГ>>  System.Monitor.Enter(this);

А что не так?

Например, в джаве это нормальная практика:
sychronized public void meth() {...}

всё равно что
public void meth()
{
    synchronized(this) {...}
}
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[8]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.03.06 03:45
Оценка:
Здравствуйте, eao197, Вы писали:

LCR>>Ну да, создание копии. И никаких проблем.


E>Какие накладные расходы будут на создание отдельных копий данных при перемножении, например матриц 500x500? Какие здесь вообще предполагается создавать копии?


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

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

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

Словарь и ETS — это модифицируемые хранилища, с ними всё понятно.

Если в туплах, то при каждой модификации элемента, весь тупл (то есть массив ссылок) копируется Это не рекомендуется делать для туплов больших размеров. Необходимость копирования тупла связана с ограничениями на риал-тайм в ГЦ. Если представлять матрицу в виде тупла туплов, то при наивном последовательном подходе 1by1 каждая строка будет скопирована n^2 раз и в результат попадёт только последняя копия. Ненаивный подход — это вычислять несколько элементов одновременно. Если например вычислять одновременно 2 элемента, то количество ненужных копий уменьшится более чем в 2 раза.

Hipe-овский подход позволяет достичь скорости ETS, при этом сохранив декларативность.

LCR>>(В этом тесте запускается 500 потоков, что для Эрланга — просто детский лепет — для него и 50000 по зубам, если интересно могу привести рекорд).


E>Когда одновременно работают 1000 потоков, какой квант времени выделается одному потоку?

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

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

Нормальных длительных атомарных операций нет, то есть всегда можно обойтись без них. (Скажем, есть length(L) = O(n), однако всегда можно обойтись без функции length. А из "ненормальных" атомарных операций можно привести пример функции с 10000 аргументами, причём каждый аргумент меняет значение. Тогда вызов функции (редукция) будет занимать внушительное по меркам real-time время).

Есть функции для тонкой настройки квантования — yield/0, bump_reductions/1.
Процессу, ожидающему сообщение будет выделен квант, как только пришло что-то новое в очередь сообщений процесса, или как только сработал таймаут. Имеется ввиду следующий таймаут:
    receive
        Msg -> true
    after Time ->  % вот здесь
        Pid ! Alarm
    end.

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

Многопоточность вытесняющая.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[12]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 29.03.06 04:58
Оценка: +1
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

LCR>А что не так?


LCR>Например, в джаве это нормальная практика:


значит, в жабе тоже неправильно делают. Нельзя синхронизироваться на объекте, который видно снаружи. Вот придёт кому-то в голову синхронизироваться на этом же объекте, но в другом месте и в других целях — и всё, приплыли.
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[12]: Как можно обойти фон Неймана?
От: Cyberax Марс  
Дата: 29.03.06 05:00
Оценка:
Lazy Cjow Rhrr wrote:
> А что не так?
> Например, в джаве это нормальная практика:
> sychronized public void meth() {...}
И используется такая фича достаточно редко, так как обычно надо
использовать монитор, отличный от самого объекта.
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re[13]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.03.06 05:07
Оценка: +1
Дарней,

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


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

Да конечно, потенциальный bottleneck. Но это можно сказать про любое расшаренное состояние.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[13]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.03.06 05:27
Оценка:
Cyberax,

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

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

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

Второе _обычно_: обычно synchronized (любой) — это зло, и является первым кандидатом на удаление при проблемах с перфомансом.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[14]: Как можно обойти фон Неймана?
От: Дарней Россия  
Дата: 29.03.06 06:16
Оценка: 19 (2) +1
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

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


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


это потенциальный deadlock, вот куда приплыли.
... << RSDN@Home 1.1.4 stable rev. 510>>
Всех излечит, исцелит
добрый Ctrl+Alt+Delete
Re[14]: Как можно обойти фон Неймана?
От: Cyberax Марс  
Дата: 29.03.06 06:24
Оценка:
Lazy Cjow Rhrr wrote:
> C>И используется такая фича достаточно редко, так как *обычно* надо
> C>использовать монитор, отличный от самого объекта.
> А вот моё _обычно_: обычно такие классы представляют обёртки над
> некоторой (одной) коллекцией, поэтому нет никакой разницы
> синхронизироваться по внутренней коллекции или по самой обёртке.
И часто это нужно? Обычно имеет смысл блокироваться по достаточно грубым
мьютексам, а не по отдельным членам классов.

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

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


> Второе _обычно_: обычно synchronized (любой) — это зло, и является

> первым кандидатом на удаление при проблемах с перфомансом.
Ага.
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re[15]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 29.03.06 07:04
Оценка:
Дарней,

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


JVM не даст залочиться (там какой-то эксепшн будет). Но в принципе да, ты прав.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[16]: Как можно обойти фон Неймана?
От: Cyberax Марс  
Дата: 29.03.06 07:29
Оценка:
Lazy Cjow Rhrr wrote:
> Д>это потенциальный deadlock, вот куда приплыли.
> JVM не даст залочиться (там какой-то эксепшн будет).
Еще как даст.
Posted via RSDN NNTP Server 2.0
Sapienti sat!
Re[9]: Как можно обойти фон Неймана?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 29.03.06 12:08
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

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


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


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

LCR>Hipe-овский подход позволяет достичь скорости ETS, при этом сохранив декларативность.

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

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


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[9]: Как можно обойти фон Неймана?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 29.03.06 12:17
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

E>>Когда одновременно работают 1000 потоков, какой квант времени выделается одному потоку?

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

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


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


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


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

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


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[17]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 30.03.06 02:36
Оценка:
Cyberax,

>> JVM не даст залочиться (там какой-то эксепшн будет).

C>Еще как даст.
Да, действительно, даёт.

Когда-то я напарывался на такой эксепшн. Вполне естественно ожидать, что задача будет решена в общем случае, ан нет...
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[10]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 30.03.06 02:36
Оценка: 12 (1)
eao197,

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


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

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


Да, как-то эта проблема решается. Возможно рантайм использует асинхронный ввод-вывод, к сожалению подробностей не знаю.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[11]: Как можно обойти фон Неймана?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 30.03.06 05:15
Оценка:
Здравствуйте, Lazy Cjow Rhrr, Вы писали:

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


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


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

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


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


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


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[12]: Как можно обойти фон Неймана?
От: Трурль  
Дата: 30.03.06 06:33
Оценка:
Здравствуйте, eao197, Вы писали:

E>Круто. Т.е. они свой вытесняющий диспетчер внутрях залудили.

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

Термин "вытесняющий" в данном случае вызывает нежелательные аберрации.
Ведь если у нас интерпретатор байт-кода, переключение контекста — всего лишь сдвиг указателя и его можно делать хоть каждую редукцию.
Re[13]: Как можно обойти фон Неймана?
От: eao197 Беларусь http://eao197.blogspot.com
Дата: 30.03.06 06:40
Оценка: +1
Здравствуйте, Трурль, Вы писали:

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


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

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


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


SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re[10]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 30.03.06 09:37
Оценка: 12 (1)
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> Что именно будут делать параллельные потоки и что конкретно будет передаваться в каждый из них?

Не знаю Ну как обычно параллелят умножение матрицы — вот так же и здесь.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[14]: Как можно обойти фон Неймана?
От: Lazy Cjow Rhrr Россия lj://_lcr_
Дата: 30.03.06 09:38
Оценка: +1
eao197,

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


Особенно если на нескольких процессорах...
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[8]: Как можно обойти фон Неймана?
От: Sinclair Россия https://github.com/evilguest/
Дата: 06.04.06 07:35
Оценка: +1
Здравствуйте, Сергей Губанов, Вы писали:

СГ>Кодеки не меняются. Они стандартизированы.

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

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