subject:"\[lock\-free\] Simple DWCAS based Proxy Collector, refined... ;\^\)"

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

2018-03-29 Thread Chris M. Thomasson

On Wednesday, March 28, 2018 at 11:20:58 PM UTC-7, Dmitry Vyukov wrote:
>
> On Tue, Mar 27, 2018 at 11:23 PM, Chris M. Thomasson 
>  wrote: 
> > > Fwiw Dmitry, I have been working with fractals a lot lately, and was 
> > > wondering if I could still program a proxy collector from scratch. 
> Remember 
> > > my old collector here: 
> [...]
>
> > Old habits... :) 
>
> > Is there anything new, of just an implementation of old ideas? 
>

Unfortunately, not anything new. I just wanted to see if I can code if from 
scratch.  

Btw, there might be something a little newish coming up. Keep in mind that 
I have not worked on this stuff in a while.

At least Relacy still works for me. Thank you for creating it. :^)

-- 

--- 
You received this message because you are subscribed to the Google Groups 
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to lock-free+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/lock-free/661f1264-2b1f-40b6-aa2a-83a1e3bbab88%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

2018-03-29 Thread Chris M. Thomasson



On Wednesday, March 28, 2018 at 11:20:58 PM UTC-7, Dmitry Vyukov wrote:
>
> On Tue, Mar 27, 2018 at 11:23 PM, Chris M. Thomasson 
>  wrote: 
> > Fwiw Dmitry, I have been working with fractals a lot lately, and was 
> > wondering if I could still program a proxy collector from scratch. 
> Remember 
> > my old collector here: 
> > 
> > http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html 
> > 
> > ? 
> > 
> > You are using it as an example in Relacy. 
> > 
> > Wrt the following code, all of the membars are standalone fence 
> operations 
> > std::atomic_thread_fence. All of the membars in the atomic operations 
> are 
> > relaxed. It uses DWCAS for the acquire function because I wanted to 
> start 
> > out simple. I have also replaced a CAS with XCHG in the collect, or 
> mutate 
> > function if you will.  So far, it works in Relacy. :^) 
> > 
> > Here is a link to my code: 
> > 
> > https://pastebin.com/raw/RKTLyXWt 
> > 
> > ___ 
> > 
> > /* Simple Proxy Collector (DWCAS) - Relacy Version 
> > 
> > http://www.1024cores.net/home/relacy-race-detector 
> > 
> > Copyright 3/27/2018 
> > ___*/ 
> > 
> > 
> > #include  
> > #include  
> > #include  
> > 
> > 
> > /* Membar Abstraction 
> > ___*/ 
> > #define ct_mb_relaxed std::memory_order_relaxed 
> > #define ct_mb_acquire std::memory_order_acquire 
> > #define ct_mb_release std::memory_order_release 
> > #define ct_mb_seq_cst std::memory_order_seq_cst 
> > #define ct_mb_fence(mb_membar) std::atomic_thread_fence(mb_membar) 
> > 
> > 
> > /* Simple Proxy Collector C++11 
> > ___*/ 
> > namespace ct { 
> > namespace proxy { 
> > 
> > // User object base 
> > struct object 
> > { 
> > virtual ~object() {} 
> > }; 
> > 
> > 
> > // Proxy node 
> > struct node 
> > { 
> > std::atomic count; 
> > VAR_T(node*) next; 
> > VAR_T(object*) obj; 
> > 
> > node(std::intptr_t count_, node* next_, object* obj_) 
> > : count(count_), next(next_), obj(obj_) 
> > { 
> > 
> > } 
> > 
> > ~node() 
> > { 
> > 
> > } 
> > }; 
> > 
> > 
> > // DWCAS target 
> > struct anchor 
> > { 
> > std::intptr_t count; 
> > node* head; 
> > 
> > anchor() 
> > { 
> > 
> > } 
> > 
> > anchor(std::intptr_t count_, node* head_) 
> > { 
> > count = count_; 
> > head = head_; 
> > } 
> > 
> > bool operator == (anchor const& right) const 
> > { 
> > return count == right.count && head == right.head; 
> > } 
> > 
> > anchor operator + (anchor const& right) const 
> > { 
> > anchor res; 
> > res.count = count + right.count; 
> > res.head = right.head; 
> > return res; 
> > } 
> > 
> > anchor operator - (anchor const& right) const 
> > { 
> > anchor res; 
> > res.count = count - right.count; 
> > res.head = right.head; 
> > return res; 
> > } 
> > }; 
> > 
> > std::ostream& operator << (std::ostream& s, anchor const& right) 
> > { 
> > return s << "{" << right.count << "," << right.head << "}"; 
> > } 
> > 
> > 
> > // Collector Logic 
> > struct gc 
> > { 
> > std::atomic head; 
> > 
> > gc() : head(anchor{ 0, new node(0, nullptr, nullptr) }) {} 
> > 
> > ~gc() 
> > { 
> > anchor cmp = head.load(ct_mb_relaxed); 
> > RL_ASSERT(cmp.count > -1); 
> > RL_ASSERT(VAR(cmp.head->next) == nullptr); 
> > prv_dtor(cmp.head); 
> > } 
> > 
> > // Drops a reference count on a node 
> > bool prv_release(node* n) 
> > { 
> > std::intptr_t count = n->count.fetch_sub(2, ct_mb_relaxed); 
> > if (count == 3) return true; 
> > return false; 
> > } 
> > 
> > // Deletes a node 
> > void prv_dtor(node* n) 
> > { 
> > object* obj = VAR(n->obj); 
> > if (obj != nullptr) delete obj; 
> > delete n; 
> > } 
> > 
> > // Dumps backlinked nodes 
> > void prv_dump(node* n) 
> > { 
> > node* cur = VAR(n->next); 
> > VAR(n->next) = nullptr; 
> > 
> > // Release and collect in cur LIFO 
> > while (prv_release(cur)) 
> > { 
> > ct_mb_fence(ct_mb_acquire); 
> > node* next = VAR(cur->next); 
> > VAR(cur->next) = n; 
> > n = cur; 
> > cur = next; 
> > } 
> > 
> > // Destroy cur LIFO 
> > while (n) 
> >

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

2018-03-29 Thread Dmitry Vyukov

On Tue, Mar 27, 2018 at 11:23 PM, Chris M. Thomasson
 wrote:
> Fwiw Dmitry, I have been working with fractals a lot lately, and was
> wondering if I could still program a proxy collector from scratch. Remember
> my old collector here:
>
> http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html
>
> ?
>
> You are using it as an example in Relacy.
>
> Wrt the following code, all of the membars are standalone fence operations
> std::atomic_thread_fence. All of the membars in the atomic operations are
> relaxed. It uses DWCAS for the acquire function because I wanted to start
> out simple. I have also replaced a CAS with XCHG in the collect, or mutate
> function if you will.  So far, it works in Relacy. :^)
>
> Here is a link to my code:
>
> https://pastebin.com/raw/RKTLyXWt
>
> ___
>
> /* Simple Proxy Collector (DWCAS) - Relacy Version
>
> http://www.1024cores.net/home/relacy-race-detector
>
> Copyright 3/27/2018
> ___*/
>
>
> #include 
> #include 
> #include 
>
>
> /* Membar Abstraction
> ___*/
> #define ct_mb_relaxed std::memory_order_relaxed
> #define ct_mb_acquire std::memory_order_acquire
> #define ct_mb_release std::memory_order_release
> #define ct_mb_seq_cst std::memory_order_seq_cst
> #define ct_mb_fence(mb_membar) std::atomic_thread_fence(mb_membar)
>
>
> /* Simple Proxy Collector C++11
> ___*/
> namespace ct {
> namespace proxy {
>
> // User object base
> struct object
> {
> virtual ~object() {}
> };
>
>
> // Proxy node
> struct node
> {
> std::atomic count;
> VAR_T(node*) next;
> VAR_T(object*) obj;
>
> node(std::intptr_t count_, node* next_, object* obj_)
> : count(count_), next(next_), obj(obj_)
> {
>
> }
>
> ~node()
> {
>
> }
> };
>
>
> // DWCAS target
> struct anchor
> {
> std::intptr_t count;
> node* head;
>
> anchor()
> {
>
> }
>
> anchor(std::intptr_t count_, node* head_)
> {
> count = count_;
> head = head_;
> }
>
> bool operator == (anchor const& right) const
> {
> return count == right.count && head == right.head;
> }
>
> anchor operator + (anchor const& right) const
> {
> anchor res;
> res.count = count + right.count;
> res.head = right.head;
> return res;
> }
>
> anchor operator - (anchor const& right) const
> {
> anchor res;
> res.count = count - right.count;
> res.head = right.head;
> return res;
> }
> };
>
> std::ostream& operator << (std::ostream& s, anchor const& right)
> {
> return s << "{" << right.count << "," << right.head << "}";
> }
>
>
> // Collector Logic
> struct gc
> {
> std::atomic head;
>
> gc() : head(anchor{ 0, new node(0, nullptr, nullptr) }) {}
>
> ~gc()
> {
> anchor cmp = head.load(ct_mb_relaxed);
> RL_ASSERT(cmp.count > -1);
> RL_ASSERT(VAR(cmp.head->next) == nullptr);
> prv_dtor(cmp.head);
> }
>
> // Drops a reference count on a node
> bool prv_release(node* n)
> {
> std::intptr_t count = n->count.fetch_sub(2, ct_mb_relaxed);
> if (count == 3) return true;
> return false;
> }
>
> // Deletes a node
> void prv_dtor(node* n)
> {
> object* obj = VAR(n->obj);
> if (obj != nullptr) delete obj;
> delete n;
> }
>
> // Dumps backlinked nodes
> void prv_dump(node* n)
> {
> node* cur = VAR(n->next);
> VAR(n->next) = nullptr;
>
> // Release and collect in cur LIFO
> while (prv_release(cur))
> {
> ct_mb_fence(ct_mb_acquire);
> node* next = VAR(cur->next);
> VAR(cur->next) = n;
> n = cur;
> cur = next;
> }
>
> // Destroy cur LIFO
> while (n)
> {
> node* next = VAR(n->next);
> prv_dtor(n);
> n = next;
> }
> }
>
> // Collects a node
> void prv_collect(node* n)
> {
> anchor xchg = { 0, n };
>
> ct_mb_fence(ct_mb_release);
>
> // Swap in new node
> anchor cmp = head.exchange(xchg, ct_mb_relaxed);
>
> // Backlink
> ct_mb_fence(ct_mb_acquire);
> VAR(cmp.head->next) = xchg.head;
> ct_mb_fence(ct_mb_release);
>
> // Release and mark as

[lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

2018-03-27 Thread Chris M. Thomasson

Fwiw Dmitry , I have been 
working with fractals a lot lately, and was wondering if I could still 
program a proxy collector from scratch. Remember my old collector here:

http://webpages.charter.net/appcore/misc/pc_sample_h_v1.html

?

You are using it as an example in Relacy.

Wrt the following code, all of the membars are standalone fence operations 
std::atomic_thread_fence. 
All of the membars in the atomic operations are relaxed. It uses DWCAS for 
the acquire function because I wanted to start out simple. I have also 
replaced a CAS with XCHG in the collect, or mutate function if you will.  So 
far, it works in Relacy. :^)

Here is a link to my code:

https://pastebin.com/raw/RKTLyXWt

___

/* Simple Proxy Collector (DWCAS) - Relacy Version

http://www.1024cores.net/home/relacy-race-detector

Copyright 3/27/2018
___*/


#include 
#include 
#include 


/* Membar Abstraction
___*/
#define ct_mb_relaxed std::memory_order_relaxed
#define ct_mb_acquire std::memory_order_acquire
#define ct_mb_release std::memory_order_release
#define ct_mb_seq_cst std::memory_order_seq_cst
#define ct_mb_fence(mb_membar) std::atomic_thread_fence(mb_membar) 


/* Simple Proxy Collector C++11
___*/
namespace ct { 
namespace proxy {

// User object base
struct object
{
virtual ~object() {}
};


// Proxy node
struct node
{
std::atomic count;
VAR_T(node*) next;
VAR_T(object*) obj;

node(std::intptr_t count_, node* next_, object* obj_)
: count(count_), next(next_), obj(obj_)
{

}

~node()
{

}
};


// DWCAS target
struct anchor
{
std::intptr_t count;
node* head;

anchor()
{

}

anchor(std::intptr_t count_, node* head_)
{
count = count_;
head = head_;
}

bool operator == (anchor const& right) const
{
return count == right.count && head == right.head;
}

anchor operator + (anchor const& right) const
{
anchor res;
res.count = count + right.count;
res.head = right.head;
return res;
}

anchor operator - (anchor const& right) const
{
anchor res;
res.count = count - right.count;
res.head = right.head;
return res;
}
};

std::ostream& operator << (std::ostream& s, anchor const& right)
{
return s << "{" << right.count << "," << right.head << "}";
}


// Collector Logic
struct gc
{
std::atomic head;

gc() : head(anchor{ 0, new node(0, nullptr, nullptr) }) {}

~gc()
{
anchor cmp = head.load(ct_mb_relaxed);
RL_ASSERT(cmp.count > -1);
RL_ASSERT(VAR(cmp.head->next) == nullptr);
prv_dtor(cmp.head);
}

// Drops a reference count on a node
bool prv_release(node* n)
{
std::intptr_t count = n->count.fetch_sub(2, ct_mb_relaxed);
if (count == 3) return true;
return false;
}

// Deletes a node
void prv_dtor(node* n)
{
object* obj = VAR(n->obj);
if (obj != nullptr) delete obj;
delete n;
}

// Dumps backlinked nodes
void prv_dump(node* n)
{
node* cur = VAR(n->next);
VAR(n->next) = nullptr;

// Release and collect in cur LIFO
while (prv_release(cur))
{
ct_mb_fence(ct_mb_acquire);
node* next = VAR(cur->next);
VAR(cur->next) = n;
n = cur;
cur = next;
}

// Destroy cur LIFO
while (n)
{
node* next = VAR(n->next);
prv_dtor(n);
n = next;
}
}

// Collects a node
void prv_collect(node* n)
{
anchor xchg = { 0, n };

ct_mb_fence(ct_mb_release);

// Swap in new node
anchor cmp = head.exchange(xchg, ct_mb_relaxed);

// Backlink
ct_mb_fence(ct_mb_acquire);
VAR(cmp.head->next) = xchg.head;
ct_mb_fence(ct_mb_release);

// Release and mark as collected
std::intptr_t count = cmp.head->count.fetch_add(cmp.count + 1, 
ct_mb_relaxed);

if (count + cmp.count == 0)
{
prv_dump(cmp.head);
}
}


// Acquires current node
node* acquire()
{
anchor cmp = head.load(ct_mb_relaxed);
anchor xchg =

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

[lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

4 matches

Site Navigation

Mail list logo

Footer information