Re[10]: Вы делаете это неправильно - Философия программирования

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

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

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

К>>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.
К>>Наверное, это не единственный пример?

G>Конечно не единственный, индексы в БД хранятся в таком виде, именно чтобы уменьшить количество чтений с диска.
G>Только в БД чтение с диска выполняется явно, а в случае с виртуальной памятью — неявно и размеры страниц, их вытеснение (особенно), итп находится вне контроля приложения.

Мой вопрос был не про конкретно данный алгоритм/струкутуру данных, а вообще о таких приёмах, которые становятся не совсем эффективными потому как... (см. выше)

К>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.
К>Наверное, это не единственный пример?

Спасибо, понравилась статья. Комменты там тоже полезные.

К сожалению, на ACM очень много содержимого (в том числе, научных статей) такого качества.

Эта статья просто нелепа своим кретинизмом — это все равно, что сказать, например: посмотрите, я сортирую 100-гигабайтный массив пузырьком и вот я придумал способ, который позволяет лучше использовать виртуальную память.

И привести пример какой-нибудь челночной сортировки в качестве "изобретения".

Этот человек разрабатывал ядро FreeBSD?

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

Кстати, "You're Doing It Wrong" — просто идеальное название для статьи.

Хотя, может быть, я просто чего-то не знаю?

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

К>Мой вопрос был не про конкретно данный алгоритм/струкутуру данных, а вообще о таких приёмах, которые становятся не совсем эффективными потому как... (см. выше)
Вообще все приёмы, разработанные для баз данных, становятся актуальны для "обычных программ в памяти". По странному стечению обстоятельств "классическая" алгоритмика работает в предположении "изотропной памяти", что в наше время применимо только в пределах линейки кэша или страницы виртуальной памяти. А вот СУБД с самого начала столкнулись с тем, что не весь storage одинаково доступен, в связи с чем и разработали массу решений этой проблемы.

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

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

К>>Мой вопрос был не про конкретно данный алгоритм/струкутуру данных, а вообще о таких приёмах, которые становятся не совсем эффективными потому как... (см. выше)
S>Вообще все приёмы, разработанные для баз данных, становятся актуальны для "обычных программ в памяти". По странному стечению обстоятельств "классическая" алгоритмика работает в предположении "изотропной памяти", что в наше время применимо только в пределах линейки кэша или страницы виртуальной памяти. А вот СУБД с самого начала столкнулись с тем, что не весь storage одинаково доступен, в связи с чем и разработали массу решений этой проблемы.

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

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

К>А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.
Лексеры, например.
"Академические" лексеры обречены быть менее быстрыми, чем могли бы быть. Упирается опять отчасти в память, блочный i/o, и ветвление (кода).

Не статья а детский сад какой-то, ее правильнее было бы назвать "мой первый опыт в использовании алгоритмов на внешней памяти"

Алгоритмы на внешней памяти это отделаная тема которую кнут не рассматривал и пинать его за это — признак глубокого невежества.
Литературы по этой теме маловато, но если кому интересно то можете покопаться в stxxl или поглядеть вот эту книгу http://www.ozon.ru/context/detail/id/1685709/

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

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

К>В сабжевой статье Poul-Henning Kamp показывает, что вроде бы признанный всеми (и описанный Кнутом) алгоритм оказывается далеко не самым оптимальным, потому как сказываются подробности архитектуры современных компьютеров.

а ты вообще оптимизацией занимаешься? такие примеры сплошь да рядом. например, мне пришлось к большому хешу 32-битных значений, занимающему десятки мегабайт, добавить маленький хеш присутствия, который влезал в l2 cache, и потому делал весь процесс в несколько раз быстрее

кстати, ещё один классический пример — линейное рехеширование vs скачкообразное. какое эффективней?

одна из причин быстродействия freearc — замена традиционного в архиваторах скачкообразного рехеширования линейным

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

BZ>кстати, ещё один классический пример — линейное рехеширование vs скачкообразное. какое эффективней?

одна из причин быстродействия freearc — замена традиционного в архиваторах скачкообразного рехеширования линейным

Автоцитата из соседнего поста:

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

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

К>Автоцитата из соседнего поста:
К>

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

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

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

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

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

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

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

К>>Автоцитата из соседнего поста:
К>>

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

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

Булат, скажи мне, где я написал "только"?

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

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

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

M>Параллелить можно во многих местах, не обязательно сам алгоритм. Очень часто в общей задаче находится место, где параллелизм возникает естественным образом.

эффективен тот метод решения задачи, который можно распараллелить...

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

BZ>эффективен тот метод решения задачи, который можно распараллелить...

Прямо матра какая-то, самогипноз... Зачем параллелить генератор ходов в шахматах, если сверху все равно будет перебор? Зачем параллелить вычисление некоторого критерия (критериев), если все это выполняется внутри генетического алгоритма? Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом. А для этого нужны оптимальные однопоточные реализации.

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

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

BZ>>эффективен тот метод решения задачи, который можно распараллелить...

M>Прямо матра какая-то, самогипноз... Зачем параллелить генератор ходов в шахматах, если сверху все равно будет перебор? Зачем параллелить вычисление некоторого критерия (критериев), если все это выполняется внутри генетического алгоритма? Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом.
http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%BA%D0%BE%D0%BD_%D0%90%D0%BC%D0%B4%D0%B0%D0%BB%D0%B0

M>А для этого нужны оптимальные однопоточные реализации.
Можно поподробнее?

Не всегда оптимальные однопоточные программы можно распараллелить.

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

G>Не всегда оптимальные однопоточные программы можно распараллелить.

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

G>Можно поподробнее?

классический пример -- вместо того чтобы дико усложнять код компилятора и делать его многопоточным, паралеллелят на уровне make -jN

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

G>>Можно поподробнее?

D>классический пример -- вместо того чтобы дико усложнять код компилятора и делать его многопоточным, паралеллелят на уровне make -jN

Еще раз

M>Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом.
M>А для этого нужны оптимальные однопоточные реализации.

Связь между предложениями понять не могу.

Вполне логично что надо параллелить там где легко параллелится и будет наибольший эффект. Но зачем для этого оптимальные однопоточные реализации?

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

G>Еще раз
G>

M>>Имхо, максимальная производительность будет там, где место параллелизма выбрано с умом.
M>>А для этого нужны оптимальные однопоточные реализации.

G>Связь между предложениями понять не могу.
G>Вполне логично что надо параллелить там где легко параллелится и будет наибольший эффект. Но зачем для этого оптимальные однопоточные реализации?

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

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

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

M>Прямо матра какая-то, самогипноз... Зачем параллелить генератор ходов в шахматах

затем что я говорил про свой опыт. отучайтесь говорить за всех

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

К>А может есть примеры, касающиеся не только распределения памяти? С ходу в мою голову приходят только проблемы с изменяемым состоянием для многопроцессорной обработки.
Увы, про это я ничего не знаю. Тут скорее вопрос построения алгоритмов, более пригодных для распараллеливания.
Ну и вообще вопросы high concurrency, типа того же обслуживания веб-реквестов, где собствнно многопроцессорность не шибко важна. А важно умение эффективно распараллеливать ожидание — ну там, как, к примеру, эрланг, который и на одном процессоре бегает кругами вокруг иных многопроцессорных.

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

BZ>затем что я говорил про свой опыт. отучайтесь говорить за всех

Ну так по умолчанию выражение

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

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

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

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

Ну, тут ещё бабка надвое сказала. Есть разные виды параллелизма: мелкозернистый и крупнозернистый, функциональный и по данным.
Например, при рендеринге мы имеем дело с мелкозернистым параллелизмом, под который заточены видеокарты. Да и вообще все алгоритмы, реализуемые на видеокартах распараллеливаются на уровне небольших порций данных и никаких оптимальных однопоточных реализаций там нет.
Аналогичные примеры можно привести и для центральных процессоров: алгоритмы использующие SSE, например. Тот же alpha blending можно распараллелить двумя способами: на низком уровне использовать SSE2, а на высоком раскидать части изображения по ядрам или узлам кластера.

Поэтому выделенное у тебя слово "обычно" не очень то и верно.

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

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

BZ>>затем что я говорил про свой опыт. отучайтесь говорить за всех

M>Ну так по умолчанию выражение

M>

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

M>распространяется на все алгоритмы. Что в общем случае не так: есть ряд алгоритмов, которые никто и не будет пытаться параллелить в будущем, но при этом они будут эффективными. Что, собственно говоря, и вызвало протест, и я привел конкретные примеры, когда это неверно.

А теперь докажи что алгоритм генерации ходов вообще можно распараллелить. Насколько я себе представляю количество ходов = 16 (кол-во фигур) * 8 (максимум клеток в одно направлении) * 4 (направления) = 512, реально раз в 5 меньше. При этом ходы для пешек не такие же, как для ферзя. Поэтому я слабо представляю как такое вообще можно распараллелить.

Параллелится то, что содержит одинаковые операции множества для разных элементов. Например проверка ходов, она выполняется одинаково для любой позиции.

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

BZ>>затем что я говорил про свой опыт. отучайтесь говорить за всех

M>Ну так по умолчанию выражение

M>

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

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

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

BZ>например, алгоритм поиска хода в шахматах?

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

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

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

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

N> Аналогичные примеры можно привести и для центральных процессоров: алгоритмы использующие SSE, например. Тот же alpha blending можно распараллелить двумя способами: на низком уровне использовать SSE2, а на высоком раскидать части изображения по ядрам или узлам кластера.
То есть использование на низком уровне SSE2 для тебя не является "однопоточной оптимизацией"? По-моему, ты согласен с точкой зрения, которую пытаешься опровергнуть

N>Поэтому выделенное у тебя слово "обычно" не очень то и верно.

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

G>А теперь докажи что алгоритм генерации ходов вообще можно распараллелить. Насколько я себе представляю количество ходов = 16 (кол-во фигур) * 8 (максимум клеток в одно направлении) * 4 (направления) = 512, реально раз в 5 меньше. При этом ходы для пешек не такие же, как для ферзя. Поэтому я слабо представляю как такое вообще можно распараллелить.

G>Параллелится то, что содержит одинаковые операции множества для разных элементов. Например проверка ходов, она выполняется одинаково для любой позиции.

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

void GenerateMoves()
{
  GenerateKnightMoves();
  GenerateBishopMoves();
  GenerateRookMoves();
  GenerateQueenMoves();
  GenerateKingMoves();
  GeneratePawnMoves();
  GenerateCastles();
}

Ничто не мешает создать нам одновременно восемь потоков для каждого вида ходов. Ниже код, который выдран из Crafty, который показывает как оно в жизни:

/* modified 03/23/99 */
/*
 *******************************************************************************
 *                                                                             *
 *   GenerateCaptures() is used to generate capture and pawn promotion moves   *
 *   from the current position.                                                *
 *                                                                             *
 *   the destination square set is the set of squares occupied by opponent     *
 *   pieces, plus the set of squares on the 8th rank that pawns can advance to *
 *   and promote.                                                              *
 *                                                                             *
 *******************************************************************************
 */
int *GenerateCaptures(TREE * RESTRICT tree, int ply, int wtm, int *move)
{
  register BITBOARD target, piecebd, moves;
  register BITBOARD promotions, pcapturesl, pcapturesr;
  register int from, to, temp;

/*
 ************************************************************
 *                                                          *
 *   now, produce knight moves by cycling through the       *
 *   *_knight board to locate a [from] square and then      *
 *   cycling through knight_attacks[] to locate to squares  *
 *   that a knight on [from] attacks.                       *
 *                                                          *
 ************************************************************
 */
  if (wtm) {
    piecebd = WhiteKnights;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = knight_attacks[from] & BlackPieces;
      temp = from + (knight << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    }
/*
 ************************************************************
 *                                                          *
 *   now, produce bishop moves by cycling through the       *
 *   *_bishop board to locate a [from] square and then      *
 *   generate the AttacksFrom() bitmap which supplies the   *
 *   list of valid <to> squares.                            *
 *                                                          *
 ************************************************************
 */
    piecebd = WhiteBishops;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = AttacksBishop(from) & BlackPieces;
      temp = from + (bishop << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    }
/*
 ************************************************************
 *                                                          *
 *   now, produce rook moves by cycling through the         *
 *   *_rook board to locate a [from] square and then        *
 *   generate the AttacksFrom() bitmap which supplies the   *
 *   list of valid <to> squares.                            *
 *                                                          *
 ************************************************************
 */
    piecebd = WhiteRooks;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = AttacksRook(from) & BlackPieces;
      temp = from + (rook << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    }
/*
 ************************************************************
 *                                                          *
 *   now, produce queen moves by cycling through the        *
 *   *_queen board to locate a [from] square and then       *
 *   generate the AttacksFrom() bitmap which supplies the   *
 *   list of valid <to> squares.                            *
 *                                                          *
 ************************************************************
 */
    piecebd = WhiteQueens;
    while (piecebd) {
      from = LastOne(piecebd);
      moves = AttacksQueen(from) & BlackPieces;
      temp = from + (queen << 12);
      while (moves) {
        to = LastOne(moves);
        *move++ = temp | (to << 6) | ((-PcOnSq(to)) << 15);
        Clear(to, moves);
      }
      Clear(from, piecebd);
    } 

................................... (и т. д.)

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

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

G>>А теперь докажи что алгоритм генерации ходов вообще можно распараллелить. Насколько я себе представляю количество ходов = 16 (кол-во фигур) * 8 (максимум клеток в одно направлении) * 4 (направления) = 512, реально раз в 5 меньше. При этом ходы для пешек не такие же, как для ферзя. Поэтому я слабо представляю как такое вообще можно распараллелить.

G>>Параллелится то, что содержит одинаковые операции множества для разных элементов. Например проверка ходов, она выполняется одинаково для любой позиции.

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

M>Ничто не мешает создать нам одновременно восемь потоков для каждого вида ходов. Ниже код, который выдран из Crafty, который показывает как оно в жизни:
Думаешь такой код просто распараллелить будет с учетом того что я выше написал?

Думаешь такое распараллеливание чему-то вообще поможет?

Здесь я говорю о многопоточном\многоядерном исполнении. Распараллеливание по данным, например с помощью SSE, (векторизация) помогает гораздо лучше ибо меньше накладных расходов несет.

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

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

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

G>Думаешь такой код просто распараллелить будет с учетом того что я выше написал?
G>Думаешь такое распараллеливание чему-то вообще поможет?

Я изначально писал, что параллелить такой алгоритм плохая идея.

G>Здесь я говорю о многопоточном\многоядерном исполнении. Распараллеливание по данным, например с помощью SSE, (векторизация) помогает гораздо лучше ибо меньше накладных расходов несет.

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

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

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

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

M>Да хоть в сокет записать и отправить.

Какой тогда толк от многопроцессорной обработки если выходной канал не позволяет выдавать данные со скоростью генерации данных?

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

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

M>Так что теоретическая возможность распараллелить алгоритм существует.
А меня не теоретическая возможность интересует, а именно практическая распараллеливаемость таких алгоритмов. Ты утверждаешь что генерацию ходов можно распараллелить — приведи пример параллельной генерации, чтобы её результаты можно было потреблять не менее параллельно. А потом посмотрим дает ли она вообще что-нибудь по сравнению с непараллельной версией (есть ли реальный параллелизм). Учитывая верхнюю границу числа ходов = 500 я в этом сильно сомневаюсь.

G>>Думаешь такой код просто распараллелить будет с учетом того что я выше написал?
G>>Думаешь такое распараллеливание чему-то вообще поможет?
M>Я изначально писал, что параллелить такой алгоритм плохая идея.

Ты написал что его можно параллелить (так чтобы был эффект), а я в этом сильно сомневаюсь.
Вычисление факториала тоже можно "параллелить", запуская в разных потоках рекурсию.

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

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

M>Я говорил о генерации всех возможных ходов.

M>Я просто хочу сказать, что важность распараллеливаемости алгоритма зависит от самого алгоритма. Да, в некоторых случаях это важно (алгоритм сжатия). А в некоторых случаях многопоточная реализация никогда никого интересовать не будет

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

кстати, дальнейший ответ на вопрос Курилки — особенно важное значение приобретают алгоритмы, реализуемые на GPU

От:	Курилка	http://kirya.narod.ru/
Дата:	15.06.10 17:36
Оценка:	46 (7)

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	15.06.10 18:05
Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	15.06.10 18:24
Оценка:

	От:	Temoto
	Дата:	15.06.10 18:27
	Оценка:

	От:	Тролль зеленый и толстый
	Дата:	15.06.10 19:24
	Оценка:	+1 -3

От:	Sinclair	https://github.com/evilguest/
Дата:	16.06.10 06:37
Оценка:	46 (8) +1

От:	Mystic	http://mystic2000.newmail.ru
Дата:	16.06.10 10:09
Оценка:

От:	Nuzhny	https://github.com/Nuzhny007
Дата:	16.06.10 17:19
Оценка:

	От:	BulatZiganshin
	Дата:	16.06.10 21:24
	Оценка:	1 (1)

От:	Mamut	http://dmitriid.com
Дата:	17.06.10 11:40
Оценка: