Improved more efficient implementation

[dalewking]

Followup to our converation on Dagger2 issue list. I started to write a reply letting you know how I would want to see it implemented, but that seemed to get longer than probably just implementing it myself. But let me see if I can succinctly explain an acceptable solution and note I am also only looking at the inject side of it, you might want to do something similar for the get side of things.

First off as you know there are the two types of injection methods, the MembersInjector type and the simple inject method types. You need to handle the case where both are defined for the same class and choose one of the two (probably the simple injection method) and ignore the other.

So suppose my component defined these injection methods:

void inject(Foo f);
MembersInjector<Foo> redundantFooInjector();
Bar inject(Bar b);
MembersInjector<Baz> bazInjector();

At the top of the Bullet class we need a map from Class to a numeric index. A standard HashMap would work, but not be very efficient as it creates many, many objects and requires boxing integers. You could use something like Trove's TObjectShortHashMap but we don't want code bloat of pulling in a huge library, so I quickly threw together this class which is more efficient and you are free to use that does open addressing with double hashing:

public class ClassIndexHashTable
{
    private final Class<?>[] classes;
            // using char as an unsigned 16-bit integer
    private final char[] values;

    // Size should be a prime number and at least 30% larger than the number of entries to store
    ClassIndexHashTable(int size)
    {
        classes = new Class[size];
        values = new char[size];
    }

    private int lookup(Class<?> c)
    {
        int hash = c.hashCode();
        int index;

        do
        {
            hash = hash * 57 + 43;
            index = Math.abs(hash % classes.length);
        }
        while(classes[index] != null && classes[index] != c);

        return index;
    }

    // returns -1 if not found
    int get(Class<?> c)
    {
        int index = lookup(c);

        return classes[index] == null ? -1 : values[index];
    }

    void put(Class<?> c, char value)
    {
        int hash = lookup(c);

        classes[hash] = c;
        values[hash] = value;
    }
}

So in the Bullet generated class you would have something like this:

private static ClassIndexHashTable injectorMap;

In the constructor you add:

if(injectorMap == null)
{
    injectorMap = new ClassIndexHashTable(5);
    injectorMap.put(Foo.class, 0);
    injectorMap.put(Bar.class, 1);
    injectorMap.put(Baz.class, 2);
}

In the compiler you would need to determine an appropriate size to use based on the number of entries you know you will put in there. The number should be prime and be at least 30% larger than the number of injection methods so that the load factor on the table will be < 0.7. Take the number of injection methods divide by 0.7 and find a prime higher than that value.

Inside that if block you have a line for every injection method (minus the redundant ones). The number is an arbitrary number assigned to each injectable class. It could simply be the index into the array you created of injectable members.

The inject method would then look like this:

Class<?> c = instance.getClass();
while(c != Object.class)
{
    switch(injectorMap.get(c))
    {
        case 0:
            component.inject((Foo)instance);
            return instance;
        case 1:
            return component.inject((Bar)instance);
        case 2:
            component.bazInjector().injectMembers((Baz)instance);
            return instance;
    }

    c = c.getSuperclass();        
}

Another point is that I should be able to call the inject method and NOT throw an exception if there is no injects method because sometimes I might call this from a base class of an object that has no need for injection. So you should divide this into a method that just returns null if no injection was done that is called by another method that throws the exception if null was returned. You can either give them different names or perhaps overload the same name with an additional parameter to differentiate them. Or just make the new contract be that it returns null and the caller can check for null.

[dalewking]

Another way to go and the direction I was initially taking is to instead map from class to MembersInjector which is easy if the component defines only the MemberInjector types of inject methods.

So if you rewrote the map class I gave you to store MembersInjector<?> instead of a number. For classes that only have the simple injection method you have to create a members injector. You could generate an injector for each class, but that leads to bloat in number of classes and methods, so I envision for the example component above you generate something like this:

private class InjectorAdapter<T> implements MembersInjector<T>
{
    private final char index;
    public InjectorAdapter(char index)
    {
        this.index = index;
    }

    public <T> T injectMembers(T instance)
    {
        switch(index)
        {
            case 0:
                return (T)component.inject((Bar)instance);
        }
    }
}

And you could optimize away the switch if there is only one Class or use an if else for 2. And this is only needed in the case where there are classes that only have the simple injection method.

Then in your constructor you have:

if(injectorMap == null)
{
    injectorMap = new ClassIndexHashTable(5);
    injectorMap.put(Foo.class, component.redundantFooInjector());
    injectorMap.put(Bar.class, new InjectorAdapter<Bar>(0));
    injectorMap.put(Baz.class, component.bazInjector());
}

The inject method then becomes:

Class<?> c = instance.getClass();
while(c != Object.class)
{
    MembersInjector<?> injector = injectorMap.get(c);

    if(injector != null)
    {
        return injector.injectMembers(instance);
    }

    c = c.getSuperclass();        
}

This is all more efficient with the members injection method so you would probably want to issue a warning for any classes that only have simple injection methods. This is also why as I originally requested it would be a lot better for this to be built into Dagger 2 because it always has access to the MembersInjector for every class.

[ScottPierce]

@dalewking can you explain what's going on in the lookup method, and why the ClassIndexHashTable size must be at least 30% larger than the necessary size and a prime number?

[dalewking]

It is a necessary part of an open hash table. It needs to be prime so that as you search for a place to insert using the double hashing you will go through every location before wrapping back around to the starting point. The 30% comes from the fact that for decent hash table performance we want to aim for a max load factor of 0.7 (i.e. only 70% of the slots are used).

For understanding the algorithm see: https://en.wikipedia.org/wiki/Hash_table#Open_addressing

Note I did finish my fork of your code to do just the inject part of it. See the generic-component directories here: https://gitlab.com/NobleworksSoftware/NobleInjection/tree/master. Unfortunately, I have not gotten around to finalizing and publishing it.