Might strike a cord with Anton and/or Mich

https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/

On 10/7/2021 5:52 AM, clamky@hotmail.com wrote:
> Might strike a cord with Anton and/or Mich
>
> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
>

I am a little less strict on this topic, but my general opinion is that
things like strict aliasing should be "opt in" rather than "opt out".

But, yeah, the guy who wrote that in-general has a point, but also tends
to be a bit overly alarmist IMO about these issues.

For example, consider a case of caching struct loads, there are multiple
approaches:
1, Always do the load (my compiler did this originally);
2, Cache, but only within a single basic-block, flush on store (current
rule);
3, Cache, invalidate entries on store if matching types (strict aliasing);
4, Assume that no aliasing occurs whatsoever (playing with fire).

I have noted experimentally that 2 can gain a fair bit of speedup over
1, and is pretty much invisible within a single thread.

The 3 option is closer to what GCC and Clang do by default, but I opt
against this by default given it is unsafe. Doom and Quake and similar
still work with this option. It also seems to be only modestly faster
than 2.

The 4 option is unsafe; it is a little faster than 3 at Dhrystone, but
Doom and Quake are prone to crash if one uses this option.

A variation of this optimization has also been applied to array loads.

My preference is also that things like signed integer operations remain
sign modulo (as well as unsigned operations being unsigned modulo), that
signed right shift behaves in the usually-expected ways (arithmetic
shift), ...

So, ideally, one can try to optimize things in that don't turn into
semantic quicksand, even if this means skipping over some possible types
of optimizations.

Similarly, corner cutting is acceptable in cases where the expected
results can be reasonably well-defined, or are "basically invisible"
within reasonable use-cases.

For example, there can be a fairly significant cost difference between
"FPU that implements IEEE-754 correctly", and one that gives answers
that are "more or less correct".

Expensive FPU:
Separate FPU registers (arguably less register pressure);
FADD, FSUB, FMUL, FDIV, FSQRT, FMAC, ...
Always +/- 0.5 ULP;
Implements Denormals;
...

Cheaper FPU:
Reuse integer registers;
FADD, FSUB, FMUL;
Relaxed rounding;
Denormal as Zero;
...

For most programs, the difference between the cheap and expensive FPU is
not noticeable; and the sorts of workloads which "actually care" are
unlikely to be run on a processor that is too cheap to be able to afford
the fancier FPU (and where the relative slowness of doing everything
with software emulation is undesirable).

One might find that a more useful property though, is not so much that
the FPU is accurate, so much that things like "Single->Double->Single"
conversions can be done while keeping the original value intact.

Compiler optimization is an ongoing challenge though.

Most have been fixing various issues, recent notable bug fixes:
Binary operators needlessly converting arguments to the destination type;
Type conversion operators doing operations via unnecessary temporaries;
Unsigned loads using redundant zero-extension ops;
....

An, some sorts of partially addressed issues:
Temporaries always spilling to stack even when the value is no longer
needed (tried to add 'phi' operators to the IR, but this was a fail; did
add logic though for "don't bother storing temporary if it is never
reloaded" which also helps, but is less fine-grained than a 'phi' would
have been).

Had recently (briefly) gotten Dhrystone up to ~ 65k, but it has since
dropped to 63k, seems very sensitive to code-generation options. This is
on my custom ISA at 50MHz, so ~ 0.74 DMIPS/MHz.

While, conceivably, one can push it a little closer to ~0.78 via strict
aliasing, I don't consider this worthwhile ATM.

This seems to be in the sort of intermediate area between "slow" and
"fast" cores (though, not yet figured out what is the nature of the
dividing line). Though, having looked briefly at the SweRV core, I have
noted that they deal with the pipeline in a very different way (for
example, they seem to handle load/store with a queue and interlocks,
rather than running the L1 D$ in lockstep with the pipeline and stalling
the pipeline for each L1 miss).

It does seem like this could be a possible way to improve the speed of a
core, but would introduce its own complexities. I am not sure if this
accounts for a lot of the differences I am seeing (but, in
testing/models, the core is dumping a lot of its clock-cycles into cache
misses, and in theory this could at least help here, if it could be done
cheaply enough).

Though, as can also be noted in my case, my CPU core lacks an integer
divider, and only provides a 32-bit integer multiplier. A full 64-bit
multiplier would be slow and/or expensive. Generally, faking it as an
instruction-blob has been "fast enough".

Pretending to have instructions, but faking them with traps, is the
worst of both worlds (pointless and slow), at least a runtime call to an
ASM function can be reasonable.

I did recently fiddle around with seeing if I could make the ASM code
for integer divide faster, where options are:
Binary Long Division (current mainline option);
Lookup table of reciprocals (sorta works);
Lookup table + shifted-reciprocal (didn't win).

I had recently tried switching from solely using long division as the
default, to using a lookup table with long-division as a fallback. This
is a little faster for small divisors, but a little slower for divisors
that fall out of range of the table. It also adds the cost of the lookup
table (trades logic for cache misses). It also uses up space, and so
favors a fairly small lookup table (under 1K), where for
divide-intensive code the table will mostly fit in the L1 cache.

Shifted reciprocal can extend the range of such a small lookup table to
cover the entire integer range, but comes with a big issue:
The result is not integer exact;
In effect, the error is proportional to the relative size of the input
values.

So, it is fast for things like 3D rendering calculations where one
doesn't really care if the result is integer exact, but for C's "a/b"
operator, being integer exact is mandatory.

The problem then becomes that in many cases, trying to fix this ends up
costing more than had one just used the long division loop.

Most of the workarounds tend to be "maybe helps, maybe makes it worse".

However, most other code doesn't lean quite so heavily on integer divide
performance, so it is usually isn't quite as relevant.

I am hesitant about adding an instruction for IDIV, as for years even
fairly high end x86 CPU lines were plagued with an IDIV instruction
which was slower than doing it in software, and which performance would
likely have been better had the C compilers just called a runtime
function and done the binary long division in the C library.

Including the divide instruction in an ISA carries a non-trivial risk of
such a thing happening again (if compilers decide to use it by default
because "hey, there is an instruction for it, and dedicated instruction
implies fast, right?...").

But, in some sense, it is easier to use special case mechanisms to make
a runtime call faster, than it is to avoid a potential significant
overhead from emulating instructions which don't exist in hardware.

Granted, a possible intermediate option could be to have an instruction
whose dedicated purpose is to call into a location in a table while also
doing two register moves, ..., which then branches to the appropriate
runtime function (sorta like a special GOT mostly for stuff that was too
expensive to add to the ISA directly, but where one kinda wants to
pretend that a CPU instructions exists).

Then one can just sort of declare that all the scratch registers will be
left in an undefined state following the operation.

....

On 07/10/2021 12:52, clamky@hotmail.com wrote:
> Might strike a cord with Anton and/or Mich
>
> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
>

It seems to me that the authors have misunderstood the language entirely.

C was never meant to be a "high-level assembler" or a "portable
assembler". It was never intended that you could write low-level
systems programs in portable C. It was designed to reduce the need to
write code in assembler, and to improve the portability of code.
(Re-read that sentence if you like.) It was intended to be useable for
writing some kinds of code in a highly portable manner, and also to be
useful in non-portable systems code that depended strongly on the target
and the compiler.

From day one, operating systems "written in C" contained assembly code,
compiler extensions, and other non-portable code. That remains true
today. "Coding tricks" were often used to get efficient results due to
more limited compilers - these are much less common now as compilers
optimise better.

As I got further in the document, it seems to be just another "the
compiler should do what I want it to do, not necessarily what I /told/
it to do" rant. "C today should work the way /I/ want it to do - the
way /I/ interpret the precise wording of what someone decades ago".
"Thompson and Ritchie were saints and prophets, and their words were
holy and eternal - regardless of how computers, languages, and
programming needs have changed since the inception of C". "We were all
happy and no bugs existed in code until gcc sinned by optimising code,
and we were thrown out of Eden into a hell of undefined behaviour".
"Yes, we know that compilers often give us ways to get the semantics we
want by specific flags, but that's not good enough - everyone else
should get slower code so that we don't have to think as much or follow
the rules of the language".

Are there imperfections in C as a language standard? Sure. Show me a
perfect language standard as an alternative. Are there questionable
judgements in some of the design decisions of C toolchains? Sure -
again, show me a perfect toolchain. Is C not quite an exact fit for all
your needs for writing an OS? Sure. It's a general purpose language
that is good for a very wide range of uses - but it's unlikely to be
/perfect/ for any given use-case. And it never has been, and it never
will be. Nor will anything else. Modern C is a vastly better language
than the earliest K&R C. Modern C toolchains are vastly better than the
tools of that era. As well as the hundred steps forward, there have no
doubt been a dozen steps backwards for some people and some uses.
That's life. If you don't like it, give up programming and stick to a
safer hobby.

(For the record, I don't think type-based alias analysis actually gives
very significant optimisation opportunities in most code. On the other
hand, I also don't think it causes problems very often - not nearly as
often as the "optimisation is evil" crowd seem to behave. I write
low-level code all the time, and it is extraordinarily rarely that I
have to find a way around it.)

On 10/7/2021 2:35 PM, David Brown wrote:
> On 07/10/2021 12:52, clamky@hotmail.com wrote:
>> Might strike a cord with Anton and/or Mich
>>
>> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
>>
>
> It seems to me that the authors have misunderstood the language entirely.
>
> C was never meant to be a "high-level assembler" or a "portable
> assembler". It was never intended that you could write low-level
> systems programs in portable C. It was designed to reduce the need to
> write code in assembler, and to improve the portability of code.
> (Re-read that sentence if you like.) It was intended to be useable for
> writing some kinds of code in a highly portable manner, and also to be
> useful in non-portable systems code that depended strongly on the target
> and the compiler.
>
> From day one, operating systems "written in C" contained assembly code,
> compiler extensions, and other non-portable code. That remains true
> today. "Coding tricks" were often used to get efficient results due to
> more limited compilers - these are much less common now as compilers
> optimise better.
>
>
> As I got further in the document, it seems to be just another "the
> compiler should do what I want it to do, not necessarily what I /told/
> it to do" rant. "C today should work the way /I/ want it to do - the
> way /I/ interpret the precise wording of what someone decades ago".
> "Thompson and Ritchie were saints and prophets, and their words were
> holy and eternal - regardless of how computers, languages, and
> programming needs have changed since the inception of C". "We were all
> happy and no bugs existed in code until gcc sinned by optimising code,
> and we were thrown out of Eden into a hell of undefined behaviour".
> "Yes, we know that compilers often give us ways to get the semantics we
> want by specific flags, but that's not good enough - everyone else
> should get slower code so that we don't have to think as much or follow
> the rules of the language".
>

The author of the paper (Victor Yodaiken) has sort of a long history of
"making a mountain out of a molehill" about all this stuff...

I have my opinions, but will note that "the system" is self-regulating
to some extent, as compiler people would have a hard-time keeping people
using their compilers if they set out to break large amounts of existing
"real world" code (and will tend to back down when they face sufficient
backlash).

In cases where stuff has broken in more significant ways, it has usually
been fairly isolated (a particular build of a particular compiler),
rather than a long-term change to the status quo.

>
> Are there imperfections in C as a language standard? Sure. Show me a
> perfect language standard as an alternative. Are there questionable
> judgements in some of the design decisions of C toolchains? Sure -
> again, show me a perfect toolchain. Is C not quite an exact fit for all
> your needs for writing an OS? Sure. It's a general purpose language
> that is good for a very wide range of uses - but it's unlikely to be
> /perfect/ for any given use-case. And it never has been, and it never
> will be. Nor will anything else. Modern C is a vastly better language
> than the earliest K&R C. Modern C toolchains are vastly better than the
> tools of that era. As well as the hundred steps forward, there have no
> doubt been a dozen steps backwards for some people and some uses.
> That's life. If you don't like it, give up programming and stick to a
> safer hobby.
>

>
> (For the record, I don't think type-based alias analysis actually gives
> very significant optimisation opportunities in most code. On the other
> hand, I also don't think it causes problems very often - not nearly as
> often as the "optimisation is evil" crowd seem to behave. I write
> low-level code all the time, and it is extraordinarily rarely that I
> have to find a way around it.)
>

Will agree on this point.

In my own testing, basic caching while also aggressively invalidating
the cached results (on any explicit memory store), can give much of the
same performance benefit, while still being fairly conservative
semantically.

The problem though is when optimizations start being treated as "all or
nothing", eg, "you either accept TBAA or can't use optimizations at
all", which is a problem IMO.

Say:
x=foo->x;
*ptr=3;
y=foo->x; //Do we reuse prior result here?

Under TBAA, the second "foo->x" may reuse the result of the first, but
under more conservative semantics, the "*ptr=" would effectively
invalidate the cached result regardless of the pointer type.

Whereas, say:
x=foo->bar->x;
y=foo->bar->y;
Becomes, effectively:
t0=foo->bar;
x=t0->x;
y=t0->y;

Where no invalidation happens because local variables don't count as
stores (it is generally pretty safe to assume that local variables exist
off in their own space, roughly entirely independent from physical
memory, unless their address is taken).

One option is to specify subsets of optimizations based on settings, say:
Os, optimize for size (take slower options if smaller);
O1, optimize for speed, favoring size minimization over speed;
O2, optimize for speed, favoring speed over size;
O3, optimize for speed, enable more aggressive optimizations.

So, for example, with Os, O1, and O2, TBAA is not used, whereas for O3
or similar, things like TBAA would be enabled (with secondary options to
enable or disable TBAA semantics).

MSVC does something vaguely similar to this, though from what I have
found, for some types of programs (such as my emulators), O1 tends to be
faster than O2 (I suspect because MSVC's O2 option is a lot more prone
to make use of "misguided attempts at autovectorization" when compared
with O1).

Granted, arguably I could upgrade MSVC and see if anything is
difference, but given I am kinda battling with space on "C:\" (and there
is no real way to make it bigger), not particularly inclined to do so.

Eg, "320GB should be more than enough space for anyone."
Windows: "Nope!"
Me: "Can you at least give me an option to expand the partition?"
Windows: "What sort of insanity is this?..."

Still have space on other drives, but this isn't of much use if one
wants to install another version of Visual Studio or similar.

....

On Thursday, October 7, 2021 at 3:47:23 PM UTC-5, BGB wrote:
> On 10/7/2021 2:35 PM, David Brown wrote:
> > On 07/10/2021 12:52, cla...@hotmail.com wrote:
> >> Might strike a cord with Anton and/or Mich
> >>
> >> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
> >>
> >
>
> Under TBAA, the second "foo->x" may reuse the result of the first, but
> under more conservative semantics, the "*ptr=" would effectively
> invalidate the cached result regardless of the pointer type.
>
> Whereas, say:
> x=foo->bar->x;
> y=foo->bar->y;
> Becomes, effectively:
> t0=foo->bar;
> x=t0->x;
> y=t0->y;
<
In Operating System code; if one write the top 2 statements, one should
get at least 4 loads--it is simply UNSAFE to assume otherwise--even
if x happens to be allocated into a register (which may happen FAR after
aliasing analysis is performed.)
<
If the programmer KNOWS that there is no aliasing going on, the programmer
should write the bottom set of code.
<
If the programmer writes the top code and expects some kind of compiler
flags (or magic) can translate it to the bottom--the programmer should be
FIRED !
<
Those are the only 3 options available in Operating system code.
You do not allow IDIOTS to write such code and expect anything good to become
of your investment.
>
> Where no invalidation happens because local variables don't count as
> stores (it is generally pretty safe to assume that local variables exist
> off in their own space, roughly entirely independent from physical
> memory, unless their address is taken).
>
>
> One option is to specify subsets of optimizations based on settings, say:
> Os, optimize for size (take slower options if smaller);
> O1, optimize for speed, favoring size minimization over speed;
> O2, optimize for speed, favoring speed over size;
> O3, optimize for speed, enable more aggressive optimizations.
<
Operating systems are in a position where normal codes are not--they have
their own address space and visibility into another address space (or more).
The MMU tables can map multiple virtual addresses to a single physical page.
Are you going to make the compiler smart enough to understand that kind
of memory accessing ??!!?? No, you are not, because it is an unsolvable
problem (outside of SAS.)
>
> So, for example, with Os, O1, and O2, TBAA is not used, whereas for O3
> or similar, things like TBAA would be enabled (with secondary options to
> enable or disable TBAA semantics).
>
If an Operating system wants certain things to run really fast, then embed
this stuff in a library call and optimize the heck out of it (so long as it does
not cross the multipleVA->onePA problem domain.) Then call these optimum
functions from way less optimized code--And here is an Ideal location to
point out that if you inline the optimizable code into unoptimizable code
"text" that inlined function has to take on the unoptimizability of the original
library call.
<
It is much like handling fiearms::
<
1) all pointers are loaded at all times unless verified they are not.
2) never point a pointer at something you do not want destroyed.
3) never enable a pointer until your sights are on the target
<
4) There is NO SUCH THING as a casual pointer.
>
> MSVC does something vaguely similar to this, though from what I have
> found, for some types of programs (such as my emulators), O1 tends to be
> faster than O2 (I suspect because MSVC's O2 option is a lot more prone
> to make use of "misguided attempts at autovectorization" when compared
> with O1).
>
>
> Granted, arguably I could upgrade MSVC and see if anything is
> difference, but given I am kinda battling with space on "C:\" (and there
> is no real way to make it bigger), not particularly inclined to do so.
>
> Eg, "320GB should be more than enough space for anyone."
> Windows: "Nope!"
> Me: "Can you at least give me an option to expand the partition?"
> Windows: "What sort of insanity is this?..."
>
> Still have space on other drives, but this isn't of much use if one
> wants to install another version of Visual Studio or similar.
>
> ...

On Thursday, October 7, 2021 at 7:46:28 PM UTC-5, MitchAlsup wrote:
<
You see, here is the dilemma::
<
Assume 2 OS threads, the first in service of a trap from thread[t],
The second in service of a trap from thread[h].
<
OS[t] creates a pointer into thread[t]. Can this pointer be used in any
meaningful way in OS[h] ?
<
No (99.99%) of the time. The lower ½ of OS[t] address space is completely
unrelated to the lower ½ of OS[h] address space--even though 100% of the
upper ½ address space is shared between OS[t] and OS[h]!
<
Can compiler aliasing analysis figure any of this out ?
<
Doubtful !!

On 2021-10-08, MitchAlsup <MitchAlsup@aol.com> wrote:
> On Thursday, October 7, 2021 at 3:47:23 PM UTC-5, BGB wrote:
>> On 10/7/2021 2:35 PM, David Brown wrote:
>> > On 07/10/2021 12:52, cla...@hotmail.com wrote:
>> >> Might strike a cord with Anton and/or Mich
>> >>
>> >> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
>> >>
>> >
>>
>> Under TBAA, the second "foo->x" may reuse the result of the first, but
>> under more conservative semantics, the "*ptr=" would effectively
>> invalidate the cached result regardless of the pointer type.
>>
>> Whereas, say:
>> x=foo->bar->x;
>> y=foo->bar->y;
>> Becomes, effectively:
>> t0=foo->bar;
>> x=t0->x;
>> y=t0->y;
><
> In Operating System code; if one write the top 2 statements, one should
> get at least 4 loads--it is simply UNSAFE to assume otherwise--even
> if x happens to be allocated into a register (which may happen FAR after
> aliasing analysis is performed.)
><
> If the programmer KNOWS that there is no aliasing going on, the programmer
> should write the bottom set of code.
><
> If the programmer writes the top code and expects some kind of compiler
> flags (or magic) can translate it to the bottom--the programmer should be
> FIRED !

Isn't it that GC are always advertised as way to solve *cycling references*?

>> ...

--

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

On 2021-10-08, MitchAlsup <MitchAlsup@aol.com> wrote:
> On Thursday, October 7, 2021 at 7:46:28 PM UTC-5, MitchAlsup wrote:
><
> You see, here is the dilemma::
><
> Assume 2 OS threads, the first in service of a trap from thread[t],
> The second in service of a trap from thread[h].
><
> OS[t] creates a pointer into thread[t]. Can this pointer be used in any
> meaningful way in OS[h] ?
><
> No (99.99%) of the time. The lower ½ of OS[t] address space is completely
> unrelated to the lower ½ of OS[h] address space--even though 100% of the
> upper ½ address space is shared between OS[t] and OS[h]!
>
Isn't it that threads are defined as sharing same address space, unlike
processes? Actually there is no other difference between processes and
threads...

<
> Can compiler aliasing analysis figure any of this out ?
><
> Doubtful !!
>
Compiler is nothing, just distraction, buggy assumptions at that...
But you have to know bugs of compilers in order to use them :P

--

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

BGB <cr88192@gmail.com> schrieb:

> Say:
> x=foo->x;
> *ptr=3;
> y=foo->x; //Do we reuse prior result here?
>
Depends on the type of ptr, if it agrees with foo.x or not.
If both are (for example) *int, then it is not possible to
reuse it. If foo.x is *float and ptr is *unsigned int, then
yes.

MitchAlsup <MitchAlsup@aol.com> schrieb:

> It is much like handling fiearms::
><
> 1) all pointers are loaded at all times unless verified they are not.
> 2) never point a pointer at something you do not want destroyed.
> 3) never enable a pointer until your sights are on the target
><
> 4) There is NO SUCH THING as a casual pointer.

I _love_ that.

David Brown <david.brown@hesbynett.no> schrieb:
> "We were all
> happy and no bugs existed in code until gcc sinned by optimising code,
> and we were thrown out of Eden into a hell of undefined behaviour".

*snarf*

That was the sound of that qoute hitting the gcc bugzilla quip file.

On Fri, 08 Oct 2021 01:41:35 GMT, Branimir Maksimovic
<branimir.maksimovic@icloud.com> wrote:

>On 2021-10-08, MitchAlsup <MitchAlsup@aol.com> wrote:
>> On Thursday, October 7, 2021 at 7:46:28 PM UTC-5, MitchAlsup wrote:
>><
>> You see, here is the dilemma::
>><
>> Assume 2 OS threads, the first in service of a trap from thread[t],
>> The second in service of a trap from thread[h].
>><
>> OS[t] creates a pointer into thread[t]. Can this pointer be used in any
>> meaningful way in OS[h] ?
>><
>> No (99.99%) of the time. The lower ½ of OS[t] address space is completely
>> unrelated to the lower ½ of OS[h] address space--even though 100% of the
>> upper ½ address space is shared between OS[t] and OS[h]!
>>
>Isn't it that threads are defined as sharing same address space, unlike
>processes? Actually there is no other difference between processes and
>threads...

That's a de facto definition rather than a canon one. Technically
both "process" and "thread" are execution contexts, and they mean
whatever they are defined to mean in a given system. The idea that a
process represents an address space / protection domain while a thread
represents a code path is really only an artifact of the way in which
threads initially were implemented.

As a counter example, consider that on the Mill multiple threads in
the same program simultaneously can be in different protection
domains.

Take a look at "scheduler activations" for a different idea of how the
kernel can support multiple threads.
https://homes.cs.washington.edu/~tom/pubs/sched_act.pdf
http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html

Note: scheduler activations initially may /look/ similar to M:N
threading (userspace threads multiplexed on kernel threads), but
underneath they are quite different.

>> Can compiler aliasing analysis figure any of this out ?
>><
>> Doubtful !!
>>
>Compiler is nothing, just distraction, buggy assumptions at that...
>But you have to know bugs of compilers in order to use them :P

On 10/8/2021 12:51 AM, Thomas Koenig wrote:
> BGB <cr88192@gmail.com> schrieb:
>
>> Say:
>> x=foo->x;
>> *ptr=3;
>> y=foo->x; //Do we reuse prior result here?
>>
> Depends on the type of ptr, if it agrees with foo.x or not.
> If both are (for example) *int, then it is not possible to
> reuse it. If foo.x is *float and ptr is *unsigned int, then
> yes.
>

I left this part deliberately vague, but yeah.
Under type-based aliasing rules, that would be correct.

I took a more conservative interpretation here by default, and made my
compiler assume that aliasing may occur regardless of any of the actual
types involved.

This gets much of the performance advantage, without a lot of the
potential drawbacks of full strict-aliasing semantics (such as it
interfering with the ability to cast whatever pointer to whatever type
and then perform operations on it).

On 07/10/2021 22:47, BGB wrote:
> On 10/7/2021 2:35 PM, David Brown wrote:
>> On 07/10/2021 12:52, clamky@hotmail.com wrote:
>>> Might strike a cord with Anton and/or Mich
>>>
>>> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
>>>
>>>
>>
>> It seems to me that the authors have misunderstood the language entirely.
>>
>> C was never meant to be a "high-level assembler" or a "portable
>> assembler".  It was never intended that you could write low-level
>> systems programs in portable C.  It was designed to reduce the need to
>> write code in assembler, and to improve the portability of code.
>> (Re-read that sentence if you like.)  It was intended to be useable for
>> writing some kinds of code in a highly portable manner, and also to be
>> useful in non-portable systems code that depended strongly on the target
>> and the compiler.
>>
>>  From day one, operating systems "written in C" contained assembly code,
>> compiler extensions, and other non-portable code.  That remains true
>> today.  "Coding tricks" were often used to get efficient results due to
>> more limited compilers - these are much less common now as compilers
>> optimise better.
>>
>>
>> As I got further in the document, it seems to be just another "the
>> compiler should do what I want it to do, not necessarily what I /told/
>> it to do" rant.  "C today should work the way /I/ want it to do - the
>> way /I/ interpret the precise wording of what someone decades ago".
>> "Thompson and Ritchie were saints and prophets, and their words were
>> holy and eternal - regardless of how computers, languages, and
>> programming needs have changed since the inception of C".  "We were all
>> happy and no bugs existed in code until gcc sinned by optimising code,
>> and we were thrown out of Eden into a hell of undefined behaviour".
>> "Yes, we know that compilers often give us ways to get the semantics we
>> want by specific flags, but that's not good enough - everyone else
>> should get slower code so that we don't have to think as much or follow
>> the rules of the language".
>>
>
> The author of the paper (Victor Yodaiken) has sort of a long history of
> "making a mountain out of a molehill" about all this stuff...
>

It seems that way. Often there are some good points - as I wrote, no
language or tool is perfect, and it's important that people find weak
points or make suggestions for improvement. Massively exaggerated
rants, however, are worse than useless - they encourage other fanatics
who feed on the same myths, doom-saying and exaggerations. And they
ensure that those who actually have a say in the tools and language -
the standards committees and compiler developers - will ignore all their
concerns and write them off as fanatics. Good points they raise get
thrown out and ignored along with the reams of rubbish,
misunderstandings and misrepresentations that hide them.

>
> I have my opinions, but will note that "the system" is self-regulating
> to some extent, as compiler people would have a hard-time keeping people
> using their compilers if they set out to break large amounts of existing
> "real world" code (and will tend to back down when they face sufficient
> backlash).

Agreed. Compiler writers have no interest in making tools that people
don't want to use. If feedback suggests a new compiler version does not
work the way people expect and want, then the compiler developers take
that seriously - they discuss matters with the users, they change the
behaviour of the tools, they add flags or options to give users more
control of the behaviour. In particular, they aim to test out new
changes during pre-release and beta test stages so that potential
problems get handled sooner.

A similar process applies to language standards - there are long periods
of proposals, discussions, and voting before changes are made. Big
compiler users (like Linux distributions, corporations such as IBM,
Microsoft, Google), big compiler implementers, researchers, and anyone
else who is interested can get involved and share their opinion.

You are never going to please everyone all of the time. And you are
never going to please the small but vocal community who object to
everything and accuse compiler writers and/or language committees of all
sorts of evil motives and conspiracies. But they do a solid job
overall, which is why languages like C are still a good choice for a lot
of tasks.

>
> In cases where stuff has broken in more significant ways, it has usually
> been fairly isolated (a particular build of a particular compiler),
> rather than a long-term change to the status quo.
>

And usually a "significant break" is found during testing stages, rather
than post release.

>>
>> Are there imperfections in C as a language standard?  Sure.  Show me a
>> perfect language standard as an alternative.  Are there questionable
>> judgements in some of the design decisions of C toolchains?  Sure -
>> again, show me a perfect toolchain.  Is C not quite an exact fit for all
>> your needs for writing an OS?  Sure.  It's a general purpose language
>> that is good for a very wide range of uses - but it's unlikely to be
>> /perfect/ for any given use-case.  And it never has been, and it never
>> will be.  Nor will anything else.  Modern C is a vastly better language
>> than the earliest K&R C.  Modern C toolchains are vastly better than the
>> tools of that era.  As well as the hundred steps forward, there have no
>> doubt been a dozen steps backwards for some people and some uses.
>> That's life.  If you don't like it, give up programming and stick to a
>> safer hobby.
>>
>
>>
>> (For the record, I don't think type-based alias analysis actually gives
>> very significant optimisation opportunities in most code.  On the other
>> hand, I also don't think it causes problems very often - not nearly as
>> often as the "optimisation is evil" crowd seem to behave.  I write
>> low-level code all the time, and it is extraordinarily rarely that I
>> have to find a way around it.)
>>
>
> Will agree on this point.
>
> In my own testing, basic caching while also aggressively invalidating
> the cached results (on any explicit memory store), can give much of the
> same performance benefit, while still being fairly conservative
> semantically.
>

There is a move towards "providence tracking" for memory and pointers as
an alternative to things like type-based alias analysis. This is a lot
more powerful, as it tracks when different references to the same type
cannot alias, and thus can give much more optimisation opportunities and
static error analysis benefits. It subsumes most TBAA, since pointers
to different types usually have different providences. But in cases
where the providence is actually the same, aliases (or potential
aliases) are handled correctly. However, it turns out to be quite
difficult to specify all this, and it is a work in progress (both for
language standards and implementations).

> The problem though is when optimizations start being treated as "all or
> nothing", eg, "you either accept TBAA or can't use optimizations at
> all", which is a problem IMO.
>
> Say:
>   x=foo->x;
>   *ptr=3;
>   y=foo->x;  //Do we reuse prior result here?
>
> Under TBAA, the second "foo->x" may reuse the result of the first, but
> under more conservative semantics, the "*ptr=" would effectively
> invalidate the cached result regardless of the pointer type.
>
> Whereas, say:
>   x=foo->bar->x;
>   y=foo->bar->y;
> Becomes, effectively:
>   t0=foo->bar;
>   x=t0->x;
>   y=t0->y;
>
> Where no invalidation happens because local variables don't count as
> stores (it is generally pretty safe to assume that local variables exist
> off in their own space, roughly entirely independent from physical
> memory, unless their address is taken).
>
>
> One option is to specify subsets of optimizations based on settings, say:
>   Os, optimize for size (take slower options if smaller);
>   O1, optimize for speed, favoring size minimization over speed;
>   O2, optimize for speed, favoring speed over size;
>   O3, optimize for speed, enable more aggressive optimizations.
>
> So, for example, with Os, O1, and O2, TBAA is not used, whereas for O3
> or similar, things like TBAA would be enabled (with secondary options to
> enable or disable TBAA semantics).
>

On 08/10/2021 08:21, Thomas Koenig wrote:
> David Brown <david.brown@hesbynett.no> schrieb:
>> "We were all
>> happy and no bugs existed in code until gcc sinned by optimising code,
>> and we were thrown out of Eden into a hell of undefined behaviour".
>
> *snarf*
>
> That was the sound of that qoute hitting the gcc bugzilla quip file.
>

I hope you didn't attribute it as a real quotation from the referenced
paper!

(And I hope I didn't offend anyone with some of the imagery I used.)

On 2021-10-08, George Neuner <gneuner2@comcast.net> wrote:
> As a counter example, consider that on the Mill multiple threads in
> the same program simultaneously can be in different protection
> domains.
>
> Take a look at "scheduler activations" for a different idea of how the
> kernel can support multiple threads.
> https://homes.cs.washington.edu/~tom/pubs/sched_act.pdf
> http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html
>
> Note: scheduler activations initially may /look/ similar to M:N
> threading (userspace threads multiplexed on kernel threads), but
> underneath they are quite different.
>
Thanks, I'll look into it.

--

7-77-777
Evil Sinner!
with software, you repeat same experiment, expecting different results...

On 10/8/2021 4:43 AM, David Brown wrote:

>
> There is a move towards "providence tracking" for memory and pointers as
> an alternative to things like type-based alias analysis. This is a lot
> more powerful, as it tracks when different references to the same type
> cannot alias, and thus can give much more optimisation opportunities and
> static error analysis benefits. It subsumes most TBAA, since pointers
> to different types usually have different providences. But in cases
> where the providence is actually the same, aliases (or potential
> aliases) are handled correctly. However, it turns out to be quite
> difficult to specify all this, and it is a work in progress (both for
> language standards and implementations).

provenance?

MitchAlsup <MitchAlsup@aol.com> wrote:
> On Thursday, October 7, 2021 at 3:47:23 PM UTC-5, BGB wrote:
> > On 10/7/2021 2:35 PM, David Brown wrote:
> > > On 07/10/2021 12:52, cla...@hotmail.com wrote:
> > >> Might strike a cord with Anton and/or Mich
> > >>
> > >> https://www.yodaiken.com/2021/10/06/plos-2021-paper-how-iso-c-became-unusable-for-operating-system-development/
> > >>
> > >
> >
> > Under TBAA, the second "foo->x" may reuse the result of the first, but
> > under more conservative semantics, the "*ptr=" would effectively
> > invalidate the cached result regardless of the pointer type.
> >
> > Whereas, say:
> > x=foo->bar->x;
> > y=foo->bar->y;
> > Becomes, effectively:
> > t0=foo->bar;
> > x=t0->x;
> > y=t0->y;
> <
> In Operating System code; if one write the top 2 statements, one should
> get at least 4 loads--it is simply UNSAFE to assume otherwise--even
> if x happens to be allocated into a register (which may happen FAR after
> aliasing analysis is performed.)

Sorry, code _assuming_ aliasing there is simply insane, regardless
if this in operating system on not. If anybody really needs
aliansing in such context this should be done by special purpose
construct.

> If the programmer KNOWS that there is no aliasing going on, the programmer
> should write the bottom set of code.
> <
> If the programmer writes the top code and expects some kind of compiler
> flags (or magic) can translate it to the bottom--the programmer should be
> FIRED !
> <
> Those are the only 3 options available in Operating system code.
> You do not allow IDIOTS to write such code and expect anything good to become
> of your investment.

Code as above is typical result of macro expansion (or inlining).
_Depending_ on optimization for any specific use is unwise. But
most systems are written to get good _average_ performance and
in large systems optimization makes difference to average
performance.

> > Where no invalidation happens because local variables don't count as
> > stores (it is generally pretty safe to assume that local variables exist
> > off in their own space, roughly entirely independent from physical
> > memory, unless their address is taken).
> >
> >
> > One option is to specify subsets of optimizations based on settings, say:
> > Os, optimize for size (take slower options if smaller);
> > O1, optimize for speed, favoring size minimization over speed;
> > O2, optimize for speed, favoring speed over size;
> > O3, optimize for speed, enable more aggressive optimizations.
> <
> Operating systems are in a position where normal codes are not--they have
> their own address space and visibility into another address space (or more).
> The MMU tables can map multiple virtual addresses to a single physical page.
> Are you going to make the compiler smart enough to understand that kind
> of memory accessing ??!!?? No, you are not, because it is an unsolvable
> problem (outside of SAS.)

In normal compiler it is compiler who allocates local and global variables
and they are allocated from different memory pool than dynamic memory.
OS that messes with compiler locals is simply insane. OS that plays
tricks with global variables arguably should do this using special
constructs known to compiler (like memory barries, volatile etc.).
Compiler normally are rather conservative in their assumprions about
dynamically allocated memory. So OS that invalidates compiler
assumptions is simply badly designed OS.
--
Waldek Hebisch

On 08/10/2021 14:17, Ivan Godard wrote:
> On 10/8/2021 4:43 AM, David Brown wrote:
>
>
>>
>> There is a move towards "providence tracking" for memory and pointers as
>> an alternative to things like type-based alias analysis.  This is a lot
>> more powerful, as it tracks when different references to the same type
>> cannot alias, and thus can give much more optimisation opportunities and
>> static error analysis benefits.  It subsumes most TBAA, since pointers
>> to different types usually have different providences.  But in cases
>> where the providence is actually the same, aliases (or potential
>> aliases) are handled correctly.  However, it turns out to be quite
>> difficult to specify all this, and it is a work in progress (both for
>> language standards and implementations).
>
> provenance?

Yes, that's the word I intended to use! Once Thunderbird's auto-correct
had turned my mangled guess at the spelling into a correctly spelt but
unintended word, I reused it without thinking.

David Brown <david.brown@hesbynett.no> schrieb:
> On 08/10/2021 08:21, Thomas Koenig wrote:
>> David Brown <david.brown@hesbynett.no> schrieb:
>>> "We were all
>>> happy and no bugs existed in code until gcc sinned by optimising code,
>>> and we were thrown out of Eden into a hell of undefined behaviour".
>>
>> *snarf*
>>
>> That was the sound of that qoute hitting the gcc bugzilla quip file.
>>
>
> I hope you didn't attribute it as a real quotation from the referenced
> paper!

No, I just added the sentence as is (with Americanized spelling).

I thought it fit the critera of "something clever or funny or
boring (but not obscene or offensive, please)".

(If you have a bugzilla account, you can also extend the quip list;
I have put in a few over the years).

antispam@math.uni.wroc.pl <antispam@math.uni.wroc.pl> schrieb:
> MitchAlsup <MitchAlsup@aol.com> wrote:
>> On Thursday, October 7, 2021 at 3:47:23 PM UTC-5, BGB wrote:
>> > Whereas, say:
>> > x=foo->bar->x;
>> > y=foo->bar->y;
>> > Becomes, effectively:
>> > t0=foo->bar;
>> > x=t0->x;
>> > y=t0->y;
>> <
>> In Operating System code; if one write the top 2 statements, one should
>> get at least 4 loads--it is simply UNSAFE to assume otherwise--even
>> if x happens to be allocated into a register (which may happen FAR after
>> aliasing analysis is performed.)
>
> Sorry, code _assuming_ aliasing there is simply insane, regardless
> if this in operating system on not. If anybody really needs
> aliansing in such context this should be done by special purpose
> construct.

Which is why I like Fortran's handling of pointers and allocatables
better than C's.

In Fortran, a pointer is an alias to a variable. That variable
can be allocated via the ALLOCATE statement or can be a variable
declared with the TARGET attribute. The compiler can assume
(and, to a large extent, check) that no pointer points at
something that is not a TARGET. Pointers to arrays, or parts
of arrays, are also possible.

An allocatable variable is a different beast. It is allocated by
an ALLOCATE statement or by automatic (re-)allocation. No other
pointer can point to it, unless it is also declared TARGET.
It is also deallocated automatically upon going out of scope.

And a dummy argument (parameter in C) is something else again.
You cannot have these aliasing when one of them is assigned to.

C has conflated these three concepts into one, pointers, together
with pointer arithmetic for array access. This all made sense
in the 1970s when the language was designed for when the language
had to fit on a small machine. Today, not so much.

George Neuner wrote:
> On Fri, 08 Oct 2021 01:41:35 GMT, Branimir Maksimovic
> <branimir.maksimovic@icloud.com> wrote:
>
>> On 2021-10-08, MitchAlsup <MitchAlsup@aol.com> wrote:
>>> On Thursday, October 7, 2021 at 7:46:28 PM UTC-5, MitchAlsup wrote:
>>> <
>>> You see, here is the dilemma::
>>> <
>>> Assume 2 OS threads, the first in service of a trap from thread[t],
>>> The second in service of a trap from thread[h].
>>> <
>>> OS[t] creates a pointer into thread[t]. Can this pointer be used in any
>>> meaningful way in OS[h] ?
>>> <
>>> No (99.99%) of the time. The lower ½ of OS[t] address space is completely
>>> unrelated to the lower ½ of OS[h] address space--even though 100% of the
>>> upper ½ address space is shared between OS[t] and OS[h]!
>>>
>> Isn't it that threads are defined as sharing same address space, unlike
>> processes? Actually there is no other difference between processes and
>> threads...
>
> That's a de facto definition rather than a canon one. Technically
> both "process" and "thread" are execution contexts, and they mean
> whatever they are defined to mean in a given system. The idea that a
> process represents an address space / protection domain while a thread
> represents a code path is really only an artifact of the way in which
> threads initially were implemented.
>
> As a counter example, consider that on the Mill multiple threads in
> the same program simultaneously can be in different protection
> domains.
>
> Take a look at "scheduler activations" for a different idea of how the
> kernel can support multiple threads.
> https://homes.cs.washington.edu/~tom/pubs/sched_act.pdf
> http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html
>
> Note: scheduler activations initially may /look/ similar to M:N
> threading (userspace threads multiplexed on kernel threads), but
> underneath they are quite different.

Unless I missed something, these scheduler activations are user mode
threads that switch on blocking events like page faults to a different
user mode thread by having the OS punt back to user mode on blocking.
Why wouldn't I just use normal kernel scheduled threads?

On 08/10/2021 17:42, Thomas Koenig wrote:
> David Brown <david.brown@hesbynett.no> schrieb:
>> On 08/10/2021 08:21, Thomas Koenig wrote:
>>> David Brown <david.brown@hesbynett.no> schrieb:
>>>> "We were all
>>>> happy and no bugs existed in code until gcc sinned by optimising code,
>>>> and we were thrown out of Eden into a hell of undefined behaviour".
>>>
>>> *snarf*
>>>
>>> That was the sound of that qoute hitting the gcc bugzilla quip file.
>>>
>>
>> I hope you didn't attribute it as a real quotation from the referenced
>> paper!
>
> No, I just added the sentence as is (with Americanized spelling).
>
> I thought it fit the critera of "something clever or funny or
> boring (but not obscene or offensive, please)".
>
> (If you have a bugzilla account, you can also extend the quip list;
> I have put in a few over the years).
>

I do have an account, and have registered a few bugs, but I did not know
about the quip list. It's always a rare pleasure to learn something new
from Usenet!

On 10/8/2021 8:56 AM, EricP wrote:
> George Neuner wrote:
>> On Fri, 08 Oct 2021 01:41:35 GMT, Branimir Maksimovic
>> <branimir.maksimovic@icloud.com> wrote:
>>
>>> On 2021-10-08, MitchAlsup <MitchAlsup@aol.com> wrote:
>>>> On Thursday, October 7, 2021 at 7:46:28 PM UTC-5, MitchAlsup wrote:
>>>> <
>>>> You see, here is the dilemma::
>>>> <
>>>> Assume 2 OS threads, the first in service of a trap from thread[t],
>>>> The second in service of a trap from thread[h].
>>>> <
>>>> OS[t] creates a pointer into thread[t]. Can this pointer be used in any
>>>> meaningful way in OS[h] ?
>>>> <
>>>> No (99.99%) of the time. The lower ½ of OS[t] address space is
>>>> completely
>>>> unrelated to the lower ½ of OS[h] address space--even though 100% of
>>>> the
>>>> upper ½ address space is shared between OS[t] and OS[h]!
>>>>
>>> Isn't it that threads are defined as sharing same address space, unlike
>>> processes?  Actually there is no other difference between processes and
>>> threads...
>>
>> That's a de facto definition rather than a canon one.  Technically
>> both "process" and "thread" are execution contexts, and they mean
>> whatever they are defined to mean in a given system.  The idea that a
>> process represents an address space / protection domain while a thread
>> represents a code path is really only an artifact of the way in which
>> threads initially were implemented.
>>
>> As a counter example, consider that on the Mill multiple threads in
>> the same program simultaneously can be in different protection
>> domains.
>>
>> Take a look at "scheduler activations" for a different idea of how the
>> kernel can support multiple threads.
>> https://homes.cs.washington.edu/~tom/pubs/sched_act.pdf
>> http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html
>>
>> Note: scheduler activations initially may /look/ similar to M:N
>> threading (userspace threads multiplexed on kernel threads), but
>> underneath they are quite different.
>
> Unless I missed something, these scheduler activations are user mode
> threads that switch on blocking events like page faults to a different
> user mode thread by having the OS punt back to user mode on blocking.
> Why wouldn't I just use normal kernel scheduled threads?
>
>

Because, for most current systems, a kernel thread switch is thousands
of cycles.

Ivan Godard wrote:
> On 10/8/2021 8:56 AM, EricP wrote:
>> George Neuner wrote:
>>> On Fri, 08 Oct 2021 01:41:35 GMT, Branimir Maksimovic
>>> <branimir.maksimovic@icloud.com> wrote:
>>>
>>>> On 2021-10-08, MitchAlsup <MitchAlsup@aol.com> wrote:
>>>>> On Thursday, October 7, 2021 at 7:46:28 PM UTC-5, MitchAlsup wrote:
>>>>> <
>>>>> You see, here is the dilemma::
>>>>> <
>>>>> Assume 2 OS threads, the first in service of a trap from thread[t],
>>>>> The second in service of a trap from thread[h].
>>>>> <
>>>>> OS[t] creates a pointer into thread[t]. Can this pointer be used in
>>>>> any
>>>>> meaningful way in OS[h] ?
>>>>> <
>>>>> No (99.99%) of the time. The lower ½ of OS[t] address space is
>>>>> completely
>>>>> unrelated to the lower ½ of OS[h] address space--even though 100%
>>>>> of the
>>>>> upper ½ address space is shared between OS[t] and OS[h]!
>>>>>
>>>> Isn't it that threads are defined as sharing same address space, unlike
>>>> processes? Actually there is no other difference between processes and
>>>> threads...
>>>
>>> That's a de facto definition rather than a canon one. Technically
>>> both "process" and "thread" are execution contexts, and they mean
>>> whatever they are defined to mean in a given system. The idea that a
>>> process represents an address space / protection domain while a thread
>>> represents a code path is really only an artifact of the way in which
>>> threads initially were implemented.
>>>
>>> As a counter example, consider that on the Mill multiple threads in
>>> the same program simultaneously can be in different protection
>>> domains.
>>>
>>> Take a look at "scheduler activations" for a different idea of how the
>>> kernel can support multiple threads.
>>> https://homes.cs.washington.edu/~tom/pubs/sched_act.pdf
>>> http://web.mit.edu/nathanw/www/usenix/freenix-sa/freenix-sa.html
>>>
>>> Note: scheduler activations initially may /look/ similar to M:N
>>> threading (userspace threads multiplexed on kernel threads), but
>>> underneath they are quite different.
>>
>> Unless I missed something, these scheduler activations are user mode
>> threads that switch on blocking events like page faults to a different
>> user mode thread by having the OS punt back to user mode on blocking.
>> Why wouldn't I just use normal kernel scheduled threads?
>>
>>
>
> Because, for most current systems, a kernel thread switch is thousands
> of cycles.

According to the HTML paper dated 2002 titled
"An Implementation of Scheduler Activations on the NetBSD Operating System"
in the section "Performance Analysis"
a Linux 2.4.19 kernel thread context switch is 82 us,
GNU PTH Portable Threads user mode library on NetBSD is 166 us,
and Scheduler Activations on NetBSD is 225 us.

I don't know what that 2002 version of Linux scheduler did but
around that time they used a single Big Lock for many OS resources.
Since then much of the locking has been made finer grain and scheduling
in particular is separated for each core so no locking is required.
So kernel thread context switch should be proportionally even faster.