sábado, 29 de março de 2008

Pensando como programador em C

Estava tentando fazer um cache para valores de uma função. O resultado é a macro que esta abaixo.


(defmacro with-cache (cache key &body body)
(with-gensyms (cached? value)
`(if ,cache
(multiple-value-bind (,cached? ,value) (has-key? ,cache ,key)
(if ,cached?
,value
(set-value ,cache ,key
(progn
,@body))))
;; cache eq null -> no caching
(progn ,@body))))


Nada mais simples. Se a variavel cache for nil body é executado, caso contrário testa-se para ver se key já esta no cache com a função has-key?, que caso o valor esteja presente já o retorna como segundo valor. Se o valor não estiver no cache, o valor retornado por body é armazenado e retornado por set-value.

A primeira implementação e has-key? e set-value utilizavam somente hash-table, o problema é que quando um valor é armazenado no cache ele ali permanece para sempre. Por isso eu precisava implementar alguma forma de controle.

Pensei em controlar o tamanho do cache, quando ele ficasse cheio eu eliminaria os valores mais antigos da hash table. O problema é descobrir uma função que retorna-se a quantidade de memória utilizada por um dado objeto, um equivalente sizeof do C. Só encontrei uma função específica do Allegro CL: find-object-size e mais nada.

Só que eu estava pensando como um programador em C, viciado em controle manual de memória. O que eu precisava era uma forma de avisar o Garbage Colletor que os valores no cache podiam ser deselocados quando fosse preciso.

Como quase sempre a solução para o meu problema já existia em Lisp, e se chama weak reference[1]. Uma weak reference é um ponteiro que não conta na hora de avaliar se um objeto pode ser jogado no lixo ou não. Em algumas implementações (SBCL incluído) é possível especificar no make-hash-table se os ponteiros vão ser do tipo weak com o parâmetro :weakness.

Existem diversas opção de weakness para hash-table, eu escolhe o tipo :value, que mantém o pair key,value enquanto houverem referências para o valor.

[1] http://www.haible.de/bruno/papers/cs/weak/WeakDatastructures-writeup.html

Nenhum comentário: