Optimizar verificación ArrayList.contains() con operaciones de bits
El problema
En StellarProtect (plugin Minecraft), el hot-path verificaba constantemente si un material estaba en una lista de materiales protegidos usando ArrayList.contains(). Con 200+ jugadores interactuando con miles de bloques por segundo, esta operación O(n) estaba causando stuttering en el hilo principal. El profiler mostró que el 12% del tiempo de tick se gastaba en estas verificaciones lineales.
Solución
- 1Convertí la lista de materiales a un BitSet donde cada bit representa si un material (por su ordinal) está presente.
- 2La verificación de pertenencia cambió de O(n) a O(1): set.get(material.ordinal()) es una simple operación AND bit a bit con máscara.
- 3Para hash maps con claves potencia de 2, reemplacé hash % capacity por hash & (capacity - 1), que es 10-20x más rápido según JMH.
- 4En generación de IDs compactos usé desplazamientos (value << 8) en lugar de multiplicación (value * 256), porque el compilador no siempre optimiza esto.
- 5Para comparaciones insensibles a mayúsculas, forcé minúsculas con c | 0x20 en lugar de Character.toLowerCase() para evitar llamadas de método.
- 6Máscaras & 0xFF para prevenir extensión de signo al convertir bytes a ints y evitar valores negativos inesperados.
Aprendizajes
- ›BitSet es extremadamente eficiente para conjuntos de enteros densos: usa 1 bit por elemento vs 32+ bytes por entrada en HashSet.
- ›Las operaciones bit a bit son primitivas de CPU: AND/OR/XOR son una sola instrucción vs llamadas de método con overhead.
- ›El módulo con potencias de 2 SIEMPRE debe usar & (n-1) en hot-paths porque es una optimización que el JIT no garantiza.
- ›Los desplazamientos de bits (<<, >>) son útiles más allá de multiplicar/dividir por 2, también para empaquetar datos en enteros.
- ›Las máscaras bit a bit eliminan ramas: if (c >= A && c <= Z) se convierte en una operación sin salto condicional.