BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the
application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good
when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000 ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
On 6/22/2026 9:26 AM, Niklas Holsti wrote:
On 2026-06-22 17:59, Stephen Fuld wrote:
On 6/22/2026 3:44 AM, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
There is a discussion going on at the moment about "pointer
providence"
Perhaps you meant pointer "provenance"? I hope we will not rely on the >>>>> "careful governance and guidance of God", or on an "instance of divine >>>>> intervention" to ensure pointer safety...
Has pointer safety been shown to be equivalent to the halting
problem?-a If so, "careful governance and guidance from God" may
indeed be required.
I don't know the answer to your question, but presumably we can do
better than C does.-a Isn't that one of the, at least claimed,
advantages of Rust, and perhaps even Ada?
Both Rust and Ada have to be restricted in certain ways in order to
ensure absence of pointer errors: Rust has to avoid "unsafe" code,
I like Rust's solution.-a You can do unsafe things - sometimes they are
just necessary - but they are not the default was of doing things, and
you have to notate them in the source code which serves to discourage
them and points people debugging errors to certain areas of the code
that are more likley to be problematic.
and Ada has to avoid pointer-related "unchecked" constructs and
certain undefined behavior (which does exist in Ada, but less so than
in C). The Ada subset called SPARK, together with its proof tools, is
meant for such programming, and has a feature similar to Rust
"ownership" though standard Ada does not.
Is programming under SPARK rules significantly harder than under
nonSPARK Ada?
One could indeed say so, because the reason is Putin's attack on-aAlso, I believe that had the originators of C not allowed arithmetic
on pointers (comparisons for equality would still be allowed, and
array addressing would have to use subscripts) many of the problems
with C pointers wouldn't have occurred.-a Of course, that horse has
left the barn a long time ago.
I recently helped to debug an Ada program that now and then, but not
often, was overwriting some buffers. At one point in that program I
had *cough* used pointer arithmetic *blush* instead of array indexing,
for what I felt were good reasons at the time. But it bit me. An
amusing clue to the error was that the bug happened more often when
the satellite running the program was above Russia's borders. Perhaps
you can guess reasons for that :-)
Interesting.-a Perhaps it is because Russia has less "careful governance
and guidance from God" :-)
On 6/21/2026 2:56 PM, Robert Swindells wrote:
On Sun, 21 Jun 2026 13:55:59 -0500, BGB wrote:
Though, I guess one merit of a Lisp like language is that it is a lot
easier to parse, and it could be possible to implement a fairly cheap
compiler for it (in the basic case).
Usual downside it that the excessive parenthesis tend to turn into a
usability issue.
You use an editor that keeps track of them.
Probably.
The main editor I use on Windows, Notepad2, has syntax highlighting and >parenthesis matching.
Normal Notepad does not.
Though, would seem that these features have become fairly common in >text-editors in Linux land.
On 2026-06-22 19:50, Stephen Fuld wrote:
On 6/22/2026 9:26 AM, Niklas Holsti wrote:
On 2026-06-22 17:59, Stephen Fuld wrote:
On 6/22/2026 3:44 AM, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
-a-a [snip]
There is a discussion going on at the moment about "pointer
providence"
Perhaps you meant pointer "provenance"? I hope we will not rely on >>>>>> the
"careful governance and guidance of God", or on an "instance of
divine
intervention" to ensure pointer safety...
Has pointer safety been shown to be equivalent to the halting
problem?-a If so, "careful governance and guidance from God" may
indeed be required.
I don't know the answer to your question, but presumably we can do
better than C does.-a Isn't that one of the, at least claimed,
advantages of Rust, and perhaps even Ada?
Both Rust and Ada have to be restricted in certain ways in order to
ensure absence of pointer errors: Rust has to avoid "unsafe" code,
I like Rust's solution.-a You can do unsafe things - sometimes they are
just necessary - but they are not the default was of doing things, and
you have to notate them in the source code which serves to discourage
them and points people debugging errors to certain areas of the code
that are more likley to be problematic.
Same in Ada, mostly: some unsafe things are named "Unchecked_Xxx",
others are available only if some specific predefined packages are used, which are not needed for most safe things.
and Ada has to avoid pointer-related "unchecked" constructs and
certain undefined behavior (which does exist in Ada, but less so than
in C). The Ada subset called SPARK, together with its proof tools, is
meant for such programming, and has a feature similar to Rust
"ownership" though standard Ada does not.
Is programming under SPARK rules significantly harder than under
nonSPARK Ada?
I don't have personal experience, but my impression is that it does not
make it markedly harder than the usual restrictions on embedded, more- or-less critical software do. SPARK is defined and supported by the
AdaCore company, not a standards group, and is evolving. The
documentation is at https://www.adacore.com/documentation?tab=spark; the main restrictions are (quoted from https://docs.adacore.com/live/wave/ spark2014/html/spark2014_rm/introduction.html#principal-language- restrictions, with my comments in []):
--- quote:
To facilitate formal analyses and verification, SPARK enforces a number
of global restrictions to Ada. While these are covered in more detail in
the remaining chapters of this document, the most notable restrictions are:
- Restrictions on the use of access types and values [pointers], similar
in some ways to the ownership model of the programming language Rust.
- All expressions (including function calls) are free of side effects.
- Aliasing of names is not permitted in general but the renaming of
entities is permitted as there is a static relationship between the two names. In analysis all names introduced by a renaming declaration are replaced by the name of the renamed entity. This replacement is applied recursively when there are multiple renames of an entity.
- Backward goto statements are not permitted.
- The use of controlled types is not currently permitted. [These are
types with automatic invocation of user-defined initialization and finalization operations on object creation, copying, and deletion.]
- Tasks and protected objects are permitted only if the Ravenscar
profile (or the Jorvik profile) is specified. [The main limitation in
these profiles is that the set of tasks (threads) is static, no task
ever terminates, and inter-task communication is by protected objects (monitors, synchronized objects) and not by rendez-vous.]
- Raising and handling of exceptions is not currently permitted
(exceptions can be included in a program but proof must be used to show
that they cannot be raised).
--- end quote.
One could indeed say so, because the reason is Putin's attack on-aAlso, I believe that had the originators of C not allowed
arithmetic on pointers (comparisons for equality would still be
allowed, and array addressing would have to use subscripts) many of
the problems with C pointers wouldn't have occurred.-a Of course,
that horse has left the barn a long time ago.
I recently helped to debug an Ada program that now and then, but not
often, was overwriting some buffers. At one point in that program I
had *cough* used pointer arithmetic *blush* instead of array
indexing, for what I felt were good reasons at the time. But it bit
me. An amusing clue to the error was that the bug happened more often
when the satellite running the program was above Russia's borders.
Perhaps you can guess reasons for that :-)
Interesting.-a Perhaps it is because Russia has less "careful
governance and guidance from God" :-)
Ukraine, as you may have guessed.
The Ada program runs a satellite-based GNSS receiver that acquires
(finds) and then tracks GNSS signals from GNSS satellites (GPS, Galileo,
and others) as those satellites rise or set. The purpose is to measure atmospheric properties from the way the atmosphere refracts the signal.
The design and/or coding error was in the transition between two stages
of the multi-stage procedure for finding and starting to track a GNSS
signal from a GNSS satellite.
So then: Russia attacks Ukraine => Ukraine defends itself with long- distance drones => Russia jams and perturbs GNSS signals along its
borders => the satellite software often loses track of a signal it is tracking => the satellite software often has to re-acquire signals =>
the bug manifests more often over Russia's borders.
If one favours the Ukrainian Orthodox church, which objects to this war, Russia is going against God's guidance. If one favours the Russian
Orthodox church, which blesses this war, Russia is following God's
guidance.
(The bug was not found in testing because it did not manifest on every transition between the two acquisition stages -- it manifested only when
two other dynamic program states occurred together, at the same time as
the transition, and one of these states is rather rare, at least in test conditions.)
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the >> > application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good
when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000 ISA--except for the case where one wants to walk the stack back on a THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Thomas Koenig <tkoenig@netcologne.de> posted:
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:The debugger runs in a separate process with access to application
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the >> >> > application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good >> >> when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000
ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Root pointer and ASID. In that process, Call-stack is RW-.
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
Thomas Koenig <tkoenig@netcologne.de> posted:
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:The debugger runs in a separate process with access to application
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the >>>>>> application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good >>>>> when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000 >>>> ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Root pointer and ASID. In that process, Call-stack is RW-.
GLIBC has a function to obtain a backtrace at a current point
in time. This is called in the context of the thread that invokes
the call. It requires access to the call records on the stack
in the context of the thread (the glicb functions are backtrace(3)
and backtrace_symbols(3)).
/**
* Log a simulator stack traceback.
*/
void
c_osdep::backtrace(c_logger *lp)
{
int num_frames;
void *framelist[100];
char **strings;
num_frames = ::backtrace(framelist, sizeof(framelist)/sizeof(framelist[0]));
strings = ::backtrace_symbols(framelist, num_frames);
if (strings == NULL) {
lp->log("Unable to obtain simulator stack traceback: %s\n",
strerror(errno));
return;
}
for(int frame=0; frame < num_frames; frame++) {
lp->log("[%2.2d] %s\n", frame, strings[frame]);
}
::free(strings);
}
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:Perhaps you meant pointer "provenance"? I hope we will not rely on the
There is a discussion going on at the moment about "pointer providence" >>>
anton@mips.complang.tuwien.ac.at (Anton Ertl) posted:
John Levine <johnl@taugh.com> writes:
C killed off every memory model other than flat byte addressed
memory.
At least in the C standard the memory is segmented into objects.
Pointers are sort of typed, but any real C program does stuff like >>>>>>> this:
-a-a p = (struct foo *) malloc(42 * sizeof(struct foo));
That produces an object of a certain size, and you must only
access it
through pointers derived from p.-a And programs usually satisfy that >>>>>> requirement.
-a-a-a-a-a {
-a-a-a-a-a-a-a-a-a p = (struct foo *) malloc(42 * sizeof(struct foo)); >>>>> -a-a-a-a-a-a-a-a-a fprintf( stream, "0x16,", p );
-a-a-a-a-a-a-a-a-a ...
-a-a-a-a-a-a-a-a-a if( fscanf( stream, "x16", q ) ) {
-a-a-a-a-a-a-a-a-a-a-a-a-a use q
-a-a-a-a-a-a-a-a-a }
-a-a-a-a-a }
is q "derived" though p ??
"careful governance and guidance of God", or on an "instance of divine
intervention" to ensure pointer safety...
Has pointer safety been shown to be equivalent to the halting
problem?-a If so, "careful governance and guidance from God" may
indeed be required.
I would assume it is undecidable, for unrestricted programs. The aim of pointer provenance is no doubt to restrict programs to make it decidable
to some extent.
I am reminded of the person, apparently very religious, who some decades
ago posted to solicit help for reimplementing all of computing (gcc,
GNU, et cetera) on Biblical principles, because he thought Richard
Stallman was too atheistic and had tainted his products. I have not
heard how that went.
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only optimize based on what can be verified by the compiler within certain fundamental assumptions.
Say:
Pointer 1 points at a stack array in the local function;
Pointer 2 was derived from taking the address of a global array;
Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume they don't alias with a pointer to a local array;
I am reminded of the person, apparently very religious, who some decades ago posted to solicit help for reimplementing all of computing (gcc,
GNU, et cetera) on Biblical principles, because he thought Richard Stallman was too atheistic and had tainted his products. I have not
heard how that went.
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
Thomas Koenig <tkoenig@netcologne.de> posted:
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:The debugger runs in a separate process with access to application
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the
application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good >> >> when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000 >> > ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Root pointer and ASID. In that process, Call-stack is RW-.
GLIBC has a function to obtain a backtrace at a current point
in time. This is called in the context of the thread that invokes
the call. It requires access to the call records on the stack
in the context of the thread (the glicb functions are backtrace(3)
and backtrace_symbols(3)).
BGB <cr88192@gmail.com> posted:
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only
optimize based on what can be verified by the compiler within certain
fundamental assumptions.
Say:
Pointer 1 points at a stack array in the local function;
Pointer 2 was derived from taking the address of a global array;
Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume they
don't alias with a pointer to a local array;
C requires the compiler to prove that the pointers cannot alias.
Fortran specifies that if the 2 argument alias, it is a programming error.
-----------------
I am reminded of the person, apparently very religious, who some decades >>> ago posted to solicit help for reimplementing all of computing (gcc,
GNU, et cetera) on Biblical principles, because he thought Richard
Stallman was too atheistic and had tainted his products. I have not
heard how that went.
Rick...
C requires the compiler to prove that the pointers cannot alias.Hard proof that alias is impossible is harder to achieve in practice...
Fortran specifies that if the 2 argument alias, it is a programming error. >>
A softer "there is no reasonable possibility of alias" is easier to achieve.
According to BGB <cr88192@gmail.com>:
C requires the compiler to prove that the pointers cannot alias.Hard proof that alias is impossible is harder to achieve in practice...
Fortran specifies that if the 2 argument alias, it is a programming error. >>>
A softer "there is no reasonable possibility of alias" is easier to achieve.
Sort of. The standard says that the compiler can assume no type punning, so that
if pointers are of different types, they can't point at the same thing (with an
exception for pointers to unions.)
Even so, C has "restrict" to tell the compiler to assume that pointers never alias, and "volatile" to assume they always do.
Consider the Push/Pop mechanics in HW compared to FMAC in HW--which
do you think is easier ???
Now consider 16 pushed in a row versus a single instruction that performs
the same amount of work. Which one needs to translate an address more
often, which one needs to AGEN more often, and which one can access the
cache once for up to 8 registers ???
C requires the compiler to prove that the pointers cannot alias.
Thomas Koenig <tkoenig@netcologne.de> posted:
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:The debugger runs in a separate process with access to application
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the >> >> > application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good >> >> when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000
ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Root pointer and ASID. In that process, Call-stack is RW-.
scott@slp53.sl.home (Scott Lurndal) posted:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
Thomas Koenig <tkoenig@netcologne.de> posted:
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:The debugger runs in a separate process with access to application
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the
application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good
when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000 >> >> > ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Root pointer and ASID. In that process, Call-stack is RW-.
GLIBC has a function to obtain a backtrace at a current point
in time. This is called in the context of the thread that invokes
the call. It requires access to the call records on the stack
in the context of the thread (the glicb functions are backtrace(3)
and backtrace_symbols(3)).
When Thread is unExceptional it cannot access Call Stack,
when Thread is Exceptional it can.
ENTER, EXIT, and RET are exempt from the protection check.
Call Stack Pointer is not accessible to unprivileged code.
Don't see how one gets from a running application into debugger without taking an exception !?! or from running in the debugger to running in application without returning from an exception !!!
Usual downside it that the excessive parenthesis tend to turn into a usability issue.
BGB <cr88192@gmail.com> posted:
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only
optimize based on what can be verified by the compiler within certain
fundamental assumptions.
Say:
Pointer 1 points at a stack array in the local function;
Pointer 2 was derived from taking the address of a global array;
Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume they
don't alias with a pointer to a local array;
C requires the compiler to prove that the pointers cannot alias.
Fortran specifies that if the 2 argument alias, it is a programming error.
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
On 6/23/2026 9:25 PM, John Levine wrote:
According to BGB-a <cr88192@gmail.com>:
C requires the compiler to prove that the pointers cannot alias.Hard proof that alias is impossible is harder to achieve in practice...
Fortran specifies that if the 2 argument alias, it is a programming
error.
A softer "there is no reasonable possibility of alias" is easier to
achieve.
Sort of.-a The standard says that the compiler can assume no type
punning, so that
if pointers are of different types, they can't point at the same thing
(with an
exception for pointers to unions.)
Even so, C has "restrict" to tell the compiler to assume that pointers
never
alias, and "volatile" to assume they always do.
Possibly, though traditional type-based aliasing rules run into a
problem in that pointer casting can break its assumptions, and a lot of
code doesn't respect these rules (which taken purely at face value, are overly limiting).
One option though is "if enabled, assume the rules are followed unless
the compiler sees them being broken", in which case it disables TBAA
when faced with TBAA violations.
This approach seems to be moderately
effective, and allows benefiting from some of the performance advantages
of TBAA while also being more friendly to code that goes "wild west"
with things like pointer casts and "cast and dereference" patterns.
So, say, a nicer compromise (even if still breakable).
-a int foo1(char *s, int *t)
-a {
-a-a-a *s=*t+1;
-a-a-a return *t;
-a }
-a //assume not directly visible within same context:
-a int foo2()
-a {
-a-a-a int i, j;
-a-a-a i=4;
-a-a-a j=foo1((char *)(&i), &i);
-a-a-a return j;
-a }
What is the result of calling foo2?...
-a Here, foo2 breaks TBAA but in a way invisible to foo1.
For volatile, one typically needs to go a little further:
-a Every load and store needs to be performed explicitly;
-a There is a need to disallow load/store reordering;
-a ...
Mostly because volatile may be used to access MMIO, and MMIO is more
strict than normal RAM in this area.
Though, could maybe be better if "volatile" could be broken into several subtypes depending on which particular behaviors are needed:
-a Weaker case: Assume aliasing happens.
-a-a-a May still prune non-aliasing load/store or reorder;
-a Normal case:
-a-a-a Every load/store needs to happen;
-a-a-a No reordering allowed.
-a Stronger case:
-a-a-a Like the above, but also needs to be synchronous between cores;
-a-a-a Though, this role overlaps with _Atomic.
There is also ambiguity as to how far the volatile-ness extends, but
this can be avoided by doing it at the point of cast-and-deref:
-a (*(volatile uint64_t *)ptr)
In this case, it applying explicitly to the deref operation rather than
the handling of the pointer before this point.
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
scott@slp53.sl.home (Scott Lurndal) posted:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
Thomas Koenig <tkoenig@netcologne.de> posted:
MitchAlsup <user5857@newsgrouper.org.invalid> schrieb:The debugger runs in a separate process with access to application
BGB <cr88192@gmail.com> posted:
On 6/20/2026 5:01 PM, MitchAlsup wrote:---------------
Tagging to make it harder to stomp the link register;
Put it somewhere it can't be stomped on !! like in memory on a page the
application has no access permissions.
Multiple stacks is a big ask, and non-accessible memory is not so good
when dealing with an ISA where user code needs to handle the Link-Register.
Code does not need to access or look at the return address in My 66000 >> >> > ISA--except for the case where one wants to walk the stack back on a
THROW() and its unstructured equivalent longjump().
What about a debugging stack trace?
Root pointer and ASID. In that process, Call-stack is RW-.
GLIBC has a function to obtain a backtrace at a current point
in time. This is called in the context of the thread that invokes
the call. It requires access to the call records on the stack
in the context of the thread (the glicb functions are backtrace(3)
and backtrace_symbols(3)).
When Thread is unExceptional it cannot access Call Stack,
when Thread is Exceptional it can.
ENTER, EXIT, and RET are exempt from the protection check.
Call Stack Pointer is not accessible to unprivileged code.
Don't see how one gets from a running application into debugger without >taking an exception !?! or from running in the debugger to running in >application without returning from an exception !!!
On Sat, 20 Jun 2026 10:15:41 -0400, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
Robert Swindells [2026-06-19 11:20:10] wrote:
On Fri, 19 Jun 2026 06:02:16 GMT, Anton Ertl wrote:[...]
Another architectural feature: One might think that tagging support
would help dynamically typed programming languages (e.g., Lisp), and
SPARC contains some support for that, but as one of the IIRC Franz
Lisp developers has explained in this newsgroup, they actually did
not use this feature, because the performance benefit was not big
enough to
Franz Lisp doesn't use tags at all and only ran on VAX and 68k.
I guess you two aren't talking bout the same "Franz Lisp". AFAIK Anton
is referring to the commercial Common Lisp compiler associated with the >>Franz Inc company, marketed under the name "Allegro".
=== Stefan
ISTM there were at least a couple of Lisps available for the Vax. I
can't speak to Franz, but I do know at least one Vax Lisp was a BIBOP[1] system that (generally) did not use tags.
In BIBOP, memory "pages"[2] are dedicated to a single data type. The
base address of the page is mapped to the type of the objects the page contains, and so the objects (and pointers to them) need no type
information themselves. This allowed for full width pointers, fixnums
and floats, and for conses, boxes, and other fixed sized data types (including user types) to avoid tagging.
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in
the C standard are ideal ...
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
On 6/24/2026 3:17 PM, John Levine wrote:-------------------
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
This one is why I added a "_memlzcpy()" function to my C library, whose
main purpose is to give this sort of self-overlapping copy behavior (and
to consolidate nearly every LZ77 style decompressor otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()", but as noted the behavior in the case of a short forwards copy are different.
For non-overlap cases it can just invoke "memcpy()".
BGB <cr88192@gmail.com> schrieb:
Usual downside it that the excessive parenthesis tend to turn into a usability issue.Ample fun has been made of this over time.
From: jasmerb@mist.cs.orst.edu (Bryce Jasmer)
Newsgroups: rec.humor.funny
Subject: The Strategic Defense Initiative (SDI/Star Wars)
Keywords: computer, funny
Message-ID: <137457@looking.on.ca>
Date: 23 Apr 90 10:30:08 GMT
Sender: funnyr@looking.on.ca
Posted: Mon Apr 23 11:30:08 1990
Reply-Path: mist.cs.orst.edu!jasmerb
Through some clever security hole manipulation if I have been able to
break into all of the government's computers and acquire the Lisp code
to SDI. Here is the last page (tail -10) of it to prove that I actually
have the code:
)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) ))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
On 6/24/2026 3:17 PM, John Levine wrote:
According to David Brown-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish.-a Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address.-a One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined.-a It is debatable as to whether the rules in >>> the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write
code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
-a-a-a-achar a[100];
-a-a-a-aa[0] = 42;
-a-a-a-amemcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't.-a This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
This one is why I added a "_memlzcpy()" function to my C library, whose
main purpose is to give this sort of self-overlapping copy behavior (and
to consolidate nearly every LZ77 style decompressor otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()", but as noted the behavior in the case of a short forwards copy are different.
For non-overlap cases it can just invoke "memcpy()".
On 24/06/2026 23:34, BGB wrote:
On 6/24/2026 3:17 PM, John Levine wrote:"memmove" will not fill the array above with 42.-a "memmove" acts as
According to David Brown-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish.-a Actually, by default gcc assumes (i.e., it does not prove) >>>>> that pointers to different types (except char) do not point to the
same address.-a One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined.-a It is debatable as to whether the
rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write
code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
-a-a-a-achar a[100];
-a-a-a-aa[0] = 42;
-a-a-a-amemcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't.-a This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
This one is why I added a "_memlzcpy()" function to my C library,
whose main purpose is to give this sort of self-overlapping copy
behavior (and to consolidate nearly every LZ77 style decompressor
otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()", but
as noted the behavior in the case of a short forwards copy are different.
For non-overlap cases it can just invoke "memcpy()".
though it copies the source to a temporary buffer, then copies that temporary buffer to the destination.-a (If you want to fill the buffer
with the value 42, "memset" is the function to use.)
How is your "_memlzcpy" defined that is different from that?Here:
On Mon, 22 Jun 2026 18:49:40 -0400, George Neuner wrote:
On Sat, 20 Jun 2026 10:15:41 -0400, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
Robert Swindells [2026-06-19 11:20:10] wrote:
On Fri, 19 Jun 2026 06:02:16 GMT, Anton Ertl wrote:[...]
Another architectural feature: One might think that tagging support
would help dynamically typed programming languages (e.g., Lisp), and >>>>> SPARC contains some support for that, but as one of the IIRC Franz
Lisp developers has explained in this newsgroup, they actually did
not use this feature, because the performance benefit was not big
enough to
Franz Lisp doesn't use tags at all and only ran on VAX and 68k.
I guess you two aren't talking bout the same "Franz Lisp". AFAIK Anton
is referring to the commercial Common Lisp compiler associated with the >>>Franz Inc company, marketed under the name "Allegro".
=== Stefan
ISTM there were at least a couple of Lisps available for the Vax. I
can't speak to Franz, but I do know at least one Vax Lisp was a BIBOP[1]
system that (generally) did not use tags.
Franz Lisp used BiBOP.
On 6/25/2026 2:22 AM, David Brown wrote:
On 24/06/2026 23:34, BGB wrote:
On 6/24/2026 3:17 PM, John Levine wrote:"memmove" will not fill the array above with 42.|e-a "memmove" acts as
According to David Brown|e-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish.|e-a Actually, by default gcc assumes (i.e., it does not prove) >>>>>> that pointers to different types (except char) do not point to the>>>>>> same address.|e-a One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined.|e-a It is debatable as to whether the
rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write
code that
is intuitively reasonable and sometimes works but isn't portable, e.g.: >>>>
|e-a|e-a|e-a|e-achar a[100];
|e-a|e-a|e-a|e-aa[0] = 42;
|e-a|e-a|e-a|e-amemcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that>>>> moves larger blocks won't.|e-a This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
This one is why I added a "_memlzcpy()" function to my C library,
whose main purpose is to give this sort of self-overlapping copy
behavior (and to consolidate nearly every LZ77 style decompressor
otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()", but >>> as noted the behavior in the case of a short forwards copy are
different.
For non-overlap cases it can just invoke "memcpy()".
though it copies the source to a temporary buffer, then copies that
temporary buffer to the destination.|e-a (If you want to fill the buffer
with the value 42, "memset" is the function to use.)
Yeah, this is why I created "_memlzcpy()", because the defined behavior
for "memmove()" is not what one wants for self-overlapping forward copy.
How is your "_memlzcpy" defined that is different from that?Here:
-a _memlzcpy(dst+1, dst, len);
Is functionally equivalent to:
-a memset(dst+1, *dst, len);
But, it can do more:
-a _memlzcpy(dst+2, dst, len);-a //repeating 2-byte pattern
-a _memlzcpy(dst+3, dst, len);-a //repeating 3-byte pattern
-a ...
So, required to work for every self-overlap distance.
Or, in the case as commonly used in an LZ77 style decompressor:
-a _memlzcpy(dest, dest-distance, length);
Though, there are also:I'm guessing you really meant up to 31 bytes extra?
-a _memcpyf()
-a _memmovef()
-a _memlzcpyf()
Where the 'f' in this case means:
Allowed to be a little faster by potentially going up to 32 bytes extra.
Robert Swindells [2026-06-24 14:38:02] wrote:
On Mon, 22 Jun 2026 18:49:40 -0400, George Neuner wrote:
On Sat, 20 Jun 2026 10:15:41 -0400, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
Robert Swindells [2026-06-19 11:20:10] wrote:
On Fri, 19 Jun 2026 06:02:16 GMT, Anton Ertl wrote:[...]
Another architectural feature: One might think that tagging support >>>>>> would help dynamically typed programming languages (e.g., Lisp),
and SPARC contains some support for that, but as one of the IIRC
Franz Lisp developers has explained in this newsgroup, they
actually did not use this feature, because the performance benefit >>>>>> was not big enough to
Franz Lisp doesn't use tags at all and only ran on VAX and 68k.
I guess you two aren't talking bout the same "Franz Lisp". AFAIK Anton >>>>is referring to the commercial Common Lisp compiler associated with
the Franz Inc company, marketed under the name "Allegro".
=== Stefan
ISTM there were at least a couple of Lisps available for the Vax. I
can't speak to Franz, but I do know at least one Vax Lisp was a
BIBOP[1]
system that (generally) did not use tags.
Franz Lisp used BiBOP.
Side note: the BiBoP technique is largely orthogonal to the
architectural support for pointer tagging, because usually BiBoP is used
to "eliminate" the tags present inside the heap representation of
objects rather than the few tagbits stolen from pointers: the purpose of those tagbits is usually to be able to determine the type of the object *without* any memory access whereas BiBoP stores the corresponding info
in memory.
E.g. tagbits are most commonly used to distinguish between an immediate
small integer value and a pointer. BiBoP wouldn't help with that,
forcing the small integer to be stored in some "page of small integers"
which could have a very serious performance impact.
=== Stefan
BGB wrote:
On 6/25/2026 2:22 AM, David Brown wrote:
On 24/06/2026 23:34, BGB wrote:
On 6/24/2026 3:17 PM, John Levine wrote:"memmove" will not fill the array above with 42.|e-a "memmove" acts as though it copies the source to a temporary buffer, then copies that temporary buffer to the destination.|e-a (If you want to fill the buffer with the value 42, "memset" is the function to use.)
According to David Brown|e-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias. >>>>>>>I wish.|e-a Actually, by default gcc assumes (i.e., it does not prove) >>>>>>> that pointers to different types (except char) do not point to the >>>>>>> same address.|e-a One has to turn that off with -fno-strict-aliasing. >>>>>>> Other C compilers use the same assumption.
That's the way C is defined.|e-a It is debatable as to whether the rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.: >>>>>
|e-a|e-a|e-a|e-achar a[100];
|e-a|e-a|e-a|e-aa[0] = 42;
|e-a|e-a|e-a|e-amemcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that >>>>> moves larger blocks won't.|e-a This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
This one is why I added a "_memlzcpy()" function to my C library, whose main purpose is to give this sort of self-overlapping copy behavior (and to consolidate nearly every LZ77 style decompressor otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()", but as noted the behavior in the case of a short forwards copy are different.
For non-overlap cases it can just invoke "memcpy()".
Yeah, this is why I created "_memlzcpy()", because the defined behavior for "memmove()" is not what one wants for self-overlapping forward copy.
How is your "_memlzcpy" defined that is different from that?Here:
-a-a _memlzcpy(dst+1, dst, len);
Is functionally equivalent to:
-a-a memset(dst+1, *dst, len);
But, it can do more:
-a-a _memlzcpy(dst+2, dst, len);-a //repeating 2-byte pattern
-a-a _memlzcpy(dst+3, dst, len);-a //repeating 3-byte pattern
-a-a ...
So, required to work for every self-overlap distance.
Or, in the case as commonly used in an LZ77 style decompressor:
-a-a _memlzcpy(dest, dest-distance, length);
Though, there are also:
-a-a _memcpyf()
-a-a _memmovef()
-a-a _memlzcpyf()
Where the 'f' in this case means:
Allowed to be a little faster by potentially going up to 32 bytes extra.
I'm guessing you really meant up to 31 bytes extra?
This is what my own (faster than Google's version) LZ4 decompressor uses internally.
I am using either a pair of SSE or a single AVX register (so 32 bytes in both cases) as the copy granule. For the specific,very common, case of an overlapping copy that unrolls RLL-encoded data, I start by loading the starting pattern into the bottom of a register, then use the pattern length to index into a table of swizzle patterns that will generate the required results, for any pattern up to 32 bytes long.
swizzle_table:
[0,0,0,0,0,0,0,...
[0,1,0,1,0,1,0,1,...
[0,1,2,0,1,2,0,1,2,...
[0,1,2,3,0,1,2,3,...
[0,1,2,3,4,0,1,2,3,..
etc.
Note that having 31 entries of 32 bytes each means that I'm allocating almost a KB of $L1 cache space just for this table, but when you're decompressing lots of data it pays off.
Terje
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in >>the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that >is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
"memmove" will not fill the array above with 42. "memmove" acts as
though it copies the source to a temporary buffer, then copies that temporary buffer to the destination. (If you want to fill the buffer
with the value 42, "memset" is the function to use.)
On 2026-Jun-25 08:39, Terje Mathisen wrote:We do have that, in the form of a masked move, but it is more efficient
BGB wrote:
On 6/25/2026 2:22 AM, David Brown wrote:
On 24/06/2026 23:34, BGB wrote:
On 6/24/2026 3:17 PM, John Levine wrote:"memmove" will not fill the array above with 42.|arCU|e-a "memmove" acts >>>> as though it copies the source to a temporary buffer, then copies
According to David Brown|arCU|e-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias. >>>>>>>>I wish.|arCU|e-a Actually, by default gcc assumes (i.e., it does not >>>>>>>> prove)
that pointers to different types (except char) do not point to the >>>>>>>> same address.|arCU|e-a One has to turn that off with
-fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined.|arCU|e-a It is debatable as to whether >>>>>>> the rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to
write code that
is intuitively reasonable and sometimes works but isn't portable, >>>>>> e.g.:
|arCU|e-a|arCU|e-a|arCU|e-a|arCU|e-achar a[100];
|arCU|e-a|arCU|e-a|arCU|e-a|arCU|e-aa[0] = 42;
|arCU|e-a|arCU|e-a|arCU|e-a|arCU|e-amemcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that >>>>>> moves larger blocks won't.|arCU|e-a This example is really obvious (it's >>>>>> why there's also memmove()) but there's plenty of more subtle ones. >>>>>>
This one is why I added a "_memlzcpy()" function to my C library,
whose main purpose is to give this sort of self-overlapping copy
behavior (and to consolidate nearly every LZ77 style decompressor
otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()",
but as noted the behavior in the case of a short forwards copy are >>>>> different.
For non-overlap cases it can just invoke "memcpy()".
that temporary buffer to the destination.|arCU|e-a (If you want to fill >>>> the buffer with the value 42, "memset" is the function to use.)
Yeah, this is why I created "_memlzcpy()", because the defined
behavior for "memmove()" is not what one wants for self-overlapping
forward copy.
How is your "_memlzcpy" defined that is different from that?Here:
|e-a|e-a _memlzcpy(dst+1, dst, len);
Is functionally equivalent to:
|e-a|e-a memset(dst+1, *dst, len);
But, it can do more:
|e-a|e-a _memlzcpy(dst+2, dst, len);|e-a //repeating 2-byte pattern
|e-a|e-a _memlzcpy(dst+3, dst, len);|e-a //repeating 3-byte pattern
|e-a|e-a ...
So, required to work for every self-overlap distance.
Or, in the case as commonly used in an LZ77 style decompressor:
|e-a|e-a _memlzcpy(dest, dest-distance, length);
Though, there are also:
|e-a|e-a _memcpyf()
|e-a|e-a _memmovef()
|e-a|e-a _memlzcpyf()
Where the 'f' in this case means:
Allowed to be a little faster by potentially going up to 32 bytes extra.
I'm guessing you really meant up to 31 bytes extra?
This is what my own (faster than Google's version) LZ4 decompressor
uses internally.
I am using either a pair of SSE or a single AVX register (so 32 bytes >> in both cases) as the copy granule. For the specific,very common, case
of an overlapping copy that unrolls RLL-encoded data, I start by
loading the starting pattern into the bottom of a register, then use
the pattern length to index into a table of swizzle patterns that will
generate the required results, for any pattern up to 32 bytes long.
swizzle_table:
[0,0,0,0,0,0,0,...
[0,1,0,1,0,1,0,1,...
[0,1,2,0,1,2,0,1,2,...
[0,1,2,3,0,1,2,3,...
[0,1,2,3,4,0,1,2,3,..
etc.
Note that having 31 entries of 32 bytes each means that I'm allocating
almost a KB of $L1 cache space just for this table, but when you're
decompressing lots of data it pays off.
If I had 256b,32B registers I would like to have LDV Load Variable and > STV Store Variable
instructions, which take an address, a src/dst simd register, and either
a scalar register
or immediate byte count in the range 0..32. LDV loads the specified
number of bytes into
the simd starting at the least significant byte and zero-fills any
unread ones.
These should be relatively easy to implement if one already has
unaligned SIMD LD/ST.
One might also consider LDBV/STBV variable length bit vectors 0 to 256b,
Thomas Koenig <tkoenig@netcologne.de> writes:
BGB <cr88192@gmail.com> schrieb:
Usual downside it that the excessive parenthesis tend to turn into a usability issue.Ample fun has been made of this over time.
From rec.humor.funny:
From: jasmerb@mist.cs.orst.edu (Bryce Jasmer)
Newsgroups: rec.humor.funny
Subject: The Strategic Defense Initiative (SDI/Star Wars)
Keywords: computer, funny
Message-ID: <137457@looking.on.ca>
Date: 23 Apr 90 10:30:08 GMT
Sender: funnyr@looking.on.ca
Posted: Mon Apr 23 11:30:08 1990
Reply-Path: mist.cs.orst.edu!jasmerb
Through some clever security hole manipulation if I have been able to
break into all of the government's computers and acquire the Lisp code
to SDI. Here is the last page (tail -10) of it to prove that I actually have the code:
)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))) ))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
Andy Valencia--- Synchronet 3.22a-Linux NewsLink 1.2
Home page: https://www.vsta.org/andy/
To contact me: https://www.vsta.org/contact/andy.html
No AI was used in the composition of this message
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in >the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
On 24/06/2026 23:34, BGB wrote:---------------------
"memmove" will not fill the array above with 42. "memmove" acts as
though it copies the source to a temporary buffer, then copies that temporary buffer to the destination. (If you want to fill the buffer
with the value 42, "memset" is the function to use.)
How is your "_memlzcpy" defined that is different from that?
David Brown <david.brown@hesbynett.no> posted:
On 24/06/2026 23:34, BGB wrote:---------------------
"memmove" will not fill the array above with 42. "memmove" acts as
though it copies the source to a temporary buffer, then copies that
temporary buffer to the destination. (If you want to fill the buffer
with the value 42, "memset" is the function to use.)
Act as though it copies twice is utterly unnecessary as overlapping
memory can simply be performed back-to-front instead of front-to-back.
How is your "_memlzcpy" defined that is different from that?
John Levine <johnl@taugh.com> posted:
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in >> >the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
Why not::
memset( a, 42, 100 );
BGB wrote:
On 6/25/2026 2:22 AM, David Brown wrote:
On 24/06/2026 23:34, BGB wrote:
On 6/24/2026 3:17 PM, John Levine wrote:"memmove" will not fill the array above with 42.|e-a "memmove" acts as
According to David Brown|e-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias. >>>>>>>I wish.|e-a Actually, by default gcc assumes (i.e., it does not prove) >>>>>>> that pointers to different types (except char) do not point to the >>>>>>> same address.|e-a One has to turn that off with -fno-strict-aliasing. >>>>>>> Other C compilers use the same assumption.
That's the way C is defined.|e-a It is debatable as to whether the >>>>>> rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to
write code that
is intuitively reasonable and sometimes works but isn't portable,
e.g.:
|e-a|e-a|e-a|e-achar a[100];
|e-a|e-a|e-a|e-aa[0] = 42;
|e-a|e-a|e-a|e-amemcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that >>>>> moves larger blocks won't.|e-a This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
This one is why I added a "_memlzcpy()" function to my C library,
whose main purpose is to give this sort of self-overlapping copy
behavior (and to consolidate nearly every LZ77 style decompressor
otherwise needing to supply their own version).
In the case of a short backwards copy, it will call "memmove()", but
as noted the behavior in the case of a short forwards copy are
different.
For non-overlap cases it can just invoke "memcpy()".
though it copies the source to a temporary buffer, then copies that
temporary buffer to the destination.|e-a (If you want to fill the
buffer with the value 42, "memset" is the function to use.)
Yeah, this is why I created "_memlzcpy()", because the defined
behavior for "memmove()" is not what one wants for self-overlapping
forward copy.
How is your "_memlzcpy" defined that is different from that?Here:
-a-a _memlzcpy(dst+1, dst, len);
Is functionally equivalent to:
-a-a memset(dst+1, *dst, len);
But, it can do more:
-a-a _memlzcpy(dst+2, dst, len);-a //repeating 2-byte pattern
-a-a _memlzcpy(dst+3, dst, len);-a //repeating 3-byte pattern
-a-a ...
So, required to work for every self-overlap distance.
Or, in the case as commonly used in an LZ77 style decompressor:
-a-a _memlzcpy(dest, dest-distance, length);
Though, there are also:
-a-a _memcpyf()
-a-a _memmovef()
-a-a _memlzcpyf()
Where the 'f' in this case means:
Allowed to be a little faster by potentially going up to 32 bytes extra.
I'm guessing you really meant up to 31 bytes extra?
This is what my own (faster than Google's version) LZ4 decompressor uses internally.
I am using either a pair of SSE or a single AVX register (so 32 bytes in both cases) as the copy granule. For the specific,very common, case of
an overlapping copy that unrolls RLL-encoded data, I start by loading
the starting pattern into the bottom of a register, then use the pattern length to index into a table of swizzle patterns that will generate the required results, for any pattern up to 32 bytes long.
swizzle_table:
[0,0,0,0,0,0,0,...
[0,1,0,1,0,1,0,1,...
[0,1,2,0,1,2,0,1,2,...
[0,1,2,3,0,1,2,3,...
[0,1,2,3,4,0,1,2,3,..
etc.
Note that having 31 entries of 32 bytes each means that I'm allocating almost a KB of $L1 cache space just for this table, but when you're decompressing lots of data it pays off.
David Brown <david.brown@hesbynett.no> posted:
On 24/06/2026 23:34, BGB wrote:---------------------
"memmove" will not fill the array above with 42. "memmove" acts as
though it copies the source to a temporary buffer, then copies that
temporary buffer to the destination. (If you want to fill the buffer
with the value 42, "memset" is the function to use.)
Act as though it copies twice is utterly unnecessary as overlapping
memory can simply be performed back-to-front instead of front-to-back.
How is your "_memlzcpy" defined that is different from that?
Andy Valencia <vandys@vsta.org> posted:
Thomas Koenig <tkoenig@netcologne.de> writes:
BGB <cr88192@gmail.com> schrieb:
Usual downside it that the excessive parenthesis tend to turn into aAmple fun has been made of this over time.
usability issue.
From rec.humor.funny:
From: jasmerb@mist.cs.orst.edu (Bryce Jasmer)
Newsgroups: rec.humor.funny
Subject: The Strategic Defense Initiative (SDI/Star Wars)
Keywords: computer, funny
Message-ID: <137457@looking.on.ca>
Date: 23 Apr 90 10:30:08 GMT
Sender: funnyr@looking.on.ca
Posted: Mon Apr 23 11:30:08 1990
Reply-Path: mist.cs.orst.edu!jasmerb
Through some clever security hole manipulation if I have been able to
break into all of the government's computers and acquire the Lisp code
to SDI. Here is the last page (tail -10) of it to prove that I actually
have the code:
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
I remember the LISP on PDP-8. One could use the character ] to mean as many )s as needed to close the lambda.
The glibc function ::backtrace can be called at any time, in any context.
Then there are the unix context functions that also allow access to
resources not normally visible to an application - getcontext(2), makecontext(3) and the setjmp/sigsetjmp functions which also
gather the thread context, including the current stack pointer.
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
/**
* Log a simulator stack traceback.
*/
void
c_osdep::backtrace(c_logger *lp)
{
int num_frames;
void *framelist[100];
char **strings;
num_frames = ::backtrace(framelist, sizeof(framelist)/sizeof(framelist[0]));
strings = ::backtrace_symbols(framelist, num_frames);
if (strings == NULL) {
lp->log("Unable to obtain simulator stack traceback: %s\n",
strerror(errno));
return;
}
for(int frame=0; frame < num_frames; frame++) {
lp->log("[%2.2d] %s\n", frame, strings[frame]);
}
::free(strings);
}
"Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
On 6/19/2026 11:59 AM, John Levine wrote:
According to David Brown <david.brown@hesbynett.no>:
Possibly the biggest millstone around the neck of computing
architectures is the C language. ...
De-facto standards are /always/ albatrosses to some extent. Things are >>>> done that way because things are done that way - processors are designed >>>> to run C (or C-model languages, if you like) because that's what
existing code is written in, and code is written in C (or similar
languages, or languages with a VM written in C) because that's how
existing processors work.
C killed off every memory model other than flat byte addressed memory.
Pointers are sort of typed, but any real C program does stuff like this: >>>
p = (struct foo *) malloc(42 * sizeof(struct foo));
Fwiw, why all of the casts?
C and C++ handle void* conversions differently. You must cast
the malloc result to a pointer of the declared type when using C++.
It doesn't hurt to add the cast in C, and may help with documenting
the intention of the programmer who wrote the code.
GLIBC has a function to obtain a backtrace at a current point
in time. This is called in the context of the thread that invokes
the call. It requires access to the call records on the stack
in the context of the thread (the glicb functions are backtrace(3)
and backtrace_symbols(3)).
/**
* Log a simulator stack traceback.
*/
void
c_osdep::backtrace(c_logger *lp)
scott@slp53.sl.home (Scott Lurndal) posted:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
/**
* Log a simulator stack traceback.
*/
void
c_osdep::backtrace(c_logger *lp)
{
int num_frames;
void *framelist[100];
char **strings;
num_frames = ::backtrace(framelist, sizeof(framelist)/sizeof(framelist[0]));
Where does ::backtrace get access to the number of preserved registers
on the stack and where the return address is on a per subroutine basis ??
That is: each stack frame is of a different size with return address at a different spot per subroutine.
BGB <cr88192@gmail.com> posted:
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only
optimize based on what can be verified by the compiler within certain
fundamental assumptions.
Say:
Pointer 1 points at a stack array in the local function;
Pointer 2 was derived from taking the address of a global array;
Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume they
don't alias with a pointer to a local array;
C requires the compiler to prove that the pointers cannot alias.
Fortran specifies that if the 2 argument alias, it is a programming error.
-----------------
I am reminded of the person, apparently very religious, who some decades >>> ago posted to solicit help for reimplementing all of computing (gcc,
GNU, et cetera) on Biblical principles, because he thought Richard
Stallman was too atheistic and had tainted his products. I have not
heard how that went.
Rick...
--------
But if you know that you have a "page of small integers" then you can just
do address comparisons between them, the Franz Lisp compiler did this.
According to MitchAlsup <user5857@newsgrouper.org.invalid>:
John Levine <johnl@taugh.com> posted:
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
Why not::
memset( a, 42, 100 );
Jeez, it's an example.
John Levine [2026-06-25 19:19:47] wrote:
According to MitchAlsup <user5857@newsgrouper.org.invalid>:
John Levine <johnl@taugh.com> posted:
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.: >>>>
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
Why not::
memset( a, 42, 100 );
Jeez, it's an example.
It's an example, indeed, but it's a pretty bad one since using `memset`
is more clear, more concise, and actually works, whereas your example
seems very contrived.
John Levine <johnl@taugh.com> posted:
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in >>> the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
Why not::
memset( a, 42, 100 );
MitchAlsup wrote:
John Levine <johnl@taugh.com> posted:
According to David Brown-a <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish.-a Actually, by default gcc assumes (i.e., it does not prove) >>>>> that pointers to different types (except char) do not point to the
same address.-a One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined.-a It is debatable as to whether the
rules in
the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write
code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
-a-a-a-achar a[100];
-a-a-a-aa[0] = 42;
-a-a-a-amemcpy(a+1, a, 99);
Why not::
-a-a-a-a-a-a-a memset( a, 42, 100 );
In the case of a single repeating byte, memset is of course optimal, but
the same LZ4 encoding is used to encode any repeating pattern, of
lengths from 1 and up. There is no indexed memset where the pattern is
of arbitrary length.
On 6/23/2026 5:54 PM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only
optimize based on what can be verified by the compiler within certain
fundamental assumptions.
Say:
-a-a-a Pointer 1 points at a stack array in the local function;
-a-a-a Pointer 2 was derived from taking the address of a global array;
-a-a-a Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume they
don't alias with a pointer to a local array;
C requires the compiler to prove that the pointers cannot alias.
Fortran specifies that if the 2 argument alias, it is a programming error.
sorry of if this is way off base, but well...
What about container_of, or CONTAINING_RECORD?
scott@slp53.sl.home (Scott Lurndal) posted:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
/**
* Log a simulator stack traceback.
*/
void
c_osdep::backtrace(c_logger *lp)
{
int num_frames;
void *framelist[100];
char **strings;
num_frames = ::backtrace(framelist, sizeof(framelist)/sizeof(framelist[0]));
Where does ::backtrace get access to the number of preserved registers
on the stack and where the return address is on a per subroutine basis ??
Scott Lurndal <scott@slp53.sl.home> schrieb:
GLIBC has a function to obtain a backtrace at a current point
in time. This is called in the context of the thread that invokes
the call. It requires access to the call records on the stack
in the context of the thread (the glicb functions are backtrace(3)
and backtrace_symbols(3)).
/**
* Log a simulator stack traceback.
*/
void
c_osdep::backtrace(c_logger *lp)
Nit: That is not glibc code, glibc code is C (it would be strange to
have a C++ runtime library for C...)
it is certainly the case that people
have used memcpy() with overlapping regions and an assumption that it
copies forward in some way.
David Brown <david.brown@hesbynett.no> writes:
it is certainly the case that people
have used memcpy() with overlapping regions and an assumption that it
copies forward in some way.
More precisely, in 2010 there was a big flamewar because a newer glibc
used backwards stride on some processors for some combinations of
source and destination addresses, and this broke a pre-existing binary
(of a Flash player IIRC).
John Levine <johnl@taugh.com> posted:
According to David Brown <david.brown@hesbynett.no>:
On 24/06/2026 07:48, Anton Ertl wrote:
MitchAlsup <user5857@newsgrouper.org.invalid> writes:
C requires the compiler to prove that the pointers cannot alias.
I wish. Actually, by default gcc assumes (i.e., it does not prove)
that pointers to different types (except char) do not point to the
same address. One has to turn that off with -fno-strict-aliasing.
Other C compilers use the same assumption.
That's the way C is defined. It is debatable as to whether the rules in >>> the C standard are ideal ...
One of the less fortunate things about C is that it is easy to write code that
is intuitively reasonable and sometimes works but isn't portable, e.g.:
char a[100];
a[0] = 42;
memcpy(a+1, a, 99);
Why not::
memset( a, 42, 100 );
?????
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
On 2026-Jun-26 06:24, Chris M. Thomasson wrote:
On 6/23/2026 5:54 PM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only >>>> optimize based on what can be verified by the compiler within certain
fundamental assumptions.
Say:
-a-a-a Pointer 1 points at a stack array in the local function;
-a-a-a Pointer 2 was derived from taking the address of a global array; >>>> -a-a-a Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume they >>>> don't alias with a pointer to a local array;
C requires the compiler to prove that the pointers cannot alias.
Fortran specifies that if the 2 argument alias, it is a programming
error.
sorry of if this is way off base, but well...
What about container_of, or CONTAINING_RECORD?
If that is what I think it is, where it cast from
a pointer to a field inside a struct back to the containing struct
by subtracting the field byte offset and changing the pointer type, irrespective of programming language that mechanism has been used
by operating systems at least since RSX days.
It is a compact way of having structs linked to many other structures.
That macro is just a variant of the mechanism for C.
The method is used by WinNT and Linux, and I believe also by the BSD's.
GCC has a compile option, no_strict_alias or something, that anyone
using it and doing "illegal" pointer casting must use.
In Windows land, pointer casting at least used to be Microsoft's
recommended method and is supported by their compiler because
they use it too, extensively.
I have used it when I had complex multiple linkages between data
structures.
Say an object is in multiple double linked lists and an index tree and I
need to cast from a pointer to a list link field back to the object containing that link field. I also often put a validity check marker for
each object type at the start of the container and Assert its correctness. The marker is zeroed when the container is destroyed to catch
any dangling references.
On 6/26/2026 7:11 AM, EricP wrote:
On 2026-Jun-26 06:24, Chris M. Thomasson wrote:
On 6/23/2026 5:54 PM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 6/22/2026 7:38 AM, Niklas Holsti wrote:-------------
On 2026-06-22 13:44, Thomas Koenig wrote:
Niklas Holsti <niklas.holsti@tidorum.invalid> schrieb:
On 2026-06-21 22:15, David Brown wrote:
On 21/06/2026 20:57, MitchAlsup wrote:
In my case, I tended to use more conservative approaches and then only >>>>> optimize based on what can be verified by the compiler within certain >>>>> fundamental assumptions.
Say:
-a-a-a Pointer 1 points at a stack array in the local function;
-a-a-a Pointer 2 was derived from taking the address of a global array; >>>>> -a-a-a Compiler can safely assume no-alias.
Also, if two pointers were passed into a function, can also assume
they
don't alias with a pointer to a local array;
C requires the compiler to prove that the pointers cannot alias.
Fortran specifies that if the 2 argument alias, it is a programming
error.
sorry of if this is way off base, but well...
What about container_of, or CONTAINING_RECORD?
If that is what I think it is, where it cast from
a pointer to a field inside a struct back to the containing struct
by subtracting the field byte offset and changing the pointer type,
irrespective of programming language that mechanism has been used
by operating systems at least since RSX days.
It is a compact way of having structs linked to many other structures.
That macro is just a variant of the mechanism for C.
The method is used by WinNT and Linux, and I believe also by the BSD's.
GCC has a compile option, no_strict_alias or something, that anyone
using it and doing "illegal" pointer casting must use.
In Windows land, pointer casting at least used to be Microsoft's
recommended method and is supported by their compiler because
they use it too, extensively.
I have used it when I had complex multiple linkages between data
structures.
Say an object is in multiple double linked lists and an index tree and I
need to cast from a pointer to a list link field back to the object
containing that link field. I also often put a validity check marker for
each object type at the start of the container and Assert its
correctness.
The marker is zeroed when the container is destroyed to catch
any dangling references.
Yup. You got it and basically had to use it the same way I have in the
past. Its really cool. Also, check this shit out:
#define RALLOC_ALIGN_OF(mp_type) \
-a offsetof( \
-a-a-a struct { \
-a-a-a-a-a char pad_RALLOC_ALIGN_OF; \
-a-a-a-a-a mp_type type_RALLOC_ALIGN_OF; \
-a-a-a }, \
-a-a-a type_RALLOC_ALIGN_OF \
-a )
;^D
a[0] = 42;
memcpy(a+1, a, 99);
A naive byte copy will fill a[] with 42, a more typical version that
moves larger blocks won't. This example is really obvious (it's
why there's also memmove()) but there's plenty of more subtle ones.
The burroughs B3500 and medium systems successors, which is a >memory-to-memory architecture had a number of move instructions,
several of which had architecturally defined semantics for
overlapping source and destination fields, which included
functionality similar to that you describe above. ...
Chris M. Thomasson wrote:
On 6/19/2026 7:16 AM, Terje Mathisen wrote:I don't know, I'm just the FP emulation guy in the project. :-)
[...]
The Mill is probably the closest to Cheri that is still in active
development.
How close are you guys to making a Mill processor?
On 26/06/2026 15:08, Terje Mathisen wrote:
In the case of a single repeating byte, memset is of course optimal,
but the same LZ4 encoding is used to encode any repeating pattern, of >> lengths from 1 and up. There is no indexed memset where the pattern is
of arbitrary length.
I don't think memset is necessarily "optimal", because the optimal
solution will depend on the number of bytes to fill, and possibly alignments, and details of the exact processor.-a A particular memset implementation could be close to optimal for large blocks, where it is > worth picking the best algorithm at runtime.-a And a compiler could pick
the algorithm details at compile time if it knows the size of the target block.-a "Optimal" is a strong word.
I would think that the kind of copying you need for LZ4 is quite
specialised for that task - a function to do that belongs in LZ4 implementation code rather than as a standard function.-a Trying to use memcpy() for the task is, however, a recipe for having your name cursed
by future maintainers!
On 2026-Jun-26 12:15, Anton Ertl wrote:
David Brown <david.brown@hesbynett.no> writes:
it is certainly the case that people
have used memcpy() with overlapping regions and an assumption that it
copies forward in some way.
More precisely, in 2010 there was a big flamewar because a newer glibc
used backwards stride on some processors for some combinations of
source and destination addresses, and this broke a pre-existing binary
(of a Flash player IIRC).
Unbroken parts of Flash player existed?
David Brown <david.brown@hesbynett.no> writes:
it is certainly the case that people
have used memcpy() with overlapping regions and an assumption that it
copies forward in some way.
More precisely, in 2010 there was a big flamewar because a newer glibc
used backwards stride on some processors for some combinations of
source and destination addresses, and this broke a pre-existing binary
(of a Flash player IIRC). The "solution" was to use memmove for
memcpy for existing binaries, and use the processor-dependent memcpy
for new binaries. I heard no complaints about the solution for
existing binaries.
This shows that no binaries that link to glibc assumed that dest can
overlap source with dest>src, and get some kind of replicating
behaviour (probably because glibc stopped using byte-by-byte copying
much earlier, if it ever had it at all).
What the Flash player apparently used is operlapping memcpy with
dest<src. It worked like memmove before the glibc release that caused
the flame war, and actually used memmove once the solution was
implemented.
A better solution might have been to implement memcpy on the funny
processors as follows:
if (prefer_forward_stride(dest,src) || (((uintptr_t)src)-((uintptr_t)dest))<n )
return memcpy_forward_stride(dest, src, n);
else
return memcpy_backward_stride(dest, src, n);
This would have covered the Flash player usage (and any like it). Of
course, memmove is only slightly more expensive to implement (you also
have to cover the case where src<dest<src+n).
But this shows the recently discussed problem with shared libraries.
When they change things, programs may break, even if the change
is allowed according to the applicable standards and documentation.
EricP <ThatWouldBeTelling@thevillage.com> schrieb:
On 2026-Jun-26 12:15, Anton Ertl wrote:
David Brown <david.brown@hesbynett.no> writes:
it is certainly the case that people
have used memcpy() with overlapping regions and an assumption that it
copies forward in some way.
More precisely, in 2010 there was a big flamewar because a newer glibc
used backwards stride on some processors for some combinations of
source and destination addresses, and this broke a pre-existing binary
(of a Flash player IIRC).
Unbroken parts of Flash player existed?
Granted (maybe the first drafts which didn't do anyting yet, the sort of
int main()
{
return 0;
}
program, it didn't have any serious bugs yet, at least not in the functionality that was implemented up to that time. But remember
IEFBR14...)
But this shows the recently discussed problem with shared libraries.
When they change things, programs may break, even if the change
is allowed according to the applicable standards and documentation.
Thomas Koenig <tkoenig@netcologne.de> writes:
But this shows the recently discussed problem with shared libraries.
When they change things, programs may break, even if the change
is allowed according to the applicable standards and documentation.
Anyone who treats an incomplete specification as a license to change behaviour is probably in violation of Hyrum's law,
Anton Ertl <anton@mips.complang.tuwien.ac.at> schrieb:
Thomas Koenig <tkoenig@netcologne.de> writes:
But this shows the recently discussed problem with shared libraries.
When they change things, programs may break, even if the change
is allowed according to the applicable standards and documentation.
Anyone who treats an incomplete specification as a license to change
behaviour is probably in violation of Hyrum's law,
Not sure where you see the problem there. "Undefined behavior" in
the C standard is something that programmers must avoid, on penalty
of their programs doing weird thigns that they never expected.
UNLESS they stick to a certain version of library, compiler and
the rest of the tool chain and have tested this exhaustively.
Unfortunately, shared libraries make this impossible.
But I agree that Fortran's "shall" and "shall not" is clearer
and leads to less confusion.
It's never easy for implementers to determine when they should pay most attention to giving good results to those that use their functions correctly, and when they should help those that have used their
functions incorrectly avoid the consequences of their mistakes.
David Brown <david.brown@hesbynett.no> schrieb:
It's never easy for implementers to determine when they should pay most
attention to giving good results to those that use their functions
correctly, and when they should help those that have used their
functions incorrectly avoid the consequences of their mistakes.
I have a clear preference there, and I believe it is shared in
general by the gcc community.
First, correct code should not be penalized.
Second, the user should be given as much help as possible to find
incorrect code. Code that violates the respective standard, be
it undefined behavior in C or violation of a "shall" directive
that is not a constraint in Fortran, should be noted, in order
of preference, by
1. Compile-time checking
2. Low (factor 2-3) overhead checks for debugging runs (address
sanitizer etc)
3. High overhead checks (valgrind)
Third, dubious code that has a correct interpretation but is very
likely not what the user intended should be warned about.
A classic of the last case is Fortran's
real :: a
read (*,*) a
print *,a**(5/7)
end
which will print 1.0 as long as the input is finite.
program, it didn't have any serious bugs yet, at least not in the functionality that was implemented up to that time. But remember
IEFBR14...)
David Brown <david.brown@hesbynett.no> schrieb:
It's never easy for implementers to determine when they should pay most
attention to giving good results to those that use their functions
correctly, and when they should help those that have used their
functions incorrectly avoid the consequences of their mistakes.
I have a clear preference there, and I believe it is shared in
general by the gcc community.
First, correct code should not be penalized.
Second, the user should be given as much help as possible to find
incorrect code. Code that violates the respective standard, be
it undefined behavior in C or violation of a "shall" directive
that is not a constraint in Fortran, should be noted, in order
of preference, by
1. Compile-time checking
2. Low (factor 2-3) overhead checks for debugging runs (address
sanitizer etc)
3. High overhead checks (valgrind)
Third, dubious code that has a correct interpretation but is very
likely not what the user intended should be warned about.
A classic of the last case is Fortran's
real :: a
read (*,*) a
print *,a**(5/7)
end
which will print 1.0 as long as the input is finite.
S/390 added the confusing;y named MOVE LONG UNICODE which moves and pads pairs >of bytes. (That works OK for UTF-16, not any other Unicode encoding)
Copying strings is surprisingly complicated.
Thomas Koenig wrote:
Third, dubious code that has a correct interpretation but is very
likely not what the user intended should be warned about.
A classic of the last case is Fortran's
real :: a
read (*,*) a
print *,a**(5/7)
end
which will print 1.0 as long as the input is finite.
Integer division (5/7) will always be zero, so the power operation
returns one?
David Brown <david.brown@hesbynett.no> schrieb:
It's never easy for implementers to determine when they should pay most attention to giving good results to those that use their functions correctly, and when they should help those that have used their
functions incorrectly avoid the consequences of their mistakes.
I have a clear preference there, and I believe it is shared in
general by the gcc community.
First, correct code should not be penalized.
Second, the user should be given as much help as possible to find
incorrect code. Code that violates the respective standard, be
it undefined behavior in C or violation of a "shall" directive
that is not a constraint in Fortran, should be noted, in order
of preference, by
1. Compile-time checking
2. Low (factor 2-3) overhead checks for debugging runs (address
sanitizer etc)
3. High overhead checks (valgrind)
Third, dubious code that has a correct interpretation but is very
likely not what the user intended should be warned about.
A classic of the last case is Fortran's
real :: a
read (*,*) a
print *,a**(5/7)
end
which will print 1.0 as long as the input is finite.
Thomas Koenig wrote:
program, it didn't have any serious bugs yet, at least not in the functionality that was implemented up to that time. But remember IEFBR14...)
Funnily enough, the IEFBR14 bug was repeated a couple of decades later
in MSDOS when DUMMY.COM which simply returned to the OS without doing anything had the exact same issue:
The original DUMMY.COM was one byte long, containing just a RET opcode:
The 256-byte PSP which was loaded in front of all .COM programs intentionally contained CD 20h (INT 20h -> Terminate the running
program) as the first two bytes, with a zero word pushed onto the stack,
so that any program which used the CP/M convention that you could RET to
the OS would work.
Just like the original IEFBR14, this setup did not return a fixed
ERRORLEVEL which batch scripts could use to determine if an error had happened, so for the MSDOS version the single-byte program needed to be changed to something like
MOV AX,4700h
INT 21h
which would call the exit program OS function (AH=47h) with a return
code (AL) of zero.
Terje
PS. Why do I still remember the x86 hex codes for all of this almost 40 years after I last wrote 16-bit ASM code which needed it?
Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
Thomas Koenig wrote:
Third, dubious code that has a correct interpretation but is very
likely not what the user intended should be warned about.
A classic of the last case is Fortran's
real :: a
read (*,*) a
print *,a**(5/7)
end
which will print 1.0 as long as the input is finite.
Integer division (5/7) will always be zero, so the power operation
returns one?
Exactly.
It's subtle enough so gfortran (well, me) put in a warning:
$ gfortran -Wall exp.f90
exp.f90:3:16:
3 | print *,a**(5/7)
| 1
Warning: Integer division truncated to constant '0' at (1) [-Winteger-division]
Another trap I fell into in my student days was 10**n for values
of n which were in a loop with a range which had both positive
and negative values...
The REP MOVSB variants here are significantly slower than the
word-copying loop, because in the non-overlapping case they REP MOVSB
uses non-temporal stores, so the result is not in the near caches, so
the next copying operation has to load the result from the L3 cache
(judging by the ~160 cycles per additional CMOVE used) again.
Another, probably better approach is to fill a number of SIMD
registers with the pattern to be replicated, and then write that. I
have not measured this approach, but I expect that it's the fastest
one in many cases.
The bottom line is that a fast memmove is less complex to implement
than a REP MOVSB that is fast for all cases, even if the specification
of REP MOVSB looks simpler.
In order to handle the LZ4 style repeated copies of 1-n bytes, up to
length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to 16 or
32 bytes, then fills an internal cache line sized buffer with the >corresponding pattern, before doing a number of cache lines stores with
a final partial line.
Obviously doable at 1 or 2 cycles of startup overhead,
Terje Mathisen <terje.mathisen@tmsw.no> writes:
In order to handle the LZ4 style repeated copies of 1-n bytes, up to
length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to 16 or
32 bytes, then fills an internal cache line sized buffer with the
corresponding pattern, before doing a number of cache lines stores with
a final partial line.
You can use VPERMB to replicate the pattern in a ZMM register. With
just one ZMM register, you can put in patterns up to 64 bytes, and
store floor(64/n)*n bytes at a time. You would need a table of
indices (each 64 bytes) and a table of strides (each 1 byte) for
lengths up to 32 (for pattern length 33-64 there is no replication in
the register and the store stride is the pattern length).
With more ZMM registers, longer patterns can be used with that
approach, and even for shorter patterns, one may be able to waste
less. E.g., with a pattern length of 33 and one register, only 52% of
the capacity is used; with two registers, 77%; with 3 registers, 86%,
with 4, 90%, etc. But you also need more storage space for the
patterns.
For the final partial store, you use the store with AVX-512's mask
feature.
Obviously doable at 1 or 2 cycles of startup overhead,
My impression (based on REP MOVSB performance for non-overlapping
copies 10 years ago) is that the minimal cost of such microcode assist
things was 12 cycles or so. I'll have to make measurements with newer
CPUs to see if there has been any improvement there.
David Brown wrote:
On 26/06/2026 15:08, Terje Mathisen wrote:Which is of course the main reason I wrote the SSE/AVX version to beat
In the case of a single repeating byte, memset is of course optimal,
but the same LZ4 encoding is used to encode any repeating pattern, of
lengths from 1 and up. There is no indexed memset where the pattern
is of arbitrary length.
I don't think memset is necessarily "optimal", because the optimal
solution will depend on the number of bytes to fill, and possibly
alignments, and details of the exact processor.-a A particular memset
implementation could be close to optimal for large blocks, where it is
worth picking the best algorithm at runtime.-a And a compiler could
pick the algorithm details at compile time if it knows the size of the
target block.-a "Optimal" is a strong word.
I would think that the kind of copying you need for LZ4 is quite
specialised for that task - a function to do that belongs in LZ4
implementation code rather than as a standard function.-a Trying to use
memcpy() for the task is, however, a recipe for having your name
cursed by future maintainers!
both the compiler autovectorizer and Google's reference code. :-)
Terje
... but C++ has new and new is not compatible with area.
Algol was ruined with its parameter passing in 'thunks' and strict
1-file compilation.
On 6/26/2026 3:46 PM, Terje Mathisen wrote:
David Brown wrote:
On 26/06/2026 15:08, Terje Mathisen wrote:Which is of course the main reason I wrote the SSE/AVX version to beat both the compiler autovectorizer and Google's reference code. :-)
In the case of a single repeating byte, memset is of course optimal,
but the same LZ4 encoding is used to encode any repeating pattern, of >>> lengths from 1 and up. There is no indexed memset where the pattern
is of arbitrary length.
I don't think memset is necessarily "optimal", because the optimal
solution will depend on the number of bytes to fill, and possibly
alignments, and details of the exact processor.-a A particular memset
implementation could be close to optimal for large blocks, where it is
worth picking the best algorithm at runtime.-a And a compiler could
pick the algorithm details at compile time if it knows the size of the
target block.-a "Optimal" is a strong word.
I would think that the kind of copying you need for LZ4 is quite
specialised for that task - a function to do that belongs in LZ4
implementation code rather than as a standard function.-a Trying to use >> memcpy() for the task is, however, a recipe for having your name
cursed by future maintainers!
In my case, it was a library extension, hence the "_" prefix (say, sorta like "_msize()" and friends in MSVCRT).
But, yeah, personally I found it commonly needed enough to where I felt justified in adding a library function for it.
But, yeah:
LZ4, RP2, Deflate, etc, can all use it...
So, not really something that is only relevant to LZ4.
Sometimes it has other uses though, such as using it as a way to
flood-fill a raster image with a single color (can be faster than using
a generic "for()" loop for this task).
Though, one could maybe make a case for adding, say:
_memset_2b(void *dest, uint16_t size_t n);
_memset_4b(void *dest, uint32_t size_t n);
_memset_8b(void *dest, uint64_t size_t n);
As another way to express the same idea of flood-filling memory (and slightly different for the compiler to generate something inline without needing to pattern-match the arguments).
Terje
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
In order to handle the LZ4 style repeated copies of 1-n bytes, up
to length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to
16 or 32 bytes, then fills an internal cache line sized buffer
with the corresponding pattern, before doing a number of cache
lines stores with a final partial line.
You can use VPERMB to replicate the pattern in a ZMM register. With
just one ZMM register, you can put in patterns up to 64 bytes, and
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win, much better to have a hardware assist to do
it for you.
store floor(64/n)*n bytes at a time. You would need a table of
indices (each 64 bytes) and a table of strides (each 1 byte) for
lengths up to 32 (for pattern length 33-64 there is no replication
in the register and the store stride is the pattern length).
It might be possible to generate the store pattern on the fly, at
least for patterns of length greater than 4 or 8: Start by loading
the next 64 bytes and save it to a 128-byte buffer, then overwrite
from where the pattern should repeat, extending a 10-byte pattern to
20 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
repeat once more to get 40 bytes 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
which is the maximum repeat length for a 64-byte store, at a cost of
The initial load (always in $L1 cache), unaligned load
Store to temp buffer, aligned store
Store again at pattern length offset, unaligned store
load from temp buffer
store again at double pattern length offset
load final pattern from the temp buffer
This looks like 3 loads and 3 stores, most of them dependent upon the previous so at least 6 clock cycles?
With more ZMM registers, longer patterns can be used with that
approach, and even for shorter patterns, one may be able to waste
less. E.g., with a pattern length of 33 and one register, only 52%
of the capacity is used; with two registers, 77%; with 3 registers,
86%, with 4, 90%, etc. But you also need more storage space for the patterns.
For the final partial store, you use the store with AVX-512's mask
feature.
Obviously doable at 1 or 2 cycles of startup overhead,
My impression (based on REP MOVSB performance for non-overlapping
copies 10 years ago) is that the minimal cost of such microcode
assist things was 12 cycles or so. I'll have to make measurements
with newer CPUs to see if there has been any improvement there.
No, no! No microcode, this would need to be a proper hardwired
function unit. More or less like the difference between classic 40-80
cycle FDIV and the latest AMD which does it in 7-10.
Terje
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
In order to handle the LZ4 style repeated copies of 1-n bytes, up
to length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to
16 or 32 bytes, then fills an internal cache line sized buffer
with the corresponding pattern, before doing a number of cache
lines stores with a final partial line.
You can use VPERMB to replicate the pattern in a ZMM register. With
just one ZMM register, you can put in patterns up to 64 bytes, and
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win, much better to have a hardware assist to do
it for you.
store floor(64/n)*n bytes at a time. You would need a table of
indices (each 64 bytes) and a table of strides (each 1 byte) for
lengths up to 32 (for pattern length 33-64 there is no replication
in the register and the store stride is the pattern length).
It might be possible to generate the store pattern on the fly, at
least for patterns of length greater than 4 or 8: Start by loading
the next 64 bytes and save it to a 128-byte buffer, then overwrite
from where the pattern should repeat, extending a 10-byte pattern to
20 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
repeat once more to get 40 bytes
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
which is the maximum repeat length for a 64-byte store, at a cost of
The initial load (always in $L1 cache), unaligned load
Store to temp buffer, aligned store
Store again at pattern length offset, unaligned store
load from temp buffer
store again at double pattern length offset
load final pattern from the temp buffer
This looks like 3 loads and 3 stores, most of them dependent upon the
previous so at least 6 clock cycles?
With more ZMM registers, longer patterns can be used with that
approach, and even for shorter patterns, one may be able to waste
less. E.g., with a pattern length of 33 and one register, only 52%
of the capacity is used; with two registers, 77%; with 3 registers,
86%, with 4, 90%, etc. But you also need more storage space for the
patterns.
For the final partial store, you use the store with AVX-512's mask
feature.
Obviously doable at 1 or 2 cycles of startup overhead,
My impression (based on REP MOVSB performance for non-overlapping
copies 10 years ago) is that the minimal cost of such microcode
assist things was 12 cycles or so. I'll have to make measurements
with newer CPUs to see if there has been any improvement there.
No, no! No microcode, this would need to be a proper hardwired
function unit. More or less like the difference between classic 40-80
cycle FDIV and the latest AMD which does it in 7-10.
Terje
Latest AMD does not do double precision FDIV in 7-10 (latency).
The fastest AMD ever did was Zen1 (8-13). For later chips it's 13.
BTW, for Intel the latest are also not the fastest, as measured by
latency in cycles. Broadwell was 10-14. Skylake and later - 13-14.
Some very old cores despite microcode based FDIV engine were also quite respectable. E.g. original Pentium did DP FDIV (x87) in 33 cycles.
The slowest in recent (20 years) memories is Intel Bonell-based Atom -
71 clock for x87 FDIV, 60 clocks for scalar SSE2 variant.
Even Pentium4 Prescott, architecture that was famous for slow execution
of less common instructions, is faster than that - 45 clocks for x87
variant, 40 clocks for SSE2 variant.
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
In order to handle the LZ4 style repeated copies of 1-n bytes, up to
length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to 16 or >>> 32 bytes, then fills an internal cache line sized buffer with the
corresponding pattern, before doing a number of cache lines stores with
a final partial line.
You can use VPERMB to replicate the pattern in a ZMM register. With
just one ZMM register, you can put in patterns up to 64 bytes, and
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win
much better to have a hardware assist to do it
for you.
store floor(64/n)*n bytes at a time. You would need a table of
indices (each 64 bytes) and a table of strides (each 1 byte) for
lengths up to 32 (for pattern length 33-64 there is no replication in
the register and the store stride is the pattern length).
It might be possible to generate the store pattern on the fly, at least
for patterns of length greater than 4 or 8: Start by loading the next 64 >bytes and save it to a 128-byte buffer, then overwrite from where the >pattern should repeat, extending a 10-byte pattern to 20 >0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
repeat once more to get 40 bytes >0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
which is the maximum repeat length for a 64-byte store, at a cost of
The initial load (always in $L1 cache), unaligned load
Store to temp buffer, aligned store
Store again at pattern length offset, unaligned store
load from temp buffer
store again at double pattern length offset
load final pattern from the temp buffer
This looks like 3 loads and 3 stores, most of them dependent upon the >previous so at least 6 clock cycles?
My impression (based on REP MOVSB performance for non-overlapping
copies 10 years ago) is that the minimal cost of such microcode assist
things was 12 cycles or so. I'll have to make measurements with newer
CPUs to see if there has been any improvement there.
No, no! No microcode, this would need to be a proper hardwired function >unit.
More or less like the difference between classic 40-80 cycle FDIV
and the latest AMD which does it in 7-10.
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
In order to handle the LZ4 style repeated copies of 1-n bytes, up
to length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to
16 or 32 bytes, then fills an internal cache line sized buffer
with the corresponding pattern, before doing a number of cache
lines stores with a final partial line.
You can use VPERMB to replicate the pattern in a ZMM register. With
just one ZMM register, you can put in patterns up to 64 bytes, and
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win, much better to have a hardware assist to do
it for you.
store floor(64/n)*n bytes at a time. You would need a table of
indices (each 64 bytes) and a table of strides (each 1 byte) for
lengths up to 32 (for pattern length 33-64 there is no replication
in the register and the store stride is the pattern length).
It might be possible to generate the store pattern on the fly, at
least for patterns of length greater than 4 or 8: Start by loading
the next 64 bytes and save it to a 128-byte buffer, then overwrite
from where the pattern should repeat, extending a 10-byte pattern to
20 0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
repeat once more to get 40 bytes
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
which is the maximum repeat length for a 64-byte store, at a cost of
The initial load (always in $L1 cache), unaligned load
Store to temp buffer, aligned store
Store again at pattern length offset, unaligned store
load from temp buffer
store again at double pattern length offset
load final pattern from the temp buffer
This looks like 3 loads and 3 stores, most of them dependent upon the
previous so at least 6 clock cycles?
With more ZMM registers, longer patterns can be used with that
approach, and even for shorter patterns, one may be able to waste
less. E.g., with a pattern length of 33 and one register, only 52%
of the capacity is used; with two registers, 77%; with 3 registers,
86%, with 4, 90%, etc. But you also need more storage space for the
patterns.
For the final partial store, you use the store with AVX-512's mask
feature.
Obviously doable at 1 or 2 cycles of startup overhead,
My impression (based on REP MOVSB performance for non-overlapping
copies 10 years ago) is that the minimal cost of such microcode
assist things was 12 cycles or so. I'll have to make measurements
with newer CPUs to see if there has been any improvement there.
No, no! No microcode, this would need to be a proper hardwired
function unit. More or less like the difference between classic 40-80
cycle FDIV and the latest AMD which does it in 7-10.
Terje
Latest AMD does not do double precision FDIV in 7-10 (latency).
The fastest AMD ever did was Zen1 (8-13). For later chips it's 13.
BTW, for Intel the latest are also not the fastest, as measured by
latency in cycles. Broadwell was 10-14. Skylake and later - 13-14.
Some very old cores despite microcode based FDIV engine were also quite respectable. E.g. original Pentium did DP FDIV (x87) in 33 cycles.
The slowest in recent (20 years) memories is Intel Bonell-based Atom -
71 clock for x87 FDIV, 60 clocks for scalar SSE2 variant.
Even Pentium4 Prescott, architecture that was famous for slow execution
of less common instructions, is faster than that - 45 clocks for x87
variant, 40 clocks for SSE2 variant.
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
In order to handle the LZ4 style repeated copies of 1-n bytes, up to
length m, you pretty much have to have a hardware circuit which
recognizes the overlapping target with an overlap less or equal to 16 or >>>> 32 bytes, then fills an internal cache line sized buffer with the
corresponding pattern, before doing a number of cache lines stores with >>>> a final partial line.
You can use VPERMB to replicate the pattern in a ZMM register. With
just one ZMM register, you can put in patterns up to 64 bytes, and
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win
2KB cost EUR 0.00003 even at todays RAM prices.
Concerning the cache, for a given n you access exactly one cache line
for a given pattern length. The cost of that depends on where the
line is now, as usual with caches: If the n has been used recently, it
may be in L1 and cost very little, if it has not been used in a long
time, it may reside in RAM and tyhe access is very expensive, but that
case is rare.
much better to have a hardware assist to do it
for you.
Sure, one can dream.
store floor(64/n)*n bytes at a time. You would need a table of
indices (each 64 bytes) and a table of strides (each 1 byte) for
lengths up to 32 (for pattern length 33-64 there is no replication in
the register and the store stride is the pattern length).
It might be possible to generate the store pattern on the fly, at least
for patterns of length greater than 4 or 8: Start by loading the next 64
bytes and save it to a 128-byte buffer, then overwrite from where the
pattern should repeat, extending a 10-byte pattern to 20
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
repeat once more to get 40 bytes
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14...
No need for a buffer, just use the destination. That's the approach I
have used earlier and that I would like to improve on with the SIMD register(s).
John Levine <johnl@taugh.com> writes:
S/390 added the confusing;y named MOVE LONG UNICODE which moves
and pads pairs of bytes. (That works OK for UTF-16, not any
other Unicode encoding)
S/390 was by far not the last system to take the "Unicode=16bit"
route. Windows NT (released 1993), Java (released 1995), and
JavaScript (released 1995) also went there. Systems that came out
after Unicode 2.0 don't have that excuse, but are there any that
made this mistake without having to be compatible with Windows NT
or Java?
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win
2KB cost EUR 0.00003 even at todays RAM prices.
No, not the bit cost, but the alternative cost of not having the cache >available for more useful stuff.
No need for a buffer, just use the destination. That's the approach I
have used earlier and that I would like to improve on with the SIMD
register(s).
This means that you need about 100 extra bytes in the target buffer
Anyway, from all of this I've come to the conclusion that I cannot do
much better than my current 15-entry AVX permutation lookup table:
It is fast enough to beat Google, while "only" using about 500 bytes of >table space, so I'll leave the code alone, at least for now. :-)
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Obviously correct, but that requires 31 entries of 64 bytes each just
for the permutation table: Blowing 2 kB on this single function is
unlikely to be a big win
2KB cost EUR 0.00003 even at todays RAM prices.
No, not the bit cost, but the alternative cost of not having the cache
available for more useful stuff.
Of course you have the caches available for the other stuff. The
caches are automatically used for anything that is accessed (except
when you ask the system not to).
In the present context, the LZ4 input and output streams will trample
all over the caches, and evict any cache lines that have been there
before.
One may consider using non-temporal loads and stores to reduce this,
but given that LZ4 decompresses by rereading parts of the output
stream, non-temporal stores to the output are probably a bad idea.
Concerning non-temporal loads (for the input stream), what I find
about them says that they have no effect on regular (write-back)
memory; but apparently you can use prefetchnta to reduce the amount of trampling (in different ways on different CPUs; see <https://stackoverflow.com/questions/53270421/difference-between-prefetch-and-prefetchnta-instructions>).
Anyway, once you need to write out a pattern of a given length, my
VPERMB solution will load the indices from memory, evicting one cache
line unless the indices for that length are already in the cache. The evicted cache line is likely either a not very recent one from the
input or a not very recent one from the output. In the former case,
that's fine, because the input is not reused (according to my very
limited understanding of LZ4); in the latter case, there is a small possibility that the cache line might have been reused before being
evicted by some load from the input stream or store to the output
stream.
Overall, I think the major downside of the VPERMB approach is not the eviction of other cache lines, but the latency of loading the index
line, which might have been evicted by the input stream loads or
output stream stores.
No need for a buffer, just use the destination. That's the approach I
have used earlier and that I would like to improve on with the SIMD
register(s).
This means that you need about 100 extra bytes in the target buffer
What for? Could it be that you think that one prepares indices in
that way? There is no point in doing that, one just copies the actual pattern to the destination and duplicates that.
Actually, given the slowness due to a full round trip through the L1
cache, it would probably be better to just store the pattern with
length >=3 repeatedly until 64 bytes are full (or almost full) and
then take the round-trip hit and load the result into the SIMD
register, now to be used for storing.
BTW, how often is the pattern more than 2 bytes long? The 1-byte case
could be special-cased with vpbraodcastb, the 2-byte case with
vpbroadcastw, and likewise for 4 and 8 bytes, without needing VPERMB
and its index vector.
Anyway, from all of this I've come to the conclusion that I cannot do
much better than my current 15-entry AVX permutation lookup table:
It is fast enough to beat Google, while "only" using about 500 bytes of
table space, so I'll leave the code alone, at least for now. :-)
Loading aligned 32 bytes from a table is going to evict a cache line
just as loading aligned 64 bytes does. The smaller table only
provides a benefit if the second entry in that cache line is used
before the cache line is evicted; e.g., if you loaded the entry for
pattern length 14, the entry for pattern length 13.
Given that you have that, you can easily measure the effect of the
table load cache misses on performance (and how that would change by
making the entries twice as large) by benchmarking it as it currently
is and with an additional 32-byte padding between the entries. You can measure the cycles, and, with better measurement tools, you can
measure the cache misses and how often the index table loads miss.
Concerning competition, where do I find your version, Google's
version, and the benchmarks? I probably won't find the time to try it
out, but you never know.
Fortunately, we were only storing strings and
passing them on, so the limited amount of code he wrote is compatible
with UTF-16, and the handling for 8-bit characters works with UTF-8.
On 6/30/2026 6:28 PM, Michael S wrote:--------------------
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Does seem like (intuitively, untested) it should be possible to turn the reciprocal part of an FDIV into a bunch of table lookups and subtracts
(each covering a part of the mantissa). Then the rest becomes a normal
FMUL. Exponent is easier to determine.
Seems like it could be viable for fast'ish Binary16 or Binary32, scaling
it up to Binary64 would likely be expensive and have a lot of adder latency.
Well, vs the existing options:Goldschmidt is cheaper than N-R.
Do N-R in software (cheapest);
User trap-and-emulate if SW uses an FDIV instruction;LoL
Use a Shift-ADD MUL/DIV unit to deal with it.
Slower than bare N-R but faster than trap-and-emulate.
Usual issue though is that making it fast isn't a priority as it usually isn't used all that often.
Except with perspective correct texturing in
3D rendering,
which does a lot of FDIV, but, it is also possible in this case to use fast approximations rather than a slow-but-accurate FDIV.
...
But, thinking some, maybe I should at some point consider doing an
OpenGL rasterizer that actually implements perspective correct rendering
Anton Ertl wrote:[...]
The only real downside from my viewpoint is that I have exactly zero >machines available supporting AVX-512. :-(
No need for a buffer, just use the destination. That's the approach I >>>> have used earlier and that I would like to improve on with the SIMD
register(s).
This means that you need about 100 extra bytes in the target buffer
What for? Could it be that you think that one prepares indices in
that way? There is no point in doing that, one just copies the actual
pattern to the destination and duplicates that.
I was thinking of having a 31-byte pattern: Load 64 bytes, then store
them back at offset 31 for a total of 95 bytes, out of which at least 62 >will be used and up to 33 "wasted" overrun.
Avoiding all branches carries its own reward, possibly making special
cases for 1,2,4(,8) byte lengths less of a win. It depends on which
lengths actually occur often enough in compressed LZ4 files.
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings and
passing them on, so the limited amount of code he wrote is compatible
with UTF-16, and the handling for 8-bit characters works with UTF-8.
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte >character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was >designed for Unicode 1.0.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
The only real downside from my viewpoint is that I have exactly zero machines available supporting AVX-512. :-(
BGB <cr88192@gmail.com> posted:
On 6/30/2026 6:28 PM, Michael S wrote:--------------------
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Does seem like (intuitively, untested) it should be possible to turn the
reciprocal part of an FDIV into a bunch of table lookups and subtracts
(each covering a part of the mantissa). Then the rest becomes a normal
FMUL. Exponent is easier to determine.
One can do a reciprocal in about 2/3rds of a DIV.
One cannot get IEEE 754 quality rounded results using a reciprocal,
without a Newton-Rafson iteration.
Seems like it could be viable for fast'ish Binary16 or Binary32, scaling
it up to Binary64 would likely be expensive and have a lot of adder latency.
We are talking about correctly rounded IEEE 754 Double Precision, here.
Goldschmidt is cheaper than N-R.
Well, vs the existing options:
Do N-R in software (cheapest);
User trap-and-emulate if SW uses an FDIV instruction;LoL
Use a Shift-ADD MUL/DIV unit to deal with it.
Slower than bare N-R but faster than trap-and-emulate.
Usual issue though is that making it fast isn't a priority as it usually
isn't used all that often.
An instruction that occurs 1% of the time that takes 20-cycles, acts as if
it occurs 20% of the time.
Except with perspective correct texturing in
3D rendering,
Mostly done by carrying around w (1/distance) and multiplying.
Still not IEEE 754 correctly rounded.
which does a lot of FDIV, but, it is also possible in this
case to use fast approximations rather than a slow-but-accurate FDIV.
...
But, thinking some, maybe I should at some point consider doing an
OpenGL rasterizer that actually implements perspective correct rendering
Perspective correct, but not correctly rounded.
Terje Mathisen <terje.mathisen@tmsw.no> posted:
Thomas Koenig wrote:
program, it didn't have any serious bugs yet, at least not in the functionality that was implemented up to that time. But remember IEFBR14...)
Funnily enough, the IEFBR14 bug was repeated a couple of decades later
in MSDOS when DUMMY.COM which simply returned to the OS without doing anything had the exact same issue:
The original DUMMY.COM was one byte long, containing just a RET opcode:
The 256-byte PSP which was loaded in front of all .COM programs intentionally contained CD 20h (INT 20h -> Terminate the running
program) as the first two bytes, with a zero word pushed onto the stack, so that any program which used the CP/M convention that you could RET to the OS would work.
Just like the original IEFBR14, this setup did not return a fixed ERRORLEVEL which batch scripts could use to determine if an error had happened, so for the MSDOS version the single-byte program needed to be changed to something like
MOV AX,4700h
INT 21h
which would call the exit program OS function (AH=47h) with a return
code (AL) of zero.
Terje
PS. Why do I still remember the x86 hex codes for all of this almost 40 years after I last wrote 16-bit ASM code which needed it?
It got burned into your retina--like the 9 step PDP-11 startup sequence--
you "punched" into the front panel got burned into mine.
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings and
passing them on, so the limited amount of code he wrote is compatible
with UTF-16, and the handling for 8-bit characters works with UTF-8.
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was designed for Unicode 1.0.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
On Wed, 1 Jul 2026 16:11:41 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
The only real downside from my viewpoint is that I have exactly zero
machines available supporting AVX-512. :-(
I think, you said here few years ago that you own Tiger Lake (Intel
core gen 11) based laptop. Do I misremember or it died since then?
On Wed, 1 Jul 2026 16:11:41 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
The only real downside from my viewpoint is that I have exactly zero
machines available supporting AVX-512. :-(
I think, you said here few years ago that you own Tiger Lake (Intel
core gen 11) based laptop. Do I misremember or it died since then?
On Sun, 28 Jun 2026 20:15:03 GMT
MitchAlsup <user5857@newsgrouper.org.invalid> wrote:
Terje Mathisen <terje.mathisen@tmsw.no> posted:
Thomas Koenig wrote:
program, it didn't have any serious bugs yet, at least not in the
functionality that was implemented up to that time. But remember
IEFBR14...)
Funnily enough, the IEFBR14 bug was repeated a couple of decades later
in MSDOS when DUMMY.COM which simply returned to the OS without doing
anything had the exact same issue:
The original DUMMY.COM was one byte long, containing just a RET opcode:
The 256-byte PSP which was loaded in front of all .COM programs
intentionally contained CD 20h (INT 20h -> Terminate the running
program) as the first two bytes, with a zero word pushed onto the stack, >>> so that any program which used the CP/M convention that you could RET to >>> the OS would work.
Just like the original IEFBR14, this setup did not return a fixed
ERRORLEVEL which batch scripts could use to determine if an error had
happened, so for the MSDOS version the single-byte program needed to be
changed to something like
MOV AX,4700h
INT 21h
which would call the exit program OS function (AH=47h) with a return
code (AL) of zero.
Terje
PS. Why do I still remember the x86 hex codes for all of this almost 40
years after I last wrote 16-bit ASM code which needed it?
My excuse is that I'm still writing DOS x86 code! - and maybe there's
some slippage - ah=4Ch, al=xx (0-FFh) sets the ERRORLEVEL (0-255d)
(47 is Get Current Directory)
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:[...]
The only real downside from my viewpoint is that I have exactly zero >>machines available supporting AVX-512. :-(
Laptops with AVX-512 have been available since 2019 (Ice Lake, later
Tiger Lake, Zen4 and Zen5). "Desktop" PCs with AVX-512 have been
available since 2021 (Rocket Lake, Zen4, Zen5). Currently I am typing
on a deskside computer with Zen4 and there is a laptop with a Tiger
Lake lying beside my screen.
On 7/1/2026 8:54 AM, Anton Ertl wrote:
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings and
passing them on, so the limited amount of code he wrote is compatible
with UTF-16, and the handling for 8-bit characters works with UTF-8.
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte
character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was
designed for Unicode 1.0.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
Well, it is a situation of:
UTF-8, Usually best-case option here for string storage;
UTF-16, Kinda meh, works well if one assumes UCS-2 is enough;
My 2025 home desktop identifies as Intel(R) Core(TM) i7-14700 (DELL)
Neither of them support AVX-512 (not surprising for the 2013 cpu, but >somewhat surprising for the 2025 cpu - likely it's e-fused out for
a binning purposes).
My CPOE work server identifies as Intel(R) Gold 6246R CPU @3.40Ghz
and does support AVX-512. It's much more expensive than a typical >non-corporate user would be able to afford.
My last work laptop might have been Core 11, but now that I'm retired my >fastest machine is an Acer with a "13th Gen Intel(R) Core(TM) i7-1365U"
cpu which only supports AVX2.
My other PC is a 7 year old Microsoft Surface Pro 7 which does handle
AVX afair, but certainly nothing beyond that.
BGB <cr88192@gmail.com> writes:
On 7/1/2026 8:54 AM, Anton Ertl wrote:
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings and
passing them on, so the limited amount of code he wrote is compatible
with UTF-16, and the handling for 8-bit characters works with UTF-8.
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte
character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was
designed for Unicode 1.0.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
Well, it is a situation of:
UTF-8, Usually best-case option here for string storage;
UTF-16, Kinda meh, works well if one assumes UCS-2 is enough;
Actually UTF-16 is the worst of the bunch, particuarly for
interoperabilty (due to byte-ordering, even if the BOM is present).
It should be avoided in all new and non windows projects, IMO.
Terje Mathisen <terje.mathisen@tmsw.no> writes:Thank You!
My last work laptop might have been Core 11, but now that I'm retired my
fastest machine is an Acer with a "13th Gen Intel(R) Core(TM) i7-1365U"
cpu which only supports AVX2.
After providing AVX-512 in the 10th and 11th generation for laptops,
Intel eliminated in in the 12th and following generations, for reasons discussed in <2026Jul2.072030@mips.complang.tuwien.ac.at>. You should
have bought a laptop with a Ryzen 7x4x for AVX-512.
My other PC is a 7 year old Microsoft Surface Pro 7 which does handle
AVX afair, but certainly nothing beyond that.
Actually, according to <https://support.microsoft.com/en-us/surface/models/surface-pro-7-specs-and-features>
the Surface Pro 7 has one of
Dual-core 10th Gen Intel|e-< Core|orCR-o i3-1005G1 Processor
Quad-core 10th Gen Intel|e-< Core|orCR-o i5-1035G4 Processor
Quad-core 10th Gen Intel|e-< Core|orCR-o i7-1065G7 Processor
all of which support AVX-512 (Intel 10th laptop generation).
Scott Lurndal wrote:
BGB <cr88192@gmail.com> writes:
On 7/1/2026 8:54 AM, Anton Ertl wrote:
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings and
passing them on, so the limited amount of code he wrote is compatible >>>>> with UTF-16, and the handling for 8-bit characters works with UTF-8.
Yes, that's the usual case and that's why UTF-8 is a good approach for >>>> code that was designed for ASCII and Latin-1, but also for double-byte >>>> character set encodings with single-byte code units, such as Big-5 or
Shift JIS.-a And likewise, UTF-16 is a good approach for code that was >>>> designed for Unicode 1.0.
But of course, if the Unicode people had realized that from the start, >>>> we would never had UCS2 and thus no UTF-16.-a And we would have been
spared a lot of pain.
Well, it is a situation of:
-a-a UTF-8, Usually best-case option here for string storage;
-a-a UTF-16, Kinda meh, works well if one assumes UCS-2 is enough;
Actually UTF-16 is the worst of the bunch, particuarly for
interoperabilty (due to byte-ordering, even if the BOM is present).
It should be avoided in all new and non windows projects, IMO.
It should in fact be avoided even for Windows: Keep everything in UTF8,
then translate only when you need to call a Windows API.
On 7/1/2026 10:48 AM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 6/30/2026 6:28 PM, Michael S wrote:--------------------
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Does seem like (intuitively, untested) it should be possible to turn the >> reciprocal part of an FDIV into a bunch of table lookups and subtracts
(each covering a part of the mantissa). Then the rest becomes a normal
FMUL. Exponent is easier to determine.
One can do a reciprocal in about 2/3rds of a DIV.
One cannot get IEEE 754 quality rounded results using a reciprocal,
without a Newton-Rafson iteration.
Possibly, but generally both tend to land on the same value.
I guess if needed could try to run some stats on x/y vs x*(1.0/y) to see
if there is a significant difference.
Well, vs the existing options:Goldschmidt is cheaper than N-R.
Do N-R in software (cheapest);
AFAICT cheap Goldschmidt needs at least a fully pipelined FPU to have
much advantage over N-R (or to do it via SIMD).
An instruction that occurs 1% of the time that takes 20-cycles, acts as if it occurs 20% of the time.
FDIV is usually very rare, except when it is not...
Most code could accept it as trap-and-emulate...
But, if using naive divide and trap-and-emulate for Quake's SW renderer
or similar, it tanks.
scott@slp53.sl.home (Scott Lurndal) writes:
My 2025 home desktop identifies as Intel(R) Core(TM) i7-14700 (DELL)
In 2025 you could have bought a machine with a Ryzen 7xxx (Zen4), 8xxx
(Zen 4), or 9xxx (Zen 5), all with AVX-512, although maybe not from
DELL.
Neither of them support AVX-512 (not surprising for the 2013 cpu, but >somewhat surprising for the 2025 cpu - likely it's e-fused out for
a binning purposes).
The problem is that the E-Cores do not support AVX-512, apparently
because Intel thought up the concept of hybrid CPUs
only late in the--- Synchronet 3.22a-Linux NewsLink 1.2
game, and did not tell the design teams of the E-Cores to design
AVX-512 in. So when they brought out the hybrid CPUs, they disabled
AVX-512 for the P-Cores in order to provide the same architecture on
both kinds of cores. Originally you could enable AVX-512 in the BIOS
if you disabled the E-Cores, but later they removed this option, and
even when they brought out the Socket-1700 Xeons where the E-cores are disabled, they still disabled AVX-512.
Supposedly the Nova Lake which will probably come out early next year
will have AVX10 (i.e., AVX-512 with a saner feature reporting
interface), but, more importantly, APX (32 GPRs and 3-address
instructions).
My CPOE work server identifies as Intel(R) Gold 6246R CPU @3.40Ghz
and does support AVX-512. It's much more expensive than a typical >non-corporate user would be able to afford.
At the moment the cheapest CPU I can buy with AVX-512 is a Ryzen 5
8400F (EUR 111 boxed, EUR 94 tray), or, if you don't want to use a
discrete graphics card, a Ryzen 5 7400 for EUR 119 (boxed).
- anton
On 7/2/2026 3:28 AM, Terje Mathisen wrote:Probably default to the W version unless you know that your UTF8 in
Scott Lurndal wrote:
BGB <cr88192@gmail.com> writes:
On 7/1/2026 8:54 AM, Anton Ertl wrote:
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings andYes, that's the usual case and that's why UTF-8 is a good approach for >>>>> code that was designed for ASCII and Latin-1, but also for double-byte >>>>> character set encodings with single-byte code units, such as Big-5 or >>>>> Shift JIS.|e-a And likewise, UTF-16 is a good approach for code that was >>>>> designed for Unicode 1.0.
passing them on, so the limited amount of code he wrote is compatible >>>>>> with UTF-16, and the handling for 8-bit characters works with UTF-8. >>>>>
But of course, if the Unicode people had realized that from the start, >>>>> we would never had UCS2 and thus no UTF-16.|e-a And we would have been >>>>> spared a lot of pain.
Well, it is a situation of:
|e-a|e-a UTF-8, Usually best-case option here for string storage;
|e-a|e-a UTF-16, Kinda meh, works well if one assumes UCS-2 is enough;
Actually UTF-16 is the worst of the bunch, particuarly for
interoperabilty (due to byte-ordering, even if the BOM is present).
It should be avoided in all new and non windows projects, IMO.
It should in fact be avoided even for Windows: Keep everything in
UTF8, then translate only when you need to call a Windows API.
Windows API? The *A or *W versions? ;^D
Chris M. Thomasson wrote:
On 7/2/2026 3:28 AM, Terje Mathisen wrote:
Scott Lurndal wrote:
BGB <cr88192@gmail.com> writes:
On 7/1/2026 8:54 AM, Anton Ertl wrote:Actually UTF-16 is the worst of the bunch, particuarly for
jgd@cix.co.uk (John Dallman) writes:
Fortunately, we were only storing strings andYes, that's the usual case and that's why UTF-8 is a good approach >>>>>> for
passing them on, so the limited amount of code he wrote is
compatible
with UTF-16, and the handling for 8-bit characters works with UTF-8. >>>>>>
code that was designed for ASCII and Latin-1, but also for double- >>>>>> byte
character set encodings with single-byte code units, such as Big-5 or >>>>>> Shift JIS.|e-a And likewise, UTF-16 is a good approach for code that >>>>>> was
designed for Unicode 1.0.
But of course, if the Unicode people had realized that from the
start,
we would never had UCS2 and thus no UTF-16.|e-a And we would have been >>>>>> spared a lot of pain.
Well, it is a situation of:
|e-a|e-a UTF-8, Usually best-case option here for string storage;
|e-a|e-a UTF-16, Kinda meh, works well if one assumes UCS-2 is enough; >>>>
interoperabilty (due to byte-ordering, even if the BOM is present).
It should be avoided in all new and non windows projects, IMO.
It should in fact be avoided even for Windows: Keep everything in
UTF8, then translate only when you need to call a Windows API.
Windows API? The *A or *W versions? ;^D
Probably default to the W version unless you know that your UTF8 in
reality is just 7-bit US ASCII. :-)
Terje Mathisen <terje.mathisen@tmsw.no> writes:
My last work laptop might have been Core 11, but now that I'm retired my >>fastest machine is an Acer with a "13th Gen Intel(R) Core(TM) i7-1365U" >>cpu which only supports AVX2.
After providing AVX-512 in the 10th and 11th generation for laptops,
Intel eliminated in in the 12th and following generations, for reasons >discussed in <2026Jul2.072030@mips.complang.tuwien.ac.at>. You should
have bought a laptop with a Ryzen 7x4x for AVX-512.
My other PC is a 7 year old Microsoft Surface Pro 7 which does handle
AVX afair, but certainly nothing beyond that.
Actually, according to ><https://support.microsoft.com/en-us/surface/models/surface-pro-7-specs-and-features>
the Surface Pro 7 has one of
Dual-core 10th Gen Intel-< Corerao i3-1005G1 Processor
Quad-core 10th Gen Intel-< Corerao i5-1035G4 Processor
Quad-core 10th Gen Intel-< Corerao i7-1065G7 Processor
all of which support AVX-512 (Intel 10th laptop generation).
- anton
BGB <cr88192@gmail.com> posted:
On 7/1/2026 10:48 AM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 6/30/2026 6:28 PM, Michael S wrote:--------------------
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Does seem like (intuitively, untested) it should be possible to turn the >>>> reciprocal part of an FDIV into a bunch of table lookups and subtracts >>>> (each covering a part of the mantissa). Then the rest becomes a normal >>>> FMUL. Exponent is easier to determine.
One can do a reciprocal in about 2/3rds of a DIV.
One cannot get IEEE 754 quality rounded results using a reciprocal,
without a Newton-Rafson iteration.
Possibly, but generally both tend to land on the same value.
The thing is, and FPU is either IEEE correct or it is not.
An architecture is either IEEE correct or it is not.
There is no way around this--no matter what you may believe.
If 100% of all 2^(2|u53) possible FIDVs are not 100% identical with
IEEE correct FIDV values, the FPU is not IEEE correct. There is no
other way to think about it.
I guess if needed could try to run some stats on x/y vs x*(1.0/y) to see
if there is a significant difference.
You will see the error is greater than 0.5 ULP--which means it is not
IEEE correct.
Even if you make 1 rounding error every 1,000,000 FDIVs, it is still not
IEEE correct.
-------------------
Well, vs the existing options:Goldschmidt is cheaper than N-R.
Do N-R in software (cheapest);
AFAICT cheap Goldschmidt needs at least a fully pipelined FPU to have
much advantage over N-R (or to do it via SIMD).
Goldschmidt has 2 independent multiplies per iteration.
Newton-Raphson has 2 dependent multiplies per iteration.
This means there are a large number of ways to make GS
faster than N-R.
------------------
----------------------
An instruction that occurs 1% of the time that takes 20-cycles, acts as if >>> it occurs 20% of the time.
FDIV is usually very rare, except when it is not...
Most code could accept it as trap-and-emulate...
Most supercomputer codes require an FDIV that is on the order of 4|u
the latency of FMUL or FMAC.
But, if using naive divide and trap-and-emulate for Quake's SW renderer
or similar, it tanks.
Proving, once again, that either:
a) you are an idiot,
b) you cannot learn,
c) you do not listen !!!
So, which is it ???
On Thu, 02 Jul 2026 05:41:24 GMT, anton@mips.complang.tuwien.ac.at...
(Anton Ertl) wrote:
After providing AVX-512 in the 10th and 11th generation for laptops,
But not all Intel 10th generation have AVX-512. I have an i7-10700
(Comet Lake) desktop that has AVX and AVX2, but not AVX-512.
Ironically, I have a laptop I had gotten recentish which was the first >machine I got to have native AVX-256 (had a "Core i7 8th Gen").
Enabling it still doesn't see much performance gain for some basic test >programs (assuming auto vectorization is doing its thing),
but at least
(as a plus point) enabling it doesn't actively make performance worse
I still remain personally skeptical that 256-bit SIMD is actually that
much of a value add though, less so 512-bit SIMD.
On 7/2/2026 12:35 PM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 7/1/2026 10:48 AM, MitchAlsup wrote:
BGB <cr88192@gmail.com> posted:
On 6/30/2026 6:28 PM, Michael S wrote:--------------------
On Tue, 30 Jun 2026 20:57:06 +0200
Terje Mathisen <terje.mathisen@tmsw.no> wrote:
Anton Ertl wrote:
Does seem like (intuitively, untested) it should be possible to
turn the
reciprocal part of an FDIV into a bunch of table lookups and subtracts >>>>> (each covering a part of the mantissa). Then the rest becomes a normal >>>>> FMUL. Exponent is easier to determine.
One can do a reciprocal in about 2/3rds of a DIV.
One cannot get IEEE 754 quality rounded results using a reciprocal,
without a Newton-Rafson iteration.
Possibly, but generally both tend to land on the same value.
The thing is, and FPU is either IEEE correct or it is not.
An architecture is either IEEE correct or it is not.
There is no way around this--no matter what you may believe.
If 100% of all 2^(2|u53) possible FIDVs are not 100% identical with
IEEE correct FIDV values, the FPU is not IEEE correct. There is no
other way to think about it.
I guess if needed could try to run some stats on x/y vs x*(1.0/y) to see >>> if there is a significant difference.
You will see the error is greater than 0.5 ULP--which means it is not
IEEE correct.
Even if you make 1 rounding error every 1,000,000 FDIVs, it is still not
IEEE correct.
-------------------
Well, vs the existing options:Goldschmidt is cheaper than N-R.
-a-a-a-a Do N-R in software (cheapest);
AFAICT cheap Goldschmidt needs at least a fully pipelined FPU to have
much advantage over N-R (or to do it via SIMD).
Goldschmidt has 2 independent multiplies per iteration.
Newton-Raphson has 2 dependent multiplies per iteration.
This means there are a large number of ways to make GS
faster than N-R.
------------------
----------------------
An instruction that occurs 1% of the time that takes 20-cycles, acts
as if
it occurs 20% of the time.
FDIV is usually very rare, except when it is not...
Most code could accept it as trap-and-emulate...
Most supercomputer codes require an FDIV that is on the order of 4|u
the latency of FMUL or FMAC.
But, if using naive divide and trap-and-emulate for Quake's SW renderer
or similar, it tanks.
Proving, once again, that either:
a) you are an idiot,
b) you cannot learn,
c) you do not listen !!!
So, which is it ???
I suspect it may be another manifestation of BGB's "bias" toward gaming
and graphics, and not much experience with scientific applications.-a In graphics, if the FP calculations are off by a bit occasionally, it
probably doesn't matter, and that is the world BGB is in.-a But as we
have discussed in a different context, the requirements for FP in
scientific calculations is different, and more exacting/less forgiving. While you, Mitch, certainly have experience with graphics requirements,
you also have the experience in scientific applications that BGB
apparently lacks.
So if BGB is willing to accept that his design will only be acceptable
for gaming/graphics applications and not for scientific applications,
his FP implementation is perhaps OK.-a But if he wants it to be a general purpose CPU, then it probably isn't.
According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte >>character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was >>designed for Unicode 1.0.
UTF-16 isn't really a good approach for anything due to the ugly way it
uses surrogates to shoehorn in code points above 64K. You can't tell
whether a code point is one or two byte pairs without looking at each
one,
and sorting or comparing them is painful.
One of the underappreciated aspects of UTF-8 is that a naive unsigned
byte sorts or comparisons of UTF-8 strings gives you the same order as >sorting or comparing the equivalent UTF-32.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
It was literally another case of "64K is enough for anyone."
John Levine <johnl@taugh.com> writes:
According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte
character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was
designed for Unicode 1.0.
UTF-16 isn't really a good approach for anything due to the ugly way it
uses surrogates to shoehorn in code points above 64K. You can't tell
whether a code point is one or two byte pairs without looking at each
one,
True, but that's rarely needed.
and sorting or comparing them is painful.
Sorting or comparing according to locale is painful indeed.
One of the underappreciated aspects of UTF-8 is that a naive unsigned
byte sorts or comparisons of UTF-8 strings gives you the same order as
sorting or comparing the equivalent UTF-32.
Interesting, but does it really matter? If you compare or sort the
strings that way, probably any total order is good enough.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
It was literally another case of "64K is enough for anyone."
I think that the major mistake was the assumption that we need to deal
with individual code points efficiently. There are not that many
places where that is actually needed. If it was needed a lot, UTF-32
would have won, not UTF-8.
- anton
John Levine <johnl@taugh.com> writes:
According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
Yes, that's the usual case and that's why UTF-8 is a good approach for
code that was designed for ASCII and Latin-1, but also for double-byte
character set encodings with single-byte code units, such as Big-5 or
Shift JIS. And likewise, UTF-16 is a good approach for code that was
designed for Unicode 1.0.
UTF-16 isn't really a good approach for anything due to the ugly way it
uses surrogates to shoehorn in code points above 64K. You can't tell
whether a code point is one or two byte pairs without looking at each
one,
True, but that's rarely needed.
and sorting or comparing them is painful.
Sorting or comparing according to locale is painful indeed.
One of the underappreciated aspects of UTF-8 is that a naive unsigned
byte sorts or comparisons of UTF-8 strings gives you the same order as
sorting or comparing the equivalent UTF-32.
Interesting, but does it really matter? If you compare or sort the
strings that way, probably any total order is good enough.
But of course, if the Unicode people had realized that from the start,
we would never had UCS2 and thus no UTF-16. And we would have been
spared a lot of pain.
It was literally another case of "64K is enough for anyone."
I think that the major mistake was the assumption that we need to deal
with individual code points efficiently. There are not that many
places where that is actually needed. If it was needed a lot, UTF-32
would have won, not UTF-8.
Anton Ertl wrote:-----------------------
John Levine <johnl@taugh.com> writes:
According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
I think that the major mistake was the assumption that we need to deal
with individual code points efficiently. There are not that many
places where that is actually needed. If it was needed a lot, UTF-32
would have won, not UTF-8.
The real deal-breaker is the fact that if you use chunked storage, like
most editors will do, then it becomes trivial to skip forward/back N character positions by simply jumping past any intermediate chunks, then iterate to locate the exact character.
If you really care (locally) about direct linear UTF-32 access, then you simply unpack the current chunk, do whatever you need to do, then pack
it back up.
The very first time I needed to write a text editor, in Borland's Turbo Pascal, I simply used a list of lines, each limited by the TP 255-byte length limit. It was plenty fast enough, you could never see any delay between hitting a key and the screen update.
Terje
On 7/3/2026 12:03 PM, Anton Ertl wrote:
John Levine <johnl@taugh.com> writes:
According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
Yes, that's the usual case and that's why UTF-8 is a good approach for >>>> code that was designed for ASCII and Latin-1, but also for double-byte >>>> character set encodings with single-byte code units, such as Big-5 or
Shift JIS.-a And likewise, UTF-16 is a good approach for code that was >>>> designed for Unicode 1.0.
UTF-16 isn't really a good approach for anything due to the ugly way it
uses surrogates to shoehorn in code points above 64K.-a You can't tell
whether a code point is one or two byte pairs without looking at each>>> one,
True, but that's rarely needed.
From a space POV, if the text consists of a lot of CJK characters or emojis, UTF-16 is a win.
If any significant amount of ASCII characters, it is a loss.
-a For alphabets like Greek or Cyrillic, it is break-even.
For English or Western European languages, Codepage-1252 is typically
the densest form.
and sorting or comparing them is painful.
Sorting or comparing according to locale is painful indeed.
Usual thing IME is to ignore locale in both cases and compare according
to raw values. For things that are not directly user facing, can ignore locale.
Well, and treat things like case-insensitive compare as an obscure
special case.
Sort and search in a case-insensitive manner is actually quite hard toOne of the underappreciated aspects of UTF-8 is that a naive unsigned>>> byte sorts or comparisons of UTF-8 strings gives you the same order as
sorting or comparing the equivalent UTF-32.
Interesting, but does it really matter?-a If you compare or sort the
strings that way, probably any total order is good enough.
Same strategy works for UTF-16, just using 16-bit values.
BGB wrote:
On 7/3/2026 12:03 PM, Anton Ertl wrote:
John Levine <johnl@taugh.com> writes:
According to Anton Ertl <anton@mips.complang.tuwien.ac.at>:
Yes, that's the usual case and that's why UTF-8 is a good approach for >>>>> code that was designed for ASCII and Latin-1, but also for double-byte >>>>> character set encodings with single-byte code units, such as Big-5 or >>>>> Shift JIS.-a And likewise, UTF-16 is a good approach for code that was >>>>> designed for Unicode 1.0.
UTF-16 isn't really a good approach for anything due to the ugly way it >>>> uses surrogates to shoehorn in code points above 64K.-a You can't tell >>>> whether a code point is one or two byte pairs without looking at each
one,
True, but that's rarely needed.
-aFrom a space POV, if the text consists of a lot of CJK characters or
emojis, UTF-16 is a win.
If any significant amount of ASCII characters, it is a loss.
-a-a For alphabets like Greek or Cyrillic, it is break-even.
For English or Western European languages, Codepage-1252 is typically
the densest form.
and sorting or comparing them is painful.
Sorting or comparing according to locale is painful indeed.
Usual thing IME is to ignore locale in both cases and compare
according to raw values. For things that are not directly user facing,
can ignore locale.
Well, and treat things like case-insensitive compare as an obscure
special case.
One of the underappreciated aspects of UTF-8 is that a naive unsigned
byte sorts or comparisons of UTF-8 strings gives you the same order as >>>> sorting or comparing the equivalent UTF-32.
Interesting, but does it really matter?-a If you compare or sort the
strings that way, probably any total order is good enough.
Same strategy works for UTF-16, just using 16-bit values.
Sort and search in a case-insensitive manner is actually quite hard to
make really fast.
For sort of more complicated character sets like Norwegian, the best
I've been able to come up with is to start by making monocased keys consisting of the first N characters plus the index of the original
string. The same stage can also convert special character pairs into
single values, like AA->|a, AE->|a, OE->|y etc.
After the first stage sort of these keys, do a fixup stage using the
full strings for any duplicate keys.
Boyer-Moore string search needs something similar where the original
search key is copied twice, into a lower-only and an upper-only version.
This is needed because inline monocasing of arbitrary Unicode letters
can be quite expensive.
Looking on the bright side, you can use a small (byte-sized) skip table
even for 16 or 32-bit character encodings or directly on the UTF-8
sequence, you just have to accept that some of those skips will be non- optimal since each entry needs to contains the shortest skip length indicated by any colliding character keys.
From a space POV, if the text consists of a lot of CJK characters or
emojis, UTF-16 is a win.
If any significant amount of ASCII characters, it is a loss.
The real deal-breaker is the fact that if you use chunked storage, like
most editors will do, then it becomes trivial to skip forward/back N >character positions by simply jumping past any intermediate chunks, then >iterate to locate the exact character.
Terje Mathisen <terje.mathisen@tmsw.no> writes:
The real deal-breaker is the fact that if you use chunked storage, like
most editors will do, then it becomes trivial to skip forward/back N
character positions by simply jumping past any intermediate chunks, then
iterate to locate the exact character.
Even if you don't, and use, e.g., a gap buffer (which I found much
easier to work with than some line-based representation when I wrote
an editor a long time ago),
Anton Ertl wrote:
Even if you don't, and use, e.g., a gap buffer (which I found much
easier to work with than some line-based representation when I wrote
an editor a long time ago),
I have used a gap buffer in later years, after getting out of the 16bit >world.
Back in the MsDos era, I would have been limited to just 64KB of text
unless I accepted the need for some kind of chunking, switching to one
"far ptr" per line meant that I now could have 16K lines, and it made
all those vertical cursor moves trivial.
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:
Even if you don't, and use, e.g., a gap buffer (which I found much
easier to work with than some line-based representation when I wrote
an editor a long time ago),
I have used a gap buffer in later years, after getting out of the 16bit
world.
Back in the MsDos era, I would have been limited to just 64KB of text
My editor was on the C64, so I was limited to 64KB of text anyway.
But with 170KB disks, that was not a limit I found restrictive.
unless I accepted the need for some kind of chunking, switching to one
"far ptr" per line meant that I now could have 16K lines, and it made
all those vertical cursor moves trivial.
You still have to check the line length. And often move the line when
it grows.
I found that special-casing line ends added lots of complications to
my line-based editor, which all went away in the gap-buffer based
editor. E.g., when the user presses Backspace at the start of a line,
you have to combine the current line with the previous line, whereas
the gap buffer version just deletes the newline character before the
cursor, just like what Backspace does to any other character.
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:
Even if you don't, and use, e.g., a gap buffer (which I found much
easier to work with than some line-based representation when I wrote
an editor a long time ago),
I have used a gap buffer in later years, after getting out of the 16bit
world.
Back in the MsDos era, I would have been limited to just 64KB of text
My editor was on the C64, so I was limited to 64KB of text anyway.
But with 170KB disks, that was not a limit I found restrictive.
unless I accepted the need for some kind of chunking, switching to one
"far ptr" per line meant that I now could have 16K lines, and it made
all those vertical cursor moves trivial.
You still have to check the line length.-a And often move the line when
it grows.
My choice was strongly influenced by the fact that Turbo Pascal had length-preceeded strings, so the actual/current length is always just a single byte load away.
I found that special-casing line ends added lots of complications to
my line-based editor, which all went away in the gap-buffer based
editor.-a E.g., when the user presses Backspace at the start of a line,
you have to combine the current line with the previous line, whereas
the gap buffer version just deletes the newline character before the
cursor, just like what Backspace does to any other character.
The only hard thing for me was the need to reduce the line count, the
actual merging was just a line[i-1] := line[i-1]+line[i];
Anyway, we are (mostly) in violent agreement: Having a flat address
space and a gap buffer makes almost everything much simpler. If you need
to do massive block operations all the time, then it might make sense to move to a more complicated data structure.
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:
Even if you don't, and use, e.g., a gap buffer (which I found much
easier to work with than some line-based representation when I wrote
an editor a long time ago),
I have used a gap buffer in later years, after getting out of the 16bit
world.
Back in the MsDos era, I would have been limited to just 64KB of text
My editor was on the C64, so I was limited to 64KB of text anyway.
But with 170KB disks, that was not a limit I found restrictive.
unless I accepted the need for some kind of chunking, switching to one
"far ptr" per line meant that I now could have 16K lines, and it made
all those vertical cursor moves trivial.
You still have to check the line length.-a And often move the line when
it grows.
My choice was strongly influenced by the fact that Turbo Pascal had length-preceeded strings, so the actual/current length is always just a single byte load away.
I found that special-casing line ends added lots of complications to
my line-based editor, which all went away in the gap-buffer based
editor.-a E.g., when the user presses Backspace at the start of a line,
you have to combine the current line with the previous line, whereas
the gap buffer version just deletes the newline character before the
cursor, just like what Backspace does to any other character.
The only hard thing for me was the need to reduce the line count, the
actual merging was just a line[i-1] := line[i-1]+line[i];
Anyway, we are (mostly) in violent agreement: Having a flat address
space and a gap buffer makes almost everything much simpler. If you need
to do massive block operations all the time, then it might make sense to move to a more complicated data structure.
On 7/5/2026 4:05 AM, Terje Mathisen wrote:
Anton Ertl wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Anton Ertl wrote:
Even if you don't, and use, e.g., a gap buffer (which I found much
easier to work with than some line-based representation when I wrote >>>>> an editor a long time ago),
I have used a gap buffer in later years, after getting out of the 16bit >>>> world.
Back in the MsDos era, I would have been limited to just 64KB of text
My editor was on the C64, so I was limited to 64KB of text anyway.
But with 170KB disks, that was not a limit I found restrictive.
unless I accepted the need for some kind of chunking, switching to one >>>> "far ptr" per line meant that I now could have 16K lines, and it made
all those vertical cursor moves trivial.
You still have to check the line length.|e-a And often move the line when >>> it grows.
My choice was strongly influenced by the fact that Turbo Pascal had
length-preceeded strings, so the actual/current length is always just >> a single byte load away.
I found that special-casing line ends added lots of complications to
my line-based editor, which all went away in the gap-buffer based
editor.|e-a E.g., when the user presses Backspace at the start of a line, >>> you have to combine the current line with the previous line, whereas
the gap buffer version just deletes the newline character before the
cursor, just like what Backspace does to any other character.
The only hard thing for me was the need to reduce the line count, the >> actual merging was just a line[i-1] := line[i-1]+line[i];
Anyway, we are (mostly) in violent agreement: Having a flat address
space and a gap buffer makes almost everything much simpler. If you
need to do massive block operations all the time, then it might make
sense to move to a more complicated data structure.
Fwiw, for some reason this made me think of Ropes:
https://en.wikipedia.org/wiki/Rope_(data_structure)
Chris M. Thomasson wrote:
https://en.wikipedia.org/wiki/Rope_(data_structure)Ropes are of course one of the most efficient ways to implement chunked=20 >storage.
=20
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Chris M. Thomasson wrote:Ropes are good for one thing: concatenating two strings.
https://en.wikipedia.org/wiki/Rope_(data_structure)Ropes are of course one of the most efficient ways to implement chunked=20 >>storage.
=20
As for editors, the gap buffer is simple and efficient for the usual operations,
but if moving the data is expensive for some reason, the right
alternative is the piece table, which has been designed for the
purpose, and has been used successfully for the purpose <https://en.wikipedia.org/wiki/Piece_table#Usage>; however, as the
various problems with Microsoft Word .doc documents show, better
consolidate the representation for permanent storage.
Anton Ertl [2026-07-07 04:37:03] wrote:
Terje Mathisen <terje.mathisen@tmsw.no> writes:
Chris M. Thomasson wrote:Ropes are good for one thing: concatenating two strings.
https://en.wikipedia.org/wiki/Rope_(data_structure)Ropes are of course one of the most efficient ways to implement chunked=20 >>>storage.
=20
They're also pretty good to keep different versions of an editor's buffer.
As for editors, the gap buffer is simple and efficient for the usual
operations,
Indeed. Especially as memory bandwidth has nicely increased over the
years, so the extra cost incurred when moving the gap has been going
down faster than the extra cost of indirecting through the various nodes
of a rope.
but if moving the data is expensive for some reason, the right
alternative is the piece table, which has been designed for the
purpose, and has been used successfully for the purpose
<https://en.wikipedia.org/wiki/Piece_table#Usage>; however, as the
various problems with Microsoft Word .doc documents show, better
consolidate the representation for permanent storage.
The "same" problem appears for the piece table itself: it can be kept as
a tree (like ropes would) or as an array when you may want to use a gap
to handle insertion/deletion of elements.
My C64 has 64KB and it's CPU can move about 64KB/s
(5/6 cycles load, 5/6 cycles store, 2 cycles increment, 3 cycles
branch, and a little bit of overhead all 256 bytes, all at 1MHz). My
Ryzen 8700G has 64GB and a memory bandwidth of 64GB/s (the memory
controller and RAM can probably can do more, but the interface between
the CCX and the RAM is limited to 64GB); I have not measured block
copy yet, and it will not exceed 32GB/s, but basically block copy
speed has roughly grown with RAM.
Stefan Monnier <monnier@iro.umontreal.ca> writes:
Anton Ertl [2026-07-07 04:37:03] wrote:I don't know which problem you mean.
but if moving the data is expensive for some reason, the rightThe "same" problem appears for the piece table itself: it can be kept as
alternative is the piece table, which has been designed for the
purpose, and has been used successfully for the purpose
<https://en.wikipedia.org/wiki/Piece_table#Usage>; however, as the
various problems with Microsoft Word .doc documents show, better
consolidate the representation for permanent storage.
a tree (like ropes would) or as an array when you may want to use a gap
to handle insertion/deletion of elements.
Lisp is a funny language: Big promises in the design; But, only
deliver them poorly (and can't improve on the delivery of any given
thing without eroding the original promises).
Usual downside it that the excessive parenthesis tend to turn into a usability issue.
One other major hassle was typically a lack of C style loops (with
break or continue), but this could be addressed in theory.
I'm not trying to defend SPARC and am happy to take your word for it
that M88K was fast for the time.
Has pointer safety been shown to be equivalent to the halting
problem?
On 2026-06-22 13:44, Thomas Koenig wrote:
Has pointer safety been shown to be equivalent to the halting
problem? If so, "careful governance and guidance from God" may
indeed be required.
I would assume it is undecidable, for unrestricted programs.
The aim of pointer provenance is no doubt to restrict programs
to make it decidable to some extent.
If that is what I think it is, where it cast from a pointer to a
field inside a struct back to the containing struct by subtracting
the field byte offset and changing the pointer type, irrespective
of programming language that mechanism has been used by operating
systems at least since RSX days.
It is a compact way of having structs linked to many other structures.
That macro is just a variant of the mechanism for C.
The method is used by WinNT and Linux, and I believe also by the
BSD's.
GCC has a compile option, no_strict_alias or something, that
anyone using it and doing "illegal" pointer casting must use.
In Windows land, pointer casting at least used to be Microsoft's
recommended method and is supported by their compiler because they
use it too, extensively.
| Sysop: | Amessyroom |
|---|---|
| Location: | Fayetteville, NC |
| Users: | 74 |
| Nodes: | 6 (0 / 6) |
| Uptime: | 49:09:50 |
| Calls: | 1,100 |
| Files: | 1,339 |
| Messages: | 275,768 |