Memory bound алгоритмы и haskell

нужно создать большую матрицу

Ну будет у тебя кэш в lru, так? А хранить всю матрицу где? mmap? Чем здесь может помочь lrucache?

haskell

большую матрицу

изменяться

в произвольных местах

Эталонный троллинг. Но ладно верю, тебе реально это надо

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

иди дальше учить скалу.

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

LRu, судя по описанию, не подойдёт т.к. это симуляция lru.

Плюс можно поиграться со storable векторами и повыделять объекты там.

А что конкретно нужно? Большая матрица? На сколько большая?

Я не критиковал твой любимый хаскелль, я тоже считаю его хорошим ЯП. «Мутабельная большая матрица в хаскелле» - это просто масляная тема троллинга, был удивлен увидеть тему.

Как вариант: можно же отобразить двухмерную таблицу в одномерную, и загнать в БД. Но с БД я опять-таки никогда не работал. Умеют ли БД кэшировать некие "горячие точки" в произвольных местах?

В haskell есть мутабельные структуры, но не из коробки.

зря я свой коммент удалил. http://www.reddit.com/r/haskell/comments/17jzxn/are_there_examples_of_filebac...

ну тут-то особо троллить не получится, есть же как и мутабельные вектора в ST/IO, а про то, что там хуже (?!) с фьюжоном я думаю те, кто захотят потроллить не знают. Тем более под «большую» матрицу RTS выделит общий свои страницы и разницы с любым другим языком не будет.

Ещё непонятно, что ТС хочет хранить и как, возможно ему хватит storable mutable vector, возможно со структурой описывающей где какой ряд/строка начинается.

и вообще http://ro-che.info/ccc/02.html

storable векторами

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

Да, там эта идея тоже высказывалась. Просто один из первых постов в том треде был про какие-то дебри GHC, я на нём надолго залип.

1). не вижу проблемы, проблемы начинаются когда кол-во данных многобольше оперативки. А так будет большая их часть лежать в свопе, а загружены будут только используемые страницы. Ещё можно взять System.IO.Mmap и переложить заботу об этом на ось (если тебе в итоге нужен файл будет). Так же можно засунуть прогу в свою цгруппу и поменять ей swappines и memory_in_bytes, чтобы явно положить в своп данные.

2). но я так понимаю, что заранее частота не известна? И ещё, какие-либо свойства матрицы используются или это просто хранилище?

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

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

Ещё можно взять System.IO.Mmap и переложить заботу об этом на ось (если тебе в итоге нужен файл будет). Так же можно засунуть прогу в свою цгруппу и поменять ей swappines и memory_in_bytes, чтобы явно положить в своп данные.

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

но я так понимаю, что заранее частота не известна

Нет.

И ещё, какие-либо свойства матрицы используются или это просто хранилище?

Да, хранилище.

не возиться с cgroups

вся возня заключается в трёх коммандах: cgcreate, cgset, cgexec.

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

Логика вычислительных программ не должна быть привязана к каким-либо системным сервисам.

Да что уж там, давайте отвяжем логику от ОС, вдруг там винда будет. И от ЯП тоже отвяжем, вдруг там хаскеля не будет.

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

Да что уж там, давайте отвяжем логику от ОС

Логика и не должна быть привязана к ОС. Это же логика. Прикладной софт должен быть кроссплатформенным.

а не отвергай предлагаемые решения под сомнительными предлогами

Это не решение, а скорее крайняя мера. Я уж скорее свой lru-велосипед напишу.

Логика и не должна быть привязана к ОС.

Прикладной софт должен быть кроссплатформенным.

я вижу противоречия. Ну хотя бы то что из первого не вытекает второе. Это помимо того что есть ОС/environment-зависимые, но от того не менее эффективные средства.

Это не решение, а скорее крайняя мера.

mmap это крайняя мера?

скорее свой lru-велосипед напишу.

чем это будет отличаться от mmap для системы? Точно так же программа может уйти в ненужный своп.

Размер порядка 100к на 100к, но разреженная. Насколько разрфеженная - не могу предсказать.

чем это будет отличаться от mmap для системы

В одной странице могут быть как часто, так и редко используемые данные. Эффективнее свопить сами данные.

ОС/environment-зависимые, но от того не менее эффективные средства.

В научном софте их использовать не принято. C экранной клавиатуры лень расписывать почему.

В научном софте их использовать не принято

Это ты придумал. Лень расписывать откуда я это знаю.

А и не надо расписывать. Достаточно пары контрпримеров.

// модератор скатывает тему в оффтопик, спешите видеть

Достаточно пары контрпримеров.

легко, главное для учёных это публикации, а не код. Поэтому 99% кода делается «лишь бы работало». Конечно, есть и библиотеки, и фреймворки и ещё много чего, но это редкость. Исключения это проектная работа, но и там в бОльшинстве случаев кросс-платформенность не главное. Тем более если это добавляет проблем. Про кросс-платформенность вспоминают на этапе когда пытаются сделать стартап.

Конкретный пример: у меня друг phd делает в области machine learning, анализирует текст на предмет агрессии, троллинга итп. У него был эффективный алгоритм обхода графа, но он был деструктивный для данных. Будь у них код не на яве можно было бы форкнуться и в потомке делать все разрушающие вычисления. А т.к. ява не дружит с форком пришлось нудно писать код для копирования графа.

Я тоже учавствовал на разных стадиях в различных проектах (конкретно p2p вещание и краем уха (на уровне помочь с C) на реранкинге поисковой выдачи). Я знаю что такое наука и какой код там пишется и какие цели при этом ставятся.

Это примеры немного из другой области, во-первых это CS, во-вторых, как я понимаю, софт уровня proof of concept либо какие-то внутренние разработки.

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

Всё, закончим на этом флейм. Считай, что то решение не подходит мне по религиозным соображением или что угодно.

или двух mkdir и echo :)

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

ограничение на уровне OS (хотя да, на кластере его не будет, если не договориться). И да какая тебе разница съест ли оно там всю оперативку, всё равно узел(ы) будет отдан твоей программе полностью.

И главное я не очень понимаю, почему ты об этом паришься сейчас, пока у тебя данных ~оперативке, а не 10-100 оперативок и при этом доступ пойдет в определенные страницы, даже и не задумывайся над кешерами, просто сделай работающую программу. Когда у тебя будет работающая программа - пускай на кластере и у тебя будет время, чтобы её оптимизировать (пока работает старая и появлются новые данные), во-первых ты будешь видеть особенности решения, во-вторых у тебя будет реальный шанс сравнить поведение с предыдущим. Мне кажется, что эффективный алгоритм будет сильно зависеть от особенностей задачи и использовать некий универсальный алгоритм это не лучшая идея, тем более если это просто хранилище - то реализуется это просто.

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

ИМХО, если уж очень хочется можно сделать аналог кеша так: 1). разбить матрицу на блоки разумного размера 2). выделить storable vector максимально позволительного размера, сделать «индекс» описывающий, какие блоки в этом векторе 3). при изменении элемента в блоке повышать соотв порядок в индексе на 1. Если блока нет в индексе - выгружать последний блок и загружать нужный.

И тут тебя ждёт куча unsafe и Ptr :) зато ограничения по памяти будут четко исполнены.

http://en.wikipedia.org/wiki/R-tree

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

Like B-trees, this makes R-trees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory.

даже и не задумывайся над кешерами, просто сделай работающую программу

Собственно я её и сделал - с разреженными матрицами на плюсах. Тут всё даже в память моего ноута влезает, если firefox закрыть (для неполных данных). Просто мне видно, что в задаче есть горячие точки, которые держать в памяти выгодно, а есть много мест, к которым программа обращается один раз за всё время работы. Если бы эти места можно было выгружать, то хватило бы на порядок меньшего объёма памяти.

Т.е. эта задача меня просто натолкнула на рассуждения о том, как можно было бы подобного рода вещи оптимизировать. Казалось бы, для высокоуровневых языков это самая подходящая ниша: производительность упирается только в IO и эффективность алгоритмов, никаких сложных вычислений нет. Странно, что готовых решений почти нет.

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

Собственно я её и сделал - с разреженными матрицами на плюсах.

разреженными матрицами

может с этого начинать надо было? :) меньше месяца назад в cafe было обсуждение про pure-haskell библиотеки для работы с разреженными матрицами, хотя я бы написал байндинги к super-lu.

может с этого начинать надо было

Так это неэффективно же.

анализирует текст на предмет агрессии, троллинга итп

Ссылку на статью можно?

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

Возможно, я тебя обманул. Тогда речь шла, скорее всего, об этой работе (это не совсем то):

http://ceur-ws.org/Vol-762/paper3.pdf

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

Если тебе интересно, могу спросить.

Спасибо за статью, я наконец её осилил. Но там не говорится, собственно, про natural language processing, что меня интересовало. Если можно, спроси своего знакомого.

а какая именно тематика тебя интересует? Знакомых достаточно много, думаю они могут подобрать что-то интересное, не только из того что они пишут :).

а какая именно тематика тебя интересует

Ну, меня заинтересовало, как детектируют эмоциональность текста (на примере оскорблений). Надо думать, это к NLP относится.

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

К любому ресерчу надо относится скептически. Фуфела хватает. Даже если там написано google research fellow.

Про эмоциональность спрошу в понедельник.