[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: performance

This page is part of the web mail archives of SRFI 101 from before July 7th, 2015. The new archives for SRFI 101 contain all messages, not just those from before July 7th, 2015.



Taylor R Campbell wrote:
   Date: Fri, 18 Sep 2009 08:21:51 -0400
   From: David Van Horn <dvanhorn@xxxxxxxxxxxxxxx>

In short, the space consumption has at worst a logarithmic overhead compared to a plain ol' list. Right? I'm still not sure I'm answering the question you're asking.

Yes, you've answered my question.  I'm a little concerned now, though,
that the representation you've chosen will cause problems if, for
whatever reason, one tries to store a node as an element of a
random-access list.  For example, suppose one has written a debugger
that uses random-access lists, and one is trying to use that debugger
to debug a routine internal to the random-access list library which
has nodes as the values of local variables, which get stored in the
debugger's random-access lists.  Code of the form (if (node? t) ... (f
t)) makes me nervous.  But I still haven't read the implementation
thoroughly; maybe this isn't an issue.

There would be problems if you stored a node as a leaf element of a tree, that's correct. But the node record type is not accessible outside of the library implementation, so I'm not worried. An implementation that exposed the node type would be taking matters into its own hands, but this is just the general problem of destroying abstraction barriers. I don't think it's worth coding defensively in this case.

David