Are there any logical loopholes in ClassIndex?

[endison1986]

@enricostara hello friend， I have a question

This api ClassIndex.getIndexOrAddClasses(Class<?> klass) used for get or create index for component type. If hash codes for component types collide，Does it always return the index of the first component？

[enricostara]

Hi @endison1986 ! Yes, it checks if an index already exists for the Class type before adding a new index

[endison1986]

But，I found that in the dominion framework, only the ClassIndex.getIndexOrAddClass method is called and If there are two classes with the same hash value, B can never add its own index via the ClassIndex.getIndexOrAddObject method and A's index will be returned. If the above situation is true, the useFallbackMap will not work

ClassIndex ci = new ClassIndex();
// If the hashCode of A.class equals the hashCode of B.class
var aIndex = ci.getIndexOrAddObject(A.class);
var bIndex = ci.getIndexOrAddObject(B.class); // aIndex == bIndex

public int getIndexOrAddObject(Object klass) {
    int value = getObjectIndexVolatile(klass);
    if (value != 0) {
        return value;
    }
    return addObject(klass); // If A.class added already, this line never called when getIndexOrAddObject(B.class);
}

public int getObjectIndexVolatile(Object klass) {
    if (useFallbackMap.get()) { // always return false here, 
        return fallbackMap.get((Class<?>) klass);
    }
    int identityHashCode = capHashCode(System.identityHashCode(klass), hashBit);
    return unsafe.getIntVolatile(null, getIdentityAddress(identityHashCode, memoryAddress));
}

[enricostara]

Nope, there is a controlMap. See the addObject(klass) implementation (called by getIndexOrAddObject), use controlMap to see if there is a collision and if so, ClassIndex will start using fallbackMap to avoid any collision.

[endison1986]

If collision, Whether the function getObjectIndexVolatile(klass) will return non-zero

public int getIndexOrAddObject(Object klass) {
    int value = getObjectIndexVolatile(klass); // this line
    if (value != 0) {
        return value;
    }
    return addObject(klass);
}

I test addObject and getIndexOrAddObject with a lot of classes, when I use addObject the ClassIndex.useFallbackMap.get() return true, but when I use getIndexOrAddObject the ClassIndex.useFallbackMap.get() return false.

public static void main(String[] args) throws Exception {
    ClassIndex classIndex = new ClassIndex(14, true, Logging.Context.TEST);
    var cp = com.google.common.reflect.ClassPath.from(getDefaultClassLoader());
    System.out.println(cp.getTopLevelClasses().size());
    for (ClassPath.ClassInfo topLevelClass : cp.getTopLevelClasses()) {
        try {
            final var c = getDefaultClassLoader().loadClass(topLevelClass.getName());
            classIndex.addClass(c);
        }catch (Throwable t) {
        }
    }
    System.out.println(classIndex.useFallbackMap.get());
}

[enricostara]

Yes, you are right. We should find a solution to this problem, but the solution must not affect performance

[endison1986]

Yes, the premise of solving the problem is not affecting performance. Of course, with the current default hashBit(20), it may take hundreds or even thousands of Components to conflict. Projects like mine even have less than 100 Components, but this is indeed a potential risk.

[endison1986]

I added an IndexedObjectCache class instead of controlMap to cache indexed classes. and change the ClassIndex to fix this bug. I don’t know if this plan is reasonable. Please help evaluate and review it. thank you @enricostara

package dev.dominion.ecs.engine.system;

import sun.misc.Unsafe;

/**
 * @author endison1986
 */
public class IndexedObjectCache {
    private static final Unsafe U = UnsafeFactory.INSTANCE;
    private static final int MAX_CAPACITY = 1 << 30;
    private static final long CAPCTL;
    private static final int ABASE;
    private static final int ASHIFT;
    private volatile Object[] values;
    private volatile int capacity;

    static {
        try {
            CAPCTL = U.objectFieldOffset(IndexedObjectCache.class.getDeclaredField("capacity"));
            ABASE = U.arrayBaseOffset(Object[].class);
            int scale = U.arrayIndexScale(Object[].class);
            if ((scale & (scale - 1)) != 0) {
                throw new Error("array index scale not a power of two");
            }
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (Throwable e) {
            throw new Error(e);
        }
    }

    public Object get(int index) {
        return U.getObjectVolatile(values, offset(ABASE, ASHIFT, index));
    }

    public void set(int index, Object value) {
        ensureCapacity(index + 1);
        final long offset = offset(ABASE, ASHIFT, index);
        for (; ; ) {// like cas
            final Object[] before = values;
            U.putOrderedObject(before, offset, value);
            final Object[] after = values;

            if (before == after) {
                return;
            }
        }
    }

    private void ensureCapacity(int minCapacity) {
        int cap;
        while (minCapacity > (cap = capacity)) {
            if (cap < 0) {
                Thread.yield();
            } else if (U.compareAndSwapInt(this, CAPCTL, cap, -1)) {
                Object[] finalArray = values;

                int newCapacity = tableSizeFor(minCapacity);
                if (newCapacity > MAX_CAPACITY) {
                    throw new IndexOutOfBoundsException("" + newCapacity);
                }

                Object[] objs = new Object[newCapacity];

                if (finalArray != null) {
                    System.arraycopy(finalArray, 0, objs, 0, finalArray.length);
                }
                values = objs;
                capacity = newCapacity;
            }
        }
    }
    public int tableSizeFor(final int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAX_CAPACITY) ? MAX_CAPACITY : n + 1;
    }
    public long offset(final long arrayBase, final int arrayShift, final int index) {
        return ((long) index << arrayShift) + arrayBase;
    }
}

/*
 * Copyright (c) 2021 Enrico Stara
 * This code is licensed under the MIT license. See the LICENSE file in the project root for license terms.
 */

package dev.dominion.ecs.engine.system;

import sun.misc.Unsafe;

import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * The ClassIndex class is the cornerstone of Dominion.
 * In less than 2 nanoseconds, this implementation can provide a progressive int value for each different component type.
 * This allows you to use the blazing fast counting sort algorithm - with O(n+k) time complexity - to sort component
 * types (even finding duplicates) and implement a very efficient {@link IndexKey} to represent a multi-component type
 * key for Map.
 */
public final class ClassIndex implements AutoCloseable {
    public final static int INT_BYTES_SHIFT = 2;
    public static final int DEFAULT_HASH_BIT = 20; // 1MB -> about 1K classes
    public static final int MIN_HASH_BIT = 14;
    public static final int MAX_HASH_BIT = 24;
    private static final System.Logger LOGGER = Logging.getLogger();
    private static final Unsafe unsafe = UnsafeFactory.INSTANCE;
    private final IndexedObjectCache cache = new IndexedObjectCache();
    private final int hashBit;
    private final long memoryAddress;
    private final AtomicBoolean useFallbackMap = new AtomicBoolean(false);
    private final boolean fallbackMapEnabled;
    private final AtomicInteger atomicIndex = new AtomicInteger(0);
    private final int capacity;
    private int index = 1;
    private final ClassValue<Integer> fallbackMap = new ClassValue<>() {
        @Override
        protected Integer computeValue(Class<?> type) {
            return index++;
        }
    };

    public ClassIndex() {
        this(DEFAULT_HASH_BIT, true, Logging.Context.TEST);
    }

    public ClassIndex(int hashBit, boolean fallbackMapEnabled, Logging.Context loggingContext) {
        this.hashBit = Math.min(Math.max(hashBit, MIN_HASH_BIT), MAX_HASH_BIT);
        this.fallbackMapEnabled = fallbackMapEnabled;
        capacity = (1 << hashBit) << INT_BYTES_SHIFT;
        memoryAddress = unsafe.allocateMemory(capacity);
        unsafe.setMemory(memoryAddress, capacity, (byte) 0);
        if (Logging.isLoggable(loggingContext.levelIndex(), System.Logger.Level.DEBUG)) {
            LOGGER.log(
                    System.Logger.Level.DEBUG, Logging.format(loggingContext.subject()
                            , "Creating " + this
                    )
            );
        }
    }

    private static long getIdentityAddress(long identityHashCode, long address) {
        return address + (identityHashCode << INT_BYTES_SHIFT);
    }

    public int getHashBit() {
        return hashBit;
    }

    public int addClass(Class<?> newClass) {
        return addObject(newClass);
    }

    public int addObject(Object newClass) {
        if (useFallbackMap.get()) {
            return fallbackMap.get((Class<?>) newClass);
        }
        int identityHashCode = capHashCode(System.identityHashCode(newClass), hashBit);
        long i = getIdentityAddress(identityHashCode, memoryAddress);
        int currentIndex = unsafe.getInt(i);
        if (currentIndex == 0) {
            int idx = fallbackMapEnabled ?
                    fallbackMap.get((Class<?>) newClass) :
                    atomicIndex.incrementAndGet();
            unsafe.putIntVolatile(null, i, idx);
            cache.set(idx - 1, newClass);
            return idx;
        } else {
            if (cache.get(currentIndex - 1) != newClass) {
                int idx = fallbackMap.get((Class<?>) newClass);
                useFallbackMap.set(true);
                return idx;
            }
        }
        return currentIndex;
    }

    public int getIndex(Class<?> klass) {
        return getObjectIndex(klass);
    }

    public int getObjectIndex(Object klass) {
        if (useFallbackMap.get()) {
            return fallbackMap.get((Class<?>) klass);
        }
        int identityHashCode = capHashCode(System.identityHashCode(klass), hashBit);
        int index = unsafe.getInt(getIdentityAddress(identityHashCode, memoryAddress));
        if (index != 0 && cache.get(index - 1) == klass) {
            return index;
        }
        return 0;
    }

    public int getObjectIndexVolatile(Object klass) {
        if (useFallbackMap.get()) {
            return fallbackMap.get((Class<?>) klass);
        }
        int identityHashCode = capHashCode(System.identityHashCode(klass), hashBit);
        int index = unsafe.getIntVolatile(null, getIdentityAddress(identityHashCode, memoryAddress));
        if (index != 0 && cache.get(index - 1) == klass) {
            return index;
        }
        return 0;
    }

    public int getIndexOrAddClass(Class<?> klass) {
        return getIndexOrAddObject(klass);
    }

    public int getIndexOrAddObject(Object klass) {
        int value = getObjectIndexVolatile(klass);
        if (value != 0) {
            return value;
        }
        return addObject(klass);
    }

    public int[] getIndexOrAddClassBatch(Class<?>[] classes) {
        int[] indexes = new int[classes.length];
        for (int i = 0; i < classes.length; i++) {
            indexes[i] = getIndexOrAddClass(classes[i]);
        }
        return indexes;
    }

    /**
     * Provides a multi-component type key by implementing the counting-sort algorithm
     *
     * @param objects the given components
     * @return the multi-component type key
     */
    @SuppressWarnings("ForLoopReplaceableByForEach")
    public IndexKey getIndexKey(Object[] objects) {
        int length = objects.length;
        boolean[] checkArray = new boolean[index + length + 1];
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < length; i++) {
            int value = getIndexOrAddClass(objects[i].getClass());
            if (checkArray[value]) {
                throw new IllegalArgumentException("Duplicate object types are not allowed");
            }
            checkArray[value] = true;
            min = Math.min(value, min);
            max = Math.max(value, max);
        }
        return new IndexKey(checkArray, min, max, length);
    }

    @SuppressWarnings("ForLoopReplaceableByForEach")
    public IndexKey getIndexKeyByType(Class<?>[] classes) {
        int length = classes.length;
        boolean[] checkArray = new boolean[index + length + 1];
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < length; i++) {
            int value = getIndexOrAddClass(classes[i]);
            if (checkArray[value]) {
                throw new IllegalArgumentException("Duplicate object types are not allowed");
            }
            checkArray[value] = true;
            min = Math.min(value, min);
            max = Math.max(value, max);
        }
        return new IndexKey(checkArray, min, max, length);
    }

    public <E extends Enum<E>> IndexKey getIndexKeyByEnum(E enumValue) {
        int cIndex = getIndex(enumValue.getClass());
        cIndex = cIndex == 0 ? getIndexOrAddClass(enumValue.getClass()) : cIndex;
        return new IndexKey(new int[]{cIndex, enumValue.ordinal()});
    }

    private int capHashCode(int hashCode, int hashBits) {
        return hashCode >> (32 - hashBits);
    }

    public int size() {
        return fallbackMapEnabled ?
                index - 1 :
                atomicIndex.get();
    }

    public void useUseFallbackMap() {
        useFallbackMap.set(true);
    }

    @Override
    public void close() {
        unsafe.freeMemory(memoryAddress);
    }

    @Override
    public String toString() {
        return "ClassIndex={"
                + "hashBit=" + hashBit
                + ", capacity=" + capacity + "|off-heap"
                + '}';
    }
}

[enricostara]

Hi @endison1986 , did you run any benchmarks? You can use the ClassIndex benchmarks already provided to see the difference by running with and without your change.

[endison1986]

this result is with my change

Benchmark                               Mode  Cnt  Score   Error  Units
ClassIndexBenchmark.addClass            avgt    3  3.382 ± 0.246  ns/op
ClassIndexBenchmark.addClassFallback    avgt    3  3.243 ± 0.139  ns/op
ClassIndexBenchmark.getIndex            avgt    3  3.380 ± 0.212  ns/op
ClassIndexBenchmark.getIndexFallback    avgt    3  3.232 ± 0.064  ns/op
ClassIndexBenchmark.getIndexOrAddClass  avgt    3  3.845 ± 0.420  ns/op
ClassIndexBenchmark.hashGet             avgt    3  3.769 ± 0.044  ns/op
ClassIndexBenchmark.hashPut             avgt    3  9.434 ± 0.069  ns/op

this result is without my change

Benchmark                               Mode  Cnt  Score   Error  Units
ClassIndexBenchmark.addClass            avgt    3  4.807 ± 0.657  ns/op
ClassIndexBenchmark.addClassFallback    avgt    3  3.240 ± 0.034  ns/op
ClassIndexBenchmark.getIndex            avgt    3  1.565 ± 0.640  ns/op
ClassIndexBenchmark.getIndexFallback    avgt    3  3.242 ± 0.369  ns/op
ClassIndexBenchmark.getIndexOrAddClass  avgt    3  2.200 ± 0.205  ns/op
ClassIndexBenchmark.hashGet             avgt    3  3.771 ± 0.207  ns/op
ClassIndexBenchmark.hashPut             avgt    3  9.430 ± 0.030  ns/op

The optimized code performance is basically the same as ClassValue. There is a certain performance improvement on addClass because a thread-safe array is used instead of ConcurrentHashMap. However, there is additional performance loss on getIndex and getIndexOrAddClass, mainly due to the addition of conflict detection.

I modified the implementation of IndexedObjectCache and added volatile get and non-volatile get methods. The new addClass and getIndex methods have a certain performance improvement.

public Object get(int index) {
    return U.getObject(values, offset(ABASE, ASHIFT, index));
}

public Object getVolatile(int index) {
    return U.getObjectVolatile(values, offset(ABASE, ASHIFT, index));
}

This is the new benchmark result after optimization

Benchmark                               Mode  Cnt  Score   Error  Units
ClassIndexBenchmark.addClass            avgt    3  2.560 ± 0.432  ns/op
ClassIndexBenchmark.addClassFallback    avgt    3  3.258 ± 0.277  ns/op
ClassIndexBenchmark.getIndex            avgt    3  2.586 ± 0.545  ns/op
ClassIndexBenchmark.getIndexFallback    avgt    3  3.258 ± 0.292  ns/op
ClassIndexBenchmark.getIndexOrAddClass  avgt    3  3.801 ± 0.006  ns/op
ClassIndexBenchmark.hashGet             avgt    3  3.773 ± 0.151  ns/op
ClassIndexBenchmark.hashPut             avgt    3  9.436 ± 0.126  ns/op

[enricostara]

Hi @endison1986 , did you also have the chance to run the ClassIndexTest to see if the new optimized version is still passing all the tests?

[endison1986]

After modify the code, I ran the ClassIndexTest and it passed. But I did not modify ClassIndexTest

[endison1986]

I optimized the code, and get a new benchmark result, and it also passed unit test.

Benchmark                               Mode  Cnt  Score   Error  Units
ClassIndexBenchmark.addClass            avgt    3  3.284 ± 0.652  ns/op
ClassIndexBenchmark.addClassFallback    avgt    3  3.229 ± 0.033  ns/op
ClassIndexBenchmark.getIndex            avgt    3  2.560 ± 0.171  ns/op
ClassIndexBenchmark.getIndexFallback    avgt    3  3.234 ± 0.093  ns/op
ClassIndexBenchmark.getIndexOrAddClass  avgt    3  2.572 ± 0.412  ns/op
ClassIndexBenchmark.hashGet             avgt    3  3.773 ± 0.362  ns/op
ClassIndexBenchmark.hashPut             avgt    3  9.511 ± 1.507  ns/op

I optimized the getObjectIndex and addObject methods, put the detection of memory inconsistencies caused by concurrency into addObject as much as possible.

public int getIndexOrAddObject(Object klass) {
    int value =  getObjectIndex(klass); // use getObjectIndex instead of getObjectIndexVolatile
    if (value != 0) {
        return value;
    }
    return addObject(klass);
}

public int addObject(Object newClass) {
    if (useFallbackMap.get()) {
        return fallbackMap.get((Class<?>) newClass);
    }
    int identityHashCode = capHashCode(System.identityHashCode(newClass), hashBit);
    long i = getIdentityAddress(identityHashCode, memoryAddress);
    int currentIndex = unsafe.getInt(i);
    if(currentIndex == 0) {
        int idx = fallbackMapEnabled ? fallbackMap.get((Class<?>) newClass) : atomicIndex.incrementAndGet();
// use cas to check, is there an index to an existing class
        if(unsafe.compareAndSwapInt(null, i, 0, idx)) {
            cache.set(idx - 1, newClass);
            return idx;
        } else {
// whether the existing index and the new index are the same. If they are different, it means there is a hash conflict.
            if(idx != unsafe.getIntVolatile(null, i)) {
                useFallbackMap.set(true);
            }
            return idx;
        }
    } else {
        if (cache.getVolatile(currentIndex - 1) != newClass) {
            int idx = fallbackMap.get((Class<?>) newClass);
            useFallbackMap.set(true);
            return idx;
        }
    }
    return currentIndex;
}

[enricostara]

awesome! I think you are ready now to create a pull request for the develop branch (not the main)

[endison1986]

sorry, I forget to add the lic header to the IndexedObjectCache file

[enricostara]

You can add it, the PR is still open with other minor changes requested