6

I've been looking for a flyweight pattern implementation and gave up after reaching page 20 of Google search. While there are countless stupid examples out there, it seems no one has ever published are reusable implementation in Java.

For me, flyweight really only makes sense if you have to keep many such instances, so it has to be implemented as a collection. What I would like is a Factory that takes a byte/short/int/long mapper implementation, and returns either a List, Set or Map, that looks like a normal Object collection, but stores it's data internally as an array of primitive, thereby saving lots of ram. The mapper would take an object of type X, and map it to a primitive, or do it the other way around.

Is there something like that available somewhere?

[EDIT] I am looking for a Collection library that support this pattern, not just any example, of which there are hundreds.

5
  • 1
    You now at least one - java.lang.String.. See also stackoverflow.com/questions/2909848/… Jul 27, 2011 at 7:49
  • 2
    You seem to have quite specific requirements, why not write it yourself. Jul 27, 2011 at 7:58
  • @Oliver Interned Strings are not collections. Jul 27, 2011 at 10:07
  • @NimChimpsky No I have not. Flyweight is a well-known GOF pattern, and it therefore not a "special" requirement. I could write it myself in a an hours or two, but I try not to reinvent the wheel. Jul 27, 2011 at 10:10
  • @Sebastien Diot, you are not reinventing the wheel by writing your own implementation. What you want sounds like a very special case anyway. How do you think a generic library should be parametrized to your case? Patterns describe general ideas for solutions, usually they don't describe "library ready code". Jul 28, 2011 at 12:17

6 Answers 6

3

If you want to replace List, you can use TByteArrayList instead. If youw ant to replace List where MyClass { int a; T object; } you can use TIntObjectHashMap instead.

If you want to replace something with two fields which must be ordered or three or more fields, you need to implement your own class which wraps arrays to hold the data. This is using a column based table model.

e.g.

class MyClass {
    byte b;
    int i;
    String s;
}

class MyClassList {
    int size = 0;
    int capacity;
    byte[] bytes;
    int[] ints;
    String[] strings;

    MyClassList(int capacity) {
        this.capacity = capacity;
    }

    public void add(MyClass myClass) {
        if (size == capacity) resize();
        bytes[size] = myClass.b;
        ints[size] = myClass.i;
        strings[size] = myClass.s;
        size++;
    }

    public void get(MyClass myClass, int index) {
        if (index > size) throw new IndexOutOfBoundsException();
        myClass.b = bytes[index]; 
        myClass.i = ints[index];
        myClass.s = strings[index];
    }
}

From Java 5.0, the auto-boxing caches are examples of flyweights.

Integer i1 = 1;
Integer i2 = 1;
System.out.println(i1 == i2); // true, they are the same object.

Integer i3 = -200;
Integer i4 = -200;
System.out.println(i3 == i4); // false, they are not the same object.

If you want to read the code, have a look at Integer.valueOf(int) in your IDE or http://www.docjar.com/html/api/java/lang/Integer.java.html line 638

EDIT: Autoboxing for Integer uses IntegerCache which is a collection. An ArrayList is a class which wraps an array and has a size...

private static class IntegerCache {
    static final int high;
    static final Integer cache[];
6
  • I know. It has been mentioned before. But it is not a collection. Jul 27, 2011 at 10:14
  • Being pedantic, Integer.valueof(String) and Integer.valueof(int) are not the same. In early versions of Java, the former method didn't use the cache. What do you mean by a collection? IntegerCache is basically the same as an ArrayList IMHO. Jul 27, 2011 at 10:22
  • Sorry, I read it too quickly. A collections is something List<MyClass>, where MyClass is a class I implemented myself, with a "small" state. And I want the collection to behave just like a very big List<MyClass>, except that it internally store the state of MyClass using a primitive type, instead of an object reference. Jul 27, 2011 at 10:32
  • That rather depends on what MyClass contains. If you want a mix of primitives and references, you may not be saving as much as you think. Jul 27, 2011 at 10:39
  • I have added an example of how you can store the data by column, minimising any per-object overhead. Jul 27, 2011 at 10:47
2

I think, Integer.valueOf(String s) is quite a flyweight. Because, as far as I know, it keeps some amount of the created Integers internally, so, when you pass the String that you have passed before - it returns you an existing instance.

1
  • Yes it is, but it is not a collection. Jul 27, 2011 at 10:10
1

Have you seen Gang of Four -- Design Patterns? I shall rewrite theirs implementation (albeit it is in C++) if you want to, but a little bit later.

This is one of those book you should have -- never know when it might come in handy.

2
  • Yes, that is where I come from. I just can't believe that no one out there has thought of doing a reusable implementation based on collections. Jul 27, 2011 at 10:16
  • Well, I unfortunately did not need a Flyweight since perhaps 15 or 16 years :D Jul 28, 2011 at 12:22
1

For your requirement i think you should try Trove or Colt.These library's support primitive collections.

1

GNU Trove does something like that with the gnu.trove.decorator package (Map and Set only, not List).

This sort of thing is quite inefficient though, I doubt there are many situations where the trade-off is worth it.

Why not just use appropriate primitive collections?

4
  • I was thinking of using Trove as storage if I had to do it myself. I did not know of the Decorators. This seems about as close as it gets. That depends on how you define inefficient. A Java object requires 8 bytes, plus data. If the data is one byte, and you have say, 100,000,000 of them in memory, then flyweight is very efficient, if you ask me. That is 1/9 of the memory footprint, just for maybe one more array access to map a byte to an instance. Jul 27, 2011 at 10:27
  • Oh, and I forgot the reference to the object as well, which is another 4 (or 8) bytes. Jul 27, 2011 at 10:33
  • I didn't mean flyweight in general, just constantly wrapping/unwrapping primitives to pretend that you're a Collection. Every time you iterate that 100,000,000 set, it will create and discard an new object for each item. The Trove docs in particular are adamant that this shouldn't be used for anything performance sensitive.
    – Dmitri
    Jul 27, 2011 at 11:27
  • If you can make your simple classes immutable, you could cache and reuse them, reducing GC to a minimum. This is what I want to do. Jul 27, 2011 at 16:08
0

I've made a test-program to see how well Flyweight would work in Java. For the record, I'll describe my results here. YMMV

1) If you have several fields in you objects, you will save some CPU by mashing them together in a single int or long. This is a pain to program and error prone, but it is a few percent faster, because multiple array access are more expensive than bit manipulation. More so as the number of fields grow.

2) For small instances (4 bytes of state) It will run about 25% slower then storing the instance directly. But, ONLY if you don't create a new instance on every get. This is where the real problem is. Having to create a new instance on every get is very expensive; in that case, it's not 25% slower, but 500% slower!

3) I see two way of saving the instance creation on get:

A) Your get method fills-in a pre-existing instance, instead of creating a new one. In other words, you pass a result object as input to your get method.

B) You use immutable instances, cache them, and return a cached instance from get. This is only useful if your list index is significant, and you expect to reuse the same values many times in your list. If you do this, then you may as well store directly a reference to your cached instance in your collection, instead of some state, because then you only pay the 4 bytes per instance for the reference anyway. In that case, your state would have to be 2 bytes or less before it made sense to store the state instead of a reference.

So, as final answer, the reason there is no general purpose library out there for Flyweight is that it only pays under specific conditions, otherwise it's not really worth it.

Not the answer you're looking for? Browse other questions tagged or ask your own question.