Libgdx: IntMap capacity limitations

[tomcashman]

Issue details

Current IntMap implementation seems to have a maximum capacity around 11425 entries. I've tested on both 1.9.10 and 1.9.11-SNAPSHOT. I've also tried generating a hashcode() and equals() method for the TestObject.

See unit test below as reproduction.

Reproduction steps/code

import com.badlogic.gdx.math.MathUtils;
import com.badlogic.gdx.math.RandomXS128;
import com.badlogic.gdx.utils.IntMap;
import org.junit.Assert;
import org.junit.Test;

public class IntMapTest {

    @Test
    public void testLargeMap() {
        final int totalEntries = 11427;

        final float minX = -64000f;
        final float minY = -38400f;
        final float maxX = Math.abs(minX);
        final float maxY = Math.abs(minY);

        MathUtils.random = new RandomXS128(1024);

        final IntMap<TestObject> intMap = new IntMap<TestObject>(totalEntries);
        for(int i = 0; i < totalEntries; i++) {
            final TestObject testObject = new TestObject();
            testObject.x = MathUtils.random(minX, maxX);
            testObject.y = MathUtils.random(minY, maxY);

            intMap.put(testObject.getIndex(), testObject);
        }
        Assert.assertEquals(totalEntries, intMap.size);
    }

    private class TestObject {
        float x, y;

        public int getIndex() {
            final int row = MathUtils.floor(y / 8f);
            final int column = MathUtils.floor(x / 8f);
            return (row * ((64000 / 8))) + column;
        }
    }
}

[tommyettinger]

Looking into it now.

[tommyettinger]

There's no issue here; when you insert the same key into a Map, it replaces the original value with the new value, and returns the original value (see: IntMap.put() docs, or Map.put() in the JDK). And that's all that's happening; your test always inserts 3 keys (results of getIndex()) when that key already exists in the IntMap, and 11424 are inserted with no duplicate present. I added debug prints when an index is repeated:

21094870 was the same as 21094870
-13869065 was the same as -13869065
-17368612 was the same as -17368612

expected:<11427> but was:<11424>
Expected :11427
Actual   :11424

That's 3 duplicates, and 3 less items in the IntMap as a result. If 11424 was a hard maximum, then the following would be impossible:

21094870 was the same as 21094870
-13869065 was the same as -13869065
-17368612 was the same as -17368612

expected:<12427> but was:<12424>
Expected :12427
Actual   :12424

But we actually can get more than 11424 items in a thoroughly-tested Map implementation... One of the many tests this went through in January for a PR I made involved benchmarking the libGDX collections with 100,000 or 1,000,000 entries put into it, so I was pretty confident that it could handle 11,427.

This test does expose a quirk of 1.9.10's hash-based collections, and it's another reason that PR for 1.9.11 matters -- ObjectMap, ObjectSet, IntMap, IntIntMap, IntFloatMap, LongMap, IdentityMap, OrderedMap, and OrderedSet (did I miss any?) will rarely call MathUtils.random(2) internally, which messes up an otherwise deterministic set of calls to MathUtils' random number generation methods with a seeded RandomXS128 or Random object. That means the floats handed to TestObject are different in 1.9.10, in 1.9.11, and in 1.9.10 with all IntMap calls removed (just logging the floats generated by MathUtils). There still isn't a capacity limit, and the behavior observed is still the expected, documented behavior for a Map, but the actual size of the IntMap will be different because the stream of random numbers it is given is different on libGDX 1.9.10 (1.9.11 is only slightly different, with two repeat values instead of 3, but all of the numbers after a certain point are different because it doesn't compete with IntMap's calls to MathUtil's static Random variable).

[tomcashman]

Thanks for investigating! I'll re-review how I'm calculating my indices in-game but there shouldn't be duplicates. Must have just been a coincidence that it was always 11425 entries on both the game and the unit test. I'll re-open the issue if I pinpoint anything in the IntMap.