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.
Do you have any performance tests to show that the asymptotic improvements are worth the constant factors? Examples of complex programs that are best expressed using this data structure, and which consequently perform much better than the would with vanilla lists? What space usage are random-access lists guaranteed to exhibit? Growth order and constant factors are both interesting -- growth order to specify in the SRFI, and constant factors to satisfy my curiosity. For instance, while this is not guaranteed, a list of length n will usually occupy O(n) storage, and in particular usually no more than 4 n words of memory. A vector of length n will also usually occupy O(n) storage, often with O(1) extra space, and in particular usually no more than 2 n + 4 or so words of memory and often no more than n + 1. Assuming the overhead of every record is a constant, how does the space used by a random-access list grow as a function of its length; and, given the constant overhead of a record, and assuming that there is one word of memory per field per record, how many words does a random-access list of length n occupy?