Construir colecciones: builders, capacidad y boxing

Hasta aquí las colecciones han aparecido ya construidas, como si listOf y mutableMapOf fueran conjuros neutros que producen la estructura evidente. No lo son. Cada fábrica de la biblioteca estándar toma decisiones concretas sobre qué clase instancia, cuánta memoria reserva y qué garantías ofrece, y esas decisiones son visibles desde fuera con más frecuencia de la que su discreción sugiere: hay una fábrica que devuelve una lista de tamaño fijo respaldada por un array, hay otra que devuelve siempre el mismo objeto compartido, y las que producen conjuntos y mapas eligen deliberadamente una implementación más cara que la obvia para poder prometer algo que la plataforma no promete. Añade a eso el mecanismo de crecimiento por duplicación, el coste del empaquetado de los tipos primitivos y el contrato de sellado de los builders, y tienes el conjunto de hechos que separa construir una colección de construirla bien.

Qué devuelve cada fábrica

Las tres fábricas de listas de solo lectura devuelven tres cosas distintas según cuántos argumentos reciban, y la tercera es la que sorprende. Sin argumentos, listOf devuelve un objeto vacío compartido por todo el programa. Con un argumento, devuelve una lista de un solo elemento especializada. Con varios, devuelve una vista sobre el array de argumentos variables: una lista de tamaño fijo cuyo contenido está respaldado por ese array, no un ArrayList recién copiado.

val vacia = listOf<Int>()          // objeto vacio compartido, sin asignacion
val uno = listOf(42)               // lista especializada de un elemento
val varios = listOf(1, 2, 3)       // vista de tamano fijo sobre el array

val mutable = mutableListOf(1, 2, 3)   // ArrayList de verdad, con copia

Con los conjuntos y los mapas la decisión interesante es otra. setOf y mutableSetOf producen una tabla con lista enlazada, y mapOf y mutableMapOf hacen lo propio, de modo que ambos conservan el orden de inserción al iterar. Es una elección deliberada de la biblioteca estándar frente a la implementación sin orden que sería más barata, y la razón es de ingeniería antes que de rendimiento: un programa cuyos conjuntos iteran en un orden estable produce salidas reproducibles, mensajes de registro comparables entre ejecuciones y pruebas que no fallan de forma intermitente.

val ordenado = mutableSetOf(3, 1, 2)      // itera 3, 1, 2: orden de insercion
val disperso = hashSetOf(3, 1, 2)         // itera en el orden de la tabla
val comparado = sortedSetOf(3, 1, 2)      // itera 1, 2, 3: orden natural

Si de verdad no necesitas el orden de inserción y el coste te importa, las fábricas con prefijo de tabla te dan la versión sin él a cambio de un nodo menos por entrada; y si lo que necesitas es orden por comparación en vez de por llegada, las ordenadas usan un árbol y cambian el coste constante de la búsqueda por uno logarítmico. La lección de fondo es que hay tres estructuras distintas detrás de tres nombres muy parecidos, y que el nombre corto y evidente no apunta a la más barata sino a la más predecible.

Los builders y el contrato de sellado

Cuando la construcción no cabe en una fábrica porque hay condiciones, bucles o pasos opcionales, la alternativa clásica es declarar una lista mutable, llenarla y devolverla convertida a solo lectura. Los builders hacen exactamente eso con dos mejoras. La primera es de alcance: el receptor mutable solo existe dentro de la lambda y no queda ninguna variable mutable en el ámbito exterior. La segunda es de contrato: al terminar, la colección se sella, de modo que cualquier intento posterior de modificarla a través de una referencia que se haya escapado falla en tiempo de ejecución en vez de corromper un resultado ya publicado.

val filas = buildList<Fila> {
    add(cabecera)
    if (incluirTotales) add(totales)
    datos.forEach { add(it.aFila()) }
}

val indice = buildMap<String, Int>(datos.size) {
    datos.forEachIndexed { i, d -> put(d.clave, i) }
}

Los tres builders son funciones inline con un contrato que declara que la lambda se ejecuta exactamente una vez en el sitio, lo que permite al compilador razonar sobre la inicialización de variables y no asigna ningún objeto por la lambda. La sobrecarga que recibe un entero es la que resuelve el problema de la sección siguiente: reserva de antemano la capacidad esperada, que es información que tú sueles tener y la biblioteca nunca.

El sellado conviene verlo fallar una vez para entender qué garantiza exactamente. No impide que el receptor se escape, porque nada puede impedirlo; lo que hace es convertir el uso posterior de esa referencia escapada en un error inmediato y localizado en lugar de en una modificación silenciosa de un valor que otros ya consideran terminado.

var fugado: MutableList<Int>? = null

val resultado = buildList {
    add(1)
    fugado = this          // la referencia sale del ambito
}

fugado?.add(2)             // falla: la coleccion ya esta sellada

Comparado con la alternativa clásica de declarar una lista mutable, llenarla y devolverla como List<T>, el builder gana precisamente en ese punto: en la versión manual la referencia mutable sigue viva en el ámbito exterior y nada impide seguir escribiendo sobre el resultado ya devuelto.

Capacidad inicial y crecimiento por duplicación

Un ArrayList guarda sus elementos en un array, y un array no puede crecer. Cuando se llena, la lista asigna uno nuevo aproximadamente la mitad más grande, copia todo el contenido y descarta el anterior. La capacidad por defecto es diez, así que construir una lista de diez mil elementos elemento a elemento provoca del orden de veinte reasignaciones con sus veinte copias, y la última de ellas copia casi diez mil referencias. El coste amortizado por inserción sigue siendo constante, que es el argumento de los libros de texto, pero el trabajo total y la basura generada no son despreciables cuando la cifra es conocida de antemano.

// Cero reasignaciones: se sabe el tamano final antes de empezar
val destino = ArrayList<Registro>(entradas.size)
entradas.forEach { destino += transformar(it) }

// Lo mismo, idiomatico y sellado al salir
val resultado = buildList(entradas.size) {
    entradas.forEach { add(transformar(it)) }
}

Con los mapas basados en tabla hay un factor adicional que se olvida: además de la capacidad hay un factor de carga, por defecto tres cuartos, y la tabla se redimensiona cuando la ocupación lo supera. Redimensionar una tabla no es solo copiar: obliga a recolocar todas las entradas según su código de dispersión. Por eso la capacidad que hay que pedir para un mapa no es el número de entradas previsto sino ese número dividido por el factor de carga, y por eso buildMap con capacidad es preferible a construir el mapa y confiar en que crezca.

flowchart LR
A[Lista con capacidad diez] --> B[Se llena]
B --> C[Reserva un array mayor]
C --> D[Copia todos los elementos]
D --> E[Descarta el array anterior]
E --> B
F[Capacidad inicial correcta] --> G[Ninguna copia ni basura]

Primitivos, empaquetado y arrays especializados

Los genéricos de la plataforma trabajan sobre referencias, de modo que un List<Int> no guarda enteros de cuatro bytes sino punteros a objetos envoltorio. La diferencia es de un orden de magnitud: donde un array de enteros ocupa cuatro bytes por elemento, la lista ocupa la referencia más la cabecera del objeto más el valor, y añade una indirección en cada lectura y una asignación en cada escritura de un valor fuera del rango de la caché de enteros pequeños que la plataforma reutiliza.

val caros: List<Int> = List(1_000_000) { it }        // un objeto por elemento
val baratos: IntArray = IntArray(1_000_000) { it }   // memoria contigua, sin objetos

val suma = baratos.sum()                             // sin empaquetar nada
val convertida = baratos.toList()                    // aqui si se empaqueta todo

Los tipos especializados que existen son los arrays de cada primitivo y sus variantes sin signo, y su ergonomía es peor a propósito: no hay listas ni conjuntos primitivos en la biblioteca estándar de Kotlin, así que en cuanto necesitas tamaño variable o pertenencia rápida tienes que elegir entre volver a los genéricos o recurrir a una biblioteca externa especializada.

val a = intArrayOf(1, 2, 3)
val b = intArrayOf(1, 2, 3)

a == b                 // false: comparacion por identidad
a.contentEquals(b)     // true: comparacion por contenido
a.toList()             // empaqueta los tres elementos
a.asList()             // vista sobre el array, empaqueta solo al leer

Ese listado recoge las dos trampas que hay que memorizar. La primera es que los arrays no tienen igualdad estructural, ni siquiera los de primitivos, de modo que compararlos con el operador habitual devuelve casi siempre lo que no esperas y hay que usar la operación explícita de contenido. La segunda es la asimetría entre convertir y envolver: la conversión copia y empaqueta todos los elementos de una vez, mientras que la envoltura devuelve una vista de solo lectura sobre el mismo array y solo empaqueta el elemento concreto que se lea, lo que la hace muy preferible cuando solo necesitas pasar el array a una API que pide una lista.