¿Cómo puedo reutilizar una búsqueda gethash en Common Lisp?

Question

Tengo una tabla hash donde las claves son listas bastante complejas, con sublistas de símbolos y enteros, y el valor debe modificarse dependiendo del valor existente. La tabla se crea con :test #'equal.

que hacer algo similar a esto muchas veces:

(defun try-add (i) 
    (let ((old-i (gethash complex-list table nil))) 
    (if (may-add old-i) 
     (push i (gethash complex-list table))))) 

de perfiles muestra que equal pruebas toman mucho tiempo. Tengo una idea de optimización, que la cantidad de búsquedas gethash podría reducirse de dos a uno. Se puede hacer en C++ reutilizando el iterador, pero no estoy seguro de cómo se haría en Lisp. ¿Algunas ideas?

Answer 1

No haga nada especial, porque la implementación lo hace por usted.

Por supuesto, este enfoque es específico de la implementación, y el rendimiento de la tabla hash varía entre las implementaciones. (Pero las preguntas de optimización son siempre específicas de la implementación.)

La siguiente respuesta es para SBCL. Recomiendo comprobar si las tablas hash de Lisp realizan la misma optimización. ¡Quejarse con su proveedor si no lo hacen!

Lo que sucede en SBCL es que la tabla hash almacena en caché el último índice de tabla al que accede GETHASH.

Cuando se llama PUTHASH (o equivalentemente, (GetHash SETF)), se comprueba en primer lugar si la clave de ese índice en caché está EQ a la tecla que está pasando en.

Si es así, toda la tabla hash la rutina de búsqueda es pasada por alto, y PUTHASH almacena directamente en el índice en caché.

Tenga en cuenta que EQ es solo una comparación de puntero y, por lo tanto, extremadamente rápida: no tiene que atravesar la lista en absoluto.

Por lo tanto, en el ejemplo del código, no hay sobrecarga.

Answer 2

Algunas soluciones podrían ser:

Si el patrón común es el de búsqueda -> find-it -> sobreescritura-él, entonces se podría sustituir el tipo de valor a una lista que contiene el tipo de valor. Luego, después de encontrar el objeto de valor para la clave, simplemente reemplaza destructivamente su primer elemento, p.

(defun try-add (i) 
    (let ((old-i-list (gethash complex-list table nil))) 
    (if (may-add (first old-i-list)) 
     (setf (first old-i-list) i)      ; overwrite without searching again 
     (setf (gethash complex-list table) (list i))))) ; not there? too bad, we have to gethash again 

Alternativamente, si el patrón común se parece más a las operaciones de búsqueda -> está-no-no -> add-se, es posible que desee considerar la posibilidad de hash las teclas de su propia, y luego tener la tabla hash utilizar su valor hash como la clave. Esto podría ser más complicado, dependiendo de la profundidad y la semántica de estas listas complejas. En el caso simple, puede salirse con una función hash que (recursivamente) xor es el valor hash de los elementos de su argumento de lista.

---

EDITADO: responder a la pregunta en los comentarios: la idea es que en lugar de las teclas de mapeo tabla hash a los valores, la tabla hash ahora asignar teclas a las listas solo elemento, donde el elemento es el valor. Luego puede cambiar el contenido de estas listas sin tocar la tabla hash en sí. Lo siguiente es de SBCL:

* (defparameter *my-hash* (make-hash-table)) 
*MY-HASH* 

* (setf (gethash :my-key *my-hash*) (list "old-value")) 
("old-value") 

* (gethash :my-key *my-hash*) 
("old-value") 
T 

* (defparameter old-value-container (gethash :my-key *my-hash*)) 
OLD-VALUE-CONTAINER 

* (setf (first old-value-container) "new value") 
"new value" 

* (gethash :my-key *my-hash*) 
("new value") 
T 

Answer 3

Una cosa que podría hacer es el uso defstruct para crear un valor que cada entrada en los puntos de la tabla hash para. Su lista de valores (a los que está presionando en su ejemplo actual) podría almacenarse allí. La creación de struct podría hacerse en esa llamada gethash inicial (como el valor predeterminado), o podría hacerse manualmente si observa que no hay ningún valor allí. Entonces, el objeto puede verse afectado de la manera que lo estás haciendo.

(Esto ignora la cuestión de si realmente desea utilizar valores tan complejos como las claves de tabla de claves, o si hay una forma de evitar esto. Por ejemplo, podría estar utilizando estructuras/objetos CLOS en lugar de listas complejas como sus claves, y luego podría usar una tabla hash EQ en su lugar. Pero eso depende mucho de lo que esté haciendo)

Answer 4

"La creación de perfiles muestra que las pruebas iguales tardan mucho tiempo".

Sí, pero ha verificado que # 'EQUAL tablas de hash búsquedas ¿también toman mucho tiempo?

¿Ha compilado esto para la velocidad en un compilador de optimización como SBCL y miró las notas del compilador?

Después de haber resuelto estas dos preguntas, también puede probar una tabla hash anidada para cada nivel de las claves de su lista. No debería ser difícil escribir una macro para tablas hash anidadas arbitrariamente.

Answer 5

Tal vez estoy perdiendo algo obvio, pero:

(defun try-add (i) 
    (let ((old-i (gethash complex-list table))) 
    (when (may-add old-i) 
     (push i old-i)))) 

desde:

• nula ya es el valor predeterminado para GetHash
• GetHash saca todo el objeto por lo que sólo puede modificar en lugar de decir PUSH cómo buscarlo de nuevo
• (punto de estilo: utilice CUANDO en lugar de IF cuando no haya otra cláusula)

Editar: Vaya, yo estaba: Extrañé el caso donde viejo-i es nulo. Pero si ese no es el caso común, entonces todavía podría ser una victoria, ya que sólo tiene que hacer la búsqueda en ese caso:

(defun try-add (i) 
    (let ((old-i (gethash complex-list table))) 
    (when (may-add old-i) 
     (if old-i 
     (push i old-i) 
     (push i (gethash complex-list table)))))) 

Hmm, funciona eso?

Answer 6

Es posible que en realidad esté accediendo a la tabla hash tres veces. ¿Por qué? Porque la macro push se puede expandir en un código que hace un gethash para obtener la lista, y luego alguna operación system::sethash para almacenar el valor.

En este problema, está inspeccionando el valor de un lugar, que es una lista. Si esa lista satisface alguna prueba de predicado, entonces empuja algo hacia ese lugar.

Este problema puede ser atacado por la creación de operador de propósito especial que captura esta semántica:

(push-if <new-value> <predicate> <place>) 

Por ejemplo:

(push-if i #'may-add (gethash complex-list table)) 

Este push-if se define como un macro que utiliza la función de get-setf-expansion en el argumento de forma <place> para obtener las piezas necesarias para generar el código para acceder a ese lugar una sola vez.

El código generado evalúa una forma de carga para obtener el valor anterior del lugar, luego aplica la condición al valor anterior y, si tiene éxito, prepara el nuevo valor en la variable de almacenamiento temporal apropiada obtenida de get-setf-expansion y evalúa el formulario de la tienda.

Esto es lo mejor que puede hacer en Lisp portátil, y es posible que todavía realice dos operaciones de hash, como se mencionó anteriormente. (En cuyo caso se espera hay una optimización de almacenamiento en caché decente en la propia tabla hash, pero al menos se ha reducido a dos operaciones..)

El enfoque será tan optimizado como el construido en el lugar mutando formas: incf, push , rotatef, etc. Nuestra push-if estará a la par de las incorporadas.

Si aún es asqueroso (realiza dos hash para actualizar un hash, sin optimización del almacenamiento en caché), la única forma de solucionarlo es en el nivel de implementación.

push-if código sigue: expansión

(defmacro push-if (new-value predicate-fun list-place &environment env) 
    (multiple-value-bind (temp-syms val-forms 
         store-vars store-form access-form) 
         (get-setf-expansion list-place env) 
    (let ((old-val (gensym))) 
     (when (rest store-vars) 
     (error "PUSH-IF: cannot take ref of multiple-value place")) 
     `(multiple-value-bind (,@temp-syms) (values ,@val-forms) 
     (let ((,old-val ,access-form)) 
      (when (funcall ,predicate-fun ,old-val) 
      (setf ,(first store-vars) (cons ,new-value ,old-val)) 
      ,store-form)))))) 

muestra:

> (macroexpand '(push-if new test place)) 
(LET* ((#:VALUES-12731 (MULTIPLE-VALUE-LIST (VALUES)))) 
(LET ((#:G12730 PLACE)) 
    (WHEN (FUNCALL TEST #:G12730) (SETF #:NEW-12729 (CONS NEW #:G12730)) 
    (SETQ PLACE #:NEW-12729)))) ; 

Parece cuerdo para el caso simple cuando el lugar es una variable. Solo hay un pequeño problema que no voy a solucionar: los formularios new, test y place se evalúan una sola vez, pero no de izquierda a derecha.

prueba con un lugar de la tabla de hash (CLISP):

> (macroexpand '(push-if new test (gethash a b))) 
(LET* 
((#:VALUES-12736 (MULTIPLE-VALUE-LIST (VALUES A B))) 
    (#:G12732 (POP #:VALUES-12736)) (#:G12733 (POP #:VALUES-12736))) 
(LET ((#:G12735 (GETHASH #:G12732 #:G12733))) 
    (WHEN (FUNCALL TEST #:G12735) (SETF #:G12734 (CONS NEW #:G12735)) 
    (SYSTEM::PUTHASH #:G12732 #:G12733 #:G12734)))) ; 

Aha; ahora hay un código algo más interesante que se genera para evitar evaluar a y b dos veces. La función gethash se invoca una vez, pero sus argumentos son variables gensym. El valor anterior se captura como #:G12735. Se aplica la prueba y, si se aprueba, la tienda variabel #:G12734 se actualiza con el valor anterior de la lista con new en frente. Entonces, ese valor se pone en la tabla hash con system::puthash.

Por lo tanto, en esta implementación de Lisp, no hay forma de evitar dos operaciones de la tabla hash para realizar una actualización: gethash y system::puthash. Esto es lo mejor que podemos hacer y esperamos que los dos funcionen como un par optimizado.