RFC: C++0x memory model and parallel shift

Hi,

I've nearly finished my master thesis which covers the shift to
parallelism and C++0x's upcoming memory model. I'd really like get to
some comments on the C++ part from you experts. Of course, you are
more than welcome to comment on other parts too.

The document and some example lock-free C++0x code can be found at
http://74.53.180.2/~thorpe/

ABSTRACT

The first part is an overview of the paradigmatic shift to parallelism
that is currently taking place. It explains why processors needs to
become parallel, how they might function and what types of parallelism
that are. Given that information, it explains why threads and locks is
not a suitable programming model, how threading is being improved and
used to extract parallel performance and what problems awaits new
parallel programming models and how they might work. The final chapter
surveys the landscape of existing parallel software and hardware
projects and relates them to the overview. The overview is intended
for desktop and embedded programmers and architects.

The second part explains how to use C++'s upcoming memory model and
atomic API. It also relates the memory model to classical definitions
of distributed computing in an attempt to bridge the gap in
terminology between the research literature and C++. An implementation
of hazard pointers and a lock-free stack and queue are given as
example C++0x code. This part is aimed at expert C++ developers and
the research community.


Best Regards, Johan Torp

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 6 sep, 18:33, Johan Torp <johan.t...@gmail.com> wrote:

> An implementation
> of hazard pointers

Aren't those patented, and thus, unusable?
It's just sad how so many things in lock-free programming seem to be
patented. What's the point of research if it cannot be used in the
real world before decades?

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

"Mathias Gaunard" <loufoque@gmail.com> wrote in message
news:a6f7d31a-3bab-483b-8d6d-18f4d9f5d0f4@k7g2000hsd.googlegroups.com...
> On 6 sep, 18:33, Johan Torp <johan.t...@gmail.com> wrote:
>
>> An implementation
>> of hazard pointers
>
> Aren't those patented,

Yes.




> and thus, unusable?

You would need to grab a licence from IBM.




> It's just sad how so many things in lock-free programming seem to be
> patented. What's the point of research if it cannot be used in the
> real world before decades?

RCU is patented and its used within the Linux Kernel. If you use Linux, your
using patented algorihtms indeed!

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 2008-09-07 02:28, Mathias Gaunard wrote:
> On 6 sep, 18:33, Johan Torp <johan.t...@gmail.com> wrote:
>
>> An implementation
>> of hazard pointers
>
> Aren't those patented, and thus, unusable?
> It's just sad how so many things in lock-free programming seem to be
> patented. What's the point of research if it cannot be used in the
> real world before decades?


Well, there is still parts of the world where software patents are not
recognised, so unless you plan to export your software to parts where
they are you can still use them.

--
Erik Wikström


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

{ I'm assuming that this has some relevance to C++0x or later, but it would be
nice if such relevance could be made explicit. Not all mods are expert in every
aspect of C++, and I just have to guess at the topicality here! TIA., -mod }


On Sep 7, 2:28 am, Mathias Gaunard <loufo...@gmail.com> wrote:
> On 6 sep, 18:33,Johan Torp<johan.t...@gmail.com> wrote:
>
> > An implementation
> > of hazard pointers
>
> Aren't those patented, and thus, unusable?

Yes, http://www.freepatentsonline.com/y2006/0265373.html

I'm not sure how unusable they are, if they can be used in commercial
applications with Maged Michael's approval. I can also imagine that
Michael patented hazard pointers to not get run over by the patents of
big companies.

> It's just sad how so many things in lock-free programming seem to be
> patented. What's the point of research if it cannot be used in the
> real world before decades?

I agree, it's a real shame. Lock-free programming might have a short
shelf-life too, since transactional memory is hopefully on the way and
since non thread-based programming models will hopefully become more
and more commonplace. I.e., lock-free programming should be applied
now, to help extract performance out of today's threading solutions.
The whole concept of lock-free programming (not the lock-free
property) seems like a big hack to me, you really do not want to
program that way but have to with today's software stack if you are to
extract maximum throughput, responsiveness and to avoid dead-locks.

Johan



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 7 sep, 13:19, "Chris M. Thomasson" <n...@spam.invalid> wrote:

> RCU is patented and its used within the Linux Kernel.

That's because IBM allows royalty-free usage of RCU for any software
licensed under GPL.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Sep 6, 8:28 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
> On 6 sep, 18:33, Johan Torp <johan.t...@gmail.com> wrote:
>
> > An implementation
> > of hazard pointers
>
> Aren't those patented, and thus, unusable?
> It's just sad how so many things in lock-free programming seem to be
> patented. What's the point of research if it cannot be used in the
> real world before decades?
I have made a lock-free memory reclaimator that works and is not
patented. Nor do I really care to patent it--there is no way I am
going to reclaim the patent fee's for something like this.
It is composed of four pieces:
1. Allocator
2. intrusive reference counter + version field
3. isolated_ptr that obtains pointer suitable for dereferencing (like
a shared_ptr)
4. mutual_ptr that is lock-free, but not dereferenceable (like a
weak_ptr), that also support CAS


You use it like so:
struct A:
enable_mutual_ptr<A>//allocator and intrusive ref counter
{
int a;
int b;
};

mutual_ptr<A> global;//multiple threads can access atomically
void threadfunc(void*){
isolated_ptr<A> read;
isolated_ptr<A> update;
do{
read=global;
if(read){
update.reset(new A(*read));//copy
update->a=read->a+1011;//modify, etc
}else{
update.reset(new A);
//more stuff
}
}while(global.CAS(read,update));
}

The allocator serves a few purposes:
1. That only A's are allocated, since fields may be accessed after
return to the allocator (a standard allocator does not allow this)
2. I used DCAS internally, however special allocator would allow for
pointer compression if DCAS is undesirable
3. it is also lock-free

The basics of the guts are this:

When an A is constructed, a version is stored inside the object next
to the reference count. a 0 value for version is special.
The mutual_ptr stores both the pointer and the version
The release method checks both the reference count and the version. If
the versions match AND the refcount is 0, then the version is also set
to 0. (i.e. if refcount is 1 and version is X, set (version,refcount)-
>(0,0) atomically. Then delete.
//part of "enable_mutual_ptr"
friend void mutual_ptr_release(T const* p){
//storage_type is pair of refcount and version(tag)
do{
storage_type oldval(p->m_refs.get_data(),p->m_refs.get_tag());//tag
and count
unsigned new_tag=oldval.get_tag();
if(new_tag==0)return;
unsigned cnt=oldval.get_data();
if(cnt==1)new_tag=0;
storage_type newval(cnt-1,new_tag);
if(p->m_refs.CAS(oldval,newval)){
if(cnt==1) delete const_cast<T*>(p);
return;
}
}while(true);

}
Now, the tricky part comes in when making an isolated_ptr from a
mutual_ptr -- it is possible that mutual_ptr contains a stale pointer.
So instead of the traditional refcount increment, we do this

//part of "enable_mutual_ptr"
freind unsigned mutual_ptr_add_ref(T const* p, unsigned version){
//storage_type is pair of refcount and version
unsigned ret=0;
do{
storage_type oldval(p->m_refs.get_version(),p->m_refs.get_tag());//
tag and count
if(oldval.get_tag()!=tag)return 0;
ret=oldval.get_data()+1;
storage_type newval(ret,tag);
if(p->m_refs.CAS(oldval,newval))break;
}while(true);
return ret;
}
When the pointer is isolated, the traditional "increment the reference
count" can be done.
Now when making the copy, we must try a repeatable read (some will
argue that a repeatable read is not strictly lock-free, since is it
possible that no thread makes progress. However, it woould have the
obstruction free property--if I compressed the pointer, it would be
lock free)
template<class Y>
isolated_ptr(mutual_ptr<Y> const & mutual_rhs)
{
//m_p is member which is pair of pointer and version
do{
m_p=mutual_rhs.m_p;//pointer and version
if(!m_p.CAS(mutual_rhs.m_p,mutual_rhs.m_p))//not sliced
continue;
T* lcl=m_p.get_data();
if(lcl==0)return;
unsigned cnt = mutual_ptr_add_ref(lcl,m_p.get_tag());
if(cnt >0)//not a zombie
return;
else{
sched_yield();//backoff
}
//eventually mutual_rhs will either have a live value or a 0
}while(true);
}


These are basically the highlights. I use this inside some market data
servers (those things that takes all those stock market ticks and does
stuff with them --typically 100K msg per second with <1ms latency)

So there you have it. A lockfree pointer that has no patents (and not
even a copyright). I suppose a newsgroup is evidence enough of prior-
art is someone did try to patent it.
Lance



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

"Johan Torp" <johan.torp@gmail.com> wrote in message
news:3213cba5-ae62-44aa-8209-202223ee7469@d45g2000hsc.googlegroups.com...
>{ I'm assuming that this has some relevance to C++0x or later, but it would
>be
> nice if such relevance could be made explicit. Not all mods are expert in
> every
> aspect of C++, and I just have to guess at the topicality here!
> TIA., -mod }
>
>
> On Sep 7, 2:28 am, Mathias Gaunard <loufo...@gmail.com> wrote:
>> On 6 sep, 18:33,Johan Torp<johan.t...@gmail.com> wrote:
>>
>> > An implementation
>> > of hazard pointers
>>
>> Aren't those patented, and thus, unusable?
>
> Yes, http://www.freepatentsonline.com/y2006/0265373.html
>
> I'm not sure how unusable they are, if they can be used in commercial
> applications with Maged Michael's approval. I can also imagine that
> Michael patented hazard pointers to not get run over by the patents of
> big companies.
>
>> It's just sad how so many things in lock-free programming seem to be
>> patented. What's the point of research if it cannot be used in the
>> real world before decades?
>
> I agree, it's a real shame. Lock-free programming might have a short
> shelf-life too,

C++0x is geared toward providing the ability for programmers to be able to
create portable lock-free programming indeed! Good for C++.

Anyway, you have not done proper research because lock-free programming has
been around for ages. Sorry, but its has already been on the shelf for a
very long time indeed. One simple example:

http://publibz.boulder.ibm.com/epubs/pdf/dz9zr002.pdf

In appendix A, under multi-processing. Freelist and the execellent PLO
instruction.




> since transactional memory is hopefully on the way


BTW, did you know that transaction memory has been around for ages as well?
You need to do some more research. Think of the Journal File System for AIX
in rs/6000:

http://groups.google.com/group/comp....5379a16beb3b69


How would you solve the major caveats?

http://groups.google.com/group/comp.....threads&q=STM

http://groups.google.com/group/comp....ctional+memory

Live-lock for starters:

http://groups.google.com/group/comp....170262d5b55519
(read all; even Intel STM compiler does not have an answer!)


AFAICT, the best thing so far would be the excellent research from AMD.
However, its geared toward creating lock-free algorihtms:

http://groups.google.com/group/comp....9708596c832a18

Lock-free programming is not going away anytime soon indeed.




> and
> since non thread-based programming models will hopefully become more
> and more commonplace. I.e., lock-free programming should be applied
> now, to help extract performance out of today's threading solutions.

Sure. C++0x will be a GREAT help indeed.




> The whole concept of lock-free programming (not the lock-free
> property) seems like a big hack to me

Why???




> , you really do not want to
> program that way but have to with today's software stack if you are to
> extract maximum throughput, responsiveness and to avoid dead-locks.

This is nothing new.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

"Lance Diduck" <lancediduck@nyc.rr.com> wrote in message
news:5881bea8-baf7-4451-a7cf-3200c1745d89@a1g2000hsb.googlegroups.com...
> On Sep 6, 8:28 pm, Mathias Gaunard <loufo...@gmail.com> wrote:
>> On 6 sep, 18:33, Johan Torp <johan.t...@gmail.com> wrote:
>>
>> > An implementation
>> > of hazard pointers
>>
>> Aren't those patented, and thus, unusable?
>> It's just sad how so many things in lock-free programming seem to be
>> patented. What's the point of research if it cannot be used in the
>> real world before decades?
> I have made a lock-free memory reclaimator that works and is not
> patented. Nor do I really care to patent it--there is no way I am
> going to reclaim the patent fee's for something like this.
> It is composed of four pieces:
> 1. Allocator
> 2. intrusive reference counter + version field
> 3. isolated_ptr that obtains pointer suitable for dereferencing (like
> a shared_ptr)
> 4. mutual_ptr that is lock-free, but not dereferenceable (like a
> weak_ptr), that also support CAS
[...]

I posted the following in a forum in which its on-topic:

http://groups.google.com/group/comp....a8fde275843504

Please respond as I am interested in your algorithm. Anyway, there are
several non-patented memory reclamation algorihtms here:

http://atomic-ptr-plus.sourceforge.net


Here is one of mine:

http://webpages.charter.net/appcore/...mple_h_v1.html

Here is another:

http://groups.google.com/group/comp....ed0e3c5496eaa0

If you want instructions on how to use them, please post a query in
comp.programming.threads.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

"Mathias Gaunard" <loufoque@gmail.com> wrote in message
news:c83397e3-56db-4186-b5cc-0c0856dcfa74@y38g2000hsy.googlegroups.com...
> On 7 sep, 13:19, "Chris M. Thomasson" <n...@spam.invalid> wrote:
>
>> RCU is patented and its used within the Linux Kernel.
>
> That's because IBM allows royalty-free usage of RCU for any software
> licensed under GPL.

Right. Its up to the patent holder to decide how his/her invention is going
to be used!

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]