Re: Cons cell archaic!?

On Oct 23, 1:35 pm, seeWebInst...@xxxxxxxxxxxxxxxx (Robert Maas,
http://tinyurl.com/uh3t) wrote:

From: smallpond <smallp...@xxxxxxxx>
You could imagine a language similar to lisp in which everything is
either an atom or a null terminated list, and not having dotted pairs.

Under that plan, it'd be impossible to build lists incrementally,
which is essential for efficiently implementing READ and other
parser for other variable-width list representations. The best that
could be done is to either pre-allocated the largest reasoanble
array then copy it to a smaller array after the parse is done, and
switch to a larger array whenever an unexpectedly large list is
seen, or allocate blocks of elements that are chained together, and
then re-copy the chain to a single array when the READ operation is
done, or to emulate CDR-linked cells by using CADR-linked cells
instead and re-copy to a single array when done, or somehow emulate
a binary search tree to emulate an extensible array and re-copy to
a single array when done. [...]


There are better strategies than you list (pun not originally
intended :-). You can realloc a vector as you go, allocating some
extra slots each time in anticipation of future appends. If you bump
up the size exponentially (making it a constant multiple larger at
each realloc), the amortized cost for appending to a vector is only
O(1). Moreover, if you choose a factor less than 2 (say 1.5 or
something) for your reallocations, you'll use less memory than a
linked list when you're finished. If you're memory allocator is
smart, you might occasionally get a larger vector without any
copying. Finally, traversing a vector will cause less cache grief
than traversing a linked list.

.

Relevant Pages

  • Re: garbage collection problem in large linked lists
    ... Instead all buckets are allocated at once in an array. ... VG.net, which must be very scalable, but only for lists which would normally ... Linked lists require pointer dereferencing in order to traverse. ... When you run out of space, you allocate a new smaller array. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Dict sharing vs. duplication
    ... array to enforce unique keys and I use lists to enforce order. ... API in a page or two of Tcl code, it isn't so much a missing feature ... OpenACS database API which creates a new specialized data structure, ...
    (comp.lang.tcl)
  • Re: Translating python to scheme
    ... Scheme has mutation, and there are reasons to use it. ... confusing when considering a 2d array. ... in other languages: Lisp Lists and Vectors. ...
    (comp.lang.scheme)
  • Re: Cons cell archaic!?
    ... Under that plan, it'd be impossible to build lists incrementally, ... array then copy it to a smaller array after the parse is done, ... instead and re-copy to a single array when done, or somehow emulate ... structures there'd be no difference even in efficiency; ...
    (comp.lang.lisp)
  • Re: vasam
    ... // Set the size for long lists in records #2 and #3 only! ... Here is the sequel of my previous post "Variable array sizes as members" ... I was given some advice on how to use malloc and realloc in oder to achieve ...
    (microsoft.public.vc.language)