Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

You are an insult to my intelligence! I demand that you log off immediately.


devel / comp.lang.c++ / xchg based thing...

SubjectAuthor
* xchg based thing...Chris M. Thomasson
+- Re: xchg based thing...Chris M. Thomasson
+- Re: xchg based thing...Chris M. Thomasson
+* Re: xchg based thing...Chris M. Thomasson
|+* Re: xchg based thing...Chris M. Thomasson
||`- Re: xchg based thing...Chris M. Thomasson
|`* Re: xchg based thing...Chris M. Thomasson
| `- Re: xchg based thing...Chris M. Thomasson
+* Re: xchg based thing...Chris M. Thomasson
|`* Re: xchg based thing...Chris M. Thomasson
| +* Re: xchg based thing...Chris M. Thomasson
| |`* Re: xchg based thing...Chris M. Thomasson
| | `- Re: xchg based thing...Chris M. Thomasson
| `- Re: xchg based thing...Chris M. Thomasson
+- Re: xchg based thing...Chris M. Thomasson
+- Re: xchg based thing...Chris M. Thomasson
`* Re: xchg based thing...Chris M. Thomasson
 `- Re: xchg based thing...Chris M. Thomasson

1
xchg based thing...

<uk1c4s$3lfmh$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2822&group=comp.lang.c%2B%2B#2822

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: xchg based thing...
Date: Sun, 26 Nov 2023 22:14:52 -0800
Organization: A noiseless patient Spider
Lines: 245
Message-ID: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 27 Nov 2023 06:14:52 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="30f2cf8ee5bf5c1f108724574b2965a0";
logging-data="3849937"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/lrc1dd0682hTVMdVLy90iP+LPG1HRLco="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:2vuIYDpaTglyTpEHw8Y2AVNlqZY=
Content-Language: en-US
 by: Chris M. Thomasson - Mon, 27 Nov 2023 06:14 UTC

Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
work queue thing. Not sure how to classify it quite yet. I am going to
use it as a work "queue" for my parts of my CPU based rendering engine,
no need for it wrt my shader work. However, I needed to do it. It's
passing Relacy tests. That's a good thing. Now I need to add in a slow
path so it can wait in the kernel during periods of no work. I think an
eventcount should work for it. Or perhaps I might integrate some state
in the pointer values for futexes, or whatever. I have not made up my
mind yet.

I will port my Relacy test units over to standard C++. It's not all that
hard. In fact, it's rather straightforward.

Speaking of pointer values, take note of CT_PENDING.

The fun part about this scheme is that it only uses atomic exchange for
its logic. It also has wait-free loopless push and flush:

void push(work* w)
{
// this completes the pending logic...
w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
work* head = m_head.exchange(w, rl::mo_release, $);
w->m_next.store(head, rl::mo_release, $);
}

work* flush()
{
return m_head.exchange(nullptr, rl::mo_acquire, $);
}

Here is my current Relacy test unit:

https://github.com/dvyukov/relacy
_______________________________
#include <iostream>
#include <relacy/relacy.hpp>

#define CT_PRODUCERS_N 2
#define CT_CONSUMERS_N 3
#define CT_THREAD_N (CT_PRODUCERS_N + CT_CONSUMERS_N)

// Notes:
// Using spin backoff for waits as of now
// Need to slow-path it with with kernel waits
// Need to refine the per-node backoff

// humm...
#define CT_PENDING ((ct_xchg_lifo_ver_001::work*)(0xDEADBEEF))

struct ct_xchg_lifo_ver_001
{

// simulate some work...
struct work
{
rl::atomic<work*> m_next;
VAR_T(unsigned long) m_work;

work()
: m_next(CT_PENDING),
m_work(0)
{

}

~work()
{
RL_ASSERT(VAR(m_work) == 1);
}

// no data races on m_work!
void execute_work()
{
VAR(m_work) += 1;
}

// this is the pending node logic...
work* get_next()
{
work* next = m_next.load(rl::mo_consume, $);

while (next == CT_PENDING)
{
rl::backoff();
next = m_next.load(rl::mo_consume, $);
}

return next;
}
};

rl::atomic<work*> m_head;

ct_xchg_lifo_ver_001()
: m_head(nullptr)
{

}

~ct_xchg_lifo_ver_001()
{
RL_ASSERT(! m_head.load(rl::mo_relaxed, $));
}

void push(work* w)
{
// this completes the pending logic...
w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
work* head = m_head.exchange(w, rl::mo_release, $);
w->m_next.store(head, rl::mo_release, $);
}

work* flush()
{
return m_head.exchange(nullptr, rl::mo_acquire, $);
}

void process(work* cur)
{
// process work nodes...

while (cur)
{
// do real work _before_ the pending logic
// this is highly beneficial.
cur->execute_work();

// get the next work node.
cur = cur->get_next();
}
}

// dump worked on nodes...
void destroy(work* cur)
{
while (cur)
{
work* next = cur->m_next.load(rl::mo_relaxed, $);

// no pending work shall be destroyed!
RL_ASSERT(next != CT_PENDING);

delete cur;
cur = next;
}
}
};

struct ct_relacy_test_fun : rl::test_suite<ct_relacy_test_fun, CT_THREAD_N>
{ ct_xchg_lifo_ver_001 m_work_lifo;

void before()
{

}

void after()
{
ct_xchg_lifo_ver_001::work* w = m_work_lifo.flush();
m_work_lifo.process(w);
m_work_lifo.destroy(w);
}

void producer(unsigned int tidx)
{
ct_xchg_lifo_ver_001::work* w = new ct_xchg_lifo_ver_001::work();
m_work_lifo.push(w);
}

void consumer(unsigned int tidx)
{
ct_xchg_lifo_ver_001::work* w = m_work_lifo.flush();
m_work_lifo.process(w);
m_work_lifo.destroy(w);
}

void thread(unsigned int tidx)
{
if (tidx < CT_PRODUCERS_N)
{
// producer threads
producer(tidx);
}

else
{
// consumer threads
consumer(tidx);
}
}
};

int
main()
{ std::cout << "Exchange LIFO Container Experiment ver:0.0.1\n";
std::cout << "Relacy Unit Test ver:0.0.1\n";
std::cout << "by: Chris M. Thomasson\n";
std::cout << "__________________________________\n" << std::endl;

{
rl::test_params p;

p.iteration_count = 400000;
//p.execution_depth_limit = 33333;
//p.search_type = rl::sched_bound;
//p.search_type = rl::fair_full_search_scheduler_type;
//p.search_type = rl::fair_context_bound_scheduler_type;

std::cout << "Executing Relacy Unit Test...\n";
std::cout << "__________________________________" << std::endl;

rl::simulate<ct_relacy_test_fun>(p);
}

return 0;
} _______________________________

Re: xchg based thing...

<uk1cff$3li7q$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2823&group=comp.lang.c%2B%2B#2823

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sun, 26 Nov 2023 22:20:31 -0800
Organization: A noiseless patient Spider
Lines: 88
Message-ID: <uk1cff$3li7q$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 27 Nov 2023 06:20:31 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="30f2cf8ee5bf5c1f108724574b2965a0";
logging-data="3852538"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+yWP8XBEp16EcYsD4aUB1Yd8w7UqVsM3Q="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:A5a9j4slKVc+i8ohYQyr2qzySbg=
Content-Language: en-US
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
 by: Chris M. Thomasson - Mon, 27 Nov 2023 06:20 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
> use it as a work "queue" for my parts of my CPU based rendering engine,
> no need for it wrt my shader work. However, I needed to do it. It's
> passing Relacy tests. That's a good thing. Now I need to add in a slow
> path so it can wait in the kernel during periods of no work. I think an
> eventcount should work for it. Or perhaps I might integrate some state
> in the pointer values for futexes, or whatever. I have not made up my
> mind yet.
>
> I will port my Relacy test units over to standard C++. It's not all that
> hard. In fact, it's rather straightforward.
>
> Speaking of pointer values, take note of CT_PENDING.
>
> The fun part about this scheme is that it only uses atomic exchange for
> its logic. It also has wait-free loopless push and flush:
>
>
>     void push(work* w)
>     {
>         // this completes the pending logic...
>         w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
>         work* head = m_head.exchange(w, rl::mo_release, $);
>         w->m_next.store(head, rl::mo_release, $);
>     }
>
>
>     work* flush()
>     {
>         return m_head.exchange(nullptr, rl::mo_acquire, $);
>     }
>
>
> Here is my current Relacy test unit:
>
> https://github.com/dvyukov/relacy
> _______________________________
> #include <iostream>
> #include <relacy/relacy.hpp>
>
>
> #define CT_PRODUCERS_N 2
> #define CT_CONSUMERS_N 3
> #define CT_THREAD_N (CT_PRODUCERS_N + CT_CONSUMERS_N)
>
>
> // Notes:
> // Using spin backoff for waits as of now
> // Need to slow-path it with with kernel waits
> // Need to refine the per-node backoff
>
>
> // humm...
> #define CT_PENDING ((ct_xchg_lifo_ver_001::work*)(0xDEADBEEF))
>
> struct ct_xchg_lifo_ver_001
> {
> [...]
>         // this is the pending node logic...
>         work* get_next()
>         {
>             work* next = m_next.load(rl::mo_consume, $);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Now, I think I might be able to get away with using a relaxed membar
here instead of consume. I think so because of the acquire release
relation ship between the push and flush functions. This is were Relacy
can come in handy. I will have some more time to work on it later on
tonight. I need to test that. I don't think a consume membar is needed
here. I think relaxed should work fine. Not exactly sure right now.

>
>             while (next == CT_PENDING)
>             {
>                 rl::backoff();
>                 next = m_next.load(rl::mo_consume, $);
>             }
>
>             return next;
>         }
>     };
[...]

Re: xchg based thing...

<uk1cpb$3li7q$3@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2825&group=comp.lang.c%2B%2B#2825

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!news.hispagatos.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sun, 26 Nov 2023 22:25:47 -0800
Organization: A noiseless patient Spider
Lines: 56
Message-ID: <uk1cpb$3li7q$3@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 27 Nov 2023 06:25:47 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="30f2cf8ee5bf5c1f108724574b2965a0";
logging-data="3852538"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/qnQ71MDwi2TyRjIMBJ6P76CqW/0LdTrA="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:EJ8w3zoFGXvhjFCHFopGNrJsdAs=
Content-Language: en-US
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
 by: Chris M. Thomasson - Mon, 27 Nov 2023 06:25 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
> use it as a work "queue" for my parts of my CPU based rendering engine,
> no need for it wrt my shader work. However, I needed to do it. It's
> passing Relacy tests. That's a good thing. Now I need to add in a slow
> path so it can wait in the kernel during periods of no work. I think an
> eventcount should work for it. Or perhaps I might integrate some state
> in the pointer values for futexes, or whatever. I have not made up my
> mind yet.
>
> I will port my Relacy test units over to standard C++. It's not all that
> hard. In fact, it's rather straightforward.
>
> Speaking of pointer values, take note of CT_PENDING.
>
> The fun part about this scheme is that it only uses atomic exchange for
> its logic. It also has wait-free loopless push and flush:
>
>
>     void push(work* w)
>     {
>         // this completes the pending logic...
>         w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
>         work* head = m_head.exchange(w, rl::mo_release, $);
>         w->m_next.store(head, rl::mo_release, $);
>     }
>
>
>     work* flush()
>     {
>         return m_head.exchange(nullptr, rl::mo_acquire, $);
>     }
>
>
> Here is my current Relacy test unit:
>
> https://github.com/dvyukov/relacy
> _______________________________
[...]
>     void push(work* w)
>     {
>         // this completes the pending logic...
>         w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
>         work* head = m_head.exchange(w, rl::mo_release, $);

>         w->m_next.store(head, rl::mo_release, $);
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

I also think I can use relaxed for that store! Humm... I just need to
test it. Tonight is going to be fun. :^)

>     }
[...]

Re: xchg based thing...

<uk3jgf$ghe$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2839&group=comp.lang.c%2B%2B#2839

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Mon, 27 Nov 2023 18:32:46 -0800
Organization: A noiseless patient Spider
Lines: 303
Message-ID: <uk3jgf$ghe$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Tue, 28 Nov 2023 02:32:47 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="0cb77dcc24e2a1d3ec41353ca82b05d6";
logging-data="16942"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19jtxWyxr0otZymH0Dbcx0uVEOcOita2nM="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:jIPHXHVDbkHy6L156b/hgZS1ik4=
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Tue, 28 Nov 2023 02:32 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
> use it as a work "queue" for my parts of my CPU based rendering engine,
> no need for it wrt my shader work. However, I needed to do it. It's
> passing Relacy tests. That's a good thing. Now I need to add in a slow
> path so it can wait in the kernel during periods of no work. I think an
> eventcount should work for it. Or perhaps I might integrate some state
> in the pointer values for futexes, or whatever. I have not made up my
> mind yet.
>
> I will port my Relacy test units over to standard C++. It's not all that
> hard. In fact, it's rather straightforward.
>
> Speaking of pointer values, take note of CT_PENDING.
>
> The fun part about this scheme is that it only uses atomic exchange for
> its logic. It also has wait-free loopless push and flush:
[...]

Fwiw, here is just a little exploration into distributing it. I will
make a home for it on GitHub. Check it out, my simple first venture into
distributing the work across this experiment wrt n-threads. Take careful
notice of local work vs. foreign work.

I managed to streamline the memory barriers to the weakest possible. Got
rid of a release membar, and a consume membar. I don't think it can get
any weaker without being incorrect.

___________________________
#include <iostream>
#include <cstddef>
#include <relacy/relacy.hpp>

#define CT_THREAD_N 5
#define CT_WORK_N 3
#define CT_PRODUCER_WORK_N 5
#define CT_CONSUMER_WORK_N 2
#define CT_DISTRIBUTE_WORK_N CT_THREAD_N

// Notes:
// Using spin backoff for waits as of now
// Need to slow-path it with with kernel waits
// Need to refine the per-node backoff

// humm...
#define CT_PENDING ((ct_xchg_lifo_ver_001::work*)(0xDEADBEEF))

static unsigned long g_stats_local_work = 0;
static unsigned long g_stats_foreign_work = 0;

struct ct_xchg_lifo_ver_001
{

// simulate some work...
struct work
{
rl::atomic<work*> m_next;
VAR_T(unsigned long) m_work;
VAR_T(unsigned long) m_tidx;

work(unsigned long tidx)
: m_next(CT_PENDING),
m_work(0),
m_tidx(tidx)
{

}

~work()
{
RL_ASSERT(VAR(m_work) == 1);
}

// no data races on m_work!
void execute_work(unsigned long tidx)
{
VAR(m_work) += 1;

unsigned long local_tidx = VAR(m_tidx);

if (local_tidx != tidx)
{
g_stats_foreign_work += 1;
/*
std::cout << "foriegn work detected "
<< local_tidx
<< " -> "
<< tidx
<< std::endl;
*/
}

else
{
g_stats_local_work += 1;

/*
std::cout << "local work detected "
<< local_tidx
<< " -> "
<< tidx
<< std::endl;
*/
}
}

// this is the pending node logic...
work* get_next()
{
work* next = m_next.load(rl::mo_relaxed, $);

while (next == CT_PENDING)
{
rl::backoff();
next = m_next.load(rl::mo_relaxed, $);
}

return next;
}

static void process(work* cur, unsigned long tidx)
{
// must not be pending!
RL_ASSERT(cur != CT_PENDING);

// process work nodes...

while (cur)
{
// do real work _before_ the pending logic
// this is highly beneficial... Big time!
cur->execute_work(tidx);

// get the next work node.
cur = cur->get_next();
}
}

// dump worked on nodes...
static void destroy(work* cur, unsigned long tidx)
{
// no pending work shall be destroyed!
RL_ASSERT(cur != CT_PENDING);

while (cur)
{
work* next = cur->m_next.load(rl::mo_relaxed, $);

// no pending work shall be destroyed!
RL_ASSERT(next != CT_PENDING);

delete cur;
cur = next;
}
}
};

rl::atomic<work*> m_head;

ct_xchg_lifo_ver_001()
: m_head(nullptr)
{

}

~ct_xchg_lifo_ver_001()
{
RL_ASSERT(! m_head.load(rl::mo_relaxed, $));
}

void push(work* w)
{
// this completes the pending logic...
w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
work* head = m_head.exchange(w, rl::mo_release, $);
w->m_next.store(head, rl::mo_relaxed, $);
}

work* flush()
{
return m_head.exchange(nullptr, rl::mo_acquire, $);
}
};

// A test of a simple way to distribute work
// Using the ct_xchg_lifo_ver_001 API
template<typename T, std::size_t T_N>
struct ct_distribute_ver_001
{ T m_table[T_N];
typedef typename T::work work;

void push(work* w, unsigned int tidx)
{
T& t = m_table[tidx % T_N];
t.push(w);
}

work* pop(unsigned int tidx)
{
for (std::size_t i = 0; i < T_N; ++i)
{
T& t = m_table[(i + tidx) % T_N];
work* w = t.flush();
if (w) return w;
}

return nullptr;
}
};

// Relacy Test Unit...
struct ct_relacy_test_fun
: rl::test_suite<ct_relacy_test_fun, CT_THREAD_N>
{ typedef ct_distribute_ver_001<
ct_xchg_lifo_ver_001,
CT_DISTRIBUTE_WORK_N
> distribute;

distribute m_work;

void thread(unsigned int tidx)
{
for (unsigned long wi = 0; wi < CT_WORK_N; ++wi)
{
for (unsigned long i = 0; i < CT_PRODUCER_WORK_N; ++i)
{
distribute::work* w = new distribute::work(tidx);
m_work.push(w, tidx);
}

for (unsigned long i = 0; i < CT_CONSUMER_WORK_N; ++i)
{
distribute::work* w = m_work.pop(tidx);
distribute::work::process(w, tidx);
distribute::work::destroy(w, tidx);
}
}
}
};

int
main()
{ std::cout << "Exchange LIFO Container Experiment ver:0.0.2\n";
std::cout << "Relacy Unit Test ver:0.0.2\n";
std::cout << "by: Chris M. Thomasson\n";
std::cout << "__________________________________\n" << std::endl;

{
rl::test_params p;

p.iteration_count = 1000000;
//p.execution_depth_limit = 33333;
//p.search_type = rl::sched_bound;
//p.search_type = rl::fair_full_search_scheduler_type;
//p.search_type = rl::fair_context_bound_scheduler_type;

std::cout << "Executing Relacy Unit Test...\n";
std::cout << "__________________________________" << std::endl;

rl::simulate<ct_relacy_test_fun>(p);

std::cout << "\nwork load "
<< g_stats_local_work
<< ", "
<< g_stats_foreign_work
<< std::endl;
}

return 0;
} ___________________________

Re: xchg based thing...

<uk3jje$i47$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2840&group=comp.lang.c%2B%2B#2840

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Mon, 27 Nov 2023 18:34:22 -0800
Organization: A noiseless patient Spider
Lines: 98
Message-ID: <uk3jje$i47$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <uk3jgf$ghe$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 28 Nov 2023 02:34:22 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="0cb77dcc24e2a1d3ec41353ca82b05d6";
logging-data="18567"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19gMEtp75iPzIBAIM82WHMh7I/SGM24iVo="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:doZe/kKHEBvBgmYNYzXXqUb8EZM=
Content-Language: en-US
In-Reply-To: <uk3jgf$ghe$1@dont-email.me>
 by: Chris M. Thomasson - Tue, 28 Nov 2023 02:34 UTC

On 11/27/2023 6:32 PM, Chris M. Thomasson wrote:
> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>> Fwiw, here is a quick and dirty mock up of my atomic exchange based
>> lifo work queue thing. Not sure how to classify it quite yet. I am
>> going to use it as a work "queue" for my parts of my CPU based
>> rendering engine, no need for it wrt my shader work. However, I needed
>> to do it. It's passing Relacy tests. That's a good thing. Now I need
>> to add in a slow path so it can wait in the kernel during periods of
>> no work. I think an eventcount should work for it. Or perhaps I might
>> integrate some state in the pointer values for futexes, or whatever. I
>> have not made up my mind yet.
>>
>> I will port my Relacy test units over to standard C++. It's not all
>> that hard. In fact, it's rather straightforward.
>>
>> Speaking of pointer values, take note of CT_PENDING.
>>
>> The fun part about this scheme is that it only uses atomic exchange
>> for its logic. It also has wait-free loopless push and flush:
> [...]
>
> Fwiw, here is just a little exploration into distributing it. I will
> make a home for it on GitHub. Check it out, my simple first venture into
> distributing the work across this experiment wrt n-threads. Take careful
> notice of local work vs. foreign work.
>
>
> I managed to streamline the memory barriers to the weakest possible. Got
> rid of a release membar, and a consume membar. I don't think it can get
> any weaker without being incorrect.
>
> ___________________________
> #include <iostream>
> #include <cstddef>
> #include <relacy/relacy.hpp>
>
>
> #define CT_THREAD_N 5
> #define CT_WORK_N 3
> #define CT_PRODUCER_WORK_N 5
> #define CT_CONSUMER_WORK_N 2
> #define CT_DISTRIBUTE_WORK_N CT_THREAD_N
>
>
> // Notes:
> // Using spin backoff for waits as of now
> // Need to slow-path it with with kernel waits
> // Need to refine the per-node backoff
>
>
> // humm...
> #define CT_PENDING ((ct_xchg_lifo_ver_001::work*)(0xDEADBEEF))
>
> static unsigned long g_stats_local_work = 0;
> static unsigned long g_stats_foreign_work = 0;
>
>
> struct ct_xchg_lifo_ver_001
> {
>
>     // simulate some work...
>     struct work
>     {
>         rl::atomic<work*> m_next;
>         VAR_T(unsigned long) m_work;
>         VAR_T(unsigned long) m_tidx;
>
>
>         work(unsigned long tidx)
>         :   m_next(CT_PENDING),
>             m_work(0),
>             m_tidx(tidx)
>         {
>
>         }
>
>
>         ~work()
>         {
>             RL_ASSERT(VAR(m_work) == 1);
>         }
>
>
>         // no data races on m_work!
>         void execute_work(unsigned long tidx)
>         {
>             VAR(m_work) += 1;
>
>             unsigned long local_tidx = VAR(m_tidx);
>
>             if (local_tidx != tidx)
>             {
>                 g_stats_foreign_work += 1;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Fwiw, this is an out of bound stat that I am using. If I were keeping
stats in a real C++ impl, I would use split counters.
[...]

Re: xchg based thing...

<uk8hhc$11dma$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2844&group=comp.lang.c%2B%2B#2844

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!news.chmurka.net!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Wed, 29 Nov 2023 15:29:47 -0800
Organization: A noiseless patient Spider
Lines: 102
Message-ID: <uk8hhc$11dma$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <uk3jgf$ghe$1@dont-email.me>
<uk3jje$i47$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 29 Nov 2023 23:29:48 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="b48c7c6d1e544a3703bdce74e7ea16a2";
logging-data="1095370"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18fVMeY0nWFkOAP+C7j8r/HXwyoM5Crbjc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:+d70DFRigWzC5lCWolHXaC8pOno=
Content-Language: en-US
In-Reply-To: <uk3jje$i47$1@dont-email.me>
 by: Chris M. Thomasson - Wed, 29 Nov 2023 23:29 UTC

On 11/27/2023 6:34 PM, Chris M. Thomasson wrote:
> On 11/27/2023 6:32 PM, Chris M. Thomasson wrote:
>> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>>> Fwiw, here is a quick and dirty mock up of my atomic exchange based
>>> lifo work queue thing. Not sure how to classify it quite yet. I am
>>> going to use it as a work "queue" for my parts of my CPU based
>>> rendering engine, no need for it wrt my shader work. However, I
>>> needed to do it. It's passing Relacy tests. That's a good thing. Now
>>> I need to add in a slow path so it can wait in the kernel during
>>> periods of no work. I think an eventcount should work for it. Or
>>> perhaps I might integrate some state in the pointer values for
>>> futexes, or whatever. I have not made up my mind yet.
>>>
>>> I will port my Relacy test units over to standard C++. It's not all
>>> that hard. In fact, it's rather straightforward.
>>>
>>> Speaking of pointer values, take note of CT_PENDING.
>>>
>>> The fun part about this scheme is that it only uses atomic exchange
>>> for its logic. It also has wait-free loopless push and flush:
>> [...]
>>
>> Fwiw, here is just a little exploration into distributing it. I will
>> make a home for it on GitHub. Check it out, my simple first venture
>> into distributing the work across this experiment wrt n-threads. Take
>> careful notice of local work vs. foreign work.
>>
>>
>> I managed to streamline the memory barriers to the weakest possible.
>> Got rid of a release membar, and a consume membar. I don't think it
>> can get any weaker without being incorrect.
>>
>> ___________________________
>> #include <iostream>
>> #include <cstddef>
>> #include <relacy/relacy.hpp>
>>
>>
>> #define CT_THREAD_N 5
>> #define CT_WORK_N 3
>> #define CT_PRODUCER_WORK_N 5
>> #define CT_CONSUMER_WORK_N 2
>> #define CT_DISTRIBUTE_WORK_N CT_THREAD_N
>>
>>
>> // Notes:
>> // Using spin backoff for waits as of now
>> // Need to slow-path it with with kernel waits
>> // Need to refine the per-node backoff
>>
>>
>> // humm...
>> #define CT_PENDING ((ct_xchg_lifo_ver_001::work*)(0xDEADBEEF))
>>
>> static unsigned long g_stats_local_work = 0;
>> static unsigned long g_stats_foreign_work = 0;
>>
>>
>> struct ct_xchg_lifo_ver_001
>> {
>>
>>      // simulate some work...
>>      struct work
>>      {
>>          rl::atomic<work*> m_next;
>>          VAR_T(unsigned long) m_work;
>>          VAR_T(unsigned long) m_tidx;
>>
>>
>>          work(unsigned long tidx)
>>          :   m_next(CT_PENDING),
>>              m_work(0),
>>              m_tidx(tidx)
>>          {
>>
>>          }
>>
>>
>>          ~work()
>>          {
>>              RL_ASSERT(VAR(m_work) == 1);
>>          }
>>
>>
>>          // no data races on m_work!
>>          void execute_work(unsigned long tidx)
>>          {
>>              VAR(m_work) += 1;
>>
>>              unsigned long local_tidx = VAR(m_tidx);
>>
>>              if (local_tidx != tidx)
>>              {
>>                  g_stats_foreign_work += 1;
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>
> Fwiw, this is an out of bound stat that I am using. If I were keeping
> stats in a real C++ impl, I would use split counters.
> [...]

Actually, I should refer to the stats as out-of-band state that is
outside of the Relacy unit test.

Re: xchg based thing...

<ukbnj5$1oamk$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2845&group=comp.lang.c%2B%2B#2845

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!rocksolid2!news.neodome.net!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Thu, 30 Nov 2023 20:31:32 -0800
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <ukbnj5$1oamk$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <uk3jgf$ghe$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 1 Dec 2023 04:31:33 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="cf0aea544530b4574af4925a1242e520";
logging-data="1845972"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18tRUL6Ib222ungssvpblcyXHDsAbZfWxg="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:aU5mTAagB9VOW+b9KyVFrqKq+6k=
In-Reply-To: <uk3jgf$ghe$1@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Fri, 1 Dec 2023 04:31 UTC

On 11/27/2023 6:32 PM, Chris M. Thomasson wrote:
> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>> Fwiw, here is a quick and dirty mock up of my atomic exchange based
>> lifo work queue thing. Not sure how to classify it quite yet. [...]
>         static void process(work* cur, unsigned long tidx)
>         {
>             // must not be pending!
>             RL_ASSERT(cur != CT_PENDING);
>
>             // process work nodes...
>
>             while (cur)
>             {
>                 // do real work _before_ the pending logic
>                 // this is highly beneficial... Big time!
>                 cur->execute_work(tidx);
>
>                 // get the next work node.
>                 cur = cur->get_next();
>             }
>         }
[...]
There are several ways to allow the next work to be passed to another
thread if the real work is compute intensive, so to speak.

Re: xchg based thing...

<ukg7dk$2gpd6$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2847&group=comp.lang.c%2B%2B#2847

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 13:26:11 -0800
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <ukg7dk$2gpd6$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <uk3jgf$ghe$1@dont-email.me>
<ukbnj5$1oamk$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 2 Dec 2023 21:26:12 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="d31985ac4d5adade32b60c58e4949fb1";
logging-data="2647462"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19pY+XNWNzepHTgnTBXmFzs6dcwyVZhGD8="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:4neyumFdaxPsjGSIbfIpeSmHEBw=
In-Reply-To: <ukbnj5$1oamk$1@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Sat, 2 Dec 2023 21:26 UTC

On 11/30/2023 8:31 PM, Chris M. Thomasson wrote:
> On 11/27/2023 6:32 PM, Chris M. Thomasson wrote:
>> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>>> Fwiw, here is a quick and dirty mock up of my atomic exchange based
>>> lifo work queue thing. Not sure how to classify it quite yet. [...]
>>          static void process(work* cur, unsigned long tidx)
>>          {
>>              // must not be pending!
>>              RL_ASSERT(cur != CT_PENDING);
>>
>>              // process work nodes...
>>
>>              while (cur)
>>              {
>>                  // do real work _before_ the pending logic
>>                  // this is highly beneficial... Big time!
>>                  cur->execute_work(tidx);
>>
>>                  // get the next work node.
>>                  cur = cur->get_next();
>>              }
>>          }
> [...]
> There are several ways to allow the next work to be passed to another
> thread if the real work is compute intensive, so to speak.

Another fun aspect of this is that it can be distributed in many
different ways. Keep in mind that it only using atomic exchange...

Re: xchg based thing...

<ukg7th$2gpd6$2@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2848&group=comp.lang.c%2B%2B#2848

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 13:34:41 -0800
Organization: A noiseless patient Spider
Lines: 140
Message-ID: <ukg7th$2gpd6$2@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 2 Dec 2023 21:34:41 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="d31985ac4d5adade32b60c58e4949fb1";
logging-data="2647462"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX187gqE0Q8c+TtY10dR2V3I2EUWXyqYNDTI="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:DSmKLuW0crME/K0tiYeQLEsWHkY=
Content-Language: en-US
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
 by: Chris M. Thomasson - Sat, 2 Dec 2023 21:34 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
> use it as a work "queue" for my parts of my CPU based rendering engine,
> no need for it wrt my shader work. However, I needed to do it. It's
> passing Relacy tests. That's a good thing. Now I need to add in a slow
> path so it can wait in the kernel during periods of no work. I think an
> eventcount should work for it. Or perhaps I might integrate some state
> in the pointer values for futexes, or whatever. I have not made up my
> mind yet.
>
> I will port my Relacy test units over to standard C++. It's not all that
> hard. In fact, it's rather straightforward.
>
> Speaking of pointer values, take note of CT_PENDING.
>
> The fun part about this scheme is that it only uses atomic exchange for
> its logic. It also has wait-free loopless push and flush:
>
>
>     void push(work* w)
>     {
>         // this completes the pending logic...
>         w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
>         work* head = m_head.exchange(w, rl::mo_release, $);
>         w->m_next.store(head, rl::mo_release, $);
>     }
>
>
>     work* flush()
>     {
>         return m_head.exchange(nullptr, rl::mo_acquire, $);
>     }
>
>
> Here is my current Relacy test unit:
>
> https://github.com/dvyukov/relacy
> _______________________________
> #include <iostream>
> #include <relacy/relacy.hpp>
>
>
> #define CT_PRODUCERS_N 2
> #define CT_CONSUMERS_N 3
> #define CT_THREAD_N (CT_PRODUCERS_N + CT_CONSUMERS_N)
>
>
> // Notes:
> // Using spin backoff for waits as of now
> // Need to slow-path it with with kernel waits
> // Need to refine the per-node backoff
>
>
> // humm...
> #define CT_PENDING ((ct_xchg_lifo_ver_001::work*)(0xDEADBEEF))
>
> struct ct_xchg_lifo_ver_001
> {
>
>     // simulate some work...
>     struct work
>     {
>         rl::atomic<work*> m_next;
>         VAR_T(unsigned long) m_work;
>
>
>         work()
>         :   m_next(CT_PENDING),
>             m_work(0)
>         {
>
>         }
>
>
>         ~work()
>         {
>             RL_ASSERT(VAR(m_work) == 1);
>         }
>
>
>         // no data races on m_work!
>         void execute_work()
>         {
>             VAR(m_work) += 1;
>         }
>
>
>         // this is the pending node logic...
>         work* get_next()
>         {
>             work* next = m_next.load(rl::mo_consume, $);
>
>             while (next == CT_PENDING)
>             {
>                 rl::backoff();
>                 next = m_next.load(rl::mo_consume, $);
>             }
>
>             return next;
>         }
>     };
>
>
>
>     rl::atomic<work*> m_head;
>
>     ct_xchg_lifo_ver_001()
>     :   m_head(nullptr)
>     {
>
>     }
>
>     ~ct_xchg_lifo_ver_001()
>     {
>         RL_ASSERT(! m_head.load(rl::mo_relaxed, $));
>     }
>
>
>
>     void push(work* w)
>     {
>         // this completes the pending logic...
>         w->m_next.store(CT_PENDING, rl::mo_relaxed, $);
>         work* head = m_head.exchange(w, rl::mo_release, $);
>         w->m_next.store(head, rl::mo_release, $);
>     }
>
>
>     work* flush()
>     {
>         return m_head.exchange(nullptr, rl::mo_acquire, $);
>     }
[...]

Another fun improvement is to allow push to insert a head and tail such
that it can insert many nodes at once. Still no CAS needed for this.
Also, flush can install a new list if it wants to. No CAS needed. ;^)

A goal of mine was to create a work system using atomic exchange only.

Re: xchg based thing...

<ukgrhf$2n703$2@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2849&group=comp.lang.c%2B%2B#2849

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 19:09:35 -0800
Organization: A noiseless patient Spider
Lines: 10
Message-ID: <ukgrhf$2n703$2@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <ukg7th$2gpd6$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 3 Dec 2023 03:09:35 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="8868b8f4564f0e4e4a8d04bd2a9ce818";
logging-data="2857987"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/bfLB6a+14QYUHf+fjW6jfMOcYYrOnihY="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:rGIxlfrCKjRprrb9/6nIAj3mZmY=
In-Reply-To: <ukg7th$2gpd6$2@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Sun, 3 Dec 2023 03:09 UTC

On 12/2/2023 1:34 PM, Chris M. Thomasson wrote:
> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
[...]

I need to model a version of some real work in relacy, just for fun.
Imvvvho, an interesting question is how to gain an equipotential in 3d
space when there are an infinite number of them... One of my thoughts is
to gain three points in a normal field line, then use the surface normal
of the triangle for an equipotential. Seems like it works okay...

Re: xchg based thing...

<ukgrjt$2n703$3@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2850&group=comp.lang.c%2B%2B#2850

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!news.hispagatos.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 19:10:53 -0800
Organization: A noiseless patient Spider
Lines: 15
Message-ID: <ukgrjt$2n703$3@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <ukg7th$2gpd6$2@dont-email.me>
<ukgrhf$2n703$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 3 Dec 2023 03:10:53 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="8868b8f4564f0e4e4a8d04bd2a9ce818";
logging-data="2857987"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19F9iyItg5V0lo9smengKenucrVYgM+Ctc="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ybsEwvJx2gcjmuHYt2MXi5ePxRs=
In-Reply-To: <ukgrhf$2n703$2@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Sun, 3 Dec 2023 03:10 UTC

On 12/2/2023 7:09 PM, Chris M. Thomasson wrote:
> On 12/2/2023 1:34 PM, Chris M. Thomasson wrote:
>> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> [...]
>
> I need to model a version of some real work in relacy, just for fun.
> Imvvvho, an interesting question is how to gain an equipotential in 3d
> space when there are an infinite number of them... One of my thoughts is
> to gain three points in a normal field line, then use the surface normal
> of the triangle for an equipotential. Seems like it works okay...
>

So, real work on a fine grain level wrt that type of work can consist of
three points and an epsilon. The surface normal would be returned. This
is fairly fine grain here...

Re: xchg based thing...

<ukgrlp$2n703$4@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2851&group=comp.lang.c%2B%2B#2851

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 19:11:52 -0800
Organization: A noiseless patient Spider
Lines: 20
Message-ID: <ukgrlp$2n703$4@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <ukg7th$2gpd6$2@dont-email.me>
<ukgrhf$2n703$2@dont-email.me> <ukgrjt$2n703$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 3 Dec 2023 03:11:53 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="8868b8f4564f0e4e4a8d04bd2a9ce818";
logging-data="2857987"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+w3BUcKcDpOXdiPRoNGeLCIHUGFTA5dZg="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:FX6efXp1CtR3W4QELmSH27m727M=
Content-Language: en-US
In-Reply-To: <ukgrjt$2n703$3@dont-email.me>
 by: Chris M. Thomasson - Sun, 3 Dec 2023 03:11 UTC

On 12/2/2023 7:10 PM, Chris M. Thomasson wrote:
> On 12/2/2023 7:09 PM, Chris M. Thomasson wrote:
>> On 12/2/2023 1:34 PM, Chris M. Thomasson wrote:
>>> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>> [...]
>>
>> I need to model a version of some real work in relacy, just for fun.
>> Imvvvho, an interesting question is how to gain an equipotential in 3d
>> space when there are an infinite number of them... One of my thoughts
>> is to gain three points in a normal field line, then use the surface
>> normal of the triangle for an equipotential. Seems like it works okay...
>>
>
> So, real work on a fine grain level wrt that type of work can consist of
> three points and an epsilon. The surface normal would be returned. This
> is fairly fine grain here...

Speaking of granularity, what bout the logic that derives the three
points via field line plotting? They can be in the same work node, so to
speak.

Re: xchg based thing...

<ukh6j7$2ojqb$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2853&group=comp.lang.c%2B%2B#2853

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 22:18:12 -0800
Organization: A noiseless patient Spider
Lines: 67
Message-ID: <ukh6j7$2ojqb$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <ukg7th$2gpd6$2@dont-email.me>
<ukgrhf$2n703$2@dont-email.me> <ukgrjt$2n703$3@dont-email.me>
<ukgrlp$2n703$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 3 Dec 2023 06:18:15 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="8868b8f4564f0e4e4a8d04bd2a9ce818";
logging-data="2903883"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+4jLsKwJ+RJBfx/XA4kfBLWCr2e4tQh/c="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:Gr/m8xj8994fhhq382mL73/IXgI=
Content-Language: en-US
In-Reply-To: <ukgrlp$2n703$4@dont-email.me>
 by: Chris M. Thomasson - Sun, 3 Dec 2023 06:18 UTC

On 12/2/2023 7:11 PM, Chris M. Thomasson wrote:
> On 12/2/2023 7:10 PM, Chris M. Thomasson wrote:
>> On 12/2/2023 7:09 PM, Chris M. Thomasson wrote:
>>> On 12/2/2023 1:34 PM, Chris M. Thomasson wrote:
>>>> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>>> [...]
>>>
>>> I need to model a version of some real work in relacy, just for fun.
>>> Imvvvho, an interesting question is how to gain an equipotential in
>>> 3d space when there are an infinite number of them... One of my
>>> thoughts is to gain three points in a normal field line, then use the
>>> surface normal of the triangle for an equipotential. Seems like it
>>> works okay...
>>>
>>
>> So, real work on a fine grain level wrt that type of work can consist
>> of three points and an epsilon. The surface normal would be returned.
>> This is fairly fine grain here...
>
> Speaking of granularity, what bout the logic that derives the three
> points via field line plotting? They can be in the same work node, so to
> speak.

A thread checks the work system, gains some work and starts executing.
Humm... A real work item can tell it to compute n points of a field line
in a vector field. The work item might look like, just sketching this out:

<pseudo-code>
____________________
struct work_field_line_plot
{ // a dedicated portion of a canvas for
// this work item to plot on...
ct_canvas_section& m_canvas;

// say this work does not alter the
// vector field... so, its const
ct_vector_field const& m_field;

// line plotting data...
glm::vec4 m_origin;
glm::vec4 m_origin_radii;
float m_origin_angle;
float m_epsilon;
unsigned long m_step_n;

// get to work!
void execute()
{
// plot field lines on m_canvas...

float normal_step = 1.f / m_step_n;

// [...] Plotting logic...
}
};
____________________

Something along those lines. A work item has a constant reference to the
field and a non-constant reference to its portion of a canvas. Now,
should I give each work item its own independent canvas? I have did that
before and its nice because each work item can have its own rendering.
Combining all of them together makes the final image...

vs, each work item having its own place to plot in a single, shared
canvas? Humm... :^)

Re: xchg based thing...

<ukh6vb$2ojqb$2@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=2854&group=comp.lang.c%2B%2B#2854

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Sat, 2 Dec 2023 22:24:43 -0800
Organization: A noiseless patient Spider
Lines: 22
Message-ID: <ukh6vb$2ojqb$2@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <ukg7th$2gpd6$2@dont-email.me>
<ukgrhf$2n703$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sun, 3 Dec 2023 06:24:43 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="8868b8f4564f0e4e4a8d04bd2a9ce818";
logging-data="2903883"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19BEuFmnkoxuJdRR5DV0P3RuupOPfa2T68="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:laK2/snFA0MWD9V+EaVfJFhiU78=
In-Reply-To: <ukgrhf$2n703$2@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Sun, 3 Dec 2023 06:24 UTC

On 12/2/2023 7:09 PM, Chris M. Thomasson wrote:
> On 12/2/2023 1:34 PM, Chris M. Thomasson wrote:
>> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> [...]
>
> I need to model a version of some real work in relacy, just for fun.
> Imvvvho, an interesting question is how to gain an equipotential in 3d
> space when there are an infinite number of them... One of my thoughts is
> to gain three points in a normal field line, then use the surface normal
> of the triangle for an equipotential. Seems like it works okay... >

Afaict, it would be a very strange experiment to allow for the field
lines to be plotted using a carefully constructed race condition in the
sense that its 100% legit in C++, but, the field lines would become
corrupted in "interesting" ways, no longer isolated from one another...
The work items can race with each other while building their lines...
Something along the lines of:

https://groups.google.com/g/comp.lang.c++/c/7u_rLgQe86k/m/fYU9SnuAFQAJ

Just thinking out loud here... Sorry for flooding. ;^o

Re: xchg based thing...

<uo48lc$136kt$2@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=3047&group=comp.lang.c%2B%2B#3047

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Mon, 15 Jan 2024 13:38:52 -0800
Organization: A noiseless patient Spider
Lines: 18
Message-ID: <uo48lc$136kt$2@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 15 Jan 2024 21:38:52 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="7d1243cd4c6e96d6c76da6ed921f8d21";
logging-data="1153693"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18F2oNTi/nrCTVZZCvcNRkpKTierbFZpMk="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:m+j8d+xYUlIhbyco6nO5tWCjQEg=
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Mon, 15 Jan 2024 21:38 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
> use it as a work "queue" for my parts of my CPU based rendering engine,
> no need for it wrt my shader work. However, I needed to do it. It's
> passing Relacy tests. That's a good thing. Now I need to add in a slow
> path so it can wait in the kernel during periods of no work. I think an
> eventcount should work for it. Or perhaps I might integrate some state
> in the pointer values for futexes, or whatever. I have not made up my
> mind yet.
[...]

Got some nice test targets for the experimental xchg based "queue" of
mine to render:

https://i.ibb.co/p2xgRh2/image.png

https://i.ibb.co/sCpZ70V/image.png

Re: xchg based thing...

<up25sl$39821$1@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=3085&group=comp.lang.c%2B%2B#3085

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!news.hispagatos.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Fri, 26 Jan 2024 21:55:32 -0800
Organization: A noiseless patient Spider
Lines: 10
Message-ID: <up25sl$39821$1@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 27 Jan 2024 05:55:33 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="4de68a687a399c61b3fcd74392800b9b";
logging-data="3448897"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+kuZkpFGEvhZBB0QuIPLkuacxoCh9qyFY="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:zP2/DInMzOXGkkoao7ruFEDC7+E=
Content-Language: en-US
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
 by: Chris M. Thomasson - Sat, 27 Jan 2024 05:55 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
[...]

Humm, should have some free time to do this... Might as well use it for
n-ary fields. 3d here:

https://i.ibb.co/Qd8QtGz/image.png

Re: xchg based thing...

<uph1na$27tkp$3@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=3110&group=comp.lang.c%2B%2B#3110

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Thu, 1 Feb 2024 13:16:27 -0800
Organization: A noiseless patient Spider
Lines: 21
Message-ID: <uph1na$27tkp$3@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 1 Feb 2024 21:16:26 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="e5db24bf58349e0f24b4ca76196085dd";
logging-data="2356889"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18S7wVZ8iYobdQyGhe8OH46YPQOxPWP6g4="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:RmEo3u2p0B+u9TUgPuFPQYZ7NMU=
Content-Language: en-US
In-Reply-To: <uk1c4s$3lfmh$1@dont-email.me>
 by: Chris M. Thomasson - Thu, 1 Feb 2024 21:16 UTC

On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
> Fwiw, here is a quick and dirty mock up of my atomic exchange based lifo
> work queue thing. Not sure how to classify it quite yet. I am going to
> use it as a work "queue" for my parts of my CPU based rendering engine,
> no need for it wrt my shader work. However, I needed to do it. It's
> passing Relacy tests. That's a good thing. Now I need to add in a slow
> path so it can wait in the kernel during periods of no work. I think an
> eventcount should work for it. Or perhaps I might integrate some state
> in the pointer values for futexes, or whatever. I have not made up my
> mind yet.
>
> I will port my Relacy test units over to standard C++. It's not all that
> hard. In fact, it's rather straightforward.
[...]

Humm... Might be able to use it to quickly generate very complex models.
Reduce the loading screen time... This one is fairly complex and I can
get 60fps...

https://i.ibb.co/CBJqT8h/image.png

Re: xchg based thing...

<uph1po$280jv$2@dont-email.me>

  copy mid

https://www.novabbs.com/devel/article-flat.php?id=3111&group=comp.lang.c%2B%2B#3111

  copy link   Newsgroups: comp.lang.c++
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: chris.m....@gmail.com (Chris M. Thomasson)
Newsgroups: comp.lang.c++
Subject: Re: xchg based thing...
Date: Thu, 1 Feb 2024 13:17:45 -0800
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <uph1po$280jv$2@dont-email.me>
References: <uk1c4s$3lfmh$1@dont-email.me> <uph1na$27tkp$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 1 Feb 2024 21:17:45 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="e5db24bf58349e0f24b4ca76196085dd";
logging-data="2359935"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/r1oBpM225hDRUrrfHhp8+fPXyx+h49Z4="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:1HKfKt0xtCYl2bxvNZmm9UoFLA8=
In-Reply-To: <uph1na$27tkp$3@dont-email.me>
Content-Language: en-US
 by: Chris M. Thomasson - Thu, 1 Feb 2024 21:17 UTC

On 2/1/2024 1:16 PM, Chris M. Thomasson wrote:
> On 11/26/2023 10:14 PM, Chris M. Thomasson wrote:
>> Fwiw, here is a quick and dirty mock up of my atomic exchange based
>> lifo work queue thing. Not sure how to classify it quite yet. I am
>> going to use it as a work "queue" for my parts of my CPU based
>> rendering engine, no need for it wrt my shader work. However, I needed
>> to do it. It's passing Relacy tests. That's a good thing. Now I need
>> to add in a slow path so it can wait in the kernel during periods of
>> no work. I think an eventcount should work for it. Or perhaps I might
>> integrate some state in the pointer values for futexes, or whatever. I
>> have not made up my mind yet.
>>
>> I will port my Relacy test units over to standard C++. It's not all
>> that hard. In fact, it's rather straightforward.
> [...]
>
> Humm... Might be able to use it to quickly generate very complex models.
> Reduce the loading screen time... This one is fairly complex and I can
> get 60fps...
>
> https://i.ibb.co/CBJqT8h/image.png
>

https://i.ibb.co/02MskNt/image.png


devel / comp.lang.c++ / xchg based thing...

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor