e25
Subj : Re: Distributed Proxy Reference Counting: The VZOOM Algorithm...
To   : comp.programming.threads
From : Chris Thomasson
Date : Mon Sep 19 2005 02:35 am

>> BTW, VZOOM (designed in January 2005) does not infringe on any prior art, 
>> claims or teachings made by the RCU or SMR patents. Thank God!
>>
>> Oh yeah, its a lot more flexible than SMR or RCU...
>>
>> ;)
> Patent it!  Or have you already applied for one?  "plurality" is patent 
> speak.
> BTW, you can also patent improvements on things already patented.  If the
> improvements are on other people's patents, they're called blocking 
> patents,
> otherwise they're called defensive patents (I think).

Yes, I have filed for a patent. I figured I needed to do it if I wanted to
be able to use it at all. I basically designed VZOOM in a way that gets
around some annoying limitations in RCU, and some major scalability and
performance problems with SMR. I figured out that SMR and RCU are not very
practical for a "general solution" to the reader/writer problem. For those
who are interested, let me very briefly explain why:




RCU
-------

The main problem with RCU is it simply doesn't allow a reference to exist
over a "quiescent state". This can be very dangerous and tedious to design
around. Calling a function that might go into a "quiescent state" can be a
potentially disastrous and annoying situation. Also, RCU is simply no good
for high numbers of sustained writes. The RCU teachings were not designed
for high numbers of writes, and some implementations can run out of memory
during such conditions...


- VZOOM allows a thread to acquire a "persistent" reference to a data
object. In RCU speak, persistent references can exist across multiple
quiescent points. Plus, VZOOM can efficiently chew on very high numbers of
sustained writes. It also allows the user to adjust the depth limits of the
queues at runtime, so you can use it to manage the memory of lock-free
algorithms that are optimized for high numbers of writes.




SMR
------

The main problems with SMR is that real world implementations require a
nasty StoreLoad style memory barrier for every single acquired reference,
and it was not designed to allow a thread to acquire an arbitrary number of
references. If a thread tries to grab a new reference, and all of its hazard
pointers are already used, your kind of screwed. You have to allocate more
pointers, which brings in the added overhead of a "hazard pointer allocation
scheme". Also, you also have to think about how an abundance of freshly
allocated hazard pointers ( some might be in use, some are just about to be
used, ect... ) will be presented to the "scanning logic". A solution will
most certainly add more overhead via memory barriers and possibly atomic
operations...


- VZOOM allows a thread to acquire basically any number persistent
references to a data object without using any atomic operations and/or
StoreLoad style memory barriers.




As you can see, VZOOM != SMR and/or RCU. It was designed from the ground up
to be flexible enough to be used as a generic solution for many portable
user-space multithreaded applications that are interested in drastically
reducing overhead with regard to threads referencing shared data objects. It
is also a highly distributed algorithm. This makes it work well with NUMA
architectures. There is also an embodiment of VZOOM that can be used in
multithreaded OS Kernels, but it was really designed to be used in
user-space. I could go on and on...

:)




Any thoughts?

.

0