linked list - ¿Las listas Lisp siempre se implementan como listas vinculadas bajo el capó?

linked-list cpu-cache

Question

¿Las listas Lisp siempre se implementan como listas vinculadas bajo el capó?

¿Es esto un problema en lo que respecta al almacenamiento en caché de los procesadores? Si es así, ¿hay soluciones que utilicen estructuras más contiguas que ayuden a almacenar en caché?

Answer 1

Los pares enlazados son la implementación habitual, pero ha habido otros enfoques en el pasado.

La codificación CDR es un esquema de compresión de listas diseñado para mejorar la contigüidad y el tamaño de los datos de las listas de contras compatibles con el hardware en algunas de las máquinas Lisp. La idea básica es usar una etiqueta para indicar la forma de un inconveniente: una de las posibilidades es almacenar las siguientes contras directamente después del primer elemento, esencialmente elidiendo el campo cdr .

Las siguientes desventajas se pueden comprimir de la misma manera, por lo que en situaciones favorables se obtiene una estructura similar a una matriz con una excelente contigüidad. (No es exactamente una matriz, ya que debe haber espacio para la información de etiquetado y no se puede indexar).

Una de las partes complicadas es la mutación eficiente de car y cdr de conses comprimidos. (Consulte el documento de Steele, "Reordenación destructiva de listas codificadas por CDR".) Si los términos son inmutables, el esquema de etiquetado puede ser más simple. Esta pregunta frecuente tiene alguna discusión interesante sobre las compensaciones.

Una desventaja de la codificación de CDR es que debido a que un inconveniente puede ser de varias ''formas'' diferentes, el envío en la etiqueta es necesario para las operaciones de lista. Esto introduce el tamaño del código y los costos de errores de predicción. Estos costos hacen que la característica sea considerablemente menos atractiva, al punto que no conozco ninguna implementación moderna de Lisp que use codificación CDR.

Donde la contigüidad es una preocupación, un programador Lisp usualmente simplemente usaría una matriz.

Answer 2

Rainer ya ha mencionado que varias técnicas de administración de memoria ayudan con la localidad. Me gustaría presentar dos experimentos, usando SBCL, que ilustran su punto.

En primer lugar, una utilidad rápida para imprimir las direcciones de cada uno de los contras en una lista.

(defun print-addresses (list)
  (mapl (lambda (cons)
          (format t "address: 0x~X~%"
                  (sb-kernel:get-lisp-obj-address cons)))
        list))

En el primer experimento, podemos ver que la asignación es contigua, por lo que podemos crear una lista con diez elementos y hurgando en sus direcciones en bruto nos muestra que están muy juntas:

> (print-addresses (loop repeat 10 collect ''dummy))
address: 0x1003F57167
address: 0x1003F57177
address: 0x1003F57187
address: 0x1003F57197
address: 0x1003F571A7
address: 0x1003F571B7
address: 0x1003F571C7
address: 0x1003F571D7
address: 0x1003F571E7
address: 0x1003F571F7

Segundo experimento. ¿Qué pasa si hacemos una asignación no relacionada en el medio? Asignemos una lista así a una variable para poder insertarla más tarde.

(defparameter *another-list*
  (loop repeat 10
        ;; using eval to trick the compiler into
        ;; compiling this piece of dummy code
        do (eval ''(make-array (random 1000)))
        collect ''dummy))

Podemos ver que las direcciones son más aleatorias esta vez:

> (print-addresses *another-list*)
address: 0x10046E9AF7
address: 0x10046EB367
address: 0x10046ECB97
address: 0x10046EE827
address: 0x10046EF247
address: 0x10046F1F17
address: 0x10046F2007
address: 0x10046F3FD7
address: 0x10046F5E67
address: 0x10046F6887

Ahora, si invocamos el GC con (sb-ext:gc) , podemos ver que ha agrupado las conses:

> (sb-ext:gc)
> (print-addresses *another-list*)
address: 0x1004738007
address: 0x1004738017
address: 0x1004738027
address: 0x1004738037
address: 0x1004738047
address: 0x1004738057
address: 0x1004738067
address: 0x1004738077
address: 0x1004738087
address: 0x1004738097

En estos ejemplos no evaluamos la localidad de los elementos de la lista, supongo que es un experimento para otro día. :-)

Answer 3

Según lo entiendo, las secuencias de Clojures se implementan como VLists . Sí, las list generalmente son listas enlazadas en Lisps (aunque estoy seguro de que hay una versión experimental o dos que usan algo más).

Answer 4

Las implementaciones de Lisp a menudo pueden almacenar algunos valores directamente en las células cons: fijos, caracteres, ... Para todo lo demás, un puntero se almacenará en el car o cdr .

Hoy en día, casi todas las implementaciones que usan celdas cons no usan optimizaciones como cdr-coding .

La ubicación de la memoria generalmente se mejora al usar un recolector de basura de copiado / compactación / generacional.

• copiando -> cuando un espacio está lleno, el GC copia la lista y asignará las nuevas celdas una al lado de la otra en una nueva área de almacenamiento

• compactación -> algún esquema para deshacerse de lagunas de memoria o similar

• generational -> objetos vivos más largos serán promovidos a diferentes áreas de almacenamiento. Por lo tanto, una lista que ha sobrevivido a algunos GC se copiará a otra generación y las celdas se asignarán una al lado de la otra.

A veces las estrategias de GC se combinan de manera elegante.

También tenga en cuenta que en muchos programas Lisp muchas de esas células cons pueden ser de corta duración:

(mapcar #''1+
        (mapcar #''isqrt ''(10 20 30 40 50))  ; <- result is ''garbage''
        )

La lista de raíces cuadradas enteras es basura de inmediato. La función simplemente recorrerá las nuevas células cons y asignará nuevas células cons cont y no habrá mucho cache no local.

La asignación de las células cons se puede reducir mediante el uso de operaciones destructivas. Arriba se puede escribir como:

CL-USER 24 > (let ((s (mapcar #''isqrt ''(10 20 30 40 50))))
               (map-into s #''1+ s))
(4 5 6 7 8)

Esto eliminará una lista asignada y mejorará aún más la localidad.

Answer 5

La respuesta filosóficamente "correcta" sería "Lisp no tiene listas, solo CONSE". Las restricciones generalmente se usan para crear listas, hasta el punto de que muchas funciones en el estándar CL y en bibliotecas operan en ese tipo de listas. Pero los conceptos también se pueden usar para construir otros tipos de estructuras, como mapas o gráficos. Entonces, en los Lisp (tradicionales), la estructura de datos fundamental son los contras, no la lista. La lista es solo una aplicación conveniente de los contras. Por lo tanto, por "listas Lisp", usted realmente quiere decir "listas implementadas con consignas Lisp" y esas, bueno, no se pueden implementar con algo diferente de conses;)

Entonces, por supuesto, existen técnicas como la codificación de CDR, mencionadas en otras respuestas, que pueden usarse para representar de manera eficaz ciertas estructuras basadas en contras. También hay bibliotecas que proporcionan estructuras de datos de listas que no están basadas en conses enlazados (como FSet para Common Lisp).

Esto es cierto para Lisps "tradicionales" como Common Lisp y Scheme. Clojure tiene listas como un tipo de datos fundamental y AFAIK no tiene conses en absoluto.