Talk:VList

From Wikipedia, the free encyclopedia

I have a question. From the paper:

"During the consing of (9) the pointer offset is compared with the last used offset, LastUsed. If it is the same and less than the block size then it is simply incremented, the new entry made and LastUsed updated. "

I don't understand how vlists can be called "thread safe" since the LastUsed index gets incremented in a shared object. Without a mutex, this is a race condition, isn't it? In my mind, thread safe functional data structure means that no mutable fields are shared and thus no mutex is ever required. Cons lists, and binary trees can be thread safe in this sense.

-- (Author Unknown)

Section 2.8 of the referenced paper discusses thread safety, adding a Thread Lock bit to the sub-block.

Ken Hirsch 15:04, 11 December 2006 (UTC)

Can anyone explain how to add an element to the front of a VList in O(1) average time without breaking the other properties? In the persistent case, a thread might add one element to the head, and then hand the result off to two independent threads, which each add a different element to that list, and so on. When I do that in O(1) time, my VList head looks like a simply-linked list, which breaks the average O(1) element-access property.

-- Tim Sweeney

If there is frequent contention to the list head then the VList will have "less than optimal structure", as described in Section 2.8 of the paper. If used as a persistent data structure (whether or not in a concurrent environment), then the structure will be very wasteful unless the usage happens to fall into the head-cons pattern.

Ken Hirsch 15:04, 11 December 2006 (UTC)

This wikipedia entry is dishonest. The worst case complexity of random access is O(n), not O(log n), and so is the average case. It should be apparent that the stated time complexities only hold in the ideal case where it is never added to through two different handles. —Preceding unsigned comment added by 87.194.26.88 (talk) 18:01, 3 February 2008 (UTC)