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

G>Перед тем как посмотришь — небольшая задачка, попробуй решить ее сам (у тебя получится, и ты словишь просветление).

G>Сделай очередь FIFO, так, чтобы средневзвешенная сложность операций put и get была равна O(1) — то есть, не зависела от длины очереди.
G>Вот знаешь — std::queue? Вот, придумай, как сделать такую очередь, но без массивов. У тебя только однонаправленные иммутабельные списки, и все.

G>http://www.eecs.usma.edu/webs/people/okasaki/pubs.html

Сломал мозг. Посмотрел как предлагает делать Окасаки. Он предлагает тоже самое переворачивание списка размазывать по всем операциям put/get. Круто, конечно, но все равно остаётся ощущение кидалова. Каждая конкретная операция теперь имеет сложность O(1), но в тоже время каждая операция стала дольше ровно на столько, что теряется вся экономия от избежания переворачивания списка. Получается как белка в колесе — как ни крути, всё равно быстрее не получается.
Для реалтаймовых задач это наверное пригодится, но для HPC имеет смысл, только если мы ожидаем, что в конце у нас останется много невыбраных из очереди элементов.
Неужели для FIFO нет нормального решения? Я понимаю, что в ФП предполагается неизменяемость созданых объектов. Но ради чего это собссно затевалось? Ради дополнительных возможностей оптимизации. Дык где эта оптимизация? Неужто так трудно проанализировать вычисляемые функции и понять, что старая версия списка уже не нужна и какие-то вычисления можно делать деструктивно, in-place?
То же самое относительно больших структур данных. Я, честно говоря, рассчитывал, что компиляторам хватает мозгов сделать модификации существующих данных. Буду курить ссылки от Курилки и про монады.

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

M>Неужели для FIFO нет нормального решения? Я понимаю, что в ФП предполагается неизменяемость созданых объектов. Но ради чего это собссно затевалось? Ради дополнительных возможностей оптимизации. Дык где эта оптимизация? Неужто так трудно проанализировать вычисляемые функции и понять, что старая версия списка уже не нужна и какие-то вычисления можно делать деструктивно, in-place?

Если брать реальные языки, например тот же Ocaml, там очередь (queue из стандартной библиотеки) реализованна деструктивно.

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

M>Неужели для FIFO нет нормального решения? Я понимаю, что в ФП предполагается неизменяемость созданых объектов. Но ради чего это собссно затевалось? Ради дополнительных возможностей оптимизации. Дык где эта оптимизация?

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

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

M>Неужто так трудно проанализировать вычисляемые функции и понять, что старая версия списка уже не нужна и какие-то вычисления можно делать деструктивно, in-place?

Да, это трудно, и в общем случае невозможно (ищем Single Threaded Analysis). Более того, подобная оптимизация, если бы она и работала, является слабопредсказуемой — человеку будет почти невозможно предсказать асимптотику программы, которую он пишет. Это, на самом деле, очень плохо. Просто отвратительно. Над такими вещами, которые радикально влияют на характеристики алгоритма, программист должен иметь явный контроль.

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

T>Жизнь никто на массивах не делает, если он, конечно, в своем уме.

T>Ее делают на наборах Set Coords2D (бинарное дерево живых клеток.

Ух ты, как интересно. Двумерное дерево? С узлами 2х2 элемента (или NxN элементов, по типу BTree)? В котором удобно хранить разряженные матрицы и бесконечные массивы? Черт, а я думал, я первый это представление изобрел два года назад . Как придумаешь что-нибудь толковое — так обязательно выясняется, что твою идею украли, причем — лет за 10 до того, как она пришла тебе в голову .

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

A>А есть альтернативы Окасаки? Что-нибудь попроще в описании, на пальцах так сказать, применяемый язык, в принципе, не важен. (вон монадных туториалов как грязи, а как структуры — так сразу Окасаки ...)

Окасаки основателен, есть по кускам, та структура, эта...

Сборники:

Библиотеки http://www.haskell.org/haskellwiki/Applications_and_libraries/Data_structures
Там и Окасакиевский эдисон вроде есть

Статьи http://www.haskell.org/haskellwiki/Research_papers/Data_structures
Там и Окасаки есть

Блоги http://www.haskell.org/haskellwiki/Blog_articles/Data

Пойдёт?

Здравствуйте, Gaperton, Вы писали:
T>>Ее делают на наборах Set Coords2D (бинарное дерево живых клеток.
G>Ух ты, как интересно. Двумерное дерево?...
R-tree?

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

L>Пойдёт?

Поглядим Спасибо!

С Уважением, Andir!

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

M>Неужели для FIFO нет нормального решения? Я понимаю, что в ФП предполагается неизменяемость созданых объектов. Но ради чего это собссно затевалось? Ради дополнительных возможностей оптимизации. Дык где эта оптимизация? Неужто так трудно проанализировать вычисляемые функции и понять, что старая версия списка уже не нужна и какие-то вычисления можно делать деструктивно, in-place?

насколько я понял, как раз поддержкой этого clean и отличается от haskell. более того, там вся имперавтивность сделана через псевдопеременную realworld, которая используется таким вот single threaded way

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

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

M>>Неужели для FIFO нет нормального решения? Я понимаю, что в ФП предполагается неизменяемость созданых объектов. Но ради чего это собссно затевалось? Ради дополнительных возможностей оптимизации. Дык где эта оптимизация? Неужто так трудно проанализировать вычисляемые функции и понять, что старая версия списка уже не нужна и какие-то вычисления можно делать деструктивно, in-place?

BZ>насколько я понял, как раз поддержкой этого clean и отличается от haskell. более того, там вся имперавтивность сделана через псевдопеременную realworld, которая используется таким вот single threaded way

Чего "этого"? Модификацией in-place? Там есть unboxed массивы, но также есть и "обычные" списки...
World там действительно есть, но есть и другие переменные, моделирующие часть этого World, скажем FileSystem.
Но по сути остаётся "single threaded way".

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

M>>А как в него помещаются элементы? К голове подклеиваются?

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

G>Есть пустой список. Обозначим его [].
G>Ты добавил к нему 1. У тебя список [1].
G>Добавил к голове 2. Получилось [2, 1 ]. Ты запомнил этот список — назовем его А.
G>Теперь, ты добавляешь к А 3, потом 4. У тебя получается ДВА разных списка, [3,2,1] и [4,2,1], при этом, оба этих списка _разделяют_ общий хвост А. Понятно? Это надо понять.


Я надеюсь, в реализации не используется "переворачивание" списка, когда мы проходим по списку и из lifo порядка делаем fifo порядок?

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

[cut]

R>Я надеюсь, в реализации не используется "переворачивание" списка, когда мы проходим по списку и из lifo порядка делаем fifo порядок?

С какой целью надеешься?

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

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

К>[cut]

R>>Я надеюсь, в реализации не используется "переворачивание" списка, когда мы проходим по списку и из lifo порядка делаем fifo порядок?

К>С какой целью надеешься?

А ты вначале скажи, использует или нет
А то, я что-то тут так и не нашёл алгоритма для fifo очереди.

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

R>А ты вначале скажи, использует или нет
R>А то, я что-то тут так и не нашёл алгоритма для fifo очереди.

Используется, только переворачивание там ленивое, поэтому размазывается по операциям.

Simple and Efficient Purely Functional Queues and Deques
Здесь неплохо объяснено, если саму книжку глянуть не хочешь.

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

R>>А ты вначале скажи, использует или нет
R>>А то, я что-то тут так и не нашёл алгоритма для fifo очереди.

L>Используется, только переворачивание там ленивое, поэтому размазывается по операциям.

L>Simple and Efficient Purely Functional Queues and Deques
L>Здесь неплохо объяснено, если саму книжку глянуть не хочешь.


Понятно, значит переворачивают. Тогда такая очередь не рекомендуется к применению в качестве многопоточной очереди для передачи сообщений. Алгоритмы основанные на связанных списках и последующем "переворачивании порядка" ведут себя погано, несмотря на заявленную "O(1)". Несколько таких алгоритмов разрабатывал и исследовал, и у всех слабое место — это именно операция переворачивания.
Но это всё не относится к "однопоточному" применению fifo-очереди. В однопоточном режиме — пожалуйста. Ну не знаю... для обхода в ширину... для чего она ещё может быть нужна в однопоточном режиме...

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

R>Понятно, значит переворачивают. Тогда такая очередь не рекомендуется к применению в качестве многопоточной очереди для передачи сообщений. Алгоритмы основанные на связанных списках и последующем "переворачивании порядка" ведут себя погано, несмотря на заявленную "O(1)". Несколько таких алгоритмов разрабатывал и исследовал, и у всех слабое место — это именно операция переворачивания.
R>Но это всё не относится к "однопоточному" применению fifo-очереди. В однопоточном режиме — пожалуйста. Ну не знаю... для обхода в ширину... для чего она ещё может быть нужна в однопоточном режиме...

Ну без переворачивания как же — это же связанный список. А что значит "погано"? Можно развернуть?

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

R>>Понятно, значит переворачивают. Тогда такая очередь не рекомендуется к применению в качестве многопоточной очереди для передачи сообщений. Алгоритмы основанные на связанных списках и последующем "переворачивании порядка" ведут себя погано, несмотря на заявленную "O(1)". Несколько таких алгоритмов разрабатывал и исследовал, и у всех слабое место — это именно операция переворачивания.
R>>Но это всё не относится к "однопоточному" применению fifo-очереди. В однопоточном режиме — пожалуйста. Ну не знаю... для обхода в ширину... для чего она ещё может быть нужна в однопоточном режиме...

L>Ну без переворачивания как же — это же связанный список.

Если принять *иммутабельный* список за данное, то уже не знаю...


L>А что значит "погано"? Можно развернуть?

Медленно. И масштабируется значительно хуже, особенно на небольших очередях.
Если очередь на основе fifo списка изначально, то запросы на загрузку кэш-линий с узлами списка выдаются распределеннно во времени, следовательно лучше маскируются; плюс можно применить предвыборку следующего узла. Плюс к этому производитель и потребитель всегда работают на максимальном удалении друг от друга, следовательно меньше конкуренции за кэш-линии.
Процедура переворачивая выдаёт за минимальный промежуток времени большое число запросов на загрузку непредсказываемых данных, плюс каждое обращение вызывает промах в кэше, т.е. пока данные не поступят в кэш, не можем перемещаться к следующему узлу. Плюс производитель и потребитель периодически сталкиваются в голове списка.
Идеальный вариант — это, конечно, очередь на основе массива. Там похоже хорошую службу служит аппаратный предвыборщик данных; если в очереди всегда находится некий запас сообщений, то он может практически полностью маскировать выборку данных, т.е. можно добиться производительности порядка 10 тактов на операцию, в то время как для очереди с переворачиванием это будет порядка 40-150 в зависимости от деталей (естественно при условии правильной раскладки данных — голова и хвост разделены паддингом, уж не знаю возможно ли это в функциональных языках).
Это что-то, чего Вам не скажут люди, использующие "О большое" нотацию

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

L>>Ну без переворачивания как же — это же связанный список.

R>Если принять *иммутабельный* список за данное, то уже не знаю...

Ну так тема топика про чистые структуры.

L>>А что значит "погано"? Можно развернуть?

R>Медленно. И масштабируется значительно хуже, особенно на небольших очередях.
R>Если очередь на основе fifo списка изначально, то запросы на загрузку кэш-линий с узлами списка выдаются распределеннно во времени, следовательно лучше маскируются; плюс можно применить предвыборку следующего узла. Плюс к этому производитель и потребитель всегда работают на максимальном удалении друг от друга, следовательно меньше конкуренции за кэш-линии.
R>Процедура переворачивая выдаёт за минимальный промежуток времени большое число запросов на загрузку непредсказываемых данных, плюс каждое обращение вызывает промах в кэше, т.е. пока данные не поступят в кэш, не можем перемещаться к следующему узлу. Плюс производитель и потребитель периодически сталкиваются в голове списка.
R>Идеальный вариант — это, конечно, очередь на основе массива. Там похоже хорошую службу служит аппаратный предвыборщик данных; если в очереди всегда находится некий запас сообщений, то он может практически полностью маскировать выборку данных, т.е. можно добиться производительности порядка 10 тактов на операцию, в то время как для очереди с переворачиванием это будет порядка 40-150 в зависимости от деталей (естественно при условии правильной раскладки данных — голова и хвост разделены паддингом, уж не знаю возможно ли это в функциональных языках).
R>Это что-то, чего Вам не скажут люди, использующие "О большое" нотацию

Спасибо! То, что медленнее нечистой очереди, да на массивах, это понятно изначально

Провокационный вопрос — а для мутабельных структур данных можно разработать такую универсальную очередь? Чтобы вот интерфейс такой простой и кеш не листался? Мне кажется, подобные тонкости учитывать для универсальных структур невозможно.
Насчёт переворачивания — из-за того, что там и не списки то хранятся, а thunk-и, трудно точно сказать, когда и почему там будут промахи в кэше. Да даже для мутабельной очереди это сильно зависит от операций между push/pop.
Очередь на основе чистого массива будет тормозить страшно. Если нечистый — то это уже оффтопик.
Поэтому сделаю предположение, что в контексте топика ты говоришь немного не о том, несмотря на то, что читать тебя всегда приятно и безусловно познавательно Хотя конечно 150 vs 10 заставляет задуматься. Но ведь это тоже при хорошей игре? 10 выбивать будет не всегда, верно? А только если мы ничего не делаем, а только толкаем, да берём?

Что такое паддинг?

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

L>Провокационный вопрос — а для мутабельных структур данных можно разработать такую универсальную очередь? Чтобы вот интерфейс такой простой и кеш не листался? Мне кажется, подобные тонкости учитывать для универсальных структур невозможно.

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


L>Насчёт переворачивания — из-за того, что там и не списки то хранятся, а thunk-и, трудно точно сказать, когда и почему там будут промахи в кэше.

Какие там будут *дополнительные* промахи, действительно, сложно сказать. Но какие там будут "обязательные" промахи сказать можно. Для фифо-очереди всё очень просто — каждый элемент нужно передать от одного потока другому, это "неотвратимый, минимально-необходимый" промах на элемент, его можно даже рассматривать не как промах, а как полезную работу в каком-то смысле.
Плюс часть промахов определяется алгоритмом. Например, если и продусер и консумер периодически обращаются к одной переменной — "голове" списка, то это будет индуцировать дополнительные промахи (передачи данных от потока к потоку).
Плюс, возможно, есть какая-то часть промахов, индуцированная реализацией (thunk'и, неявные обращения к неявным переменным и т.д.).

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


L>Да даже для мутабельной очереди это сильно зависит от операций между push/pop.
L>Очередь на основе чистого массива будет тормозить страшно. Если нечистый — то это уже оффтопик.
L>Поэтому сделаю предположение, что в контексте топика ты говоришь немного не о том, несмотря на то, что читать тебя всегда приятно и безусловно познавательно Хотя конечно 150 vs 10 заставляет задуматься. Но ведь это тоже при хорошей игре? 10 выбивать будет не всегда, верно? А только если мы ничего не делаем, а только толкаем, да берём?

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


L>Что такое паддинг?

padding — "прослойка" между переменными, для разнесения их по разным кэш-линиям:

class queue
{
  node* head;
  char padding [arch::cacheline_size];
  node* tail;
};

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

Вот не поленился прогнать тест для single-producer/single-consumer fifo очереди на основе массива.
Это с паддингом между данными продюсера и консумера:
На одном ядре: 18 тактов на enqueue/dequeue
На двухядерном процессоре: 7 тактов на enqueue/dequeue (масштабируемость 2.57)
На двухпроцессорной системе: 12 тактов на enqueue/dequeue (масштабируемость 1.5)

Это закомментировал паддинг:
На одном ядре: 18 тактов на enqueue/dequeue
На двухядерном процессоре: 40 тактов на enqueue/dequeue (масштабируемость 0.45)
На двухпроцессорной системе: 104 тактов на enqueue/dequeue (масштабируемость 0.17)

Разница — одна строчка кода с неиспользуемой переменной.

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

R>Мммм... а в чём подвох? Просто очередь сделать?
R>Что имеется в виду под "универсальными" структурами? Если говорить об обычных "однопоточных" контейнерах, то такие тонкости и не релевантны. А если говорить о контейнерах как о примитивах синхронизации потоков (продюсер-консумер фифо очереди, многопоточные стеки, атомарные регистры и т.д.), то это, имхо, основные тонкости, которые надо учитывать.

Это функциональная очередь, то есть неизменная структура, все якобы мутабельные операции с ней имеют тип Query -> Query. Какие уж тут примитивы синхронизации потоков? То есть либо мы постоянно меняем какой нибудь <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-MVar.html">MVar</a> или <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/stm/Control-Concurrent-STM-TVar.html">TVar</a>, вставляя туда немутабельную очередь, либо сразу честно начинаем пользоваться предназначенными для этого каналами — опять таки <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-Chan.html">обычными</a> или <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/stm/Control-Concurrent-STM-TChan.html">STM</a>. STM, правда, немного не для того предназначен.

А исходная очередь совершенно не пригодна для использования в многопоточной среде — нужны дополнительные механизмы для синхронизации. В чистом-пречистом ФП вопросов то о потоках не стоит — программа это же просто выражение :-)

L>>Насчёт переворачивания — из-за того, что там и не списки то хранятся, а thunk-и, трудно точно сказать, когда и почему там будут промахи в кэше.

R>Какие там будут *дополнительные* промахи, действительно, сложно сказать. Но какие там будут "обязательные" промахи сказать можно. Для фифо-очереди всё очень просто — каждый элемент нужно передать от одного потока другому, это "неотвратимый, минимально-необходимый" промах на элемент, его можно даже рассматривать не как промах, а как полезную работу в каком-то смысле.
R>Плюс часть промахов определяется алгоритмом. Например, если и продусер и консумер периодически обращаются к одной переменной — "голове" списка, то это будет индуцировать дополнительные промахи (передачи данных от потока к потоку).
R>Плюс, возможно, есть какая-то часть промахов, индуцированная реализацией (thunk'и, неявные обращения к неявным переменным и т.д.).

Ну да :-(

R>Хотя честно говоря, про реализации таких вещей в функциональных языках я не сильно осведомлен. Например, с мутабельными структурами продюсер просто постоянно модифицирует "голову" списка, а консумер её периодически считывает. С иммутабельными структурами, консумеру бесполезно постоянно считывать голову списка, т.к. она иммутабельная, он там никаких изменений не увидит. Т.е. должен существовать какой-то дополнительный механизм, через который продюсер сможет передать новую голову списка консумера... хммм... напоминает проблему курицы и яйца...

Во! Проблема решается отказом от иммутабельных структур — потому что это не проблема ФП уже :)

R>Конечно, к приведенным цифрам надо относиться как к очень... не знаю как сказать... абстрактным. Т.е. это цифры, которые я получил на одном конкретном микро-бенчмарке. И скорость и масштабируемость очень зависят и от размера очереди, и от объёма полезной работы, связанной с каждым элементом, и от физического расположения общающихся потоков. Например, если объём полезной работы, связанной с каждым элементом, равен допустим 1 мс, то в принципе достаточно всё равно какая очередь используется. Тем не менее про некоторые реализации можно сказать например "одна реализация всегда не хуже и иногда лучше другой".

Ясно, спасибо.

L>>Что такое паддинг?

R>padding — "прослойка" между переменными, для разнесения их по разным кэш-линиям:
R>

R>class queue
R>{
R>  node* head;
R>  char padding [arch::cacheline_size];
R>  node* tail;
R>};
R>

R>Экстремально ключевой момент в высокопроизводительных примитивах синхронизации. Добавление паддингов в правильных местах может изменять масштабируемость с отрицательной на положительную и увеличивать производительность до 100 раз.

Понял, прикольно. В языках, которые заявляют о себе как кроссплатформенные, вряд ли это возможно сделать явно. Только под конкретный процессор, видимо, и для конкретного компилятора. В Хаскеле есть unboxed + strict значения, только это скорее исключение, чем правило, особенно если вспомнить динамические языки.

R>Вот не поленился прогнать тест для single-producer/single-consumer fifo очереди на основе массива.
R>Это с паддингом между данными продюсера и консумера:
R>На одном ядре: 18 тактов на enqueue/dequeue
R>На двухядерном процессоре: 7 тактов на enqueue/dequeue (масштабируемость 2.57)
R>На двухпроцессорной системе: 12 тактов на enqueue/dequeue (масштабируемость 1.5)

R>Это закомментировал паддинг:
R>На одном ядре: 18 тактов на enqueue/dequeue
R>На двухядерном процессоре: 40 тактов на enqueue/dequeue (масштабируемость 0.45)
R>На двухпроцессорной системе: 104 тактов на enqueue/dequeue (масштабируемость 0.17)

R>Разница — одна строчка кода с неиспользуемой переменной.

Ничего себе! А почему это всё наоборот? Ядра-процессоры стараются как то синхронизировать данные в кэшах или что? На что дополнительное время уходит?

R> :beer:

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

L>Это функциональная очередь, то есть неизменная структура, все якобы мутабельные операции с ней имеют тип Query -> Query. Какие уж тут примитивы синхронизации потоков? То есть либо мы постоянно меняем какой нибудь <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-MVar.html">MVar</a> или <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/stm/Control-Concurrent-STM-TVar.html">TVar</a>, вставляя туда немутабельную очередь, либо сразу честно начинаем пользоваться предназначенными для этого каналами — опять таки <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurrent-Chan.html">обычными</a> или <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/stm/Control-Concurrent-STM-TChan.html">STM</a>. STM, правда, немного не для того предназначен.


Я так понимаю, что многопоточную очередь можно сделать прямо из MVar'ов или TVar'ов, т.е. в каждом узле очереди в каком-то виде будет присутствовать MVar (TVar). Это будут *не* иммутабельные структуры, но тем не менее ФП, т.к. Haskell



L>>>Что такое паддинг?

R>>padding — "прослойка" между переменными, для разнесения их по разным кэш-линиям:
R>>

R>>class queue
R>>{
R>>  node* head;
R>>  char padding [arch::cacheline_size];
R>>  node* tail;
R>>};
R>>

R>>Экстремально ключевой момент в высокопроизводительных примитивах синхронизации. Добавление паддингов в правильных местах может изменять масштабируемость с отрицательной на положительную и увеличивать производительность до 100 раз.

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

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


L>В Хаскеле есть unboxed + strict значения, только это скорее исключение, чем правило, особенно если вспомнить динамические языки.

А там же вроде есть встроенный С


R>>Разница — одна строчка кода с неиспользуемой переменной.

L>Ничего себе! А почему это всё наоборот? Ядра-процессоры стараются как то синхронизировать данные в кэшах или что? На что дополнительное время уходит?

Чтобы записать в переменную ядру/процессору надо получить *всю кэш-линию* в эксклюзивный доступ (себе в кэш), если последним в какую-либо переменную в этой *кэш-линии* записывало другое ядро, то сейчас кэш-линия находится у него в кэше, следовательно надо перемещать кэш-линию от одного ядра другому — это физическое перемещение, которое включает отправку кэш-линии по какой-то шине или каналу между ядрами. На современных многоядерных процессорах Intel/AMD такое перемещение занимает 200-300 тактов.