Программная транзакционная память с большим общим фрагментом данных
Исходный вопрос
Я новичок в STM. Одна вещь, которую я хотел бы сделать в Haskell, включает в себя большой фрагмент данных и множество легковесных потоков, читающих и записывающих небольшие части этого большого фрагмента данных. Ячейки, из которых читаются и в которые записываются, можно считать по существу случайными и маленькими. STM отлично подходит для этого, но у меня есть несколько вопросов относительно того, как решить эту проблему. Я вижу несколько возможных подходов, каждый из которых имеет некоторые недостатки, а некоторые кажутся просто глупыми. Некоторые комментарии по этим или другим идеям альтернатив были бы очень признательны.
Давайте для простоты предположим, что большой фрагмент данных представляет собой Data.Vector a, где сами элементы малы.
Весь фрагмент данных как один
TVar (Vector a). Я предполагаю, что это приведет к большому количеству копий огромного фрагмента данных, поскольку STM будет думать, что каждая отдельная запись, возможно, повлияла на все общие данные. Наверняка не происходит никакого волшебства, когда STM определяет, что операции чтения и записи очень локализованы, и что согласованность в большом фрагменте данных не требуется?Огромное количество
TVar as, практически по одному на каждый элемент, что дает полностью локализованный STM, но по существу дублирует весьVector a. Это кажется глупым.Компромисс между 1 и 2 путем сегментации данных таким образом, чтобы у меня было разумное количество
TVar (вектор a), соответствующих подвекторам данных. Я чувствую, что это решение слишком сильно зависит от эвристики, например, от того, насколько большими должны быть сегменты.Обмен сообщениями. Вместо того, чтобы каждый рабочий процесс читал и записывал данные с помощью STM, каждый пишет сообщения с запросами на чтение данных или фрагментами данных для записи через некий механизм STM, например
TChan. Эти сообщения получает специальный поток, передавая данные, запрошенные через другойTChan, или беря полученные данные и записывая их в общую структуру данных. Это решение кажется свободным от проблем, связанных с решениями 1-3, но мне также кажется, что оно по существу отказывается от использования тонкостей STM для обеспечения согласованности данных. Скорее, это просто передача сообщений. Конечно, часть передачи сообщений реализована с помощью STM, но моя настоящая проблема решена с передачей сообщений. STM кажется таким замечательным, а передача сообщений так... мда.
Правильно ли я думаю об этом? Есть ли у кого-нибудь подсказки или другие предложения?
Имейте в виду, что у меня нет опыта работы с STM, и я еще не пробовал вышеуказанные решения. Я встану с кресла, но иногда полезно подумать об этих вещах, прежде чем что-то предпринимать.
Приложение: Пятый подход принадлежит Натану Хауэллу и использует TArray.Звучит как то, что я хочу, но в документации говорится:
В настоящее время он реализован как Array ix (TVar e), но в будущем может быть заменен более эффективной реализацией (интерфейс будет однако остаются прежними).
Я понимаю, что это означает, что TArray — это просто мой подход номер 2 в более красивой одежде. Документы, намекающие на «более эффективную» реализацию, интересны, поскольку они намекают на то, что на самом деле существует более приятный подход.
на ответ Вагифа Верди
Ответ Вагифа Верди очень интересен, поэтому я провел небольшой эксперимент, чтобы проверить его. У меня нет времени на сокращение кода прямо сейчас, поэтому тем, кто заинтересован в этом, придется терпеть меня в коде, а не только в содержании самого необходимого. Я решил использовать изменяемый вектор с 10 ^ 8 Int в качестве «большого общего фрагмента данных» и позволить нескольким считывателям/писателям соответствовать потокам, входящим в сетевой сокет.
Обратите внимание, что код даже не читает и не записывает только общие данные. Он просто существует, и каждый поток содержит для него TVar.
Так что же происходит? Я запускаю программу, и она сразу же занимает около 780 МБ ОЗУ, чего и следовало ожидать (это примерно то, что нужно 10^8 Int). Теперь, если я использую netcat для подключения нескольких клиентов и пишу немного текста, который программа должна просто распечатать и даже не записывать в общие данные, загрузка ЦП процесса возрастает до 100% в течение секунды. ! Есть заметная задержка перед отображением текста. С другой стороны, использование памяти остается постоянным (согласно ответу Вагифа Верди). Если я уберу вектор и TVar, то есть уберу все STM и общие данные, все будет очень быстро и отзывчиво, и когда клиент что-то пишет, заметного использования ЦП не будет.
Итак, несмотря на то, что очень приятно видеть, что общие данные на самом деле не дублируются (хотя я полагаю, что на самом деле мне следует выполнять запись в общие данные, чтобы полностью убедиться в этом), существует очень серьезное снижение производительности, связанное с поддержанием согласованности. государство. Тогда для меня остается вопрос: как правильно решать эту проблему, сохраняя тонкости STM?
Спасибо Вагифу Верди за поднятие некоторых очень интересных моментов.