Реализация Immutable Map для огромных карт

Если у меня есть неизменяемая карта, из которой я могу ожидать (за очень короткий период времени — например, несколько секунд) добавления/удаления сотни тысяч элементов, стандартный HashMap - плохая идея? Допустим, я хочу передать 1 Гб данных через Карту за ‹10 секунд таким образом, чтобы максимальный размер Карты в любой момент времени составлял всего 256 Мб.

У меня сложилось впечатление, что карта хранит какую-то «историю», но я всегда буду обращаться к последней обновленной таблице (т.е. я не передаю карту), потому что это частная переменная-член Actor, который обновляется/доступен только из реакций.

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

Будет ли мне лучше использовать другую реализацию карты, и если да, то какая?


immutability out-of-memory scala map scala-2.7
person oxbow_lakes    schedule 19.02.2010    source источник

Ответы (3)


arrow_upward
20
arrow_downward

Ой. Почему вы должны использовать неизменяемую карту? Бедный сборщик мусора! Неизменяемые карты обычно требуют (log n) новых объектов на операцию в дополнение к (log n) времени, или они действительно просто оборачивают изменяемые хеш-карты и наборы изменений слоев поверх (что замедляет работу и может увеличить количество создаваемых объектов).

Неизменяемость — это здорово, но мне кажется, что сейчас не время ее использовать. На вашем месте я бы придерживался scala.collection.mutable.HashMap. Если вам нужен одновременный доступ, вместо этого оберните Java util.concurrent.

Вы также можете увеличить размер молодого поколения в JVM: -Xmn1G или больше (при условии, что вы работаете с -Xmx3G). Также используйте пропускной (параллельный) сборщик мусора.

person Rex Kerr    schedule 19.02.2010
comment
Да, я изменил его, чтобы использовать изменяемую карту, но я думал, что весь смысл FP в том, что неизменность — это здорово! Это приложение должно легко работать в менее чем 256 МБ памяти, исходя из того, сколько данных ему действительно нужно в любой момент времени. - person oxbow_lakes; 19.02.2010
comment
Насколько велика неизменность, зависит от приложения. Если вы запускаете приложение, скажем, с деревьями потоков сообщений, отправляемых множеству клиентов, неизменяемость — это находка: вы просто отправляете текущее дерево, и вам не нужно беспокоиться об изменении самой структуры данных. из-под тебя. (Вам все равно придется отлавливать такие случаи, как запрос клиента на добавление комментария к потоку, который удаляется к моменту ответа.) Для высокопроизводительной работы в частных структурах данных, которые очень быстро обновляются, неизменность дает мало преимуществ и требует много накладных расходов. - person Rex Kerr; 19.02.2010
comment
да, вот что я узнаю! Так как же Haskell или Clojure справляются с такими ситуациями? Разве они не обеспечивают неизменяемость? - person oxbow_lakes; 19.02.2010
comment
В FP лучше использовать карту, основанную на упорядоченном, сбалансированном дереве, а не на основе хеш-таблицы — именно потому, что трудно получить постоянную версию этого. Насколько я понимаю, разработчики FP быстро отказываются от поиска O(1) хеш-таблицы в пользу O(logn) сбалансированного дерева, рассуждая в основном о том, кого волнует такая высокая производительность, она не неважно, мне больше нравится неизменность. Ну, некоторые люди просто предпочитают производительность :) - person Dimitris Andreou; 19.02.2010
comment
AFAICT, Clojure использует коллекции Java, когда ему нужны изменяемые структуры данных. Haskell использует наилучшие доступные неизменяемые алгоритмы, а затем рассматривает случайный журнал N как достойную жертву ради чистоты. - person Rex Kerr; 19.02.2010
comment
В Haskell есть спасательные люки, когда вы не можете получить необходимую производительность от неизменяемых структур данных. Например, операции Haskell Data.HashTable находятся в монаде IO (что, по сути, означает, что они не являются чисто функциональными). - person Kannan Goundan; 19.07.2011

arrow_upward
8
arrow_downward

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

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

Кстати, ConcurrentHashMap в этом дизайне не имеет смысла, учитывая, что доступ к карте осуществляется с одного актора (это я понял из описания).

person Dimitris Andreou    schedule 19.02.2010
comment
Вы правы - у меня нет требований к неизменности или параллелизму. Моя карта — это тайник, приватный для одного актора - person oxbow_lakes; 19.02.2010
comment
Я предполагаю, что, поскольку вы используете акторы, вы хотите воспользоваться преимуществами параллелизма. Эта карта/актор, который сейчас звучит как потенциальное узкое место, может быть хорошей такой возможностью (хотя и не имеет отношения к акторам), т.е. вы можете извлечь выгоду, сделав карту общей ConcurrentHashMap (не принадлежащей ни одному актору) и позволив авторам работать одновременно. , если возможно/разумно. - person Dimitris Andreou; 19.02.2010
comment
Данные карты не нужно разделять между акторами - есть около 30 акторов-экземпляров, каждый со своими картами (данными, относящимися только к ним) - person oxbow_lakes; 19.02.2010
comment
Слишком часто я слышу, что решение проблем с производительностью неизменяемых карт в Scala — это переход к изменяемости... Вы не можете говорить о стилях, когда речь идет о следовании неизменяемым структурам данных в функциональном программировании, это гораздо более фундаментально и важно. Либо мы можем это сделать и на самом деле существует другая парадигма программирования, либо нам приходится сомневаться в себе каждый раз, и поэтому здесь нет реальной жизнеспособной новой парадигмы программирования. - person dividebyzero; 14.09.2017

arrow_upward
4
arrow_downward

Так называемая (*) неизменяемая карта Scala не работает за пределами базового использования вплоть до Scala 2.7. Не верь мне, просто посмотри количество открытых билетов на него. А решение как раз "будет заменено на что-то другое на Scala 2.8" (что и было сделано).

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

(*) Неизменная карта Scala на самом деле не является неизменной. Это изменяемая внутренняя структура данных, которая требует большой синхронизации.

person Daniel C. Sobral    schedule 19.02.2010
comment
Где найти альтернативу? TreeMap в порядке? Я с трудом могу найти его на Java - person oxbow_lakes; 19.02.2010
comment
@oxbow Я думаю, что люди действительно использовали HashTreeMap в качестве альтернативы, теперь, когда вы об этом упомянули. - person Daniel C. Sobral; 19.02.2010
comment
Неизменяемая карта Scala, кажется, была недавно исправлена. Код сейчас примерный, старая схема ведения журнала, похоже, исчезла. - person Seun Osewa; 09.06.2010