A different kind of Interner (DeepInterner)
Andreas Petersson
I had a practical problem Friday afternoon at work, where i built some
highly-redundant data structures in memory, and i thought about getting
them smaller.
I had this idea, that one could detect redundancies in immutable data
structures at Runtime, and replace references inside them such that not
two single objects left in the structure would be equal - but instead
both are the same reference.
One main (possibly flawed) assumption is that if an Class or Instance is
declared immutable by the programmer - then all its Fields, Arrays, etc
can also be treated as immutable, since they should not have any further
References except inside the immutable object.
So I implemented this over the weekend.
it can be used like this:
List<Integer> intern= deepInterner.intern(ImmutableList.of(-1234, -1234));
assertTrue(intern.get(0) == intern.get(1));
unfortunately, the Interner interface in guava is a bit too rigid for my
usage, so i did not implement it.
i prefer this method declaration: public <T> T intern(T object) {...}
since the interner will not handle one type of object exclusively but
all of them.
for seeing the possible benefits i used this instrumentation for
counting the actual memory usage:
http://www.javaspecialists.eu/archive/Issue142.html
i originally had a 40 MB ImmutableListMultimap that shrinked down to
13MB using "regular" interning. this was further reduced to 3MB with
deep interning.
i dumped the output of this experiment at:
http://code.google.com/p/deep-interner
the core of the classes is here: (actual code is only about 70 lines)
http://code.google.com/p/deep-interner/source/browse/trunk/src/at/petersson/interner/DeepInterner.java
the largest portion of the code is spent determining if an object is
immutable or not.
the current rough approach for that is:
a recursive checker for truly immutable objects (most safe way but
unfortunately not enough for real-world usage)
a rough list of known JDK immutables (tbd)
a provided @Immutable annotation (you can use your own or one from the
jsr-305 or any combination)
the ImmutableXXXX collections in the guava-libraries
So my questions to you:
What do you think of this idea?
Will this actually work in real-world scenarios?
What kind of issues will this produce?
Am I missing some obviously Immutable classes?
left todo:
*) delegate actual interning to one of the guava interners instead of
the primitive one
*) sort out possible threading issues, document
*) design for better extensibility (e.g. add own classes to
ImmutabilityChecker)
*) find other bugs hidden
*) provide some other smart class specific optimizations like
ArrayList#trimToSize() which can be executed once i know an object is
immutable
*) or even switch out HashMap -> RegularImmutableMap while interning
Dimitris Andreou
Did you try create your objects in (reverse) topological order? Then you would never have to replace references to achieve your object canonicalization. If you're doing object trees/dags, the topological order induces a dynamic program, and you can have 'final' on all fields. If you have cycles, your objects are not trully immutable (at least one is modified after construction), and you would need after-the-fact reference replacement indeed.
It is known though that the subconscious conspires on fridays making up interesting problems (looking forward to the weekend, as a famous song recently clarified); this doesn't sound like the typical realistic problem one gets to deal with :-)
> guava-...@googlegroups.com
> Project site: http://guava-libraries.googlecode.com
> This group: http://groups.google.com/group/guava-discuss
>
> This list is for general discussion.
> To report an issue: http://code.google.com/p/guava-libraries/issues/entry
> To get help: http://stackoverflow.com/questions/ask (use the tag "guava")
Dimitris Andreou
Ps: there is a simpler, more direct and accurate way to measure memory consumption (i think i called it memory-measurer or so). Heinz (with whom i used to live in the same greek island once upon a time) knows this but was rather lazy to report it in his newsletter. Give it a try!