Good random number generators version 1.0, you can port it to C++

[Horizon68]

Hello,

Read this:

Good random number generators version 1.0, you can port them to C++

Look at them they are powerful.

Author: Amine Moulay Ramdane that have enhanced
both random number generators.

Description:

This is an enhanced versions of both Mersenne Twister that is a
good random number generator and Splitmix64 that is a fast random number
generator, both have passed the BigCrush tests.

Look into defines.inc file, there is many options:

{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems

Look at test.pas demo inside the zip file...

You can download it from:

https://sites.google.com/site/scalable68/good-random-number-generators

Language: FPC Pascal v2.2.0+ / Delphi 5+: http://www.freepascal.org/

Operating Systems: Win , Linux and Mac (x86).

Required FPC switches: -O3 -Sd

-Sd for delphi mode....

Required Delphi switches: -$O+



Thank you,
Amine Moulay Ramdane.

[Chris M. Thomasson]

On 10/1/2018 2:16 PM, Horizon68 wrote:
> Hello,
>
> Read this:
>
> Good random number generators version 1.0, you can port them to C++

Really random? Humm... How do they compare to a hardware TRNG?

;^)

[...]

[Chris M. Thomasson]

Fwiw, here is a 100% purely experimental thing I created, that can
generate some "interesting" bits:

https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion

;^)

>
> [...]

[Öö Tiib]

Undefined behavior (like your race condition) means that next version of
compiler can assume it can't happen and "optimize" it away.

[Chris M. Thomasson]

Just to clarify, my race condition thing is using standard atomic loads
and stores with relaxed memory ordering. There is no undefined behavior
wrt the logic that is generating the contrived race condition.

It cannot be optimized away.

[Öö Tiib]

May be in current standard. Have you noticed the cult of undefined
and inquisition of behavior in committees? Those can simply declare
techniques ill-formed because of being "arcane" witchcraft.

http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#2118
----- quote (capitalization mine)
2118. Stateful metaprogramming via friend injection
Section: 17.7.5 [temp.inject] Status: open Submitter: Richard Smith
Date: 2015-04-27

Defining a friend function in a template, then referencing that function
later provides a means of capturing and retrieving metaprogramming state.
This TECHNIQUE IS ARCANE and should be made ill-formed.

Notes from the May, 2015 meeting:

CWG agreed that such techniques should be ill-formed, although the
mechanism for prohibiting them is as yet undetermined.
----- end quote

Both gcc and clang have by now obeyed and the constexpr counters give
vague warnings about friend functions and do not work anymore.

[Chris M. Thomasson]

On 10/1/2018 11:20 PM, Öö Tiib wrote:
> On Tuesday, 2 October 2018 08:12:11 UTC+3, Chris M. Thomasson wrote:
>> On 10/1/2018 10:07 PM, Öö Tiib wrote:
>>> On Tuesday, 2 October 2018 02:15:56 UTC+3, Chris M. Thomasson wrote:
>>>> On 10/1/2018 3:53 PM, Chris M. Thomasson wrote:
>>>>> On 10/1/2018 2:16 PM, Horizon68 wrote:
>>>>>> Hello,
>>>>>>
>>>>>> Read this:
>>>>>>
>>>>>> Good random number generators version 1.0, you can port them to C++
>>>>>
>>>>> Really random? Humm... How do they compare to a hardware TRNG?
>>>>>
>>>>> ;^)
>>>>
>>>> Fwiw, here is a 100% purely experimental thing I created, that can
>>>> generate some "interesting" bits:
>>>>
>>>> https://groups.google.com/d/topic/comp.lang.c++/7u_rLgQe86k/discussion
>>>>
>>>> ;^)
>>>
>>> Undefined behavior (like your race condition) means that next version of
>>> compiler can assume it can't happen and "optimize" it away.
>>>
>>
>> Just to clarify, my race condition thing is using standard atomic loads
>> and stores with relaxed memory ordering. There is no undefined behavior
>> wrt the logic that is generating the contrived race condition.
>>
>> It cannot be optimized away.
>
> May be in current standard.

It better not be! A lot of algorithms use simple atomic loads and stores
with relaxed memory ordering.

> Have you noticed the cult of undefined
> and inquisition of behavior in committees? Those can simply declare
> techniques ill-formed because of being "arcane" witchcraft.

It is simply using atomic loads and stores along with relaxed memory
order. The atomics should not be optimized away. They better not be, or
else it would ruin things. It would seem to mess around with other
algorithms as well.

>
> http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#2118
> ----- quote (capitalization mine)
> 2118. Stateful metaprogramming via friend injection
> Section: 17.7.5 [temp.inject] Status: open Submitter: Richard Smith
> Date: 2015-04-27
>
> Defining a friend function in a template, then referencing that function
> later provides a means of capturing and retrieving metaprogramming state.
> This TECHNIQUE IS ARCANE and should be made ill-formed.
>
> Notes from the May, 2015 meeting:
>
> CWG agreed that such techniques should be ill-formed, although the
> mechanism for prohibiting them is as yet undetermined.
> ----- end quote
>
> Both gcc and clang have by now obeyed and the constexpr counters give
> vague warnings about friend functions and do not work anymore.
>

All of the atomic loads and stores in an algorithm should be intact,
damn it.

[David Brown]

The atomic loads and stores can be optimised away. But it is rare that
the compiler could prove that this is safe, so it is unlikely to do so.
In particular, they can be optimised or re-arranged if the compiler can
be sure that no other thread can see them. And if they are "relaxed"
operations, there is no synchronisation on the loads or stores - all the
compiler must guarantee is that no thread ever sees a half-way read or
write - it's either all or nothing. For object sizes that the cpu can
read and write as a single unit, a relaxed load or store can be
implemented as a normal load or store. However, the requirement for
sequencing between threads means that these can't be re-ordered or
eliminated unless the compiler knows that no other thread could access
them. You could only get this knowledge for local atomic variables that
don't "escape" in any way - such restricted cases would be almost
entirely useless for atomics. So it is likely that compilers never
bother to optimise them away, and treat them pretty much as "volatile".

However, race conditions are always undefined behaviour. And relying on
the behaviour of undefined behaviour is never a good idea.

If the compiler can figure out that you definitely always have a race
condition, it could use that knowledge to optimise away the code. I
think it is highly unlikely for it to see such cases, but it is still a
bad idea to rely on it.

People have tried to use undefined behaviour to give "random" data
before - I know of a well-publicised case where uninitialised local
variables were use to give "more entropy" to some key data. It always
ends in tears - do /not/ do this.

>
> All of the atomic loads and stores in an algorithm should be intact,
> damn it.

You can only rely on the compiler to give you the code you want when you
write the code in correct C or C++. If you write code with errors, such
as race conditions, you /might/ get what you expect - you might get
something entirely different.

[Chris Vine]

So far as I understand your code, the "racer" function is inaptly named
in the C++ sense because it modifies an atomic variable with relaxed
memory ordering. This is indeed unsynchronized with no "happens before"
relationships, and the outcome will be indeterminate; but in C++
standardeze that does not of itself generate a "data race" or undefined
behaviour.

In C++ standardeze:

The execution of a program contains a data race if it contains two
potentially concurrent conflicting actions, at least one of which is
not atomic, and neither happens before the other, except for the
special case for signal handlers described below. Any such data race
results in undefined behavior.

All your concurrent actions appear to be on a single atomic variable
and are therefore atomic. So although the second leg of the test for a
"data race" is met, the first leg is not. Note that this is different
from what most people would call a "data race" in the programmatic
sense: most people would say that any program which does not establish
the correct "happens before" relationships is "racy". But that does not
of itself give rise to undefined behaviour.

Since your atomic is instantiated for unsigned int, any compiler on any
platform you come across will translate the stores and loads with
relaxed memory ordering into plain stores and loads. But I do not
believe that then entitles the compiler to mess around with your
code further on the grounds of undefined behaviour. If your shared
variable were a plain unsigned int it could do so. If is of type
std::atomic<unsigned int> then not, as I read it.

[Rick C. Hodgin]

On 10/2/2018 2:44 AM, Chris M. Thomasson wrote:
> [snip]
Chris, I was thinking today ... the "boring" parts of a fractal,
which don't spin into infinities. Have you ever examined the
"smoothness" of their variation there in the flat areas? To see
if there isn't some unusual variations in the smoothness?

You look at a beach from a Cessna from 500 feet and you see a
smooth thing. You get down there on the ground and walk on it
you see a lot more interesting detail. It might even look like
it has fingerprints depending on the winds and waves.

Perhaps there is perturbation there which, when greatly amplified,
would yield some interesting graphs. Perhaps also there is a
"dance" between the perturbation patterns (when amplified) and
the nearby fractal reduction portions, such that a correlation
between those perturbations and the descent into fractals would
yield some interesting things, kind of like how there are some
constants encoded in fractals. Perhaps there's more in there.

--
Rick C. Hodgin

[Chris M. Thomasson]

I am artificially creating the race condition using 100% legitimate
operations; the compiler should not mess with my atomics and relaxed
memory barriers. Each load and store are there for a reason. The
compiler better not shi% it up. Sorry for the brief response, but I am
working on a fractal right now. Will have some more time later on today
David. Thanks.

[David Brown]

And your result is as undefined as if you wrote "int xs[10]; return
x[100];".

Race conditions are undefined behaviour. The compiler (and library)
don't guarantee anything here - the don't even guarantee that the
operations are atomic.

> the compiler should not mess with my atomics and relaxed
> memory barriers. Each load and store are there for a reason. The
> compiler better not shi% it up. Sorry for the brief response, but I am
> working on a fractal right now. Will have some more time later on today
> David. Thanks.
>

It doesn't matter what you think the compiler /should/ do. The
/standards/ say what the compiler should do. If you stick to /your/
side of the bargain and avoid undefined behaviour, the compiler will
stick to its side and generate code matching the specifications in the
standards.

You are breaking your side of that deal. Why do you expect the compiler
has any responsibility to help you in that?

In /practice/, I think it is highly unlikely that the compiler can tell
that you are writing jumbled crap instead of valid C code in this case.
And I think it is highly unlikely that a compiler will have
optimisations that could take effect here - simply because what you are
writing is so clearly bad that compiler writers have no interest in
finding ways to make it fast.


But you need to understand that the sole reason you get your atomic
loads and stores here is that the compiler is not omnipotent. And some
static analysis tools /will/ be able to see that there are data races
here - that means that future compilers might have the same level of
analysis, see that your code breaks all the rules, and simply remove the
broken code. Or maybe - if they are nice - give you a warning about it
and /then/ remove it.

[Chris Vine]

Where are you saying that the undefined behaviour comes from? The
concurrent operations are on a shared variable of type
std::atomic<unsigned int>. The fact that the stores and loads are with
relaxed memory ordering does not create a "data race" (and so
undefined behaviour) within the meaning of the standard.

[James Kuyper]

On 10/03/2018 03:30 AM, David Brown wrote:
> On 02/10/18 22:11, Chris M. Thomasson wrote:
>> On 10/2/2018 4:01 AM, David Brown wrote:

...

>>> However, race conditions are always undefined behaviour. And relying on
>>> the behaviour of undefined behaviour is never a good idea.
>>
>> I am artificially creating the race condition using 100% legitimate
>> operations;
>
> And your result is as undefined as if you wrote "int xs[10]; return
> x[100];".

Could you point to a single, specific, and preferably simple example of
code that he wrote which has undefined behavior, and the specific clause
from the standard that says that this code has undefined behavior?
Preferably with an explanation of how that clause applies. I'm not
disagreeing with you, but multi-threaded code is not something I have a
lot of experience with, and I haven't had time to fully digest the
descriptions of the newly added features of C that support such code. He
is disagreeing with you, and I'd like to have enough information to
decide which of you I agree with.

> Race conditions are undefined behaviour. The compiler (and library)
> don't guarantee anything here - the don't even guarantee that the
> operations are atomic.

True, per 5.1.2.4p25; but I gather that the point of disagreement here
is whether the conditions have been met for that clause to apply -
specifically, the requirement that "... at least one of which is not
atomic, ...". Could you explain what's wrong with the reasons that have
been given for believing that it doesn't apply?

[David Brown]

On 03/10/18 13:51, Chris Vine wrote:
> On Wed, 03 Oct 2018 09:30:32 +0200
> David Brown <david...@hesbynett.no> wrote:
>> On 02/10/18 22:11, Chris M. Thomasson wrote:
>>> On 10/2/2018 4:01 AM, David Brown wrote:
>>>> On 02/10/18 08:44, Chris M. Thomasson wrote:

>>>>> On 10/1/2018 11:20 PM, 嘱 Tiib wrote:
>>>>>> On Tuesday, 2 October 2018 08:12:11 UTC+3, Chris M. Thomasson wrote:

To be entirely honest here, I haven't studied your code in detail - I
have taken you at your word that you are generating race conditions in
your "racer" function. And race conditions are clearly undefined behaviour.

If it turns out that you are wrong in the characteristic of your code,
so that there are in fact no race conditions, then the behaviour is
merely unspecified, not undefined. In that case, the compiler can't
remove the code - but you still don't have anything worthy of using as a
random number generator because you have no way of knowing how it might
be implemented in practice.

[Chris Vine]

On Wed, 03 Oct 2018 14:27:11 +0200

David Brown <david...@hesbynett.no> wrote:
> On 03/10/18 13:51, Chris Vine wrote:
> > On Wed, 03 Oct 2018 09:30:32 +0200
> > David Brown <david...@hesbynett.no> wrote:
> >> On 02/10/18 22:11, Chris M. Thomasson wrote:
> >>> On 10/2/2018 4:01 AM, David Brown wrote:
> >>>> On 02/10/18 08:44, Chris M. Thomasson wrote:

> >>>>> On 10/1/2018 11:20 PM, Öö Tiib wrote:
> >>>>>> On Tuesday, 2 October 2018 08:12:11 UTC+3, Chris M. Thomasson wrote:

Wrong Chris. Here is an extract from my response to Chris T about his
choice of name for 'racer' and what the standard says about it.

"So far as I understand your code, the "racer" function is inaptly
named in the C++ sense because it modifies an atomic variable with
relaxed memory ordering. This is indeed unsynchronized with no
"happens before" relationships, and the outcome will be indeterminate;
but in C++ standardeze that does not of itself generate a "data race"
or undefined behaviour.

In C++ standardeze:

'The execution of a program contains a data race if it contains two
potentially concurrent conflicting actions, at least one of which
is not atomic, and neither happens before the other, except for the
special case for signal handlers described below. Any such data
race results in undefined behavior.'

All your concurrent actions appear to be on a single atomic variable
and are therefore atomic. So although the second leg of the test for
a "data race" is met, the first leg is not. Note that this is
different from what most people would call a "data race" in the
programmatic sense: most people would say that any program which does
not establish the correct "happens before" relationships is "racy".
But that does not of itself give rise to undefined behaviour."

There is a legitimate criticism of his implementation, which is that
although it appears guaranteed to produce a series of 0 or 1 and not
some other number, nor a hardward trap nor segfault, I think it could
probably in theory at least produce all 0 or all 1. (I would need to
study his code more to see if that could happen.)

Its random nature also depends on relaxed memory ordering in fact being
provided. In practice for unsigned int that will be the case on any
reasonable platform, but if the hardware had to have a special
instruction in order to make the assignment to unsigned int atomic at
the hardware level that would probably have the side effect of
introducing ordering. Asking for relaxed memory ordering doesn't mean
you will get it. It is an indication to the compiler that ordering
isn't required.

[David Brown]

On 03/10/18 14:38, Chris Vine wrote:
> On Wed, 03 Oct 2018 14:27:11 +0200
> David Brown <david...@hesbynett.no> wrote:
>> On 03/10/18 13:51, Chris Vine wrote:
>>> On Wed, 03 Oct 2018 09:30:32 +0200
>>> David Brown <david...@hesbynett.no> wrote:
>>>> On 02/10/18 22:11, Chris M. Thomasson wrote:
>>>>> On 10/2/2018 4:01 AM, David Brown wrote:
>>>>>> On 02/10/18 08:44, Chris M. Thomasson wrote:

>>>>>>> On 10/1/2018 11:20 PM, 嘱 Tiib wrote:
>>>>>>>> On Tuesday, 2 October 2018 08:12:11 UTC+3, Chris M. Thomasson wrote:

Sorry - I didn't notice.

> Here is an extract from my response to Chris T about his
> choice of name for 'racer' and what the standard says about it.
>
> "So far as I understand your code, the "racer" function is inaptly
> named in the C++ sense because it modifies an atomic variable with
> relaxed memory ordering. This is indeed unsynchronized with no
> "happens before" relationships, and the outcome will be indeterminate;
> but in C++ standardeze that does not of itself generate a "data race"
> or undefined behaviour.

In that case, I agree with you.

>
> In C++ standardeze:
>
> 'The execution of a program contains a data race if it contains two
> potentially concurrent conflicting actions, at least one of which
> is not atomic, and neither happens before the other, except for the
> special case for signal handlers described below. Any such data
> race results in undefined behavior.'
>
> All your concurrent actions appear to be on a single atomic variable
> and are therefore atomic. So although the second leg of the test for
> a "data race" is met, the first leg is not. Note that this is
> different from what most people would call a "data race" in the
> programmatic sense: most people would say that any program which does
> not establish the correct "happens before" relationships is "racy".
> But that does not of itself give rise to undefined behaviour."
>
> There is a legitimate criticism of his implementation, which is that
> although it appears guaranteed to produce a series of 0 or 1 and not
> some other number, nor a hardward trap nor segfault, I think it could
> probably in theory at least produce all 0 or all 1. (I would need to
> study his code more to see if that could happen.)
>

My guess - without having studied the code either - is that on a system
with a single cpu core and "run to completion" multi-threading, you'd
get very poor randomisation.

> Its random nature also depends on relaxed memory ordering in fact being
> provided. In practice for unsigned int that will be the case on any
> reasonable platform, but if the hardware had to have a special
> instruction in order to make the assignment to unsigned int atomic at
> the hardware level that would probably have the side effect of
> introducing ordering. Asking for relaxed memory ordering doesn't mean
> you will get it. It is an indication to the compiler that ordering
> isn't required.
>

Yes. The implementation can always bump up the strength of the ordering
- it just can't reduce the strength.

[David Brown]

On 03/10/18 14:15, James Kuyper wrote:
> On 10/03/2018 03:30 AM, David Brown wrote:
>> On 02/10/18 22:11, Chris M. Thomasson wrote:
>>> On 10/2/2018 4:01 AM, David Brown wrote:
> ...
>>>> However, race conditions are always undefined behaviour. And relying on
>>>> the behaviour of undefined behaviour is never a good idea.
>>>
>>> I am artificially creating the race condition using 100% legitimate
>>> operations;
>>
>> And your result is as undefined as if you wrote "int xs[10]; return
>> x[100];".
>
> Could you point to a single, specific, and preferably simple example of
> code that he wrote which has undefined behavior, and the specific clause
> from the standard that says that this code has undefined behavior?

After reading Chris Vine's posts and having another quick look, it
appears that his code does not in fact have race conditions, even though
that is how Chris Thomasson described his own code. If it /does/ have
data races that I missed, these are undefined behaviour (5.1.2.4p25 in
C11, and 1.10p21 in C++14 I think). But these define data races as
mixing atomic and non-atomic accesses, whereas the code uses only atomic
accesses.

(It may be that there is other undefined behaviour in the code - I
haven't looked in detail. My argument was based on the OP's statement
"my code uses race conditions to give random numbers", rather than a
good look at the code.)

> Preferably with an explanation of how that clause applies. I'm not
> disagreeing with you, but multi-threaded code is not something I have a
> lot of experience with, and I haven't had time to fully digest the
> descriptions of the newly added features of C that support such code. He
> is disagreeing with you, and I'd like to have enough information to
> decide which of you I agree with.
>
>> Race conditions are undefined behaviour. The compiler (and library)
>> don't guarantee anything here - the don't even guarantee that the
>> operations are atomic.
>
> True, per 5.1.2.4p25; but I gather that the point of disagreement here
> is whether the conditions have been met for that clause to apply -
> specifically, the requirement that "... at least one of which is not
> atomic, ...". Could you explain what's wrong with the reasons that have
> been given for believing that it doesn't apply?
>

As I say, it looks like the code does not contain data races after all.

[Chris M. Thomasson]

On 10/3/2018 5:57 AM, David Brown wrote:
> On 03/10/18 14:15, James Kuyper wrote:
>> On 10/03/2018 03:30 AM, David Brown wrote:
>>> On 02/10/18 22:11, Chris M. Thomasson wrote:
>>>> On 10/2/2018 4:01 AM, David Brown wrote:
>> ...
>>>>> However, race conditions are always undefined behaviour. And relying on
>>>>> the behaviour of undefined behaviour is never a good idea.
>>>>
>>>> I am artificially creating the race condition using 100% legitimate
>>>> operations;
>>>
>>> And your result is as undefined as if you wrote "int xs[10]; return
>>> x[100];".
>>
>> Could you point to a single, specific, and preferably simple example of
>> code that he wrote which has undefined behavior, and the specific clause
>> from the standard that says that this code has undefined behavior?
>
> After reading Chris Vine's posts and having another quick look, it
> appears that his code does not in fact have race conditions, even though
> that is how Chris Thomasson described his own code.

My code just shows what happens when one has a broken implementation of
the fetch-and-add function. It boils down to:
______________________________
static std::atomic<unsigned int> g_racer(0);


void racer(unsigned int n)
{
for (unsigned int i = 0; i < n; ++i)
{
// Race infested fetch-and-add op
unsigned int r = g_racer.load(std::memory_order_relaxed);
r = r + 1;
g_racer.store(r, std::memory_order_relaxed);
}
}
______________________________

Wrt the standard, this is free of race conditions and/or undefined
behavior. However, wrt the actual logic of the implementation of said
fetch-and-add operation: it is busted. This creates a seemingly endless
stream of data. Just for fun, I was thinking about seeing what happens
if it were to emit bits. Actually, when the system is under load the
"quality" of the "random numbers" seem to get better.

It seems like the bit stream can be used to infer some information from
the system. If it is under heavy load, the quality of the "random" bits
should be "better" than ones derived from a system state that is
basically doing nothing.

> If it /does/ have
> data races that I missed, these are undefined behaviour (5.1.2.4p25 in
> C11, and 1.10p21 in C++14 I think). But these define data races as
> mixing atomic and non-atomic accesses, whereas the code uses only atomic
> accesses.

Right. Everything is working off a global std::atomic<unsigned int>
called g_racer.

> (It may be that there is other undefined behaviour in the code - I
> haven't looked in detail. My argument was based on the OP's statement
> "my code uses race conditions to give random numbers", rather than a
> good look at the code.)

>> Preferably with an explanation of how that clause applies. I'm not
>> disagreeing with you, but multi-threaded code is not something I have a
>> lot of experience with, and I haven't had time to fully digest the
>> descriptions of the newly added features of C that support such code. He
>> is disagreeing with you, and I'd like to have enough information to
>> decide which of you I agree with.
>>
>>> Race conditions are undefined behaviour.

There are two different types of race conditions. Wrt the _standard_, my
code has no race conditions. Wrt the busted fetch-and-add
implementation, well, it just shows what can happen if a sync primitive
is not implemented correctly. My little program that shows this is okay
wrt the standard.

I inappropriately used the term race-condition to refer to the actual
busted fetch-and-add implementation used to generate "random" numbers.
Sorry about that.

> The compiler (and library)
>>> don't guarantee anything here - the don't even guarantee that the
>>> operations are atomic.
>>
>> True, per 5.1.2.4p25; but I gather that the point of disagreement here
>> is whether the conditions have been met for that clause to apply -
>> specifically, the requirement that "... at least one of which is not
>> atomic, ...". Could you explain what's wrong with the reasons that have
>> been given for believing that it doesn't apply?
>>
>
> As I say, it looks like the code does not contain data races after all.

I totally agree with you. Thank you for taking the time to have a
"closer" look. :^)

[Chris M. Thomasson]

On 10/2/2018 4:45 AM, Chris Vine wrote:
> On Mon, 1 Oct 2018 23:44:24 -0700
> "Chris M. Thomasson" <invalid_chr...@invalid.invalid> wrote:
>> On 10/1/2018 11:20 PM, Öö Tiib wrote:
>>> On Tuesday, 2 October 2018 08:12:11 UTC+3, Chris M. Thomasson wrote:
>>>> On 10/1/2018 10:07 PM, Öö Tiib wrote:
>>>>> On Tuesday, 2 October 2018 02:15:56 UTC+3, Chris M. Thomasson wrote:
>>>>>> On 10/1/2018 3:53 PM, Chris M. Thomasson wrote:

[...]

>> All of the atomic loads and stores in an algorithm should be intact,
>> damn it.
>
> So far as I understand your code, the "racer" function is inaptly named
> in the C++ sense because it modifies an atomic variable with relaxed
> memory ordering. This is indeed unsynchronized with no "happens before"
> relationships, and the outcome will be indeterminate; but in C++
> standardeze that does not of itself generate a "data race" or undefined
> behaviour.

Completely agreed. Perhaps a name of "simulate_foobar_fetch_and_add" is
better than "racer"...

>
> In C++ standardeze:
>
> The execution of a program contains a data race if it contains two
> potentially concurrent conflicting actions, at least one of which is
> not atomic, and neither happens before the other, except for the
> special case for signal handlers described below. Any such data race
> results in undefined behavior.
>
> All your concurrent actions appear to be on a single atomic variable
> and are therefore atomic. So although the second leg of the test for a
> "data race" is met, the first leg is not. Note that this is different
> from what most people would call a "data race" in the programmatic
> sense: most people would say that any program which does not establish
> the correct "happens before" relationships is "racy". But that does not
> of itself give rise to undefined behaviour.

Completely agreed. The foobar fetch-and-add example is racy, however
there are no race-conditions wrt the standard. ;^)

> Since your atomic is instantiated for unsigned int, any compiler on any
> platform you come across will translate the stores and loads with
> relaxed memory ordering into plain stores and loads. But I do not
> believe that then entitles the compiler to mess around with your
> code further on the grounds of undefined behaviour. If your shared
> variable were a plain unsigned int it could do so. If is of type
> std::atomic<unsigned int> then not, as I read it.
>

Right. Those atomic loads and stores should not be messed around with.
If one of them is taken out, or rearranged, it will basically destroy
the algorithm.

[Chris M. Thomasson]

On 10/2/2018 12:28 PM, Rick C. Hodgin wrote:
> On 10/2/2018 2:44 AM, Chris M. Thomasson wrote:
>> [snip]
> Chris, I was thinking today ... the "boring" parts of a fractal,
> which don't spin into infinities.

Are you referring to the equipotential bands? They can look boring,
however and fwiw, there is a heck of a lot of data within. Here are some
example renderings:

https://plus.google.com/101799841244447089430/posts/DtLtBDqKwRB

https://plus.google.com/101799841244447089430/posts/Lfx8uBxVxnF

https://plus.google.com/101799841244447089430/posts/CstcFBor8kg

And are some quick animations:

https://youtu.be/HCOsivt9aAA

https://youtu.be/UpNDkOKdcjk

https://youtu.be/ZYQJRJEETv8

>  Have you ever examined the
> "smoothness" of their variation there in the flat areas?  To see
> if there isn't some unusual variations in the smoothness?

Just so we can get on the same page, can you give me a link to a
rendering that shows these "flat areas"? Are we talking about the
Mandelbrot set here? I am just trying to clarify.

> You look at a beach from a Cessna from 500 feet and you see a
> smooth thing.  You get down there on the ground and walk on it
> you see a lot more interesting detail.  It might even look like
> it has fingerprints depending on the winds and waves.

Agreed. Zooming in on a fractal is extraordinarily similar in nature.

> Perhaps there is perturbation there which, when greatly amplified,
> would yield some interesting graphs.  Perhaps also there is a
> "dance" between the perturbation patterns (when amplified) and
> the nearby fractal reduction portions, such that a correlation
> between those perturbations and the descent into fractals would
> yield some interesting things, kind of like how there are some
> constants encoded in fractals.  Perhaps there's more in there.

I know that we can actually load/store n-ary information from/into a
Julia set by using reverse iteration and mapping the roots of the
iterations to a symbol set. In a sense, it is an infinitely complex
n-ary tree structure. Here is some example code should how one can store
and load data:

https://groups.google.com/d/topic/comp.lang.c++/bB1wA4wvoFc/discussion

This uses limited precision, well, is uses double. However, we can store
a lot more information using arbitrary precision. Theoretically, we can
store infinite data using infinite precision to calculate the roots of a
Julia set.

[David Brown]

On 03/10/18 22:55, Chris M. Thomasson wrote:

> I inappropriately used the term race-condition to refer to the actual
> busted fetch-and-add implementation used to generate "random" numbers.
> Sorry about that.
>

And I inappropriately took your name at face value and thought you meant
a data race as defined in the standards - so you have my apologies for that.

With that sorted out, I see no undefined behaviour and I agree that your
program demonstrates why synchronous primitives such as fetch-and-add
have to be atomic!

[Chris M. Thomasson]

Agreed indeed: Thanks David. :^)

[Chris M. Thomasson]

On 10/2/2018 12:28 PM, Rick C. Hodgin wrote:

What about the following results from my own software:

https://plus.google.com/101799841244447089430/posts/19LK2c9tv9i

https://plus.google.com/101799841244447089430/posts/hhVMw7eB2fx

They kind of look like some strange simulated Hubble images.

[Chris M. Thomasson]

Each pixel in the rendering is infinite.

[Chris M. Thomasson]

Might depend on the thread scheduler, system load, the number of
threads, mouse moves, ect... Fwiw, this is just a fun little test to me.
However, imvvho, it can be interesting in a sense...

>
> Its random nature also depends on relaxed memory ordering in fact being
> provided.

BIG TIME! This needs to be as relaxed as possible. If some compiler
promotes it to something stronger, well, it might cast a signature
across the data. Humm...

> In practice for unsigned int that will be the case on any
> reasonable platform, but if the hardware had to have a special
> instruction in order to make the assignment to unsigned int atomic at
> the hardware level that would probably have the side effect of
> introducing ordering. Asking for relaxed memory ordering doesn't mean
> you will get it. It is an indication to the compiler that ordering
> isn't required.
>

I want a totally relaxed order. Heck, DEC Alpha! ;^)

[Chris M. Thomasson]

Strange alien like face:

https://plus.google.com/101799841244447089430/posts/fWM7YuabUxQ

;^)