Le liste Lisp sono sempre implementate come elenchi concatenati?Le liste Lisp sono sempre implementate come elenchi concatenati?
Si tratta di un problema per quanto riguarda il caching del processore? In tal caso, ci sono soluzioni che utilizzano strutture più contigue che aiutano il caching?
Spesso le implementazioni Lisp possono memorizzare alcuni valori direttamente nelle celle: fixnum, caratteri, ... Per tutto il resto un puntatore verrà memorizzato nel car o cdr.
Al giorno d'oggi quasi tutte le implementazioni che utilizzano le celle di controllo non utilizzano ottimizzazioni come cdr-coding.
La memoria di solito viene migliorata utilizzando un garbage collector di copia/compattazione/generazionale.
copia -> quando uno spazio è pieno, le copie GC lista e assegnerà le nuove cellule uno accanto all'altro in una nuova area di stoccaggio
compattazione -> uno schema per sbarazzarsi di lacune di memoria o simili
generazionale -> oggetti di vita più lunghi saranno promossi in diverse aree di stoccaggio. Quindi una lista che è sopravvissuta ad alcuni GC verrà copiata in un'altra generazione e le celle saranno assegnate una accanto all'altra.
A volte al di sopra di GC le traiettorie sono combinate in modi fantasiosi.
Si noti inoltre che in molti programmi Lisp molte di quelle contro cellule possono essere di breve durata:
(mapcar #'1+
(mapcar #'isqrt '(10 20 30 40 50)) ; <- result is 'garbage'
)
L'elenco dei numeri interi radici quadrate è subito spazzatura. La funzione passerà semplicemente attraverso le nuove celle e allocherà nuove nuove celle e non ci sarà molta cache non locale.
L'allocazione di celle contro può essere ridotta utilizzando operazioni distruttive. Sopra può essere scritto come:
CL-USER 24 > (let ((s (mapcar #'isqrt '(10 20 30 40 50))))
(map-into s #'1+ s))
(4 5 6 7 8)
Questo eliminerà una lista assegnata e migliorerà ulteriormente la località.
A quanto ho capito, le sequenze di Clojures sono implementate come VLists. Sì, gli list sono di solito elenchi collegati in Lisps (anche se sono sicuro che ci sia una build sperimentale o due che usa qualcos'altro).
Le coppie collegate sono la solita implementazione, ma ci sono stati altri approcci in passato.
La codifica CDR è uno schema di compressione di elenchi progettato per migliorare la contiguità e la dimensione dei dati delle liste di controllo supportate nell'hardware su alcune macchine Lisp. L'idea di base è quella di utilizzare un tag per indicare la forma di un contro: una delle possibilità è quella di archiviare i cons dopo direttamente il primo elemento, essenzialmente eliminando il campo cdr.
Questo prossimo problema può essere compresso nello stesso modo, e quindi in situazioni favorevoli si finisce con una struttura a matrice con contiguità eccellente. (Non è un array in quanto deve contenere spazio per le informazioni di codifica e non è possibile indicizzarlo.)
Una delle parti più complesse supporta efficacemente la mutazione sia di car sia di cdr di conse compresse. (Vedi il documento di Steele, "Riordino distruttivo di elenchi con codice CDR"). Se i consoli sono immutabili, lo schema di codifica può essere più semplice. This FAQ ha qualche discussione interessante sui compromessi.
Uno svantaggio della codifica CDR è che, poiché un contro può essere di varie "forme" diverse, è necessaria la spedizione sul tag per le operazioni di lista. Questo introduce le dimensioni del codice e i costi di errata distribuzione dei rami. Questi costi rendono la caratteristica considerevolmente meno attraente, al punto che non conosco nessuna implementazione Lisp moderna che usi la codifica CDR.
Laddove la contiguità è un problema, un programmatore Lisp di solito utilizza semplicemente un array.
Rainer ha già menzionato che varie tecniche di gestione della memoria aiutano la località. Mi piacerebbe presentare due esperimenti, usando SBCL, che illustrano il suo punto.
Prima di tutto, un'utilità rapida per stampare gli indirizzi di ogni svantaggio in un elenco.
(defun print-addresses (list)
(mapl (lambda (cons)
(format t "address: 0x~X~%"
(sb-kernel:get-lisp-obj-address cons)))
list))
Nel primo esperimento, possiamo vedere che l'allocazione è contiguo, in modo che possiamo creare una lista con dieci elementi e frugando nei loro indirizzi prime ci mostra che sono vicini tra loro:
> (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
Secondo esperimento. Cosa succede se facciamo qualche allocazione non correlata in mezzo? Assegniamo una lista di questo tipo a una variabile in modo da poterla usare in seguito.
(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))
Possiamo vedere che gli indirizzi sono più casuali questa volta:
> (print-addresses *another-list*)
address: 0x10046E9AF7
address: 0x10046EB367
address: 0x10046ECB97
address: 0x10046EE827
address: 0x10046EF247
address: 0x10046F1F17
address: 0x10046F2007
address: 0x10046F3FD7
address: 0x10046F5E67
address: 0x10046F6887
Ora, se si invoca il GC con (sb-ext:gc), possiamo vedere che ha confezionato le conses insieme:
> (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
In questi esempi non abbiamo valutato la località degli elementi della lista, immagino che sia un esperimento per un altro giorno. :-)
La risposta "corretta" filosoficamente sarebbe "Lisp non ha liste, solo CONSES". I cons sono tipicamente usati per costruire liste, al punto che molte funzioni nello standard CL e nelle librerie operano su questi tipi di liste. Ma le consegne possono anche essere utilizzate per costruire altri tipi di strutture, come mappe o grafici. Quindi in Lisps (tradizionali) la struttura dei dati fondamentali sono i contro, non la lista. L'elenco è solo una comoda applicazione degli svantaggi. Quindi, per "liste Lisp" si intendono veramente "elenchi implementati con consegne Lisp" e quelli, beh, non possono essere implementati con qualcosa di diverso da conse;)
Quindi ovviamente ci sono tecniche come la codifica CDR, menzionate in altre risposte, che possono essere utilizzate per rappresentare in modo efficiente determinate strutture basate su cons. Ci sono anche librerie che forniscono strutture di dati di lista che non sono basate su conscons collegati (come FSet per Common Lisp).
Ciò è vero per i Lisp "tradizionali" come Common Lisp e Scheme. Clojure ha liste come un tipo di dati fondamentale e AFAIK non ha affatto consegne.
Suppongo che avrebbero dovuto chiamare la lingua CONP. –