This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Scheme style auto-resizing hashtable (fwd)



jglascoe@jay.giss.nasa.gov writes:
> On Fri, 6 Nov 1998, Maciej Stachowiak wrote:
> 
> > 
> > jglascoe@jay.giss.nasa.gov writes:
> > 
> > > (define dictionary-consume-alist!
> > >   (lambda (dictionary alist)
> > >     (if (not (null? alist))
> > > 	(let* ((pair (car alist))
> > > 	       (key (car pair))
> > > 	       (value (cdr pair))
> > > 	       (alist-cdr (cdr alist)))
> > > 	  (dictionary-insert! dictionary key value)
> > > 	  (if (not (null? alist-cdr))
> > > 	      (begin
> > > 		(set-car! alist (car alist-cdr))
> > > 		(set-cdr! alist (cdr alist-cdr))
> > > 		(dictionary-consume-alist! dictionary alist)))))))
> > > 
> > 
> > This just has the effect of dropping the alist cons cells on the floor
> > as garbage gradually instead of all at once; I am not sure this is so
> > helpful. 
> 
> woops, you're right, that is somewhat pointless.  let me change it a bit
> 
> (define dictionary-consume-alist!
>   (lambda (dictionary alist)
>     (if (not (null? alist)) 
> 	(let ((pair (car alist))
> 	      (alist-cdr (cdr alist)))
> 	  ;; (dictionary-add-pair! dictionary pair) ;; more efficient
> 	  (dictionary-add-list! dictionary (list pair))
> 	  (if (not (null? alist-cdr))
> 	      (begin
> 		(set-car! alist (car alist-cdr))
> 		(set-cdr! alist (cdr alist-cdr))
> 		(dictionary-consume-alist! dictionary alist)))))))
> 

I think this version is pointless too. There are two types of cons
cells in the alist, the ones that form the list structure, and the
ones that are the key-value pairs (these are in one-to-one
correspondence in fact). The ones that form the key-value pairs can be
shared by the dictionary and are thus not a concern memory-wise. The
ones that form the list structure will become garbage if you don't
care about the alist. Your version will just make them become garbage
one bit at a time instead of all at once when you drop the last
reference to the alist. There is no particular reason this is helpful
unless you want your program to hold a reference to the alist even if
it is destroyed. Either way the same amount of memory must be GC'd. In
fact, all your set-car!s and set-cdr!s just make things run slower. If
it is really important for the memory to be incrementally reclaimable,
just make sure dictionary-insert-alist! is tail recursive and the call
to it is the only reference to the alist. 

In general, it is useless to try to conserve memory by destructively
modifying temporary data structures in a garbage collected language.


> > In fact, if you just cdr'd down the alist and the only live reference
> > to it is passing it to dictionary-insert-alist!, you'd have the exact
> > same effect, i.e. the cells of the alist would become garbage as soon
> > as the iteration does not need them any more. 
> > 
> > What would be more useful is the ability to insert the key-value cons
> > cells of the alist explicitly, sharing the memory, rather than having
> > to extract the keys and values and then insert them. That would help
> > both speed and memory usage.
> 
> right.  I think I will add a "dictionary-add-pair!", could be called by
> "dictionary-add-list!".

That name is excessively literal, maybe dictionary-add-association! or
something?

 - Maciej Stachowiak