An atomic lock-free refcounting patent application
Joe Seigh
I can't get the illustrations to display in my browser so I can't
say anything for sure but you might say it's interesting.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Joe Seigh
> 20060037026 Lightweight reference counting using single-target
> synchronization
>
> I can't get the illustrations to display in my browser so I can't
> say anything for sure but you might say it's interesting.
>
>
by Simon Doherty, Maurice Herlihy, Victor Luchangco, and Mark Moir
of Sun Microsystems. And it appears to be (as near as I can tell
without seeing the illustrations) to be nearly identical to atomic_ptr.
Their "hold count" in the shared pointer, and "exit count" in the shared
object seem to be the same as "ephemeral count" in atomic_ptr. It's
the using two counts to distinguish between local non-shared private
references and global shared public references.
I'd say for more certain but I still can't figure out how to
display the patent images on the uspto site.
Joe Seigh
> 20060037026 Lightweight reference counting using single-target
> synchronization
>
local pointer reference count using single word CAS instead of
double word CAS. The that technique is covered in here.
http://research.sun.com/scalable/pubs/main-8.pdf
I don't know what they're going to do about it but I'm not
going to worry. After all, lock-free lifo stacks have been
patented at least twice even though the algorithm has been
in the public domain for decades and we have had any problem
with those patents.
Joe Seigh
> Joe Seigh wrote:
>
>> 20060037026 Lightweight reference counting using single-target
>> synchronization
>>
> Apparently it's based in part on a technique for maintaining a
> local pointer reference count using single word CAS instead of
> double word CAS. The that technique is covered in here.
> http://research.sun.com/scalable/pubs/main-8.pdf
>
think of a possible problem with it. It will have to wait until
they do a write up of that particular application. It will work
for something else though, but I'll let them figure out that one
also.
Chris Thomasson
> Joe Seigh wrote:
>
>> 20060037026 Lightweight reference counting using single-target
>> synchronization
>>
>> I can't get the illustrations to display in my browser so I can't
>> say anything for sure but you might say it's interesting.
>>
>>
> It's a patent application for atomic lock-free reference counting
> by Simon Doherty, Maurice Herlihy, Victor Luchangco, and Mark Moir
> of Sun Microsystems. And it appears to be (as near as I can tell
> without seeing the illustrations) to be nearly identical to atomic_ptr.
> Their "hold count" in the shared pointer, and "exit count" in the shared
> object seem to be the same as "ephemeral count" in atomic_ptr. It's
> the using two counts to distinguish between local non-shared private
> references and global shared public references.
They are apparently using the same form of differential reference
counting that one of my lock-free proxy collectors uses:
http://home.comcast.net/~vzoom/demos/pc_sample.c
The differences are they do not use a backlink reference count and they
use an alternating pointer scheme to avoid DWCAS. My algorithm just
steals some low-order bits on the proxy anchor to achieve a similar
effect. Hey, they ripped off part of my algorithm! ;)
lol.
> I'd say for more certain but I still can't figure out how to
> display the patent images on the uspto site.
I can't get them to appear either.
Chris Thomasson
> Joe Seigh wrote:
>
>> Joe Seigh wrote:
>>
>>> 20060037026 Lightweight reference counting using single-target
>>> synchronization
>>>
>> Apparently it's based in part on a technique for maintaining a
>> local pointer reference count using single word CAS instead of
>> double word CAS. The that technique is covered in here.
>> http://research.sun.com/scalable/pubs/main-8.pdf
>>
> Or maybe it won't work for lock-free refrence counting. I can
> think of a possible problem with it.
Yup. Its definitely not full-blown reference counting. Its basically
specialized to allow for a thread to remove a global pointer and free it
when the differential count hits zero, thats about it. However, you
could probably augment the algorithm with the same logic that one would
use for GC protected reference counting...
> It will have to wait until
> they do a write up of that particular application. It will work
> for something else though, but I'll let them figure out that one
> also.
Ahh yeah, if only they added my backlink reference counting... Anyway,
the proxy collector code I posted (pc_sample.c) can do exactly the same
thing as the Sun patent, plus it can do stuff that the Sun algorithm
simply cannot. Also, IMHO, it is a better solution...
:)
Chris Thomasson
> 20060037026 Lightweight reference counting using single-target
> synchronization
>
> I can't get the illustrations to display in my browser so I can't
> say anything for sure but you might say it's interesting.
>
>
Humm... I would be interested to know if anybody thinks that there could
be any infringement issues between my collector:
http://home.comcast.net/~vzoom/demos/pc_sample.c
and the SUN patent application. The form of ref-counting could be
considered to be very similar... Any thoughts? My initial thought is
probably not.
Joe Seigh
Their stuff is identical to atomic_ptr except they haven't specified how
the single target synchonization is accomplished. atomic_ptr uses
double wide compare and swap in that case. They implied it was based
on the technique in that paper I mentioned earlier but I'm not sure how
it will actually work. So you have to decide if part of your technique
is similar to the one in that paper.
Chris Thomasson
The only similarity is the way they reference count the nodes for their
LL/SC emulation implementation.
My technique basically records the number of threads that were accessing
the nodes at the time it was swapped out and then increments the nodes
"private" reference counts by that recorded number. The accessing
threads will subsequently decrement the counter one by one. So the
mathematical equation could be something like this:
ATS = the number of threads at time of ptr swap
TDR = the number of threads that will dec after ptr swap
Prove that:
ATS + (-TDR) = 0
Super Simple Proof:
If there are 5 accessing threads at the time of the pointer swap then
the ATS for the equation will be 5. The accessing threads will
subsequently drop their references so the TDR for the equation will also
be 5:
5 + (-5) = 0
I believe they are using same method to count the number of references
there are to a node when a successfully emulated SC occurs... Humm...
Chris Thomasson
Okay. The similarities in our algorithms seem to have nothing to do with
single-target synchronization. It only has to do with the way are are
managing the nodes lifetimes. They make a clear separation in the paper
between the single-target stuff and the method used for node lifetime
tracking.
The single-target stuff seems to involve alternating between two
pointers (active and inactive). They are using the even or odd quality
of a monotonic version counter to determine which pointer is active.
They modify version counter along with the number of references there
are to the node. They read the pointer along with the version count then
double-check with CAS to make sure the pointer read is synchronized with
the version read. Synchronized loads from multiple location snapshot
type stuff. Like their KCSS implementation... I really do need to read
through the patent claims.
Chris Thomasson
news:gN-dnToIidIpE7_Z...@comcast.com...
> Chris Thomasson wrote:
>> Joe Seigh wrote:
>>
>>> 20060037026 Lightweight reference counting using single-target
>>> synchronization
>>>
>>> I can't get the illustrations to display in my browser so I can't
>>> say anything for sure but you might say it's interesting.
>>>
>>>
>>
>> Humm... I would be interested to know if anybody thinks that there could
>> be any infringement issues between my collector:
>>
>> http://home.comcast.net/~vzoom/demos/pc_sample.c
>>
>> and the SUN patent application. The form of ref-counting could be
>> considered to be very similar... Any thoughts? My initial thought is
>> probably not.
>
> Their stuff is identical to atomic_ptr
Indeed... Their UpdateStatus( ... ) function, page 9 paragraphs 86-87, looks
strikingly similar to your "adjust" function in atomic_ptr...
> except they haven't specified how
> the single target synchonization is accomplished. atomic_ptr uses
> double wide compare and swap in that case.
Ahhhh... I read through the patent teachings and found out that:
*** they require "DWCAS-like" operations as well ***
Take a look at page 9 paragraphs 82-84......
> They implied it was based
> on the technique in that paper I mentioned earlier but I'm not sure how
> it will actually work.
Yeah, they "briefly mention" that their LL/SC "emulation", described in a
previous paper, can be used when DWCAS is not available... Page 11,
paragraphs 103-108... Especially, paragraph 106, line 3......
So, if they can't use DWCAS, their algorithm quickly turns into an
"extremely expensive sequence of operations"...
Their LL/SC emulation stuff requires CAS and memory barriers on both the LL
side, and the SC side. This means that in order to adjust the reference
count in conjunction with the shared reference, they have to use "at least"
2 CAS and 2 membars in a loop... Also, they have to implement an "allocation
scheme" for the internal structures that make up the LL/SC emulation
logic......
So, when their algorithm can't use DWCAS, it can "quickly become less
efficient than a mutex based design"...
I don't know why they would rely on emulated LL/SC when they could of use a
much simpler and more efficient "offset trick"... 2 CAS and 2 membars just
to increment a reference count is just too expensive, IMHO...
Any thoughts?
Joe Seigh
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:gN-dnToIidIpE7_Z...@comcast.com...
>
>>Chris Thomasson wrote:
>>
>>>Joe Seigh wrote:
>>>
>>>
>>>>20060037026 Lightweight reference counting using single-target
>>>>synchronization
>>>>
>>Their stuff is identical to atomic_ptr
>
>
> Indeed... Their UpdateStatus( ... ) function, page 9 paragraphs 86-87, looks
> strikingly similar to your "adjust" function in atomic_ptr...
>
The figures starting at fig. 3 are particularly good. I was thinking of
linking to it somehow from the atomic_ptr project page.
It would be amusing if Sun got a patent on something they can't even use
for the Sparc.
Joe Seigh
> Chris Thomasson wrote:
>
>> "Joe Seigh" <jsei...@xemaps.com> wrote in message
>> news:gN-dnToIidIpE7_Z...@comcast.com...
>>
>>> Chris Thomasson wrote:
>>>
>>>> Joe Seigh wrote:
>>>>
>>>>
>>>>> 20060037026 Lightweight reference counting using single-target
>>>>> synchronization
>>>>>
>
>>> Their stuff is identical to atomic_ptr
>>
>>
>>
>> Indeed... Their UpdateStatus( ... ) function, page 9 paragraphs 86-87,
>> looks strikingly similar to your "adjust" function in atomic_ptr...
>>
> The figures starting at fig. 3 are particularly good. I was thinking of
> linking to it somehow from the atomic_ptr project page.
>
On consideration, I may have been premature. I should have waited until
they published a paper on the technique. It would have been better
documentation.
However, now it's safe for them to try inventing things since I've stopped
bothering to invent new synchronization techniques for the time being. Unlike
them, I don't get paid to invent useless techniques. And there shouldn't be
any complaints about software patents, at least in this area. All the
important stuff has been invented long ago and is already in use. We will
never need to use new techniques. :)
(And if anyone was wondering why I was inventing stuff, it was an alternative
to Solitaire for killing time. Solitaire was a little better for that.)
Chris Thomasson
> Chris Thomasson wrote:
>> "Joe Seigh" <jsei...@xemaps.com> wrote in message
>> news:gN-dnToIidIpE7_Z...@comcast.com...
>>
>>>Chris Thomasson wrote:
>> Their UpdateStatus( ... ) function, page 9 paragraphs 86-87, looks
>> strikingly similar to your "adjust" function in atomic_ptr...
>>
> The figures starting at fig. 3 are particularly good. I was thinking of
> linking to it somehow from the atomic_ptr project page.
;)
Humm, very interesting! Lets see here...
atomic_ptr:
struct refcount {
long ecount; // ephemeral count
long rcount; // reference count
};
is equal to sun_lfrc:
struct status_s {
int exitCount; // ephermerals
int refCount; // references
};
atomic_ptr:
template<typename T> class atomic_ptr_ref {
[...]
refcount count; // reference counts
T * ptr; // ptr to actual object
}; // class atomic_ptr_ref
is equal to sun_lfrc:
struct RCL_Obj_s {
struct status_s status; // reference counts
RCL_Obj *ref;
};
atomic_ptr:
template<typename T> struct ref {
long ecount; // ephemeral count
atomic_ptr_ref<T> *ptr;
};
is equal to sun_lfrc:
struct RCL_Ref_s_s {
int holdCount; // ephermerals
RCL_Obj *ref;
};
atomic_ptr:
int atomic_ptr_ref<T>::adjust(long xephemeralCount, long xreferenceCount);
is equal to the logic in sun_lfrc:
void UpdateStatus( RCL_Obj *o, int reDelta /* refcount */, int ec Delta /*
xephermal */ );
Humm.... !
;)
[...]
>> I don't know why they would rely on emulated LL/SC when they could of use
>> a much simpler and more efficient "offset trick"... 2 CAS and 2 membars
>> just to increment a reference count is just too expensive, IMHO...
>>
>>
>>
>>
>> Any thoughts?
> It would be amusing if Sun got a patent on something they can't even use
> for the Sparc.
Well, technically, they can "use" it, and it will work on 64-bit mode
sparc... However, it would turn out to be more expensive than the original
SMR thing...
:O
Chris Thomasson
news:iYOdnea81Ky6SqfZ...@comcast.com...
> "Joe Seigh" <jsei...@xemaps.com> wrote in message
> news:gN-dnToIidIpE7_Z...@comcast.com...
>> Chris Thomasson wrote:
> So, when their algorithm can't use DWCAS, it can "quickly become less
> efficient than a mutex based design"...
>
>
> I don't know why they would rely on emulated LL/SC when they could of use
> a much simpler and more efficient "offset trick"... 2 CAS and 2 membars
> just to increment a reference count is just too expensive, IMHO...
Humm, the inventors must of missed this post:
http://groups.google.ca/group/comp.programming.threads/msg/aae28a0e1f9b0d66
:)
They did not have to use emulated LL/SC for every reference adjustment!
:O
Chris Thomasson
>
>
> template<typename T> struct ref {
> long ecount; // ephemeral count
> atomic_ptr_ref<T> *ptr;
> };
>
>
> is equal to sun_lfrc:
>
> struct RCL_Ref_s_s {
> int holdCount; // ephermerals
> RCL_Obj *ref;
should be T *ref;
> };
The DWCAS-based version of sun_lfrc == atomic_ptr.