Immutable Map implementation for huge maps

views:

334

answers:

+6 Q:

Immutable Map implementation for huge maps

If I have an immutable Map which I might expect (over a very short period of time - like a few seconds) to be adding/removing hundreds of thousands of items from, is the standard HashMap a bad idea? Let's say I want to pass 1Gb of data through the Map in <10 seconds in such a way that the maximum size of the Map at any once instant is only 256Mb.

I get the impression that the map keeps some kind of "history" but I will always be accessing the last-updated table (i.e. I do not pass the map around) because it is a private member variable of an Actor which is updated/accessed only from within reactions.

Basically I suspect that this data structure may be (partly) at fault for issues I am seeing around JVMs going out of memory when reading in large amounts of data in a short time.

Would I be better off with a different map implementation and, if so, what is it?

+10 A:

Ouch. Why do you have to use an immutable map? Poor garbage collector! Immutable maps generally require (log n) new objects per operation in addition to (log n) time, or they really just wrap mutable hash maps and layer changesets on top (which slows things down and can increase the number of object creations).

Immutability is great, but this does not seem to me like the time to use it. If I were you, I'd stick with scala.collection.mutable.HashMap. If you need concurrent access, wrap the Java util.concurrent one instead.

You also might want to increase the size of the young generation in the JVM: -Xmn1G or more (assuming you're running with -Xmx3G). Also, use the throughput (parallel) garbage collector.

Rex Kerr 2010-02-19 17:06:41

Yes - I've changed it to use the mutable Map but I though the whole point of FP was that immutability was great! This app should easily run in less than 256Mb of memory from a "how much data does it really need at any one point in time" perspective.

oxbow_lakes 2010-02-19 17:16:36

How great immutability is depends on the application. If you are running an application with, say, trees of message threads being sent around to a bunch of clients, immutability is a godsend--you just send the current tree and you don't have to worry about the data structure itself changing out from under you. (You do still have to catch cases like the client asking to add a comment to a thread that is deleted by the time they respond.) For high-throughput work in private data structures that are turning over very rapidly, immutability provides few advantages and demands a lot of overhead.

Rex Kerr 2010-02-19 17:25:01

@Rex - yeah, that'swhat I'm finding out! So how do Haskell or Clojure manage in these situations? Don't they *enforce* immutability?

oxbow_lakes 2010-02-19 17:29:40

In FP one would prefer a map based on an ordered, balanced tree, rather than one based on a hashtable - exactly because it's hard to get a persistent version of that. From my understanding, FP people are quick to give up a hashtable's O(1) lookup for a balanced tree's O(logn), with a reasoning basically amounting to "who cares about *that* much performance, it doesn't matter, I like immutability more". Well, some people just prefer performance :)

Dimitris Andreou 2010-02-19 17:35:01

AFAICT, Clojure uses Java's collections when it needs mutable data structures. Haskell uses the best available immutable algorithms and then considers an occasional log N as a worthwhile sacrifice for purity.

Rex Kerr 2010-02-19 18:30:32

+4 A:

That would be awful. You say you always want to access the last-updated table, that means you only need an ephemeral data structure, there is no need to pay the cost for a persistent data structure - it's like trading time and memory to gain completely arguable "style points". You are not building your karma by using blindly persistent structures when they are not called for.

Also, a hashtable is a particularly difficult structure to make persistent. In other words, "very, very slow" (basically it is usable when reads greatly outnumber writes - and you seem to talk about many writes).

By the way, a ConcurrentHashMap wouldn't make sense in this design, given that the map is accessed from a single actor (that's what I understand from the description).

Dimitris Andreou 2010-02-19 17:29:14

You're right - I have no requirement for immutability or concurrency. My map is a cache private to a single actor

oxbow_lakes 2010-02-19 17:39:57

I assume, since you are using actors, you want to take advantage of concurrency opportunities. This map/actor, which now sounds like a potential bottleneck, might be a good such opportunity (irrelevant from actors though), i.e. you might benefit by making the map a shared ConcurrentHashMap (not owned by any single actor) and let writers proceed concurrently, if possible/reasonable.

Dimitris Andreou 2010-02-19 17:50:48

The data is the map does not need to be shared between actors - there are about 30 actor-instances, each with their own maps (of data relevant only to them)

oxbow_lakes 2010-02-19 18:01:17

+4 A:

Scala's so-called(*) immutable Map is broken beyond basic usage up to Scala 2.7. Don't trust me, just look up the number of open tickets for it. And the solution is just "it will be replaced with something else on Scala 2.8" (which it did).

So, if you want an immutable map for Scala 2.7.x, I'd advise looking for it in something other than Scala. Or just use TreeHashMap instead.

(*) Scala's immutable Map isn't really immutable. It is a mutable data structure internally, which requires lot of synchronization.

Daniel 2010-02-19 17:39:00

Where do I find an alternative? Is `TreeMap` OK? I can hardly find one in Java

oxbow_lakes 2010-02-19 17:50:02

@oxbow I think people were using `HashTreeMap` as an alternative indeed, now that you mention it.

Daniel 2010-02-19 19:10:43

Scala's immutable map seems to have been fixed recently. The code is a trie now, the old logging scheme seems to be gone.

Seun Osewa 2010-06-09 11:48:16

ansaurus

tags:

views:

answers:

Immutable Map implementation for huge maps

related questions