Is there any Java flyweight pattern implementation out there? [closed]

Question

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.

Sungsungari

You now at least one - java.lang.String.. See also #2910348 – Oliva

You seem to have quite specific requirements, why not write it yourself. – Wile

@Oliver Interned Strings are not collections. – Sungsungari

@Wile 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. – Sungsungari

@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". – Lucid

Answer 1

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[];

Pallette

I know. It has been mentioned before. But it is not a collection. – Sungsungari

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. – Pallette

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. – Sungsungari

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. – Pallette

I have added an example of how you can store the data by column, minimising any per-object overhead. – Pallette

Much improved example. :) Most of my instances will not include object references, luckily. The things that bothers me with it, is that if I store the same class somewhere else as Map key or value, or Set value, I would have to create yet another manual mapping. With a factory/builder based API, I would only create the mapping once, and reuses it for any Collection. – Sungsungari

Answer 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.

Scruff

Yes it is, but it is not a collection. – Sungsungari

Answer 3

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.

Soluk

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. – Sungsungari

Well, I unfortunately did not need a Flyweight since perhaps 15 or 16 years :D – Lucid

Answer 4

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

Schexnayder

Answer 5

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?

Incur

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. – Sungsungari

Oh, and I forgot the reference to the object as well, which is another 4 (or 8) bytes. – Sungsungari

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. – Incur

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. – Sungsungari

Answer 6

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.

Sungsungari