On 14 June 2012 23:34, David Kastrup <d...@gnu.org> wrote: > Daniel Hartwig <mand...@gmail.com> writes: >> The >> guile core provides already a solid set of fundamental types which are >> very easy to compose to produce *exactly* the type required for any >> particular situation. > > Except when they don't. Which is what started this thread.
You don't find that the guile primitives are easy to compose? Please remind me what data structure you are precisely after? You initially were comparing with Lua tables, but then mentioned that you only required the resizable vector function. There has been at least two examples of that data types posted to this thread which use the underlying vector primitive. Both examples are very simple. Compared to a lot of the data types at the core of guile, resizable vector has *lots* of variety in it's details, the particular subset you optimize depends on your usage. >>> Another complex type, this time with quite more serious memory and >>> performance impact, that can't be implemented on top of a simple >>> resizable common primitive and has an almost, but not quite, overlapping >>> underlying feature set? >>> >>> It's almost as if you _like_ not being able to reuse code. >> >> I don't see how either hash table or multi-dimensional array type >> could benefit from a shared, resizable primitive – they are quite >> different algorithms, and both different again to the basic resizable >> vector already discussed. >> >> It is moot that hash table internally manages a vector and allocates a >> /new/ vector when needed. This is not a simple resizing operation. > > Huh? When resizing a hash table by doubling, you need to recoalesce > each bucket to two buckets, one of which is the original. Doubling the > size of the underlying vector is a reasonable start to do this operation > as a half-in-place rather than a three-address variant. What is this half-in-place algorithm that makes this efficient? If the table is to remain balanced, all items should be rehashed and reallocated to a new bucket and there is no correlation between an items old and new buckets (hash). Perhaps I miss an obvious trick, but I am thinking of … … when the table controls it's own memory: 1. allocate new vector 2. assign each item to it's new bucket 3. destroy old vector … when the table does not control it's own memory but uses an underlying resizable type: 1. resize vector 1a. allocate new vector 1b. move data to head of new vector 1c. destroy old vector 2. assign each item to it's new bucket but this time watch out for already populated buckets … which to me /seems/ less efficient, and particularly bad if the buckets are linked lists or open addressed. But I am curious if this can be done efficiently, and indeed if it is more efficient than the table managing it's own memory. > >> Are there any data types in the guile core which would benefit from >> sharing a resizable vector primitive? > > Hash tables. Apparently vlists. I am not convinced that this does not > make sense for normal and uniform vectors as an option as well. A vlist is a very different, it does not resize the underlying vectors but chains them together. This avoids the memory copy implicit to resizing vectors at the expense of some speed during other operations. The particulars also permit multiple vlists to share arbitrary tails, and other nice properties.
