From Newsgroup: comp.arch

Michael S <[email protected]> writes:

On Mon, 28 Sep 2026 02:59:06 -0700
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index
variables.

In Rust, the only acceptable array index is of type "usize", which
is effectively the same as u64 on most platforms these days, but
does not need to be so: On a 32-bit target, it would be the same
as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

That tells me a lot. Thank you.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Michael S <[email protected]> wrote:

[snip]
My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

Beginning Rust programmers tend to go through a few phases,
particularly if coming from a language like C. "Fighting the
Borrow Checker" is well-known; "traits are awesome; let's use
them everywhere!" is another.

When I started programming in Rust, most of my immediate
colleagues and I had terribly little experience in the language.
We were excited about the its potential benefits, but realized
it would take a few months to build up a sufficient level of
familiarity to use it skillfully. One quipped, "this language
has a near-vertical learning curve."

At one point a coworker (self-deprecatingly) said, "look, I'm
writing crust! C in Rust syntax!" Everyone thought this was a
great play on words, but he was correct: the programs we were
writing were essentially C programs, just expressed in Rust. We
quickly adopted that to describe our still naive code: it wasn't
an insult, just an expression that we were still coming to terms
with a new way of doing things. Some of the hallmarks of that
included using the wrong paradigms (and types!) for lots of our
code.

I'd be curious to know more about your program. I've written
several hundred kloc of Rust at this point, and while what I
write may be terribly specialized, I rarely find myself indexing
an array; often, I'm using iterators or some other abstraction
for that kind of thing. If that was the one program you have
written in Rust, my _guess_ is that you were using paradigms
appropriate to a different language, which is why you felt you
needed to reach for casts to index an array so frequently.

Again, that's not a comment on your program, so much as
suggesting an impedence mismatch between what you wrote and how
one would generally expect to use the language.

In general, I think a person's experience writing a single
program tells us very little.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Wed, 30 Sep 2026 13:57:24 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

[snip]
My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

Beginning Rust programmers tend to go through a few phases,
particularly if coming from a language like C. "Fighting the
Borrow Checker" is well-known; "traits are awesome; let's use
them everywhere!" is another.

I didn't reach the second stage. Not sure about first.

When I started programming in Rust, most of my immediate
colleagues and I had terribly little experience in the language.
We were excited about the its potential benefits, but realized
it would take a few months to build up a sufficient level of
familiarity to use it skillfully. One quipped, "this language
has a near-vertical learning curve."

IMHO, he is correct.
Rust is certainly the hardest to learn out of computer languges that I
ever tried that I would not call idiotic.

At one point a coworker (self-deprecatingly) said, "look, I'm
writing crust! C in Rust syntax!" Everyone thought this was a
great play on words, but he was correct: the programs we were
writing were essentially C programs, just expressed in Rust. We
quickly adopted that to describe our still naive code: it wasn't
an insult, just an expression that we were still coming to terms
with a new way of doing things. Some of the hallmarks of that
included using the wrong paradigms (and types!) for lots of our
code.

I'd be curious to know more about your program.

The program was an implementation scalable flood fill algorithm (i.e.
one with much better than typical worst case BigO properties, both for
speed and for space) together with test benches for correctness and
speed. As you could guess, I didn't really wrote it in Rust. It was a non-literal port from C. The purpose of translation was two-fold:
improvement of my knowledge of Rust and getting better feel for cost of mandatory bound checking for one particular sort of data structures.
Before doing Rust port I did port to Golang. Unlike for Rust, where I
only read The Book and went trough part of tutorial, I had small
previous practical experience in Go, but it was not very recent. Still,
the difference in my productivity was huge. In favor of Go, of course.

I've written
several hundred kloc of Rust at this point, and while what I
write may be terribly specialized, I rarely find myself indexing
an array; often, I'm using iterators or some other abstraction
for that kind of thing. If that was the one program you have
written in Rust, my _guess_ is that you were using paradigms
appropriate to a different language, which is why you felt you
needed to reach for casts to index an array so frequently.

Again, that's not a comment on your program, so much as
suggesting an impedence mismatch between what you wrote and how
one would generally expect to use the language.

In general, I think a person's experience writing a single
program tells us very little.

I never pretended otherwise. Although I don't see how one can avoid
cast if one wants to use indices that originate in signed domain. Or,
as was often a case in this particular program, in domain of narrower
unsigned integers.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Dan Cross wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

[snip]
My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

Beginning Rust programmers tend to go through a few phases,
particularly if coming from a language like C. "Fighting the
Borrow Checker" is well-known; "traits are awesome; let's use
them everywhere!" is another.

When I started programming in Rust, most of my immediate
colleagues and I had terribly little experience in the language.
We were excited about the its potential benefits, but realized
it would take a few months to build up a sufficient level of
familiarity to use it skillfully. One quipped, "this language
has a near-vertical learning curve."

At one point a coworker (self-deprecatingly) said, "look, I'm
writing crust! C in Rust syntax!" Everyone thought this was a
great play on words, but he was correct: the programs we were
writing were essentially C programs, just expressed in Rust. We
quickly adopted that to describe our still naive code: it wasn't
an insult, just an expression that we were still coming to terms
with a new way of doing things. Some of the hallmarks of that
included using the wrong paradigms (and types!) for lots of our
code.

I have definitely noted this in my own code, crust is a good name for it.

Quite often, when "fighting the borrow checker", typically because I'm updating a complicated data structure in two locations at the same time,
I'll fall back to "write Fortran in Rust", with every access indexed.

This is BTW one of those problems the brand new upcoming borrow checker
is supposed to be far better at figuring out: If I'm updating totally
separate parts of the same larger structure, then it should be OK to
mutate both at the same time.

I do realize that there are far more Rusty ways to solve this type of
issue, they just don't come naturally to me yet.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch


Terje Mathisen <[email protected]> posted:

Dan Cross wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

[snip]
My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

Beginning Rust programmers tend to go through a few phases,
particularly if coming from a language like C. "Fighting the
Borrow Checker" is well-known; "traits are awesome; let's use
them everywhere!" is another.

When I started programming in Rust, most of my immediate
colleagues and I had terribly little experience in the language.
We were excited about the its potential benefits, but realized
it would take a few months to build up a sufficient level of
familiarity to use it skillfully. One quipped, "this language
has a near-vertical learning curve."

At one point a coworker (self-deprecatingly) said, "look, I'm
writing crust! C in Rust syntax!" Everyone thought this was a
great play on words, but he was correct: the programs we were
writing were essentially C programs, just expressed in Rust. We
quickly adopted that to describe our still naive code: it wasn't
an insult, just an expression that we were still coming to terms
with a new way of doing things. Some of the hallmarks of that
included using the wrong paradigms (and types!) for lots of our
code.

I have definitely noted this in my own code, crust is a good name for it.

Quite often, when "fighting the borrow checker", typically because I'm updating a complicated data structure in two locations at the same time, I'll fall back to "write Fortran in Rust", with every access indexed.

Wouldn't that be FRustrating ?!?

This is BTW one of those problems the brand new upcoming borrow checker
is supposed to be far better at figuring out: If I'm updating totally separate parts of the same larger structure, then it should be OK to
mutate both at the same time.

I do realize that there are far more Rusty ways to solve this type of
issue, they just don't come naturally to me yet.

Terje

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Terje Mathisen <[email protected]> writes:

[on learning Rust]

Quite often, when "fighting the borrow checker", typically because
I'm updating a complicated data structure in two locations at the
same time, I'll fall back to "write Fortran in Rust", with every
access indexed.

This is BTW one of those problems the brand new upcoming borrow
checker is supposed to be far better at figuring out: If I'm
updating totally separate parts of the same larger structure,
then it should be OK to mutate both at the same time.

I do realize that there are far more Rusty ways to solve this
type of issue, they just don't come naturally to me yet.

(Please excuse my pursuing this non-arch topic...)

Question for any Rusters in the group --

What is the best was to learn the Rust programming language?
Which books or other documents are the best introductory or
reference materials?

Disclaimer: My experience with Rust is more than zero but
not a lot more than zero.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables.

In Rust, the only acceptable array index is of type "usize", which is
effectively the same as u64 on most platforms these days, but does not
need to be so: On a 32-bit target, it would be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial underpinnings of Rust safety. Even more importantly, all such indices
are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

But given that the checks are put in by the compiler, it seems
rather silly to insist that index expressions have type usize,
especially when a common remedy is just to add a cast. It's like
saying the car won't start unless you take off your seatbelt.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Stephen Fuld <[email protected]d> wrote:

It is obvious that you are right; the the existing choices as documented
in the standard and your post above (thanks for that) don't permit what
I want. I apologize for not recognizing that up front. But I maintain
that there should be a category that essentially says "You can do what
you want, but you must document what you did." Furthermore, if such a choice existed, most instances of undefined should be "reclassified"
into that new choice. I think that would aid programmers understanding.

In case of gcc 'ureachable()' can be given simple definition:
optimizer will assume that 'ureachable()' will never be
executed and do program transformations based on that knowledge.

Consder the following program fragment:

void foo1(int i) {
if (i < 0) {
unreachable();
}
foo2(i);
}

void foo2(int i) {
if (i < 0) {
foo3(i);
} else {
foo4(i);
}
}

In foo1 compiler could infer that 'i >= 0'. It could also inline
'foo2' into 'foo1'. After inlining it could infer that 'foo4'
will be called. So compiler could transform 'foo1' into

void foo1(int i) {
foo4(i);
}

If ever 'foo1' gets called with negative argument you would get
call to 'foo4' with negative argument.

Some people have mental model that C is compiled on statement by
statement basis. In compiler that is doing simple statement by
statement compilation 'if' in 'foo2' would prevent call to
'foo4' with negative argument. If compiler simply replaced
'unreachable()' by a trap instruction, then program would
trap in ;foo1'. But undefined behaviour opens essentially
unlimied possibilites for program transformation, based on
surrouding code.

BTW: I can image code using a macro

#define ASSERT_FACT(x) {if (x) unreachable();}

and codebase sprinkled with statements like:

ASSERT_FACT(i >= 0 && i < 100)

So 'unreachable()' essentially allows passing arbitrary assertions
to the compiler.

Let me add that given enough facts compiler should be able to
prove that all of them are true. It would be nice to have an
option so that compiler warns if it can not prove that some
'unreachable()' is really unreachable.

And note that false statement implies everthing, so if your
'unreachable()' is wrong then there are unlimited possibilities
for unexpected behaviour.
--
Waldek Hebisch
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

David Brown <[email protected]> wrote:

On 26/09/2026 16:25, Stefan Monnier wrote:

David Brown [2026-09-25 19:00:26] wrote:

A halfway point might be for the compiler to emit a warning when it
can't show that `unreachable()` is indeed unreachable.

I can certainly agree that the compiler could give a warning if the unreachable() is definitely reached. And if compiler writers can figure
out some decent heuristics about "unreachable()" being inevitably
reached after some useful code path, then a warning would be nice.
(That can't be given specifications in the standards, because you could
not define clear semantics here - but it's fine to have optional
compiler warnings on things that appear to be wrong according to some
kind of pattern recognition.)

But it would be virtually useless to have a warning any time the
compiler cannot prove that the "unreachable()" is indeed unreachable.
The whole point of its use is when the programmer knows more than the compiler, and is giving the compiler additional information. If the compiler knows that point in the code cannot be reached, then it already knows it is unreachable, and will already optimise on the assumption
that the point is not reached!

I do not think that such warning would be useful to Stefan. But
that does not make it useless. Namely, difficultly of proof
decrease sharply if you have enough knowledge. Namely, for
seqential code current gcc is reasonably adept at propagating
conditions. It can recognize _some_ looping patterns. But
in general for loops and recursion one needs appropriate
invariants and variants. It is hard to automatically
infer them. But with enough programmer supplied information
compiler in principle could verify its correctness by
simple sequential-like reasoning. Failure to verify
information provided by programmer indicates that this
info is either wrong or incomplete. Both are reasons to
change it, either by removing info that failed to verify
or adding more info in hope that this will lead to
successful proof.

[ I generally like the idea of programmers being able to request
specific optimizations and to be warned by the compiler when those
requests can't be satisfied. So we don't have to go dig in the
assembly output to confirm whether the compiler did the right thing or
not. ]

I agree on that principle - I'm a big fan of warnings when my code
appears to be wrong. But this is not a situation where warnings would
be appropriate.

Lisp compiler 'sbcl' at high optimization level emits a lot of
warnings about constructs that it can not optimize, giving
information that is needed to enable optimization. In C similar
warnings are less needed, because basic C construct already have low
level ("optimized") form. But C programmers may expect some
optimizations and it would be good for compiler to report if
optimizations did not apply.

Of course, most people using '-Werror' does not want optimization
warning to halt the build. So clearly they should go in different
category than normal warnings.
--
Waldek Hebisch
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 02/10/2026 06:10, Waldek Hebisch wrote:

Stephen Fuld <[email protected]d> wrote:

It is obvious that you are right; the the existing choices as documented
in the standard and your post above (thanks for that) don't permit what
I want. I apologize for not recognizing that up front. But I maintain
that there should be a category that essentially says "You can do what
you want, but you must document what you did." Furthermore, if such a
choice existed, most instances of undefined should be "reclassified"
into that new choice. I think that would aid programmers understanding.

In case of gcc 'ureachable()' can be given simple definition:
optimizer will assume that 'ureachable()' will never be
executed and do program transformations based on that knowledge.

Yes.

That is equivalent to saying that if the execution reaches
"unreachable()", the behaviour is undefined. In C, it is the same
thing. (Some people don't seem to like that, and think that "undefined behaviour" should really mean "something vague and nebulous - I can't
explain it to other people, never mind to a compiler, but I am sure I
know what I mean".)

In gcc and clang, the function "unreachable()" is the same as __builtin_unreachable(), and is translated directly by the front-end
into the "UB" code in the internal intermediary language of the compiler.

Consder the following program fragment:

void foo1(int i) {
if (i < 0) {
unreachable();
}
foo2(i);
}

void foo2(int i) {
if (i < 0) {
foo3(i);
} else {
foo4(i);
}
}

In foo1 compiler could infer that 'i >= 0'. It could also inline
'foo2' into 'foo1'. After inlining it could infer that 'foo4'
will be called. So compiler could transform 'foo1' into

void foo1(int i) {
foo4(i);
}

If ever 'foo1' gets called with negative argument you would get
call to 'foo4' with negative argument.

Yes, that is exactly the kind of thing "unreachable()" is useful for.

Some people have mental model that C is compiled on statement by
statement basis. In compiler that is doing simple statement by
statement compilation 'if' in 'foo2' would prevent call to
'foo4' with negative argument. If compiler simply replaced
'unreachable()' by a trap instruction, then program would
trap in ;foo1'. But undefined behaviour opens essentially
unlimied possibilites for program transformation, based on
surrouding code.

I think it is quite common to wrap "unreachable()" in a macro so that
you can quickly make such a change before rebuilding your code.
Something like :

#ifdef DEBUGGING
#define Unreachable() __builtin_trap()
#else
#define Unreachable() unreachable()
#endif

BTW: I can image code using a macro

#define ASSERT_FACT(x) {if (x) unreachable();}

Or maybe even :

#define ASSERT_FACT(x) {if (!(x)) unreachable();}


Again, support for compile-time choices of run-time checks can be
useful. And you can get a compile-time error if the compiler is able to
see that the asserted "fact" is never true.

extern void __attribute__((error("Alternative fact asserted"))) assertFactFailed(void);

#define Assert_fact(x) \
do { \
if (__builtin_constant_p(!(x))) { \
if (!(x)) { \
assertFactFailed(); \
} \
} \
#ifdef DEBUGGING
if (!(x)) __builtin_trap(); \
#else
if (!(x)) __builtin_unreachable(); \
#endif
} while (0)

and codebase sprinkled with statements like:

ASSERT_FACT(i >= 0 && i < 100)

So 'unreachable()' essentially allows passing arbitrary assertions
to the compiler.

C++23 also has the [[assume(x)]] attribute doing exactly that, but it
has not made it into C as yet.

Let me add that given enough facts compiler should be able to
prove that all of them are true. It would be nice to have an
option so that compiler warns if it can not prove that some
'unreachable()' is really unreachable.

I disagree on that one - or at least, I am very sceptical. You add an "unreachable()" to the code precisely because you know more than the
compiler can realistically know. If the compiler can figure out that
"(i >= 0 && i < 100)", then there would be no need to tell it.

But I suppose you might still use it to help inform other programmers,
or to silence some warnings (like missing return values on code paths
that are never reached).

extern void __attribute__((error("Alternative fact confirmed"))) confirmIncorrectFact(void);

extern void __attribute__((error("Fact not confirmed"))) confirmFactFailed(void);

#define Confirm_fact(x) \
do { \
if (__builtin_constant_p(!(x))) { \
if (!(x)) { \
confirmIncorrectFact(); \
} \
} else { \
confirmFactFailed(); \
} \
} while (0)

Note that whether or not the compiler can confirm a claimed fact depends
on things like optimisation flags - that makes it all a bit fragile.
But you might find use for it.

(Of course __builtin_constant_p() is not portable beyond gcc, clang, and perhaps a few other compilers.)

And note that false statement implies everthing, so if your
'unreachable()' is wrong then there are unlimited possibilities
for unexpected behaviour.

Yes.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

[on learning Rust]

Quite often, when "fighting the borrow checker", typically because
I'm updating a complicated data structure in two locations at the
same time, I'll fall back to "write Fortran in Rust", with every
access indexed.

This is BTW one of those problems the brand new upcoming borrow
checker is supposed to be far better at figuring out: If I'm
updating totally separate parts of the same larger structure,
then it should be OK to mutate both at the same time.

I do realize that there are far more Rusty ways to solve this
type of issue, they just don't come naturally to me yet.

(Please excuse my pursuing this non-arch topic...)

Question for any Rusters in the group --

What is the best was to learn the Rust programming language?
Which books or other documents are the best introductory or
reference materials?

Disclaimer: My experience with Rust is more than zero but
not a lot more than zero.

My personal Rust journey has been driven by a desire to match or beat
the fastest known times for the Advent of Code puzzles, from 2015 to 2025.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

[on learning Rust]

Quite often, when "fighting the borrow checker", typically because
I'm updating a complicated data structure in two locations at the
same time, I'll fall back to "write Fortran in Rust", with every
access indexed.

This is BTW one of those problems the brand new upcoming borrow
checker is supposed to be far better at figuring out: If I'm
updating totally separate parts of the same larger structure,
then it should be OK to mutate both at the same time.

I do realize that there are far more Rusty ways to solve this
type of issue, they just don't come naturally to me yet.

(Please excuse my pursuing this non-arch topic...)

Question for any Rusters in the group --

What is the best was to learn the Rust programming language?
Which books or other documents are the best introductory or
reference materials?

Disclaimer: My experience with Rust is more than zero but
not a lot more than zero.

My personal Rust journey has been driven by a desire to match or
beat the fastest known times for the Advent of Code puzzles, from
2015 to 2025.

That's good to know but what is a good resource to learn the Rust
language? I've looked at the Rust book several times and each
time come away rather frustrated.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Waldek Hebisch) writes:

Stephen Fuld <[email protected]d> wrote:

It is obvious that you are right; the the existing choices as
documented in the standard and your post above (thanks for that)
don't permit what I want. I apologize for not recognizing that up
front. But I maintain that there should be a category that
essentially says "You can do what you want, but you must document
what you did." Furthermore, if such a choice existed, most
instances of undefined should be "reclassified" into that new
choice. I think that would aid programmers understanding.

In case of gcc 'ureachable()' can be given simple definition:
optimizer will assume that 'ureachable()' will never be
executed and do program transformations based on that knowledge.

Consder the following program fragment:

void foo1(int i) {
if (i < 0) {
unreachable();
}
foo2(i);
}

void foo2(int i) {
if (i < 0) {
foo3(i);
} else {
foo4(i);
}
}

In foo1 compiler could infer that 'i >= 0'. It could also inline
'foo2' into 'foo1'. After inlining it could infer that 'foo4'
will be called. So compiler could transform 'foo1' into

void foo1(int i) {
foo4(i);
}

If ever 'foo1' gets called with negative argument you would get
call to 'foo4' with negative argument.

Some people have mental model that C is compiled on statement by
statement basis. In compiler that is doing simple statement by
statement compilation 'if' in 'foo2' would prevent call to
'foo4' with negative argument. If compiler simply replaced
'unreachable()' by a trap instruction, then program would
trap in ;foo1'. But undefined behaviour opens essentially
unlimied possibilites for program transformation, based on
surrouding code.

BTW: I can image code using a macro

#define ASSERT_FACT(x) {if (x) unreachable();}

and codebase sprinkled with statements like:

ASSERT_FACT(i >= 0 && i < 100)

So 'unreachable()' essentially allows passing arbitrary assertions
to the compiler.

Let me add that given enough facts compiler should be able to
prove that all of them are true. It would be nice to have an
option so that compiler warns if it can not prove that some
'unreachable()' is really unreachable.

And note that false statement implies everthing, so if your
'unreachable()' is wrong then there are unlimited possibilities
for unexpected behaviour.

How is this reasoning affected by the change in definition of
undefined behavior in C23 (as compared for example with the
definitions in C11 or C99)?
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch <[email protected]> wrote:

Thomas Koenig <[email protected]> writes:

Bubblesort is the worst of non-joke sorting algorithms, see
the quote from Numerical Recipes...

For people who don't like bubble sort, or for inclusion in a set
of benchmarks, I suggest the following recently discovered
sorting algorithm (written in C-ish pseudocode):

void
baffle_sort( unsigned n, int *elements ){
for( unsigned i = 0; i < n; i++ ){
for( unsigned j = 0; j < n; j++ ){
if( elements[i] < elements[j] ){
/* exchange elements[i] and elements[j] */
}
}
}
}

(Disclaimer: not original.)

AFAICS this is very old "sorting by choice" algortim, just written
in inefficient way (using swaps and keeping running max in the
array instead of using extra variable).
--
Waldek Hebisch
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust
language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it
disillusioned.

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker.

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference
counting after all. However, the problem in this case is the usual
thing with type inference: There is so much going on that happens
automagically (in particular automatic dereferencing in Rust), and the
Rust compiler does not know where you went wrong, so the error message
is unhelpful (while for the simpler cases the compiler usually guesses
right and gives very helpful, to-the-point error messages).

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

Thomas Koenig <[email protected]> writes:

Bubblesort is the worst of non-joke sorting algorithms, see
the quote from Numerical Recipes...

For people who don't like bubble sort, or for inclusion in a set
of benchmarks, I suggest the following recently discovered
sorting algorithm (written in C-ish pseudocode):

void
baffle_sort( unsigned n, int *elements ){
for( unsigned i = 0; i < n; i++ ){
for( unsigned j = 0; j < n; j++ ){
if( elements[i] < elements[j] ){
/* exchange elements[i] and elements[j] */
}
}
}
}

(Disclaimer: not original.)

AFAICS this is very old "sorting by choice" algortim,

I suggest you look again. It is not a selection sort.

just written
in inefficient way (using swaps and keeping running max in the
array instead of using extra variable).

I am making no claim that this sort would be a good choice if
one wanted an efficient algorithm. Surely no one would choose
it on that basis. That's not what makes it interesting.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

[on learning Rust]

Quite often, when "fighting the borrow checker", typically because
I'm updating a complicated data structure in two locations at the
same time, I'll fall back to "write Fortran in Rust", with every
access indexed.

This is BTW one of those problems the brand new upcoming borrow
checker is supposed to be far better at figuring out: If I'm
updating totally separate parts of the same larger structure,
then it should be OK to mutate both at the same time.

I do realize that there are far more Rusty ways to solve this
type of issue, they just don't come naturally to me yet.

(Please excuse my pursuing this non-arch topic...)

Question for any Rusters in the group --

What is the best was to learn the Rust programming language?
Which books or other documents are the best introductory or
reference materials?

Disclaimer: My experience with Rust is more than zero but
not a lot more than zero.

My personal Rust journey has been driven by a desire to match or
beat the fastest known times for the Advent of Code puzzles, from
2015 to 2025.

That's good to know but what is a good resource to learn the Rust
language? I've looked at the Rust book several times and each
time come away rather frustrated.

I don't have any suggestions here, I tend to google any questions I
have, then follow those links that point into the Rust std lib.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch <[email protected]> wrote:

[email protected] (Waldek Hebisch) writes:

Stephen Fuld <[email protected]d> wrote:

It is obvious that you are right; the the existing choices as
documented in the standard and your post above (thanks for that)
don't permit what I want. I apologize for not recognizing that up
front. But I maintain that there should be a category that
essentially says "You can do what you want, but you must document
what you did." Furthermore, if such a choice existed, most
instances of undefined should be "reclassified" into that new
choice. I think that would aid programmers understanding.

In case of gcc 'ureachable()' can be given simple definition:
optimizer will assume that 'ureachable()' will never be
executed and do program transformations based on that knowledge.

Consder the following program fragment:

void foo1(int i) {
if (i < 0) {
unreachable();
}
foo2(i);
}

void foo2(int i) {
if (i < 0) {
foo3(i);
} else {
foo4(i);
}
}

In foo1 compiler could infer that 'i >= 0'. It could also inline
'foo2' into 'foo1'. After inlining it could infer that 'foo4'
will be called. So compiler could transform 'foo1' into

void foo1(int i) {
foo4(i);
}

If ever 'foo1' gets called with negative argument you would get
call to 'foo4' with negative argument.

Some people have mental model that C is compiled on statement by
statement basis. In compiler that is doing simple statement by
statement compilation 'if' in 'foo2' would prevent call to
'foo4' with negative argument. If compiler simply replaced
'unreachable()' by a trap instruction, then program would
trap in ;foo1'. But undefined behaviour opens essentially
unlimied possibilites for program transformation, based on
surrouding code.

BTW: I can image code using a macro

#define ASSERT_FACT(x) {if (x) unreachable();}

and codebase sprinkled with statements like:

ASSERT_FACT(i >= 0 && i < 100)

So 'unreachable()' essentially allows passing arbitrary assertions
to the compiler.

Let me add that given enough facts compiler should be able to
prove that all of them are true. It would be nice to have an
option so that compiler warns if it can not prove that some
'unreachable()' is really unreachable.

And note that false statement implies everthing, so if your
'unreachable()' is wrong then there are unlimited possibilities
for unexpected behaviour.

How is this reasoning affected by the change in definition of
undefined behavior in C23 (as compared for example with the
definitions in C11 or C99)?

I am not aware of any change that would affect reasoning above.
AFAICS wording defining undefined behaviour is essentially the
same. But there are many scattered changes mentioning undefined
behaviour, so I may have missed something important. Still,
the reasong above is valid even with quite limited definition
of undefined behaviour, namely that up to the point of
encountering 'unreachable()' observable behaviour agrees with
abstract machine. Once 'unreachable()' is encountered,
behaviour of abstract machine is no longer defined, so
program may continue doing anything. And if 'unreachable()'
is not encountered, then propagating conditional info is
valid. Of course, time travel gives additional possibilities
for optimization, but the example above respects casuality.
--
Waldek Hebisch
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

[...]

My personal Rust journey has been driven by a desire to match or
beat the fastest known times for the Advent of Code puzzles, from
2015 to 2025.

That's good to know but what is a good resource to learn the Rust
language? I've looked at the Rust book several times and each
time come away rather frustrated.

I don't have any suggestions here, I tend to google any questions I
have, then follow those links that point into the Rust std lib.

Okay. Kind of disappointing but thank you for the followup.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

David Brown <[email protected]> wrote:

On 25/09/2026 07:39, Anton Ertl wrote:

David Brown <[email protected]> writes:

On 21/09/2026 19:17, Anton Ertl wrote:

I referred to a specific paradoxical effect, not completely avoiding
all of them: The effect of programmers who, instead of working on
making the code faster through source-level changes, have to invest
time into avoiding getting it miscompiled.

By "miscompiled", do you mean incorrect object code, or object code that >>> did not have the performance the programmer expected or hoped for?

Code that behaves differently than intended, e.g., where a bounds check
is "optimized" away.

The trouble with that is determining precisely what was intended.
Compilers are limited - the programmer has to express their intention in
the restricted form of the programming language (C or whatever else).
And the /only/ things that can be relied on to have a clear meaning are things that have clear defined behaviour as documented by the language standards or the compiler documentation.

A program is a contract between the programmer and the compiler - the programmer promises to provide good code with a clearly defined meaning,
and the compiler promises to give object code that implements that
defined meaning. If the programmer breaks their side of the contract by writing code that does not have a clear meaning (at compile-time or run-time), the compiler /cannot/ fulfil its side of the contract. It is unable to generate "correct" object code from incorrect source code.

If the programmer writes "a = b + c;" (all signed int), what is the intention? Does the programmer mean "generate an ADD assembly
instruction"? Does he/she mean "I don't care how it happens, but 'a'
should be the sum of 'b' and 'c'"? Do they mean "give me a two's
complement wrapped addition"? Do they mean "I promise there will be no overflow" ? Do they mean "I /hope/ there will be no overflow" ? Or
"While I am debugging, let me know if there is an overflow" ?

The programmer might have intended lots of subtly different things from
the same bit of code. But compilers cannot work by mind-reading. The
only thing that the /code/ intends is "Add these two numbers. I promise there will be no overflow". Whatever the programmer imagines, that is
the intention of the code. The compiler's job is to follow that - and
if the programmer breaks his promise, it is garbage in, garbage out.

I find the whole concept of optimising based on "what the programmer intended", rather than what the code they wrote means, somewhat hypocritical. The idea that "a = b + c;" should "obviously" wrap on a
two's complement machine, while "a = b + 10 + c - 10;" should
"obviously" optimise away the constants is clearly contradictory. It is
an attitude that is denying responsibility - claiming "the compiler
broke my code" rather than understanding "my code had mistakes but previously gave the right results by luck".

I am not underestimating the difficulty of writing correct code here, or
the frustration and costs involved when the behaviour of real-world code changes with different compilers or flags. But it is critical that programmers understand the origin of problems in order to deal with the issues instead of passing the blame around. Baring compiler bugs (even
my favourite compiler has one or two outstanding bugs), what you term "miscompiling" here is actually errors in the programmers' source code.

The way to improve the situation is not by blaming compiler writers, or inventing some kind of vague notion of what programmers "intended" or
"do what some old compiler did", or limiting optimisations in compilers.
Instead, it is by improving compilers, run-time checkers and static analysis tools to help identify the errors in the source code, improving teaching of programming to reduce the risk of such errors, improving languages to support lower-risk constructs, changing to programming languages with different characteristics, etc. Indeed, I find that
better compilers with more powerful optimisations means fewer bugs in my code because I can write the code in clearer ways and still get
efficient results in the end.

Performance regressions can be nasty for performance-sensitive code,
and consume time for finding a workaround (if one can be found), but
is a different thing.

Agreed. And correctness trumps speed every time.

But as
for the problems you mention w.r.t UB, I think it's just the result of >>>>> poor semantics, for which I guess we (language semanticists) are partly >>>>> to blame: we have developed fairly good tools to design sane language >>>>> specs in general,

I violently disagree. The C89 standard (just to name one) is a
partial specification not because the original C standards people were >>>> poor at specifying semantics, but because given the differences
between the compilers out there and the hardware out there, the
easiest way to reach a consensus is to leave some parts unspecified.

I have never spoken to the C standards committee or writers, either of
current standard versions or the original C89 standard, or writers of
pre-standard C specifications. So I cannot in any way claim to know
their thoughts or motivations. I also have not seen any documentation
that suggests what they might have thought about "optimisation on the
assumption that undefined behaviour does not occur" - in either
direction.

When C89 was developed, the dominating C compiler in the Unix world
was PCC. GCC came on the scene late in the game (1988), without such
assumptions and produced a significant performance advantage. Only
after several years of heavy gcc development assumptions like
-fstrict-aliasing were introduced around gcc-2.7 (which was initially
disabled by default);

("-fstrict-aliasing" is still not enabled by default - you have to
actively enable at least "-O2".)

I don't know when the assumption that signed
integer operations do not overflow was introduced, and initially it
could not be disabled (-fwrapv was added around gcc-3.4), so obviously
by that time people had taken over the gcc project who had a different
view about how undefined behaviour should be treated.

I completely disagree that this is an "obvious" conclusion. While I
cannot say anything for sure here, the explanation that comes first to
my mind is that it was part of the natural progression of gcc towards
more optimisations.

"-fwrapv" would have been added as a result of complaints about
problems with old code that made invalid assumptions that happened
to "work" because older gcc did not have as many optimisations.

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it
was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv"
would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

In hindsight, though, it would have been easy enough to use unsigned
arithmetic within GCC to support gcj.

I see absolutely no reason to assume that anyone at any time thought
such optimisations were not valid - they simply had not yet been
implemented.

I agree.

Andrew.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 04/10/2026 10:15, [email protected]d wrote:

David Brown <[email protected]> wrote:

On 25/09/2026 07:39, Anton Ertl wrote:

<snip>

I don't know when the assumption that signed
integer operations do not overflow was introduced, and initially it
could not be disabled (-fwrapv was added around gcc-3.4), so obviously
by that time people had taken over the gcc project who had a different
view about how undefined behaviour should be treated.

I completely disagree that this is an "obvious" conclusion. While I
cannot say anything for sure here, the explanation that comes first to
my mind is that it was part of the natural progression of gcc towards
more optimisations.

"-fwrapv" would have been added as a result of complaints about
problems with old code that made invalid assumptions that happened
to "work" because older gcc did not have as many optimisations.

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it
was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv"
would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Thanks for that historical information - I had no idea that the
implementation of Java was behind that feature of gcc. There are plenty
of features (compiler flags, and extensions) of gcc that came about as
the result of support of languages other than C and C++. But I did not
know about this one.

In hindsight, though, it would have been easy enough to use unsigned arithmetic within GCC to support gcj.

Yes - there's nothing that I can think of where the effect of "-fwrapv"
could not be achieved with equal run-time efficiency by using unsigned
types and some casts or other conversions. But if you need wrapping
signed integer overflow semantics, then it is obviously neater in the
source code to have it directly than to go via unsigned types.

I see absolutely no reason to assume that anyone at any time thought
such optimisations were not valid - they simply had not yet been
implemented.

I agree.

Andrew.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected]d <[email protected]d> schrieb:

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it
was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv"
would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Linear congruential random number generators, in common use when
the dinosaurs roamed the computer centers, depend on wraparound
semantics. In gfortran, they stopped working at one time because
gcc assuming that this would not happen. -fwrap is a workaround
(without changing the source), but of course using the RANDOM_NUMBER
intrinsic is better - it also uses a reasonable algorithm.

So, some people should probably be grateful to you :-)
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 04/10/2026 16:16, Thomas Koenig wrote:

[email protected]d <[email protected]d> schrieb:

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it
was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv"
would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Linear congruential random number generators, in common use when
the dinosaurs roamed the computer centers, depend on wraparound
semantics. In gfortran, they stopped working at one time because
gcc assuming that this would not happen. -fwrap is a workaround
(without changing the source), but of course using the RANDOM_NUMBER intrinsic is better - it also uses a reasonable algorithm.

So, some people should probably be grateful to you :-)

Do unsigned types in Fortran not have wrapping semantics? Or are there
no unsigned integer types in Fortran? I know not every language has the
same distinction as C here.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

David Brown <[email protected]> schrieb:

On 04/10/2026 16:16, Thomas Koenig wrote:

[email protected]d <[email protected]d> schrieb:

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it
was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv"
would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Linear congruential random number generators, in common use when
the dinosaurs roamed the computer centers, depend on wraparound
semantics. In gfortran, they stopped working at one time because
gcc assuming that this would not happen. -fwrap is a workaround
(without changing the source), but of course using the RANDOM_NUMBER
intrinsic is better - it also uses a reasonable algorithm.

So, some people should probably be grateful to you :-)

Do unsigned types in Fortran not have wrapping semantics? Or are there
no unsigned integer types in Fortran? I know not every language has the same distinction as C here.

The Fortran language has no unsigned types. Two compilers, gfortran
and flang, implement a suggestion that I made to J3 (much improved
by some people on the committee) and was accepted, but not taken
up by WG5. At the time, I had already started implementing it,
so I went ahead and completed it anyway, see

https://gcc.gnu.org/onlinedocs/gfortran/Unsigned-integers.html

(You can probably tell that this is still a sore point.)

But what the pseudo-random number generators did was use *signed*
overflow, which had been prohibited by the standard forever, but
because people needed something and it worked, they went ahead
and did it anyway.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 04/10/2026 19:46, Thomas Koenig wrote:

David Brown <[email protected]> schrieb:

On 04/10/2026 16:16, Thomas Koenig wrote:

[email protected]d <[email protected]d> schrieb:

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it
was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv"
would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Linear congruential random number generators, in common use when
the dinosaurs roamed the computer centers, depend on wraparound
semantics. In gfortran, they stopped working at one time because
gcc assuming that this would not happen. -fwrap is a workaround
(without changing the source), but of course using the RANDOM_NUMBER
intrinsic is better - it also uses a reasonable algorithm.

So, some people should probably be grateful to you :-)

Do unsigned types in Fortran not have wrapping semantics? Or are there
no unsigned integer types in Fortran? I know not every language has the
same distinction as C here.

The Fortran language has no unsigned types. Two compilers, gfortran
and flang, implement a suggestion that I made to J3 (much improved
by some people on the committee) and was accepted, but not taken
up by WG5. At the time, I had already started implementing it,
so I went ahead and completed it anyway, see

https://gcc.gnu.org/onlinedocs/gfortran/Unsigned-integers.html

(You can probably tell that this is still a sore point.)

But what the pseudo-random number generators did was use *signed*
overflow, which had been prohibited by the standard forever, but
because people needed something and it worked, they went ahead
and did it anyway.

I would guess you'd have trouble writing something that was efficient
here, and avoided UB when you don't have language support for wrapping overflow (whether it be for signed or unsigned types).

Thanks for the explanation. I can't imagine I'll ever work with
Fortran, but it's nice to know more about it anyway.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables. >>>>

In Rust, the only acceptable array index is of type "usize", which is
effectively the same as u64 on most platforms these days, but does not >>>> need to be so: On a 32-bit target, it would be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such indices
are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

But given that the checks are put in by the compiler, it seems
rather silly to insist that index expressions have type usize,
especially when a common remedy is just to add a cast. It's like
saying the car won't start unless you take off your seatbelt.

I don't know why you would say that. The point is that Rust is
strongly, statically typed and the type of an arrray index is
well-defined as `usize`. Being intentional in what one writes
is an important aspect of being a proficient Rust programmer.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Michael S <[email protected]> wrote:

On Wed, 30 Sep 2026 13:57:24 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

[snip]
My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

Beginning Rust programmers tend to go through a few phases,
particularly if coming from a language like C. "Fighting the
Borrow Checker" is well-known; "traits are awesome; let's use
them everywhere!" is another.

I didn't reach the second stage. Not sure about first.

When I started programming in Rust, most of my immediate
colleagues and I had terribly little experience in the language.
We were excited about the its potential benefits, but realized
it would take a few months to build up a sufficient level of
familiarity to use it skillfully. One quipped, "this language
has a near-vertical learning curve."

IMHO, he is correct.
Rust is certainly the hardest to learn out of computer languges that I
ever tried that I would not call idiotic.

She, actually, but yes. I guess it depends on one's background,
but in general if you are coming from many years of experience
in languages like C or C++, Rust can be a real slog. I've seen
some anecdotal reports that teaching it to programming neophytes
as a first language is actually quite productive.

At one point a coworker (self-deprecatingly) said, "look, I'm
writing crust! C in Rust syntax!" Everyone thought this was a
great play on words, but he was correct: the programs we were
writing were essentially C programs, just expressed in Rust. We
quickly adopted that to describe our still naive code: it wasn't
an insult, just an expression that we were still coming to terms
with a new way of doing things. Some of the hallmarks of that
included using the wrong paradigms (and types!) for lots of our
code.

I'd be curious to know more about your program.

The program was an implementation scalable flood fill algorithm (i.e.
one with much better than typical worst case BigO properties, both for
speed and for space) together with test benches for correctness and
speed. As you could guess, I didn't really wrote it in Rust. It was a >non-literal port from C. The purpose of translation was two-fold:
improvement of my knowledge of Rust and getting better feel for cost of >mandatory bound checking for one particular sort of data structures.

So mandatory bounds checking will usually be compiled out in
optimized builds; you can choose to keep it in, but most don't.

Before doing Rust port I did port to Golang. Unlike for Rust, where I
only read The Book and went trough part of tutorial, I had small
previous practical experience in Go, but it was not very recent. Still,
the difference in my productivity was huge. In favor of Go, of course.

Indeed. Sometimes I find Go far more productive, and other times
Rust. It really depends on the category of problem I am working
on.

I've written
several hundred kloc of Rust at this point, and while what I
write may be terribly specialized, I rarely find myself indexing
an array; often, I'm using iterators or some other abstraction
for that kind of thing. If that was the one program you have
written in Rust, my _guess_ is that you were using paradigms
appropriate to a different language, which is why you felt you
needed to reach for casts to index an array so frequently.

Again, that's not a comment on your program, so much as
suggesting an impedence mismatch between what you wrote and how
one would generally expect to use the language.

In general, I think a person's experience writing a single
program tells us very little.

I never pretended otherwise.

No I know, but at least one other reader appeared to.

Although I don't see how one can avoid
cast if one wants to use indices that originate in signed domain. Or,
as was often a case in this particular program, in domain of narrower >unsigned integers.

Well, for narrower to wider unsigned types, there is `into()`.
Depending on what you were using for the underlying collection,
there is also the `std::ops::Index` trait that you could `impl`
for index types other than `usize`, and container types other
than primitive arrays and slices.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <119jbt5$cn3a$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

[snip]
My only Rust program was full of casts of various integer types to
usize. Exactly for the purpose of array indexing.

Beginning Rust programmers tend to go through a few phases,
particularly if coming from a language like C. "Fighting the
Borrow Checker" is well-known; "traits are awesome; let's use
them everywhere!" is another.

When I started programming in Rust, most of my immediate
colleagues and I had terribly little experience in the language.
We were excited about the its potential benefits, but realized
it would take a few months to build up a sufficient level of
familiarity to use it skillfully. One quipped, "this language
has a near-vertical learning curve."

At one point a coworker (self-deprecatingly) said, "look, I'm
writing crust! C in Rust syntax!" Everyone thought this was a
great play on words, but he was correct: the programs we were
writing were essentially C programs, just expressed in Rust. We
quickly adopted that to describe our still naive code: it wasn't
an insult, just an expression that we were still coming to terms
with a new way of doing things. Some of the hallmarks of that
included using the wrong paradigms (and types!) for lots of our
code.

I have definitely noted this in my own code, crust is a good name for it.

Quite often, when "fighting the borrow checker", typically because I'm >updating a complicated data structure in two locations at the same time, >I'll fall back to "write Fortran in Rust", with every access indexed.

I myself have done this on more than one occasion; it's a quick
way to get going. When I wrote the rxv64 operating system, for
instance, and got to the part where I was implementing a 6th Ed
Unix-style buffer cache, and needed a doubly linked list, I
ended up using an array as a proxy, with next and prev indices
instead of pointers. The cache in simple systems is fixed sized
anyway, so it wasn't a major imposition.

This is BTW one of those problems the brand new upcoming borrow checker
is supposed to be far better at figuring out: If I'm updating totally >separate parts of the same larger structure, then it should be OK to
mutate both at the same time.

Yes, Polonius (named for the character from Hamlet). It is now
in Alpha in nightly rustc builds.

https://blog.rust-lang.org/2026/08/04/enabling-polonius-alpha-on-nightly/

I do realize that there are far more Rusty ways to solve this type of
issue, they just don't come naturally to me yet.

Things like Cell, RefCell, etc, supporting interior mutability
are the usual solutions to things like that.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

[on learning Rust]

Quite often, when "fighting the borrow checker", typically because
I'm updating a complicated data structure in two locations at the
same time, I'll fall back to "write Fortran in Rust", with every
access indexed.

This is BTW one of those problems the brand new upcoming borrow
checker is supposed to be far better at figuring out: If I'm
updating totally separate parts of the same larger structure,
then it should be OK to mutate both at the same time.

I do realize that there are far more Rusty ways to solve this
type of issue, they just don't come naturally to me yet.

(Please excuse my pursuing this non-arch topic...)

Question for any Rusters in the group --

What is the best was to learn the Rust programming language?
Which books or other documents are the best introductory or
reference materials?

Disclaimer: My experience with Rust is more than zero but
not a lot more than zero.

Without knowing what methods you have tried, what books you have
already explored, what you found dissatisfying about them, and
why, it is impossible to give you a good answer.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust
language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it >disillusioned.

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

I think what you mean to say is that you couldn't find a way to
implement that in the manner you were accustomed to thinking
about the problem, given your prior experience. But that is
separate from whether it can be done or not.

In fact, in Rust you can use the approximately the same
techniques you would use in Pascal, C, or (probably) Forth: raw
pointers are a part of the language, and you can simply use them
with `unsafe` code, and it would be no more "unsafe" than in C
or Pascal. One might argue that that defeats the purpose of the
language, and you'd be right to a point. The difference is that
in C or Pascal, the entire program is what Rust would call
"unsafe", whereas generally this can be restricted to just a few
lines of carefully audited code in Rust.

FWIW, for things like containers of various kinds (trees, hash
tables, linked-lists, growable arrays, etc), production programs
usually use an existing library or crate instead of rolling
their own.

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker.

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference >counting after all. However, the problem in this case is the usual
thing with type inference: There is so much going on that happens >automagically (in particular automatic dereferencing in Rust), and the
Rust compiler does not know where you went wrong, so the error message
is unhelpful (while for the simpler cases the compiler usually guesses
right and gives very helpful, to-the-point error messages).

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Sounds like you're in what we'd call the, "fighting the borrow
checker" stage. It may be that you end up really not liking
Rust or feeling that other languages are better, but I wager
that just about anyone who has seriously used the language has
gone through similar things.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2026-10-05 14:36, Dan Cross wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables. >>>>>

In Rust, the only acceptable array index is of type "usize", which is >>>>> effectively the same as u64 on most platforms these days, but does not >>>>> need to be so: On a 32-bit target, it would be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such indices
are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

But given that the checks are put in by the compiler, it seems
rather silly to insist that index expressions have type usize,
especially when a common remedy is just to add a cast. It's like
saying the car won't start unless you take off your seatbelt.

I don't know why you would say that. The point is that Rust is
strongly, statically typed and the type of an arrray index is
well-defined as `usize`. Being intentional in what one writes
is an important aspect of being a proficient Rust programmer.

The Ada language and its relatives are, arguably, even more strongly
typed in the array-indexing area, because different array types can have different index types, and the declaration of an array type also
specifies the type of the index. When combined with range-constrained
types and subtypes, this means that the bounds check can often be done statically, at compile time, and the remaining run-time checks (if any)
are usually not significant for performance.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

Thomas Koenig <[email protected]> writes:

Bubblesort is the worst of non-joke sorting algorithms, see
the quote from Numerical Recipes...

For people who don't like bubble sort, or for inclusion in a set
of benchmarks, I suggest the following recently discovered
sorting algorithm (written in C-ish pseudocode):

void
baffle_sort( unsigned n, int *elements ){
for( unsigned i = 0; i < n; i++ ){
for( unsigned j = 0; j < n; j++ ){
if( elements[i] < elements[j] ){
/* exchange elements[i] and elements[j] */
}
}
}
}

(Disclaimer: not original.)

AFAICS this is very old "sorting by choice" algortim,

I suggest you look again. It is not a selection sort.

just written
in inefficient way (using swaps and keeping running max in the
array instead of using extra variable).

I am making no claim that this sort would be a good choice if
one wanted an efficient algorithm. Surely no one would choose
it on that basis. That's not what makes it interesting.

This whole thread is probably better in something like
comp.programming.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch <[email protected]> wrote:

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

Thomas Koenig <[email protected]> writes:

Bubblesort is the worst of non-joke sorting algorithms, see
the quote from Numerical Recipes...

For people who don't like bubble sort, or for inclusion in a set
of benchmarks, I suggest the following recently discovered
sorting algorithm (written in C-ish pseudocode):

void
baffle_sort( unsigned n, int *elements ){
for( unsigned i = 0; i < n; i++ ){
for( unsigned j = 0; j < n; j++ ){
if( elements[i] < elements[j] ){
/* exchange elements[i] and elements[j] */
}
}
}
}

(Disclaimer: not original.)

AFAICS this is very old "sorting by choice" algortim,

I suggest you look again. It is not a selection sort.

Yes, you are right. First pass seclecting maximal element is
like selection sort, the other passes work as insertion sort.

just written
in inefficient way (using swaps and keeping running max in the
array instead of using extra variable).

I am making no claim that this sort would be a good choice if
one wanted an efficient algorithm. Surely no one would choose
it on that basis. That's not what makes it interesting.

Probably the most interestiong thing about it is that it actually
sorts. As a benchmork it could be useful to assess quality of
compiler removal of useless code. I suspect that currently no
compiler is able to remove useless half of this code, also
probably can not optimize sequence of swaps to array shift. But
those are not far from what is alreade done.
--
Waldek Hebisch
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

David Brown <[email protected]> wrote:

On 04/10/2026 19:46, Thomas Koenig wrote:

David Brown <[email protected]> schrieb:

On 04/10/2026 16:16, Thomas Koenig wrote:

[email protected]d <[email protected]d> schrieb:

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it >>>>> was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv" >>>>> would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Linear congruential random number generators, in common use when
the dinosaurs roamed the computer centers, depend on wraparound
semantics. In gfortran, they stopped working at one time because
gcc assuming that this would not happen. -fwrap is a workaround
(without changing the source), but of course using the RANDOM_NUMBER
intrinsic is better - it also uses a reasonable algorithm.

So, some people should probably be grateful to you :-)

Do unsigned types in Fortran not have wrapping semantics? Or are there
no unsigned integer types in Fortran? I know not every language has the >>> same distinction as C here.

The Fortran language has no unsigned types. Two compilers, gfortran
and flang, implement a suggestion that I made to J3 (much improved
by some people on the committee) and was accepted, but not taken
up by WG5. At the time, I had already started implementing it,
so I went ahead and completed it anyway, see

https://gcc.gnu.org/onlinedocs/gfortran/Unsigned-integers.html

(You can probably tell that this is still a sore point.)

But what the pseudo-random number generators did was use *signed*
overflow, which had been prohibited by the standard forever, but
because people needed something and it worked, they went ahead
and did it anyway.

I would guess you'd have trouble writing something that was efficient
here, and avoided UB when you don't have language support for wrapping overflow (whether it be for signed or unsigned types).

If language supports large enough integers and with reasonable
optimizer code like:

bigint a = 123;
bigint b = 7;
bigint c = 17;
long f() {
a = 0xffffffffffffffff &(a*c + b);
return a;
}

will be compiled using wrapping 64-bit arithmetic. If additionaly
you make sure that a is local to random number module so compiler
knows that it has seen all updates to a, and updates stay within
64 bits than compiler can use 64-bit variables.

But having explicit wrapping types is more direct and easier to
implement, which mattered for dinosaurs.
--
Waldek Hebisch
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

Thomas Koenig <[email protected]> writes:
void
baffle_sort( unsigned n, int *elements ){
for( unsigned i = 0; i < n; i++ ){
for( unsigned j = 0; j < n; j++ ){
if( elements[i] < elements[j] ){
/* exchange elements[i] and elements[j] */
}
}
}
}

...

Probably the most interestiong thing about it is that it actually
sorts. As a benchmork it could be useful to assess quality of
compiler removal of useless code. I suspect that currently no
compiler is able to remove useless half of this code, also
probably can not optimize sequence of swaps to array shift. But
those are not far from what is alreade done.

Given that gcc and clang do not optimize the sequence of swaps in the
bubble sort component of John Hennesseys stan.c benchmark collection
from the early 1980s into array rotation, I would not expect it to
happen for the above, especially given that elements[i] and
elements[j] can and regularly will alias. Ok, the compiler can infer
that no swap happens in this case, and split the inner loop into a
0..i-1 one and an i+1..n-1 one, but doing that is more involved than I
expect and have experienced from compiler optimizations for
"irrelevant" code.

For comparison, the inner loop of the bubble-sort benchmark in stan.c
is:

i=1;
while ( i<top ) {
if ( sortlist[i] > sortlist[i+1] ) {
j = sortlist[i];
sortlist[i] = sortlist[i+1];
sortlist[i+1] = j;
};
i=i+1;
};

I see fewer hurdles in optimizing that than the inner loop of
baffle_sort(), but it does not happen.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 06/10/2026 04:17, Waldek Hebisch wrote:

David Brown <[email protected]> wrote:

On 04/10/2026 19:46, Thomas Koenig wrote:

David Brown <[email protected]> schrieb:

On 04/10/2026 16:16, Thomas Koenig wrote:

[email protected]d <[email protected]d> schrieb:

"-fwrapv" didn't exist when we started gcj, which used GCC to
implement Java. After some discussion with other GCC maintainers, it >>>>>> was agreed to add wrapping signed integer semantics to GCC's IR.
"-fwrapv" provides that to C-derived languages too. Whether "-fwrapv" >>>>>> would have happened without the pull from gcj I can't say. It's
impossible to rerun history.

Linear congruential random number generators, in common use when
the dinosaurs roamed the computer centers, depend on wraparound
semantics. In gfortran, they stopped working at one time because
gcc assuming that this would not happen. -fwrap is a workaround
(without changing the source), but of course using the RANDOM_NUMBER >>>>> intrinsic is better - it also uses a reasonable algorithm.

So, some people should probably be grateful to you :-)

Do unsigned types in Fortran not have wrapping semantics? Or are there >>>> no unsigned integer types in Fortran? I know not every language has the >>>> same distinction as C here.

The Fortran language has no unsigned types. Two compilers, gfortran
and flang, implement a suggestion that I made to J3 (much improved
by some people on the committee) and was accepted, but not taken
up by WG5. At the time, I had already started implementing it,
so I went ahead and completed it anyway, see

https://gcc.gnu.org/onlinedocs/gfortran/Unsigned-integers.html

(You can probably tell that this is still a sore point.)

But what the pseudo-random number generators did was use *signed*
overflow, which had been prohibited by the standard forever, but
because people needed something and it worked, they went ahead
and did it anyway.

I would guess you'd have trouble writing something that was efficient
here, and avoided UB when you don't have language support for wrapping
overflow (whether it be for signed or unsigned types).

If language supports large enough integers and with reasonable
optimizer code like:

bigint a = 123;
bigint b = 7;
bigint c = 17;
long f() {
a = 0xffffffffffffffff &(a*c + b);
return a;
}

will be compiled using wrapping 64-bit arithmetic. If additionaly
you make sure that a is local to random number module so compiler
knows that it has seen all updates to a, and updates stay within
64 bits than compiler can use 64-bit variables.

But having explicit wrapping types is more direct and easier to
implement, which mattered for dinosaurs.

Begin direct and easier to write matters to us non-dinosaurs too!

Yes, such "bigint" code should give you correct answers, but
optimisation is not going to be guaranteed. It is likely that you are
going to need a lot of mask operations in your code - its going to be
ugly, or have to use inline functions where infix operators would be
nicer. (Does Fortran have classes with overloaded operators, like C++?)
There are certainly good optimising Fortran compilers.



--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust >>>language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it >>disillusioned.

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

I think what you mean to say is that you couldn't find a way to
implement that in the manner you were accustomed to thinking
about the problem, given your prior experience.

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);
struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these
languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of
code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1)
(but the root still has to be handled separately), but it performs
several writes instead of just one, and the recursion is not a tail
recursion, so is relatively expensive.

I wanted something with the benefits of the Pascal/C/Forth variant,
not something like the Java variants. I don't know if that counts as
"manner you were accustomed to thinking about the problem".

And I learned this technique in Pascal or Modula-2 (probably from one
of Wirth's books), and had no problem transferring the knowledge into
C or Forth, on the contrary: In C and Forth I could turn search into a
loop (in Pascal it has to be a tail-recursive function, because you
can only produce references to variables and fields through reference parameters).

For a language that aspires to take over from C for systems
programming, I expect that one can use this technique, too.

But that is separate from whether it can be done or not.

Sure, and as I found out later, it can be done.

In fact, in Rust you can use the approximately the same
techniques you would use in Pascal, C, or (probably) Forth: raw
pointers are a part of the language, and you can simply use them
with `unsafe` code, and it would be no more "unsafe" than in C
or Pascal. One might argue that that defeats the purpose of the
language, and you'd be right to a point. The difference is that
in C or Pascal, the entire program is what Rust would call
"unsafe", whereas generally this can be restricted to just a few
lines of carefully audited code in Rust.

Given that I do not understand the automagic stuff done by the Rust
compiler enough to get this kind of tree insertion past the borrow
checker, even though it is possible, I don't trust my capabilities to
audit unsafe Rust.

FWIW, for things like containers of various kinds (trees, hash
tables, linked-lists, growable arrays, etc), production programs
usually use an existing library or crate instead of rolling
their own.

When I saw that this technique cannot be implemented in Java, I
wondered why Java was not having references to fields (answer:
probably because that would make garbage collection more costly and/or
less precise), that this technique is needed for relatively few
things, mostly stuff that's in libraries. And I wondered how these
library methos are implemented (at one point I guessed that they
implemented these parts of their libraries in C, but when I actually
look, the implementation of what I looked at was in Java, IIRC along
the lines of 1)).

For a language that aspires to replace C for systems programming,
giving the Java answer is not good enough, though.

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker.

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference >>counting after all. However, the problem in this case is the usual
thing with type inference: There is so much going on that happens >>automagically (in particular automatic dereferencing in Rust), and the
Rust compiler does not know where you went wrong, so the error message
is unhelpful (while for the simpler cases the compiler usually guesses >>right and gives very helpful, to-the-point error messages).

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Sounds like you're in what we'd call the, "fighting the borrow
checker" stage. It may be that you end up really not liking
Rust or feeling that other languages are better, but I wager
that just about anyone who has seriously used the language has
gone through similar things.

I wonder about that. From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was
added later, as a convenience for the programmers who already knew the language. So the Rust programmers of the early days formed a mental
model based on "Pedestrian Rust" (i.e., with less automagic), and when
they see a program with more automagic, and need to understand some conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern
language. There are hints in the books I read, but not enough to get
a firm foundation.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

[email protected] (Waldek Hebisch) writes:

Tim Rentsch <[email protected]> wrote:

Thomas Koenig <[email protected]> writes:

Bubblesort is the worst of non-joke sorting algorithms, see
the quote from Numerical Recipes...

For people who don't like bubble sort, or for inclusion in a set
of benchmarks, I suggest the following recently discovered
sorting algorithm (written in C-ish pseudocode):

void
baffle_sort( unsigned n, int *elements ){
for( unsigned i = 0; i < n; i++ ){
for( unsigned j = 0; j < n; j++ ){
if( elements[i] < elements[j] ){
/* exchange elements[i] and elements[j] */
}
}
}
}

(Disclaimer: not original.)

[...]

I am making no claim that this sort would be a good choice if
one wanted an efficient algorithm. Surely no one would choose
it on that basis. That's not what makes it interesting.

Probably the most interestiong thing about it is that it actually
sorts.

That it actually sorts is I think the most surprising thing.

What I found most interesting is how it sorts or why it sorts. It
took me a while to understand what makes it work. It is difficult,
for example, to write invariants for this code that can be used to
establish the conclusion that sorting actually takes place. A
better name than baffle_sort() might be least_transparent_sort().
But that would ruin the surprise. ;)
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Anton Ertl) writes:

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust
language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it disillusioned.

Yes, that's the book I meant.

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker. [discovered later not to be necessary]

I think this test case is a good one. Somewhat disappointing that
Rust makes it non-obvious. Do you know if what you learned would
carry over to, for example, AVL trees?

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference counting after all.

Thank you for this reference. I am just starting to look it over.
Do you know if there is a PDF version somewhere rather than the endless-series-of-webpages format shown on its website?

However, the problem in this case is the usual
thing with type inference: There is so much going on that happens automagically (in particular automatic dereferencing in Rust), and the
Rust compiler does not know where you went wrong, so the error message
is unhelpful (while for the simpler cases the compiler usually guesses
right and gives very helpful, to-the-point error messages).

Hmm. That might be worth my while doing some web research for.

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Can I ask how much experience you have with ML-style languages
(e.g., ML, OCaml, Haskell)? I'm wondering how the type inference in
Rust compares to the type inference done in those languages.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Tim Rentsch <[email protected]> writes: >[email protected] (Anton Ertl) writes:

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker. [discovered later not to be necessary]

I think this test case is a good one. Somewhat disappointing that
Rust makes it non-obvious. Do you know if what you learned would
carry over to, for example, AVL trees?

What I learned? No. I did not really learn it. I saw how I could
modify an example from the book to achieve what I want, and understood
the explanation of that example, but I do not know how to use this
stuff to build code from scratch.

Whether it is possible to do AVL trees in safe Rust without resorting
to reference-counting and such? Maybe, but I guess there are too many
mutable references around in AVL tree operations at the same time.

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference
counting after all.

...

Do you know if there is a PDF version somewhere rather than the >endless-series-of-webpages format shown on its website?

I don't know, but I would expect it. The way it looks, it seems to
use some software for books in multiple formats.

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Can I ask how much experience you have with ML-style languages
(e.g., ML, OCaml, Haskell)? I'm wondering how the type inference in
Rust compares to the type inference done in those languages.

A little with Miranda and Haskell (Hugs), and the latter is the reason
why I have this opinion of type inference: You get a long error
message that tells you that there is some inconsistency in the
inferred types; because the types are inferred from a significant
stretch of code, the problem could be anywhere in this code.

My impression is that in Rust you tend to nail down things more often
than in Haskell, so the stretches are shorter, but there is more
automagic going on in Rust, with automatic defererencing and
referencing, automatic dropping, etc., and the borrow checker
interacts with the automagic, which makes it at least as hard to deal
with as th Haskell type inference.

For Haskell I can at least make types explicit at various places to
reduce the area where the error might hide, but in Rust I have no way
to disable the automagic, and no way (or at least I don't know it) to
tell the borrow checker what I think it should be seeing, such that it
can tell me where my error is.

I have investigated some tool that IIRC rewrite the Rust program to
give more information about how it understands the program, but at
least for my test case, it was not enlightening.

As for the type system, a friend told me that he likes Rust because it
gives him what he likes about Haskell's type system in an imperative
language.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Dan Cross wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables. >>>>>

In Rust, the only acceptable array index is of type "usize", which is >>>>> effectively the same as u64 on most platforms these days, but does not >>>>> need to be so: On a 32-bit target, it would be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such indices
are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

That's what I assumed, except I check my assumptions by godbolt'ing my
code, using -O -C "target_cpu=native" to get a bleeding edge optimized
build, and that's where I saw a loop which started with

while pos+7 < input.len() {
... here a bunch of accesses to input[p], input[p+1]...input[p+6]
}

Every one of those secodnary accesses were very obviously tested against
the input length (stored in a register for the duration)

I considered reporting this as a very clear performance bug!

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Tue, 06 Oct 2026 05:01:32 -0700, Tim Rentsch
<[email protected]> wrote:

[email protected] (Anton Ertl) writes:

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference
counting after all.

Thank you for this reference. I am just starting to look it over.
Do you know if there is a PDF version somewhere rather than the >endless-series-of-webpages format shown on its website?

At the upper right are controls to go to the GIT repository or "print"
the book as rendered. BUt it seems that if you print/save you'll lose
the table of contents.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

George Neuner <[email protected]> writes:

On Tue, 06 Oct 2026 05:01:32 -0700, Tim Rentsch
<[email protected]> wrote:

[email protected] (Anton Ertl) writes:

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference
counting after all.

Thank you for this reference. I am just starting to look it over.
Do you know if there is a PDF version somewhere rather than the
endless-series-of-webpages format shown on its website?

At the upper right are controls to go to the GIT repository or "print"
the book as rendered. BUt it seems that if you print/save you'll lose
the table of contents.

Okay great. Thank you.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

What I found most interesting is how it sorts or why it sorts. It
took me a while to understand what makes it work. It is difficult,
for example, to write invariants for this code that can be used to
establish the conclusion that sorting actually takes place.

Indeed, mostly because the first iteration (i=0) is completely different
from the other ones: the swaps that take place happen only when

i > j or i == 0

So only the first iteration of the outer loop really works on the whole
array. The subsequent ones do nothing once j > i.


=== Stefan
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Anton Ertl) writes:

Tim Rentsch <[email protected]> writes:

[email protected] (Anton Ertl) writes:

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker. [discovered later not to be necessary]

I think this test case is a good one. Somewhat disappointing that
Rust makes it non-obvious. Do you know if what you learned would
carry over to, for example, AVL trees?

What I learned? No. I did not really learn it. I saw how I could
modify an example from the book to achieve what I want, and understood
the explanation of that example, but I do not know how to use this
stuff to build code from scratch.

Whether it is possible to do AVL trees in safe Rust without resorting
to reference-counting and such? Maybe, but I guess there are too many mutable references around in AVL tree operations at the same time.

A simple search tree can do insertion only at the leaves. Other
binary tree insertion methods typically modify interior nodes, and
certainly AVL trees fall in this category. Except for the difference
of leaf-node-only modification and interior-node modification, I
don't see why they should be any different. Is there something
about the Rust-safe code that you wrote that depends on modifying
only leaf nodes?

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference
counting after all.

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Can I ask how much experience you have with ML-style languages
(e.g., ML, OCaml, Haskell)? I'm wondering how the type inference in
Rust compares to the type inference done in those languages.

A little with Miranda and Haskell (Hugs), and the latter is the reason
why I have this opinion of type inference: You get a long error
message that tells you that there is some inconsistency in the
inferred types; because the types are inferred from a significant
stretch of code, the problem could be anywhere in this code.

My impression is that in Rust you tend to nail down things more often
than in Haskell, so the stretches are shorter, but there is more
automagic going on in Rust, with automatic defererencing and
referencing, automatic dropping, etc., and the borrow checker
interacts with the automagic, which makes it at least as hard to deal
with as th Haskell type inference.

For Haskell I can at least make types explicit at various places to
reduce the area where the error might hide, but in Rust I have no way
to disable the automagic, and no way (or at least I don't know it) to
tell the borrow checker what I think it should be seeing, such that it
can tell me where my error is.

I have investigated some tool that IIRC rewrite the Rust program to
give more information about how it understands the program, but at
least for my test case, it was not enlightening.

As for the type system, a friend told me that he likes Rust because it
gives him what he likes about Haskell's type system in an imperative language.

Very interesting. Thank you for the long explanation. I am curious to
know more but comp.arch is not the right place for that discussion so
I will stop here (and perhaps continue in a better choice of forum).
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <11a3ofn$2ak3s$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables. >>>>>>

In Rust, the only acceptable array index is of type "usize", which is >>>>>> effectively the same as u64 on most platforms these days, but does not >>>>>> need to be so: On a 32-bit target, it would be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such indices >>>> are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

That's what I assumed, except I check my assumptions by godbolt'ing my
code, using -O -C "target_cpu=native" to get a bleeding edge optimized >build, and that's where I saw a loop which started with

while pos+7 < input.len() {
... here a bunch of accesses to input[p], input[p+1]...input[p+6]
}

Every one of those secodnary accesses were very obviously tested against
the input length (stored in a register for the duration)

I considered reporting this as a very clear performance bug!

I wonder if what you saw was actually loop unrolling. I just
tried something similar, albeit with a very simple sum in the
loop body, and don't see a bunch of extraneous bounds checks.

I do wonder, though, whether you'd get better object code using `input.iter().chunks(n)` or `.windows(n)`.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

[snip]
My impression is that in Rust you tend to nail down things more often
than in Haskell, so the stretches are shorter, but there is more
automagic going on in Rust, with automatic defererencing and
referencing, automatic dropping, etc., and the borrow checker
interacts with the automagic, which makes it at least as hard to deal
with as th Haskell type inference.

The rules for when references are taken, when dereferences
happen, and when things are dropped are well-defined; there's no
magic there.

To a first order approximation, a references is taken using the
`&` and `&mut` operators, or when an object is the target of a
method call that takes `&self` or `&mut self`.

An object is dereferenced using `*` operator, the `.deref()`
operator for something that impl's the `Deref` trait, or when
using the `.` operator on product types.

An object is dropped either when it goes out of scope, or when
subject to the `Drop` operator.

Rust objects and references have lifetimes, which are a
first-class part of the type system. The borrow checker
enforces rules relating the lifetimes of objects and their
references.

Specifically:

* A reference to an object cannot outlive the object itself (no
dangling references).
* If a _mutable_ reference to an object exists at some point in
time, then that reference is the only reference to that
object.
* Any number if _immutable_ references may exist to an object at
any given time, mutually exclusive with a mutable reference to
that object.

Rust references are non-nullable, and the borrow checker rules
enforce that they always point to a valid object; the language
will not allow you to take a reference to an uninitialized
object.

There are a couple of fine points here; if you have a mutable
reference to something, it's ok to call a method on it that
takes `&self`, for example, but for the most part the above is a
decent mental model.

There are also so-called "raw" pointers in Rust that are similar
to pointers in C or Pascal in that they are nullable, can
dangle, and don't necessarily have to point to a valid,
initialized object. One can create a raw pointer using the
`&raw` or `&raw mut` operators, by assignment from a reference,
or by an explicit function/cast. Creating a raw pointer is
considered safe, since they do not have to be valid. However,
dereferencing a raw pointer is `unsafe`, meaning that it is the
programmer's responsibility to ensure that it points to a valid
object before dereferencing.

Raw pointers also have a notion of "provenance", which tracks
their origin (think capabilities in the CHERI sense here; indeed
CHERI was the motivation for the "strict provenance" APIs: https://doc.rust-lang.org/std/ptr/index.html#strict-provenance).

For Haskell I can at least make types explicit at various places to
reduce the area where the error might hide, but in Rust I have no way
to disable the automagic, and no way (or at least I don't know it) to
tell the borrow checker what I think it should be seeing, such that it
can tell me where my error is.

This is classic, "fighting the borrow checker." The checker
will tell you exactly where it thinks your error is, as far as
saying, "you use a reference at this point, when the object it
points to went out of scope at this other point..." or "you
attempted to take a mutable reference to an object while another
live reference to it already existed..." or "you tried to take
*any* reference to an object while a live mutable reference
exists". There's no magic here, and generally the error
messages are pretty good.

The `unsafe` keyword is the escape hatch that tells the compiler
that I, the programmer, am doing something weird that it has no
insight into, and so it cannot automatically enforce its checks,
and that I am therefore taking on the responsibility of ensuring
that the language's rules with respect to memory safety and
concurrency are respected. Note that `unsafe` does not allow a
programmer to _violate_ those rules, it merely tells the
compiler that they've been checked manually.

Once you get used to it, the borrow checker is unintrusive, and
it really does catch errors that would lead to crashes or
mangled data in other languages. But if you are trying to write
a Rust program the same way you would in a language that is not
type- and memory-safe, like C or (I gather) Forth, you will
almost certainly find it very frustrating.

I have investigated some tool that IIRC rewrite the Rust program to
give more information about how it understands the program, but at
least for my test case, it was not enlightening.

Perhaps you are referring to Miri? That is a simulator for the
IR, that can be used to find bugs in raw pointer usage in
`unsafe` code.

As for the type system, a friend told me that he likes Rust because it
gives him what he likes about Haskell's type system in an imperative >language.

Yes. The type system allows you to make aggressive use of
things like "typestates" and "newtypes" to eliminate entire
categories of errors. The "Parse, don't validate" metaphor
introduced by Alexis King on her blog post (https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/) translates almost directly from Haskell to Rust; my colleague
Cliff Biffle has written on typestates in Rust here: https://cliffle.com/blog/rust-typestate/

When I wrote the host OS boot loader for our machines (the thing
we run from the reset vector) I used newtypes to describe page
mappings so that virtaul page addresses of a certain size _had_
to be canonical and properly aligned and _had_ to point to a
correctly sized and aligned physical page frame that was
similarly valid. Once one has parsed a virtual page address or
physical frame address into its representative type, there's no
need to revalidate it at point of use. The existence of an
instance of those types is a proof that the addresses are valid: https://github.com/oxidecomputer/phbl/blob/main/src/mmu.rs

These techniques apply to all sorts of things. Making a
erroneous combination unrepresentable at the type level is an
incredibly powerful tool.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Dan Cross wrote:

In article <11a3ofn$2ak3s$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables. >>>>>>>

In Rust, the only acceptable array index is of type "usize", which is >>>>>>> effectively the same as u64 on most platforms these days, but does not >>>>>>> need to be so: On a 32-bit target, it would be the same as u32. >>>>>>>
So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such indices >>>>> are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

That's what I assumed, except I check my assumptions by godbolt'ing my
code, using -O -C "target_cpu=native" to get a bleeding edge optimized
build, and that's where I saw a loop which started with

while pos+7 < input.len() {
... here a bunch of accesses to input[p], input[p+1]...input[p+6]
}

Every one of those secodnary accesses were very obviously tested against
the input length (stored in a register for the duration)

I considered reporting this as a very clear performance bug!

I wonder if what you saw was actually loop unrolling. I just
tried something similar, albeit with a very simple sum in the
loop body, and don't see a bunch of extraneous bounds checks.

Not unrolling, the code is here:

https://godbolt.org/z/YnY5G1K49

The interesting part starts at line 28/29 .LBB0_02 in the asm window
where you can see (starting at line 37) a bunch of cmp r8,rsi / jae
<panic> sequences.

I do wonder, though, whether you'd get better object code using `input.iter().chunks(n)` or `.windows(n)`.

I guess I can try this, I'm guessing chunks(7) will error out if less
than 7 elements are available?

The code is from Advent of Code 2024 day 3, https://github.com/TerjeWiigMathisen/aoc/tree/master/2024/day03

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[Crossposted and and Followup-To: comp.programming]

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust >>>>language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it >>>disillusioned.

The reason was that I could not get a search-tree insertion technique
to work that can be implemented in e.g., Pascal, C, and Forth, but not
in Java (because in Java I cannot produce references to a field inside
an object).

I think what you mean to say is that you couldn't find a way to
implement that in the manner you were accustomed to thinking
about the problem, given your prior experience.

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

An intersting way to write it; I understand you're trying to
reuse `search` in `insert`, below, and thus why you want to
return `rootp`.

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);

I know you said this was untested; clearly you should not
indirect the result of `search` here.

struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these
languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of
code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1)
(but the root still has to be handled separately), but it performs
several writes instead of just one, and the recursion is not a tail >recursion, so is relatively expensive.

Or, 3) Simply reimplement the comparison in `insert`; it's a
trivial amount of code.

I chose a variant of (1) for my implementation, but only because
it was easy, not because it was required. No unsafe code or
fancy reference counting here.

BEGIN `tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree { root: None }
}

/// Searches the tree for the given key, and returns
/// `Some(&value)` if it's here, otherwise returns None.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// tree.insert(2, 200);
/// tree.insert(1, 100);
/// assert_eq!(tree.search(&0), None);
/// assert_eq!(tree.search(&1), Some(&100));
/// assert_eq!(tree.search(&2), Some(&200));
/// ```
pub fn search(&self, key: &K) -> Option<&V> {
let mut root = &self.root;
while let Some(node) = root {
match key.cmp(&node.key) {
Ordering::Less => root = &node.left,
Ordering::Equal => return Some(&node.value),
Ordering::Greater => root = &node.right,
}
}
None
}

/// Inserts the given `value` into the tree with the given
/// `key`. Returns true if the node was inserted, or false
/// if the key was already in the tree.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// assert_eq!(tree.insert(1, 100), true);
/// assert_eq!(tree.insert(1, 200), false);
/// assert_eq!(tree.insert(2, 100), true);
/// ```
pub fn insert(&mut self, key: K, value: V) -> bool {
let mut root = &mut self.root;
loop {
let Some(node) = root else {
root.replace(Node::new(key, value));
return true;
};
match key.cmp(&node.key) {
Ordering::Less => root = &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => root = &mut node.right,
}
}
}

/// Print the tree, if it is not empty.
pub fn print(&self) {
if let Some(node) = &self.root {
node.print();
}
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: None,
right: None,
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
if let Some(left) = &self.left {
left.print();
}
println!("key = {:?}, value = {:?}", self.key, self.value);
if let Some(right) = &self.right {
right.print();
}
}
}

END `tree.rs`<---

Note that there's more code here than in your C code, but this
also does a lot more; this is generic over any key and value
types where the key type implements a total ordering, and where
both types implement the `Debug` trait (so they can be printed).

Just to be fancy I added some comments, and note that the
examples in thosee comments are actually unit tests that are run
with `cargo test`.

There is also a pre-order `print` routine. With a trivial
driver program, this prints:

term% cat src/main.rs
use tree::Tree;

pub fn main() {
let mut tree = Tree::<i32, i32>::new();
tree.insert(2, 200);
tree.insert(1, 100);
tree.insert(3, 300);
tree.print();
println!("tree.search(0) = {:?}", tree.search(&0));
println!("tree.search(1) = {:?}", tree.search(&1));
}
term% cargo run
Compiling tree v0.1.0 (/Users/cross/xfer/tree)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.12s
Running `target/debug/tree`
key = 1, value = 100
key = 2, value = 200
key = 3, value = 300
tree.search(0) = None
tree.search(1) = Some(100)
term%

I wanted something with the benefits of the Pascal/C/Forth variant,
not something like the Java variants. I don't know if that counts as
"manner you were accustomed to thinking about the problem".

I would say that it does. You wanted to do something that is
familiar from Pascal or Modula-2, but that is annoying to
express in Rust. However, that doesn't mean that there is not a
similar way to effect the same thing in Rust.

And I learned this technique in Pascal or Modula-2 (probably from one
of Wirth's books), and had no problem transferring the knowledge into
C or Forth, on the contrary: In C and Forth I could turn search into a
loop (in Pascal it has to be a tail-recursive function, because you
can only produce references to variables and fields through reference >parameters).

For a language that aspires to take over from C for systems
programming, I expect that one can use this technique, too.

See above. The core of the `search` and `insert` algorithms are
similar to the ones you sketched, though the pointer-to-pointer
to a node is not returned by `search`. If that is what you mean
by "technique" then you're right; doing that in Rust is
inconvenient because it violates the borrow checker's rules
about the existence of multiple simultaneous mutable references
to an object. But I claim that is just a detail, and not a
terribly interesting one at that; certainly not an impediment to
substituting Rust for C in systems programming.

Even so, as I said, one _can_ use the same technique using a
smallish-bit of `unsafe` code. This version is more faithful to
your original:

BEGIN `unsafe_tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: *mut Node<K, V>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree {
root: std::ptr::null_mut(),
}
}

fn search(&mut self, key: &K) -> &mut *mut Node<K, V> {
let mut nodep = &mut self.root;
while let Some(node) = unsafe { nodep.as_mut() } {
match key.cmp(&node.key) {
Ordering::Less => nodep = &mut node.left,
Ordering::Equal => break,
Ordering::Greater => nodep = &mut node.right,
}
}
nodep
}

pub fn insert(&mut self, key: K, value: V) {
let inodep = self.search(&key);
if let Some(node) = unsafe { inodep.as_mut() } {
node.value = value;
} else {
let node = Node::new(key, value);
*inodep = std::boxed::Box::leak(node);
}
}

pub fn print(&self) {
unsafe { self.root.as_ref() }.map(|root| root.print());
}
}

impl<K: Debug + Ord, V: Debug> Drop for Tree<K, V> {
fn drop(&mut self) {
let _root = unsafe { std::boxed::Box::from_raw(self.root) };
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: *mut Node<K, V>,
right: *mut Node<K, V>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: std::ptr::null_mut(),
right: std::ptr::null_mut(),
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
unsafe { self.left.as_ref() }.map(|left| left.print());
println!("key = {:?}, value = {:?}", self.key, self.value);
unsafe { self.right.as_ref() }.map(|right| right.print());
}
}

impl<K: Debug + Ord, V: Debug> Drop for Node<K, V> {
fn drop(&mut self) {
if !self.left.is_null() {
let _left = unsafe { std::boxed::Box::from_raw(self.left) };
}
if !self.right.is_null() {
let _right = unsafe { std::boxed::Box::from_raw(self.right) };
}
}
}

#[cfg(test)]
mod tests {
use super::*;
#[test]
fn raw_insert_works() {
let mut tree = Tree::new();
tree.insert(1, 100);
tree.insert(3, 300);
tree.insert(2, 200);
drop(tree);
}
}

END `unsafe_tree.rs`<---

I stripped comments for brevity, but added explicit `Drop` impls
to avoid leaking memory. The seemingly useless test here allows
me to exercise this under `miri` to check for memory safety
violations manipulating raw pointers with `unsafe`:

term% cargo +nightly miri test
Finished `test` profile [unoptimized + debuginfo] target(s) in 0.00s
Running unittests src/lib.rs (target/miri/aarch64-apple-darwin/debug/build/tree/6797a5ad52527de9/out/tree-6797a5ad52527de9)

running 1 test
test otree::tests::raw_insert_works ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.16s

Running unittests src/main.rs (target/miri/aarch64-apple-darwin/debug/build/tree/6121d361cfb78277/out/tree-6121d361cfb78277)

running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.03s

Doc-tests tree

running 2 tests
test src/lib.rs - Tree<K,V>::insert (line 51) ... ok
test src/lib.rs - Tree<K,V>::search (line 25) ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.11s

all doctests ran in 0.14s; merged doctests compilation took 0.03s
term%

So, we can see that it is possible to use the same technique you
are familiar with.

The difference is that, with Rust, you usually don't _want_ to
do it this way, since there's a completely safe alternative that
leverages the type system to prohibit memory leaks, dangling
pointers, and so on, by construction.

Frankly, unless I was doing something very odd, I wouldn't write
my own binary search tree at all; the standard library's
collections implementations are pretty good, and then there are
third-party libraries like Hashbrown and Crossbeam that are
best-in-class across the industry.

But that is separate from whether it can be done or not.

Sure, and as I found out later, it can be done.

Indeed; see above.

In fact, in Rust you can use approximately the same
techniques you would use in Pascal, C, or (probably) Forth: raw
pointers are a part of the language, and you can simply use them
with `unsafe` code, and it would be no more "unsafe" than in C
or Pascal. One might argue that that defeats the purpose of the
language, and you'd be right to a point. The difference is that
in C or Pascal, the entire program is what Rust would call
"unsafe", whereas generally this can be restricted to just a few
lines of carefully audited code in Rust.

Given that I do not understand the automagic stuff done by the Rust
compiler enough to get this kind of tree insertion past the borrow
checker, even though it is possible, I don't trust my capabilities to
audit unsafe Rust.

Is it significantly different than doing so in C, Pascal, or
Forth? See the second program, above; the use of `unsafe` in
the bits that correspond to your sketch in C is constrained to
two places that indirect raw pointers.

It is true that I think it is more difficult to write _correct_
`unsafe` code in Rust than in, say, C, because the language is
more demanding of the programmer. But in return for that
investment in effort, you get substantally more type and memory
safety.

FWIW, for things like containers of various kinds (trees, hash
tables, linked-lists, growable arrays, etc), production programs
usually use an existing library or crate instead of rolling
their own.

When I saw that this technique cannot be implemented in Java, I
wondered why Java was not having references to fields (answer:
probably because that would make garbage collection more costly and/or
less precise), that this technique is needed for relatively few
things, mostly stuff that's in libraries. And I wondered how these
library methos are implemented (at one point I guessed that they
implemented these parts of their libraries in C, but when I actually
look, the implementation of what I looked at was in Java, IIRC along
the lines of 1)).

For a language that aspires to replace C for systems programming,
giving the Java answer is not good enough, though.

Fortunately for Rust, that's not what it does.

At some point I thought that one would have to use the more
heavy-weight reference-counting stuff to get through the borrow
checker.

Then I found the book "Learn Rust With Entirely Too Many Linked
Lists", and I found that the problem could be solved without reference >>>counting after all. However, the problem in this case is the usual
thing with type inference: There is so much going on that happens >>>automagically (in particular automatic dereferencing in Rust), and the >>>Rust compiler does not know where you went wrong, so the error message
is unhelpful (while for the simpler cases the compiler usually guesses >>>right and gives very helpful, to-the-point error messages).

Even after reading the second book, I am still disillusioned with
Rust. The Rust fans tend to say: "If it compiles, it runs." The
problem is that it can be harder to get a Rust program to compile than
to debug a program in, say, Forth (which has barely any checking).
For debugging, I at least have a method on how to proceed. When I get
an unhelpful compiler error, I am left to trying various things,
blindly.

Sounds like you're in what we'd call the, "fighting the borrow
checker" stage. It may be that you end up really not liking
Rust or feeling that other languages are better, but I wager
that just about anyone who has seriously used the language has
gone through similar things.

I wonder about that.

It's so common that "fighting the borrow checker" is the
community's slogan to describe it. Another common phenomenon
for those who put in the work and come out the other side of
that is that one finds the discipline it imposes on how one
thinks of one's programs makes one a better programmers in
unsafe languages, like C.

From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was
added later, as a convenience for the programmers who already knew the >language. So the Rust programmers of the early days formed a mental
model based on "Pedestrian Rust" (i.e., with less automagic), and when
they see a program with more automagic, and need to understand some >conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern >language. There are hints in the books I read, but not enough to get
a firm foundation.

Early Rust was very different, and much closer to a managed
language with garbage collection, green threads, a heavy-weight
runtime, etc. Put another way, the trend has been less and less
"automagic" (as you put it) and making things more explicit over
time.

You keep conflating things you are not familiar with in a
language you are not familiar with, with the idea that those
things are "automagic." But really there is no magic here, and
I suspect the answer to your question about how one learns to
adapt their mental model of Rust is to first stop thinking of it
as magical.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Mon, 5 Oct 2026 11:36:59 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index
variables.

In Rust, the only acceptable array index is of type "usize",
which is effectively the same as u64 on most platforms these
days, but does not need to be so: On a 32-bit target, it would
be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such
indices are verified against the actual array upper boundary.
[...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

Are you sure?
Methinks The Book states otherwise: https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access





--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <11a5lqo$2v5bq$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <11a3ofn$2ak3s$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index variables. >>>>>>>>

In Rust, the only acceptable array index is of type "usize", which is >>>>>>>> effectively the same as u64 on most platforms these days, but does not >>>>>>>> need to be so: On a 32-bit target, it would be the same as u32. >>>>>>>>
So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of >>>>>>> the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial >>>>>> underpinnings of Rust safety. Even more importantly, all such indices >>>>>> are verified against the actual array upper boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

That's what I assumed, except I check my assumptions by godbolt'ing my
code, using -O -C "target_cpu=native" to get a bleeding edge optimized
build, and that's where I saw a loop which started with

while pos+7 < input.len() {
... here a bunch of accesses to input[p], input[p+1]...input[p+6]
}

Every one of those secodnary accesses were very obviously tested against >>> the input length (stored in a register for the duration)

I considered reporting this as a very clear performance bug!

I wonder if what you saw was actually loop unrolling. I just
tried something similar, albeit with a very simple sum in the
loop body, and don't see a bunch of extraneous bounds checks.

Not unrolling, the code is here:

https://godbolt.org/z/YnY5G1K49

The interesting part starts at line 28/29 .LBB0_02 in the asm window
where you can see (starting at line 37) a bunch of cmp r8,rsi / jae
<panic> sequences.

So you're not actually indexing into an _array_ here, but rather
into a _slice_, which is always bounds-checked in safe Rust
code.

I do wonder, though, whether you'd get better object code using
`input.iter().chunks(n)` or `.windows(n)`.

I guess I can try this, I'm guessing chunks(7) will error out if less
than 7 elements are available?

But really what you want is to find all subsequences matching
the regular expression , `mul([0-9]+,[0-9]+)`, and then extract
the two numeric fields, multiple them, and sum the results.
That's a reduction over a sequence of products, which is itself
a reduction over a sequence of patches that yield pairs of
integers.

I understand you want raw speed; a way to get that is to
implement the DFA corresponding to that regexp by hand, and use
something like Boyer Moore to handle the fixed part.

The code is from Advent of Code 2024 day 3, >https://github.com/TerjeWiigMathisen/aoc/tree/master/2024/day03

Oh, I don't do Advent of Code, but looking briefly at the
problem description I don't see why you couldn't use `&str` to
represent the input data. Nothing says it's not UTF-8, and from
what I understand, the guy who runs it usually isn't a jerk
about that kind of thing. I haven't tried to benchmark your
code against, e.g., this:

BEGIN<---

pub fn next(mut s: &str) -> Option<(i32, &str)> {
while !s.is_empty() {
let pos = s.find("mul(")?;
let (_, rest) = s.split_at(pos + 4);
s = rest;
let comma = s.find(|c: char| !c.is_ascii_digit())?;
let (adigits, rest) = s.split_at(comma);
let Some(rest) = rest.strip_prefix(",") else {
s = rest;
continue;
};
let a = adigits.parse::<i32>().ok()?;
let rparen = rest.find(|c: char| !c.is_ascii_digit())?;
let (bdigits, rest) = rest.split_at(rparen);
let Some(rest) = rest.strip_prefix(")") else {
s = rest;
continue;
};
let b = bdigits.parse::<i32>().ok()?;
return Some((a * b, rest));
}
None
}

#[cfg(test)]
mod tests {
use super::*;

#[test]
fn invalids() {
assert_eq!(next("aaa"), None);
assert_eq!(next(""), None);
assert_eq!(next("mul(3,5"), None);
assert_eq!(next("mul(3, 5"), None);
assert_eq!(next("mul(3,"), None);
assert_eq!(next("mul(3"), None);
assert_eq!(next("mul("), None);
}

#[test]
fn aproduct() {
let s = "abmul[1,2]mul(3,5)a";
assert_eq!(next(s), Some((15, "a")));
}

#[test]
fn mproducts() {
let s = "mul(1,2)mul(3,4)";
let aopt = next(s);
assert_eq!(aopt, Some((2, "mul(3,4)")));
let (a, s) = aopt.unwrap();
let bopt = next(s);
assert_eq!(bopt, Some((12, "")));
let (b, s) = bopt.unwrap();
assert_eq!(next(s), None);
assert_eq!(a * b, 24);
}
}

END<---

I suspect yours may be somewhat faster, though this likely does
more error checking. YMMV.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Michael S <[email protected]> wrote:

On Mon, 5 Oct 2026 11:36:59 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index
variables.

In Rust, the only acceptable array index is of type "usize",
which is effectively the same as u64 on most platforms these
days, but does not need to be so: On a 32-bit target, it would
be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such
indices are verified against the actual array upper boundary.
[...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

Are you sure?
Methinks The Book states otherwise: >https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

If the array length and index are known ahead of time, or can be
statically proven to be valid, then yes, the checks are (likely)
removed in release mode as part of the ordinary optimization
passes. In the case where one has already asserted that
`p + n < arr.len()`, then I would expect any index `arr[p + k]`
to omit the bounds check, for k < n.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Wed, 7 Oct 2026 20:05:50 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

On Mon, 5 Oct 2026 11:36:59 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index
variables.

In Rust, the only acceptable array index is of type "usize",
which is effectively the same as u64 on most platforms these
days, but does not need to be so: On a 32-bit target, it
would be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99%
of the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more
crucial underpinnings of Rust safety. Even more importantly,
all such indices are verified against the actual array upper
boundary. [...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

Are you sure?
Methinks The Book states otherwise: >https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

If the array length and index are known ahead of time, or can be
statically proven to be valid, then yes, the checks are (likely)
removed in release mode as part of the ordinary optimization
passes.

That is not different from any other bound-checked language that has
optimizing compiler.

In the case where one has already asserted that
`p + n < arr.len()`, then I would expect any index `arr[p + k]`
to omit the bounds check, for k < n.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Dan Cross wrote:

In article <11a5lqo$2v5bq$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Not unrolling, the code is here:

https://godbolt.org/z/YnY5G1K49

The interesting part starts at line 28/29 .LBB0_02 in the asm window
where you can see (starting at line 37) a bunch of cmp r8,rsi / jae
<panic> sequences.

So you're not actually indexing into an _array_ here, but rather
into a _slice_, which is always bounds-checked in safe Rust
code.

My old asm/C brain _knows_ that a slice of something with a known
address and total length is effectively the same thing as an unmutable
array.

Even if it isn't, the fact that I start by verifying that the slice
extends at least 7 bytes past the p index means that all of p,
p+1,p+2...p+6 must be valid, right?

I do wonder, though, whether you'd get better object code using
`input.iter().chunks(n)` or `.windows(n)`.

I guess I can try this, I'm guessing chunks(7) will error out if less
than 7 elements are available?

But really what you want is to find all subsequences matching
the regular expression , `mul([0-9]+,[0-9]+)`, and then extract
the two numeric fields, multiple them, and sum the results.
That's a reduction over a sequence of products, which is itself
a reduction over a sequence of patches that yield pairs of
integers.

Yes, doing it that way is easy!

I understand you want raw speed; a way to get that is to
implement the DFA corresponding to that regexp by hand, and use
something like Boyer Moore to handle the fixed part.

Collectively we've tried all sorts of stuff in order to come up with the absolute fastest solution, without having to use unsafe code.

The code is from Advent of Code 2024 day 3,
https://github.com/TerjeWiigMathisen/aoc/tree/master/2024/day03

Oh, I don't do Advent of Code, but looking briefly at the
problem description I don't see why you couldn't use `&str` to

I typically pass the input to my process(inp:&str) function that way,
but by turning it into a naked byte array (slice?), indexing is better
defined with no need to iterate over a potential UTF8 sequence (even
though we know there won't be any).

represent the input data. Nothing says it's not UTF-8, and from
what I understand, the guy who runs it usually isn't a jerk
about that kind of thing. I haven't tried to benchmark your
code against, e.g., this:

What you implement here is just Part1: After solving that you get to
read Part2 where you have to also detect "do()" and "don't()" sequences,
so that the multiplication result only adds to the part2 result if we're
not following a don't().

BEGIN<---

pub fn next(mut s: &str) -> Option<(i32, &str)> {
while !s.is_empty() {
let pos = s.find("mul(")?;
let (_, rest) = s.split_at(pos + 4);
s = rest;
let comma = s.find(|c: char| !c.is_ascii_digit())?;
let (adigits, rest) = s.split_at(comma);
let Some(rest) = rest.strip_prefix(",") else {
s = rest;
continue;
};
let a = adigits.parse::<i32>().ok()?;
let rparen = rest.find(|c: char| !c.is_ascii_digit())?;
let (bdigits, rest) = rest.split_at(rparen);
let Some(rest) = rest.strip_prefix(")") else {
s = rest;
continue;
};
let b = bdigits.parse::<i32>().ok()?;
return Some((a * b, rest));
}
None
}

#[cfg(test)]
mod tests {
use super::*;

#[test]
fn invalids() {
assert_eq!(next("aaa"), None);
assert_eq!(next(""), None);
assert_eq!(next("mul(3,5"), None);
assert_eq!(next("mul(3, 5"), None);
assert_eq!(next("mul(3,"), None);
assert_eq!(next("mul(3"), None);
assert_eq!(next("mul("), None);
}

#[test]
fn aproduct() {
let s = "abmul[1,2]mul(3,5)a";
assert_eq!(next(s), Some((15, "a")));
}

#[test]
fn mproducts() {
let s = "mul(1,2)mul(3,4)";
let aopt = next(s);
assert_eq!(aopt, Some((2, "mul(3,4)")));
let (a, s) = aopt.unwrap();
let bopt = next(s);
assert_eq!(bopt, Some((12, "")));
let (b, s) = bopt.unwrap();
assert_eq!(next(s), None);
assert_eq!(a * b, 24);
}
}

END<---

I suspect yours may be somewhat faster, though this likely does
more error checking. YMMV.

My guess is that your code (after adding the simultaneous scans for the do/don't markers) will take about twice as long (or more?) as the 7 us
both my own and u/maneatingape (reddit handle of the guy with the
fastest Rust solutions to all the 500+ puzzles) needs to deliver the result.

He is famous for solving every one of them in less than half a second:

His current total is 462 milliseconds for 524 stars.

I've managed to improve slightly on his code a few times, but more often
he is ahead of the best I've been able to come up with.

Collectively, the group discussing this on reddit have tried many
different search approaches, including unaligned load of 4 bytes as a
u32, then compare that directly against "mul(", "do()" and "don'" in a
match statement. For me, this was slower in Rust, but a C programmer
gained a us or two this way.

Setting up a combined Boyer-Moore would be doable:

If the fourth byte is '(', ')' or "'", check the preceeding bytes, if
not a match use a pre-computed skip table (maybe even one for each
initial match?) to increment the pointer. Hmmm... maybe I'll try this!

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Dan Cross wrote:

In article <[email protected]>,
Michael S <[email protected]> wrote:

On Mon, 5 Oct 2026 11:36:59 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index
variables.

In Rust, the only acceptable array index is of type "usize",
which is effectively the same as u64 on most platforms these
days, but does not need to be so: On a 32-bit target, it would
be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such
indices are verified against the actual array upper boundary.
[...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

Are you sure?
Methinks The Book states otherwise:
https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

If the array length and index are known ahead of time, or can be
statically proven to be valid, then yes, the checks are (likely)
removed in release mode as part of the ordinary optimization
passes. In the case where one has already asserted that
`p + n < arr.len()`, then I would expect any index `arr[p + k]`
to omit the bounds check, for k < n.

That's exactly what I expected when I wrote my code the way I did. I
know that Java specifically handles this situation, lifting any array
bounds checking out of inner loops if possible.

As that Godbolt link shows, my expectation was wrong.

OTOH, for such a small program having 6 extra branches, none of them
ever taken, is not likely to add any cycles to the program latency since current CPUs have more than enough issue ports to be able to handle
these branches while processing the real code.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2026-Oct-07 15:25, Michael S wrote:

https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

Does Rust allow zero length arrays, vectors, strings and slices?
Ada calls these a null slice.
In DEC Fortran 77 a zero length slice was a bounds check error,
which was really irritating because in string manipulation they happen a lot. If so, how does one specify a null slice in Rust?
I couldn't find any definition in that doc.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2026-Oct-07 16:49, EricP wrote:

On 2026-Oct-07 15:25, Michael S wrote:

https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

Does Rust allow zero length arrays, vectors, strings and slices?
Ada calls these a null slice.
In DEC Fortran 77 a zero length slice was a bounds check error,
which was really irritating because in string manipulation they happen a lot. If so, how does one specify a null slice in Rust?
I couldn't find any definition in that doc.

I asked the Google AI "does programming language rust support
zero length array slices" and it said:

Yes, Rust fully supports zero-length (empty) array slices.
A slice in Rust ([T]) represents a dynamically-sized view into
a contiguous sequence of elements. Because the length is evaluated
at runtime, a slice can safely have a length of 0.

How to Create an Empty Slice

You can create or obtain a zero-length slice in Rust in several ways:

From an empty array or vector:

let empty_array: [i32; 0] = [];
let slice: &[i32] = &empty_array; // A zero-length slice

Using a range that yields no elements:

let numbers = [1, 2, 3, 4];
let empty_slice = &numbers[2..2]; // Length is 0

Directly via standard library constants:

let empty_slice: &[i32] = &[];

Memory Layout of a Zero-Length Slice

Under the hood, a slice reference (&[T]) is a fat pointer
consisting of two components:

1. A pointer to the data.
2. The length of the slice (usize).

For a zero-length slice, the length component is 0. To avoid using
a null pointer (which Rust references cannot be), the data pointer
component points to a well-aligned, non-null "dangling" pointer
address (specifically NonNull::dangling()), making it completely
safe and overhead-free.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

EricP <[email protected]> schrieb:

On 2026-Oct-07 15:25, Michael S wrote:

https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

Does Rust allow zero length arrays, vectors, strings and slices?
Ada calls these a null slice.
In DEC Fortran 77 a zero length slice was a bounds check error,

Modern Fortran does allow it, and yes, it is very convenient.
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On 2026-Oct-07 15:25, Michael S wrote:

On Mon, 5 Oct 2026 11:36:59 -0000 (UTC)
[email protected] (Dan Cross) wrote:

In article <[email protected]>,
Tim Rentsch <[email protected]> wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

Terje Mathisen <[email protected]> writes:

Tim Rentsch wrote:

[...]

I favor a type equivalent to size_t for use as array index
variables.

In Rust, the only acceptable array index is of type "usize",
which is effectively the same as u64 on most platforms these
days, but does not need to be so: On a 32-bit target, it would
be the same as u32.

So effectively very similar to size_t.

Maybe that limitation works okay in Rust. In C sometimes it's
important to allow a signed value for indexing. Probably 99% of
the time size_t is good, but not always.

The fact that array indices are unsigned is one of the more crucial
underpinnings of Rust safety. Even more importantly, all such
indices are verified against the actual array upper boundary.
[...]

It's nice that array index values are checked against the array
bounds.

Terje was actually incorrect here; bounds checks are added in
debug mode, but are (usually) removed in optimized builds.

Are you sure?
Methinks The Book states otherwise: https://doc.rust-lang.org/book/ch03-02-data-types.html?highlight=array#invalid-array-element-access

The reference is less see-spot-run

https://doc.rust-lang.org/stable/reference/

Looking at the rules for type casting:

https://doc.rust-lang.org/stable/reference/expressions/operator-expr.html#numeric-cast

Some initial thoughts:

There are no value range checks between cast types, just bit-wise reinterpretation
to the new type with possible sign/zero extension or truncation for size change.

They don't define the order in which those two operations, type and size change, occur.
If one casts an i8 into a u16 it doesn't say whether the value is sign extended to i16 first then type changed to u16, or type changed to u8 first then zero extended to u16.

Since an array index is defined as type usize, if the index expression is signed
then it will be bit-wise reinterpreted as unsigned, and possibly turn a negative
value into a large positive usize value. If bounds checks are disabled for production builds then you get exactly the same array overflow as in C.


--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[Cross-post to comp.programming, Followup-To: comp.programming]

In article <11a6a6h$37i1n$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <11a5lqo$2v5bq$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Not unrolling, the code is here:

https://godbolt.org/z/YnY5G1K49

The interesting part starts at line 28/29 .LBB0_02 in the asm window
where you can see (starting at line 37) a bunch of cmp r8,rsi / jae
<panic> sequences.

So you're not actually indexing into an _array_ here, but rather
into a _slice_, which is always bounds-checked in safe Rust
code.

My old asm/C brain _knows_ that a slice of something with a known
address and total length is effectively the same thing as an unmutable >array.

Sadly, though, it's not. :-/

Even if it isn't, the fact that I start by verifying that the slice
extends at least 7 bytes past the p index means that all of p,
p+1,p+2...p+6 must be valid, right?

One would think!

I do wonder, though, whether you'd get better object code using
`input.iter().chunks(n)` or `.windows(n)`.

I guess I can try this, I'm guessing chunks(7) will error out if less
than 7 elements are available?

But really what you want is to find all subsequences matching
the regular expression , `mul([0-9]+,[0-9]+)`, and then extract
the two numeric fields, multiple them, and sum the results.
That's a reduction over a sequence of products, which is itself
a reduction over a sequence of patches that yield pairs of
integers.

Yes, doing it that way is easy!

Well, I mean as a conceptual thing; not necessary using a regex
library. That is, mentally write the patterns down as a DFA and
then write that out as code+state tables.

[snip]
represent the input data. Nothing says it's not UTF-8, and from
what I understand, the guy who runs it usually isn't a jerk
about that kind of thing. I haven't tried to benchmark your
code against, e.g., this:

What you implement here is just Part1: After solving that you get to
read Part2 where you have to also detect "do()" and "don't()" sequences,
so that the multiplication result only adds to the part2 result if we're
not following a don't().

Ah. Yeah, I'm going to refrain; it's cool that folks are excited
about that, but it's not my favorite biscuit.

[snip]
I suspect yours may be somewhat faster, though this likely does
more error checking. YMMV.

My guess is that your code (after adding the simultaneous scans for the >do/don't markers) will take about twice as long (or more?) as the 7 us
both my own and u/maneatingape (reddit handle of the guy with the
fastest Rust solutions to all the 500+ puzzles) needs to deliver the result.

Maybe? I dunno; the library is probably optimized to use pretty
efficient algorithms, and/or simd and all that jazz.

[snip]
Setting up a combined Boyer-Moore would be doable:

If the fourth byte is '(', ')' or "'", check the preceeding bytes, if
not a match use a pre-computed skip table (maybe even one for each
initial match?) to increment the pointer. Hmmm... maybe I'll try this!

Right. This lets you potentially go sub-linear looking for the
tokens you care about. I wonder how it would stack up against
using something like `memchr::memmem`, though, since that'll get
you hardware acceleration using SIMD instructions and goofy
stuff like that.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <11a6agf$37m70$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

[snip]
If the array length and index are known ahead of time, or can be
statically proven to be valid, then yes, the checks are (likely)
removed in release mode as part of the ordinary optimization
passes. In the case where one has already asserted that
`p + n < arr.len()`, then I would expect any index `arr[p + k]`
to omit the bounds check, for k < n.

That's exactly what I expected when I wrote my code the way I did. I
know that Java specifically handles this situation, lifting any array
bounds checking out of inner loops if possible.

As that Godbolt link shows, my expectation was wrong.

OTOH, for such a small program having 6 extra branches, none of them
ever taken, is not likely to add any cycles to the program latency since >current CPUs have more than enough issue ports to be able to handle
these branches while processing the real code.

I thought it was worth a small experiment; here's a silly pair
of functions:

```rust
#[inline(never)]
pub fn sum_sub_array(arr: [u32; 4], k: usize) -> u32 {
if k + 3 > arr.len() {
return 0;
}
arr[k] + arr[k + 1] + arr[k + 2]
}

#[inline(never)]
pub fn sum_sub_slice(sl: &[u32], k: usize) -> u32 {
if k + 3 > sl.len() {
return 0;
}
sl[k] + sl[k + 1] + sl[k + 2]
}
```

If I run these in such a way that they're not totally optimized
away and do a release build, they generate the exact same code:

```
0000000000015cb0 <rust_indices::sum_sub_array>:
15cb0: 31 c0 xor %eax,%eax
15cb2: 48 83 fe 01 cmp $0x1,%rsi
15cb6: 77 0b ja 15cc3 <rust_indices::sum_sub_array+0x13>
15cb8: 8b 44 b7 04 mov 0x4(%rdi,%rsi,4),%eax
15cbc: 03 04 b7 add (%rdi,%rsi,4),%eax
15cbf: 03 44 b7 08 add 0x8(%rdi,%rsi,4),%eax
15cc3: c3 ret
15cc4: cc int3
...
15ccf: cc int3

0000000000015cd0 <rust_indices::sum_sub_slice>:
15cd0: 31 c0 xor %eax,%eax
15cd2: 48 83 fe 01 cmp $0x1,%rsi
15cd6: 77 0b ja 15ce3 <rust_indices::sum_sub_slice+0x13>
15cd8: 8b 44 b7 04 mov 0x4(%rdi,%rsi,4),%eax
15cdc: 03 04 b7 add (%rdi,%rsi,4),%eax
15cdf: 03 44 b7 08 add 0x8(%rdi,%rsi,4),%eax
15ce3: c3 ret
15ce4: cc int3
...
15cef: cc int3
```

Perhaps it's something about the complexity of your function
that exceed some sort of threshold for the optimizer.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <jbPxS.600$[email protected]>,
EricP <[email protected]> wrote:

[snip]
The reference is less see-spot-run

https://doc.rust-lang.org/stable/reference/

Looking at the rules for type casting:

https://doc.rust-lang.org/stable/reference/expressions/operator-expr.html#numeric-cast

Some initial thoughts:

There are no value range checks between cast types, just bit-wise reinterpretation
to the new type with possible sign/zero extension or truncation for size change.

They don't define the order in which those two operations, type and size change, occur.
If one casts an i8 into a u16 it doesn't say whether the value is sign extended
to i16 first then type changed to u16, or type changed to u8 first then zero >extended to u16.

They do, but it requires looking at _two_ rules from that list.

The first,

|Casting between two integers of the same size (e.g. i32 -> u32)
|is a no-op (Rust uses 2’s complement for negative values of
|fixed integers)

and the third,

|Casting from a smaller integer to a larger integer (e.g. u8 ->
|u32) will
|
| * zero-extend if the source is unsigned
| * sign-extend if the source is signed

Note that the second of these, the third rule on the list,
mentions sign extension if the _source_ type is signed; the
signedness of the destination is not relevant.

Taken together, these imply that the source will be
sign-extended and then the conversion to unsigned will be
treated as a noop: rule #1 does not apply first because it is
specific to conversions between sign/unsigned integers of the
_same width_; so we start with rule #3, sign-extend, and _then_
we may apply rule #1.

For a negative value of a source type that is smaller than an
unsigned destination type, the result will be an unsigned value
in the upper half of the destination type's range.

term% cat cast.rs
fn main() {
let n: i8 = -2;
println!("-2 as u16 = {}", n as u16);
}
term% rustc cast.rs
term% ./cast
-2 as u16 = 65534
term%

If you wanted to force specific behavior, you could use multiple
casts (e.g., `n as u8 as u16`).

Since an array index is defined as type usize, if the index expression
is signed then it will be bit-wise reinterpreted as unsigned,

No, if the index expression is signed, it will be a compile-time
error since usize is, by definiton, unsigned, and usize is the
only permissible index type. Rust is statically typed, and
there are no implicit conversions that factor here.

and possibly turn a negative value into a large positive usize
value.

In order for this to happen, one would have to use an explicit
cast to make the negative value a `usize` first.

A fair followup question is, "suppose I do a comparison against
a signed type, but don't account for zero, and then convert it
to usize; could the optimizer remove the bounds checks?" For
example, this:

```rust
#[inline(never)]
pub fn get_a_number(k: i32) -> i32 {
const ARR: [i32; 10] = [500, 1, 200, 3, 410, 5, 37, 7, 8, -5];
if k < 10 { ARR[k as usize] } else { 0 }
}
```

When built with optimization enabled and linked with a simple
driver, panic's at runtime trying to use a negative value cast
to a (large) positive value as an index. On the other hand, if
I modify it to check the lower bound on the array, that is
optimized away. So this version,

```rust
#[inline(never)]
pub fn get_a_number(k: i32) -> i32 {
const ARR: [i32; 10] = [500, 1, 200, 3, 410, 5, 37, 7, 8, -5];
if 0 <= k && k < 10 { ARR[k as usize] } else { 0 }
}
```
yields this object code on x86_64:
```
0000000000014ad0 <rbounds::get_a_number>:
14ad0: 31 c0 xor %eax,%eax
14ad2: 83 ff 0a cmp $0xa,%edi
14ad5: 73 0c jae 14ae3 <rbounds::get_a_number+0x13>
14ad7: 89 f8 mov %edi,%eax
14ad9: 48 8d 0d 04 19 ff ff lea -0xe6fc(%rip),%rcx # 63e4 <__abi_tag+0x60e8>
14ae0: 8b 04 81 mov (%rcx,%rax,4),%eax
14ae3: c3 ret
14ae4: cc int3
...
14aef: cc int3
```

If bounds checks are disabled for
production builds then you get exactly the same array overflow as in C.

See above.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Dan Cross wrote:

In article <11a6agf$37m70$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

[snip]
If the array length and index are known ahead of time, or can be
statically proven to be valid, then yes, the checks are (likely)
removed in release mode as part of the ordinary optimization
passes. In the case where one has already asserted that
`p + n < arr.len()`, then I would expect any index `arr[p + k]`
to omit the bounds check, for k < n.

That's exactly what I expected when I wrote my code the way I did. I
know that Java specifically handles this situation, lifting any array
bounds checking out of inner loops if possible.

As that Godbolt link shows, my expectation was wrong.

OTOH, for such a small program having 6 extra branches, none of them
ever taken, is not likely to add any cycles to the program latency since
current CPUs have more than enough issue ports to be able to handle
these branches while processing the real code.

I thought it was worth a small experiment; here's a silly pair
of functions:

Thanks for testing!

```rust
#[inline(never)]
pub fn sum_sub_array(arr: [u32; 4], k: usize) -> u32 {
if k + 3 > arr.len() {
return 0;
}
arr[k] + arr[k + 1] + arr[k + 2]
}

#[inline(never)]
pub fn sum_sub_slice(sl: &[u32], k: usize) -> u32 {
if k + 3 > sl.len() {
return 0;
}
sl[k] + sl[k + 1] + sl[k + 2]
}
```

If I run these in such a way that they're not totally optimized
away and do a release build, they generate the exact same code:

That's actually what I would expect, re my post about a read-only array
and ditto slice being the same.

```
0000000000015cb0 <rust_indices::sum_sub_array>:
15cb0: 31 c0 xor %eax,%eax
15cb2: 48 83 fe 01 cmp $0x1,%rsi
15cb6: 77 0b ja 15cc3 <rust_indices::sum_sub_array+0x13>
15cb8: 8b 44 b7 04 mov 0x4(%rdi,%rsi,4),%eax
15cbc: 03 04 b7 add (%rdi,%rsi,4),%eax
15cbf: 03 44 b7 08 add 0x8(%rdi,%rsi,4),%eax
15cc3: c3 ret
15cc4: cc int3
...
15ccf: cc int3

0000000000015cd0 <rust_indices::sum_sub_slice>:
15cd0: 31 c0 xor %eax,%eax
15cd2: 48 83 fe 01 cmp $0x1,%rsi
15cd6: 77 0b ja 15ce3 <rust_indices::sum_sub_slice+0x13>
15cd8: 8b 44 b7 04 mov 0x4(%rdi,%rsi,4),%eax
15cdc: 03 04 b7 add (%rdi,%rsi,4),%eax
15cdf: 03 44 b7 08 add 0x8(%rdi,%rsi,4),%eax
15ce3: c3 ret
15ce4: cc int3
...
15cef: cc int3
```

Perhaps it's something about the complexity of your function
that exceed some sort of threshold for the optimizer.

Quite possibly so...

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Dan Cross) writes:

[Crossposted and and Followup-To: comp.programming]

Given that I don't subscribe to c.p, I kept comp.arch in the
Newsgroups.

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

An intersting way to write it; I understand you're trying to
reuse `search` in `insert`, below, and thus why you want to
return `rootp`.

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);

I know you said this was untested; clearly you should not
indirect the result of `search` here.

struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these
languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of
code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1)
(but the root still has to be handled separately), but it performs
several writes instead of just one, and the recursion is not a tail >>recursion, so is relatively expensive.

Or, 3) Simply reimplement the comparison in `insert`

That goes along with 1), but I forgot to mention it.

it's a trivial amount of code.

There's the rub. I don't consider a factor of ~2 trivial, even if it
is only 20 lines of code. And in particular, "simply reimplement"
means that the same thing occurs several times in the code, and in
maintainance one must remember to change all of the occurences.

Fortunately, that's not necessary in Rust. But the fact that you did
not find it tells me that Rust is hard even for experienced Rust
programmers.

I chose a variant of (1) for my implementation, but only because
it was easy, not because it was required. No unsafe code or
fancy reference counting here.

BEGIN `tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree { root: None }
}

/// Searches the tree for the given key, and returns
/// `Some(&value)` if it's here, otherwise returns None.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// tree.insert(2, 200);
/// tree.insert(1, 100);
/// assert_eq!(tree.search(&0), None);
/// assert_eq!(tree.search(&1), Some(&100));
/// assert_eq!(tree.search(&2), Some(&200));
/// ```
pub fn search(&self, key: &K) -> Option<&V> {
let mut root = &self.root;
while let Some(node) = root {
match key.cmp(&node.key) {
Ordering::Less => root = &node.left,
Ordering::Equal => return Some(&node.value),
Ordering::Greater => root = &node.right,
}
}
None
}

/// Inserts the given `value` into the tree with the given
/// `key`. Returns true if the node was inserted, or false
/// if the key was already in the tree.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// assert_eq!(tree.insert(1, 100), true);
/// assert_eq!(tree.insert(1, 200), false);
/// assert_eq!(tree.insert(2, 100), true);
/// ```
pub fn insert(&mut self, key: K, value: V) -> bool {
let mut root = &mut self.root;
loop {
let Some(node) = root else {
root.replace(Node::new(key, value));
return true;
};
match key.cmp(&node.key) {
Ordering::Less => root = &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => root = &mut node.right,
}
}
}

/// Print the tree, if it is not empty.
pub fn print(&self) {
if let Some(node) = &self.root {
node.print();
}
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: None,
right: None,
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
if let Some(left) = &self.left {
left.print();
}
println!("key = {:?}, value = {:?}", self.key, self.value);
if let Some(right) = &self.right {
right.print();
}
}
}

END `tree.rs`<---

Note that there's more code here than in your C code, but this
also does a lot more; this is generic over any key and value
types where the key type implements a total ordering, and where
both types implement the `Debug` trait (so they can be printed).

If I don't need any of that, does it get smaller? I don't think so.

Here's my attempt, and I expect that experienced Rust programmers will
find ways to improve on it. It includes a lookup function:

-------------------
use std::cmp::Ordering;

pub struct Tree<K: Ord, V> {
root: Subtree<K, V>,
}

type Subtree<K,V> = Option<Box<Node<K,V>>>;

struct Node<K: Ord, V> {
key: K,
val: V,
left: Subtree<K, V>,
right: Subtree<K, V>,
}

impl<K: Ord,V> Tree<K,V> {
pub fn new() -> Self {
Tree { root: None }
}

pub fn insert(&mut self, key: K, val: V) {
let mut t = &mut self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => {node.val = val; return;},
Ordering::Less => t = &mut node.left,
Ordering::Greater => t = &mut node.right,
};
};
*t = Some(Box::new(Node {key, val, left: None, right: None}))
}

pub fn lookup(&self, key: K) -> Option<&V> {
let mut t = &self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => return Some(&node.val),
Ordering::Less => t = &node.left,
Ordering::Greater => t = &node.right,
};
};
None
}
}

fn main() {
let mut q1 = Tree::new();
q1.insert(2,"abc".to_string());
q1.insert(3,"def".to_string());
q1.insert(1,"ghi".to_string());
q1.insert(3,"jkl".to_string());
println!("{:?}",q1.lookup(1));
println!("{:?}",q1.lookup(2));
println!("{:?}",q1.lookup(3));
}
----------------------------

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *"
variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

insert now integrates search, because I could not satisfy the compiler
with a separate search; maybe a more experience Rust programmer can
separate it out again. The advantage is that there is no need to
combine the found and notfound cases in one return value in search,
only to handle them as separate cases in insert. But at least there
is no duplication of the comparison code.

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable
reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

Of course, if search is factored out, both clients have to explicitly
check for both outcomes and have code for both. But that's probably
preferable to duplicating the search.

though the pointer-to-pointer
to a node is not returned by `search`. If that is what you mean
by "technique" then you're right; doing that in Rust is
inconvenient because it violates the borrow checker's rules
about the existence of multiple simultaneous mutable references
to an object.

Yes, that's what I meant by "technique". And it's possible in safe
Rust, but I had a very hard time finding it (and for a while thought
that it is not possible). The fact that you thought it is not
possible in safe Rust means that it is not just my inexperience at
fault here.

But I claim that is just a detail, and not a
terribly interesting one at that; certainly not an impediment to
substituting Rust for C in systems programming.

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not
inherently unsafe, and do it without needing to duplicate code of
other nastyness. You may wonder about "inherently unsafe": I have no definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Even so, as I said, one _can_ use the same technique using a
smallish-bit of `unsafe` code.

That's cool, but given that I have difficulty understanding why the
compiler complained about my version with separate search, I feel very uncomfortable in asserting to the compiler that my use of unsafe
features is safe once we leave the unsafe block.

Frankly, unless I was doing something very odd, I wouldn't write
my own binary search tree at all; the standard library's
collections implementations are pretty good

And I actually don't use binary search trees anyway, neither
self-written nor from libraries, because hash tables tend to be the
better alternative, except when I want to know the next-higher element
or somesuch. But being able to have a reference to a field is also
useful when implementing hash tables.

But anyway, the libraries have to be written in some language, and
given that Rust fans tell us to rewrite all C code in Rust, I would
expect that the library should be written in Rust, and, in particular
in safe Rust (otherwise, why rewrite it in Rust?).

And actually, we teach our students how to write this stuff (even in
Java), because we think it teaches them something useful. And at
least one Rust fan thinks so, too, and wrote "Learn Rust With Entirely
Too Many Linked Lists", where I found out how to implement the
mentioned technique in safe Rust.

Given that I do not understand the automagic stuff done by the Rust >>compiler enough to get this kind of tree insertion past the borrow
checker, even though it is possible, I don't trust my capabilities to
audit unsafe Rust.

Is it significantly different than doing so in C, Pascal, or
Forth? See the second program, above; the use of `unsafe` in
the bits that correspond to your sketch in C is constrained to
two places that indirect raw pointers.

I may be able to shut up the compiler and get an executable with
"unsafe", but will the resulting program work? And I can have the
same assurance in C or Forth, so why should I switch to Rust to get
that?

It's so common that "fighting the borrow checker" is the
community's slogan to describe it.

Sounds to me like "the community" has found a convenient cliche to
avoid thinking about why people have difficulties with Rust, and why
these difficulties may increase as Rust advances.

From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was
added later, as a convenience for the programmers who already knew the >>language. So the Rust programmers of the early days formed a mental
model based on "Pedestrian Rust" (i.e., with less automagic), and when
they see a program with more automagic, and need to understand some >>conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern >>language. There are hints in the books I read, but not enough to get
a firm foundation.

Early Rust was very different, and much closer to a managed
language with garbage collection, green threads, a heavy-weight
runtime, etc. Put another way, the trend has been less and less
"automagic" (as you put it) and making things more explicit over
time.

What I mean is the automatic dropping, and the fact that the Box stuff
only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type
declaration there, though).

You keep conflating things you are not familiar with in a
language you are not familiar with, with the idea that those
things are "automagic." But really there is no magic here, and
I suspect the answer to your question about how one learns to
adapt their mental model of Rust is to first stop thinking of it
as magical.

The language hides a number of things with automation, and given that
I have no good mental model for that, following Clarke's third law
("Any sufficiently advanced technology is indistinguishable from
magic."), I refer to that automatic stuff as "automagic stuff". I
don't think it's magic, it just tries to be indistinguishable. It
shouldn't.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >[email protected] (Dan Cross) writes:

[Crossposted and and Followup-To: comp.programming]

Given that I don't subscribe to c.p, I kept comp.arch in the
Newsgroups.

Ok. If it doesn't bother the regulars, then I guess that's
fine. It seems off-topic, but sure.

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

My goal was to implement search tree insertion as efficiently and >>>compactly as in Pascal, C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

An intersting way to write it; I understand you're trying to
reuse `search` in `insert`, below, and thus why you want to
return `rootp`.

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);

I know you said this was untested; clearly you should not
indirect the result of `search` here.

struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these >>>languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

I also knew Java solutions to the problem:

1) Special-case the root (which you typically have to do in Java
anyway, and otherwise always keep a pointer to the last tree node
around, and also keep the knowledge about the last left-or-right
decision around (or take it again). This all leads to quite a bit of >>>code that is duplicated relative to the code above.

2) Recurse into the tree and rewrite all the links to the subtrees
along the spine of the search. This is not quite as duplicative as 1) >>>(but the root still has to be handled separately), but it performs >>>several writes instead of just one, and the recursion is not a tail >>>recursion, so is relatively expensive.

Or, 3) Simply reimplement the comparison in `insert`

That goes along with 1), but I forgot to mention it.

It is an important distinction.

it's a trivial amount of code.

There's the rub. I don't consider a factor of ~2 trivial, even if it
is only 20 lines of code.

Repeating the conditional is 5 lines, including the closing
brace on a ine by itself. The `while` surrounding it is another
2, again including the closing brace.

And in particular, "simply reimplement"
means that the same thing occurs several times in the code, and in >maintainance one must remember to change all of the occurences.

It's a loop around a match over a conditional expression:

while let Some(node) = root {
root = match key.cmp(&node.key) {
Ordering::Less => &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => &mut node.right,
};
}

And in fact it _has_ to be different in a way, because the
reference must be mutable, whereas for searching as a lookup,
that is not necessary.

You could wrap that in a macro if you really wanted to.

Fortunately, that's not necessary in Rust. But the fact that you did
not find it tells me that Rust is hard even for experienced Rust
programmers.

I do not know what you are referring to when you write, the
"fact that you did not find it"; did you not notice that I gave
you _two_ programs, one of which was pretty much the same as the
C program you gave? What, exactly, are you referring to?

I chose a variant of (1) for my implementation, but only because
it was easy, not because it was required. No unsafe code or
fancy reference counting here.

BEGIN `tree.rs`<---

//! Simple binary search tree.

use std::cmp::Ordering;
use std::fmt::Debug;

/// A binary search tree over any key type that implements a
/// total ordering.
pub struct Tree<K: Debug + Ord, V: Debug> {
root: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Tree<K, V> {
/// Creates a new, empty tree.
pub fn new() -> Tree<K, V> {
Tree { root: None }
}

/// Searches the tree for the given key, and returns
/// `Some(&value)` if it's here, otherwise returns None.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// tree.insert(2, 200);
/// tree.insert(1, 100);
/// assert_eq!(tree.search(&0), None);
/// assert_eq!(tree.search(&1), Some(&100));
/// assert_eq!(tree.search(&2), Some(&200));
/// ```
pub fn search(&self, key: &K) -> Option<&V> {
let mut root = &self.root;
while let Some(node) = root {
match key.cmp(&node.key) {
Ordering::Less => root = &node.left,
Ordering::Equal => return Some(&node.value),
Ordering::Greater => root = &node.right,
}
}
None
}

/// Inserts the given `value` into the tree with the given
/// `key`. Returns true if the node was inserted, or false
/// if the key was already in the tree.
///
/// # Example
///
/// ```
/// let mut tree = tree::Tree::<i32, i32>::new();
/// assert_eq!(tree.insert(1, 100), true);
/// assert_eq!(tree.insert(1, 200), false);
/// assert_eq!(tree.insert(2, 100), true);
/// ```
pub fn insert(&mut self, key: K, value: V) -> bool {
let mut root = &mut self.root;
loop {
let Some(node) = root else {
root.replace(Node::new(key, value));
return true;
};
match key.cmp(&node.key) {
Ordering::Less => root = &mut node.left,
Ordering::Equal => return false,
Ordering::Greater => root = &mut node.right,
}
}
}

/// Print the tree, if it is not empty.
pub fn print(&self) {
if let Some(node) = &self.root {
node.print();
}
}
}

// A node in the tree owns its key, value, and left and right
// children.
struct Node<K: Debug + Ord, V: Debug> {
key: K,
value: V,
left: Option<Box<Node<K, V>>>,
right: Option<Box<Node<K, V>>>,
}

impl<K: Debug + Ord, V: Debug> Node<K, V> {
/// Creates a new boxed node owning the given key and value.
pub fn new(key: K, value: V) -> Box<Node<K, V>> {
Box::new(Node {
key,
value,
left: None,
right: None,
})
}

/// Pre-order print of this node and its children.
pub fn print(&self) {
if let Some(left) = &self.left {
left.print();
}
println!("key = {:?}, value = {:?}", self.key, self.value);
if let Some(right) = &self.right {
right.print();
}
}
}

END `tree.rs`<---

Note that there's more code here than in your C code, but this
also does a lot more; this is generic over any key and value
types where the key type implements a total ordering, and where
both types implement the `Debug` trait (so they can be printed).

If I don't need any of that, does it get smaller? I don't think so.

Here's my attempt, and I expect that experienced Rust programmers will
find ways to improve on it. It includes a lookup function:

-------------------
use std::cmp::Ordering;

pub struct Tree<K: Ord, V> {
root: Subtree<K, V>,
}

type Subtree<K,V> = Option<Box<Node<K,V>>>;

struct Node<K: Ord, V> {
key: K,
val: V,
left: Subtree<K, V>,
right: Subtree<K, V>,
}

impl<K: Ord,V> Tree<K,V> {
pub fn new() -> Self {
Tree { root: None }
}

pub fn insert(&mut self, key: K, val: V) {
let mut t = &mut self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => {node.val = val; return;},
Ordering::Less => t = &mut node.left,
Ordering::Greater => t = &mut node.right,
};
};
*t = Some(Box::new(Node {key, val, left: None, right: None}))
}

pub fn lookup(&self, key: K) -> Option<&V> {
let mut t = &self.root;
while let Some(node)=t {
match key.cmp(&node.key) {
Ordering::Equal => return Some(&node.val),
Ordering::Less => t = &node.left,
Ordering::Greater => t = &node.right,
};
};
None
}
}

This is essentially the same program I just presented to you;
you added a type alias, changed `insert` to set the value, and
used `*t` instead of `.replace` for inserting a new node, used
ersatz formatting (ie, not `rustfmt`), and omitted the comments.

I find it strange that you claim this as different from what I
presented to you, except in trivial details, while also telling
me that I "did not find" something.

Are you sure you actually ready my post, and the programs in it?

fn main() {
let mut q1 = Tree::new();
q1.insert(2,"abc".to_string());
q1.insert(3,"def".to_string());
q1.insert(1,"ghi".to_string());
q1.insert(3,"jkl".to_string());
println!("{:?}",q1.lookup(1));
println!("{:?}",q1.lookup(2));
println!("{:?}",q1.lookup(3));
}
----------------------------

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *" >variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

Sure. I do not think it is an interesting exercise, though.

insert now integrates search, because I could not satisfy the compiler
with a separate search; maybe a more experience Rust programmer can
separate it out again. The advantage is that there is no need to
combine the found and notfound cases in one return value in search,
only to handle them as separate cases in insert. But at least there
is no duplication of the comparison code.

I fail to see how your program is very different from mine,
aside from using the type alias for `Subtree`. The comparison
is clearly duplicated in your code. Perhaps you are commenting
on a hypothetical where that does not happen, as in my second
example?

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable
reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

If it offends you that much, you could use a macro.

By analogy, in your C, how would it affect things if you wanted
to `const` qualify the tree pointer for lookups?

Of course, if search is factored out, both clients have to explicitly
check for both outcomes and have code for both. But that's probably >preferable to duplicating the search.

See my second program in the post you responded to.

though the pointer-to-pointer
to a node is not returned by `search`. If that is what you mean
by "technique" then you're right; doing that in Rust is
inconvenient because it violates the borrow checker's rules
about the existence of multiple simultaneous mutable references
to an object.

Yes, that's what I meant by "technique". And it's possible in safe
Rust, but I had a very hard time finding it (and for a while thought
that it is not possible). The fact that you thought it is not
possible in safe Rust means that it is not just my inexperience at
fault here.

I did not say that it was "not possible"; indeed, I can think of
any number of ways to do it, using interior mutability, arcs,
etc. I said it was inconvenient, and I would argue not very
interesting.

You seem to be claiming you have a solution to this, but have
yet to present that code; your program above was basically a
copy of my program, and your commentary suggests you couldn't
figure out a different way to write it yourself.

But I claim that is just a detail, and not a
terribly interesting one at that; certainly not an impediment to >>substituting Rust for C in systems programming.

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not
inherently unsafe, and do it without needing to duplicate code of
other nastyness.

I think that criteria is both silly and arbitrary, and has no
basis in actual practice. You are asserting that an arbitrary
implementation detail of this one program is a useful yardstick
by which to measure a language's applicability to an entire
problem domain, and then defined your criteria so that it
excludes the most obvious translation.

You may wonder about "inherently unsafe": I have no
definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Actually, I think perhaps it's the other way around: you do not
seem to know what "unsafe" means in a Rust context. It is
merely a statement that the compiler cannot infer that the
"unsafe" code meets the language's memory safety criteria, and
that the programmer is asserting that it does; that is exactly
the same as every line in a C program.

Even so, as I said, one _can_ use the same technique using a
smallish-bit of `unsafe` code.

That's cool, but given that I have difficulty understanding why the
compiler complained about my version with separate search, I feel very >uncomfortable in asserting to the compiler that my use of unsafe
features is safe once we leave the unsafe block.

I'm afraid that sounds like a problem for you to deal with, not
a problem with Rust.

Frankly, unless I was doing something very odd, I wouldn't write
my own binary search tree at all; the standard library's
collections implementations are pretty good

And I actually don't use binary search trees anyway, neither
self-written nor from libraries, because hash tables tend to be the
better alternative, except when I want to know the next-higher element
or somesuch. But being able to have a reference to a field is also
useful when implementing hash tables.

But anyway, the libraries have to be written in some language, and
given that Rust fans tell us to rewrite all C code in Rust, I would
expect that the library should be written in Rust, and, in particular
in safe Rust (otherwise, why rewrite it in Rust?).

I'm not sure how useful it is to try to explain this, since your
thoughts on the matter appear to have already calcified.

But the reason is that locality of reasoning is a powerful tool
when building reuseable components. Does the Rust standard
library use `unsafe` code? Yes, it does. However, it wraps
that in a safe facade, and competent Rust programmers seek to
minimize it. The `unsafe` code is then heavily audited; this
does not guarantee bug freedom, but no one serious ever claimed
that it did. However, it _does_ make debugging dramatically
easier: if a program dumps core at some point down the road,
it's likely that the crash originated in `unsafe` code in a
library, and that becomes the focus for looking for the bug.

And actually, we teach our students how to write this stuff (even in
Java), because we think it teaches them something useful. And at
least one Rust fan thinks so, too, and wrote "Learn Rust With Entirely
Too Many Linked Lists", where I found out how to implement the
mentioned technique in safe Rust.

Yes. Gankra was also the driving force behind the strict
pointer provenance work. You may enjoy her writing on, "the
tower of weakenings."

Given that I do not understand the automagic stuff done by the Rust >>>compiler enough to get this kind of tree insertion past the borrow >>>checker, even though it is possible, I don't trust my capabilities to >>>audit unsafe Rust.

Is it significantly different than doing so in C, Pascal, or
Forth? See the second program, above; the use of `unsafe` in
the bits that correspond to your sketch in C is constrained to
two places that indirect raw pointers.

I may be able to shut up the compiler and get an executable with
"unsafe", but will the resulting program work? And I can have the
same assurance in C or Forth, so why should I switch to Rust to get
that?

Because with C and Forth you can't just wrap the unsafe bits
behind a safe interface that consumers can rely on, placing the
burden on all users to ensure safety, whereas in Rust, you can.

Consider the arguments in in your Tree example; the tree itself
is a pointer to a pointer to the root. What if that pointer is
garbage? What if it's dangling? In Rust, `&self` is guaranteed
to be a valid, non-nil reference to a live object, and moreover
you are guaranteed that no other thread is trying to mutate that
object while you're holding that ref. Neither C nor Forth can
give you any such guarantee. Similarly, `&mut self` guarantees
that no other reference to the object exists. Visibility
similarly gives you control; by wrapping, say, a raw pointer
inside of an `struct` as a non-public member, you can guarantee
that the same pointer is the one used in multiple, subsequent
function calls: as written, your C code has two functions that
share no relationship save that one calls the other. I could
cal `insert`, and then go and muck with the tree myself, so that
its ordering constraints are violated, and then call `insert`
again and have a tree that didn't respect the BST properties. I
could pass a random garbage `root` pointer and cause the program
to crash. And so on.

Do I really need to go on, here?

It's so common that "fighting the borrow checker" is the
community's slogan to describe it.

Sounds to me like "the community" has found a convenient cliche to
avoid thinking about why people have difficulties with Rust, and why
these difficulties may increase as Rust advances.

Bluntly, I think you are not really in a position to make that
claim, and are inventing excuses to justify your preconceptions
and biases.

From the books I read, I get the impression that
Rust used to have less automagic stuff, and much of the automagic was >>>added later, as a convenience for the programmers who already knew the >>>language. So the Rust programmers of the early days formed a mental >>>model based on "Pedestrian Rust" (i.e., with less automagic), and when >>>they see a program with more automagic, and need to understand some >>>conveniently short piece of Rust code in detail, they form a mental
model of the code in Pedestrian Rust. But how can a Rust programmer
who starts now learn Pedestrian Rust and how it relates to the modern >>>language. There are hints in the books I read, but not enough to get
a firm foundation.

Early Rust was very different, and much closer to a managed
language with garbage collection, green threads, a heavy-weight
runtime, etc. Put another way, the trend has been less and less >>"automagic" (as you put it) and making things more explicit over
time.

What I mean is the automatic dropping, and the fact that the Box stuff
only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type
declaration there, though).

Drop and box as a smart pointer is simply "RAII", which has been
in C++ since the 1980s. Hindley and Milner created the type
inference rules you are referring to here in the 1970s.

You keep conflating things you are not familiar with in a
language you are not familiar with, with the idea that those
things are "automagic." But really there is no magic here, and
I suspect the answer to your question about how one learns to
adapt their mental model of Rust is to first stop thinking of it
as magical.

The language hides a number of things with automation, and given that

No, it really doesn't.

I have no good mental model for that, following Clarke's third law
("Any sufficiently advanced technology is indistinguishable from
magic."), I refer to that automatic stuff as "automagic stuff". I
don't think it's magic, it just tries to be indistinguishable. It
shouldn't.

Sorry, but I see no evidence that you have taken the time to
actually understand that the things you attribute to automation
are actually rather explicit; you're a smart guy, and I'm quite
sure you could do it if you wanted; it's really all rather
obvious once you dig into it a little bit. Given that, and that
you continue to assert that it's "automagic" I can tell that you
simply don't want to, perhaps because it is different from what
you are used to.

Hint: when an object goes out of scope, it is "dropped." A type
can register a "drop handler" by implementing the `Drop` trait.
For a smart pointer like `Box`, that simply frees the thing it
points to. Same with a Mutex: the `lock()` operation returns a
`MutexGuard` object that holds the lock. When it goes out of
scope, its `drop()` method unlocks the mutex. Cf, https://cliffle.com/blog/rust-mutexes/

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

On Tue, 06 Oct 2026 08:29:19 GMT
[email protected] (Anton Ertl) wrote:

[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote:

Tim Rentsch <[email protected]> writes:

That's good to know but what is a good resource to learn the Rust >>>language? I've looked at the Rust book several times and each
time come away rather frustrated.

If you mean "The Rust Programming Language", I came away from it >>disillusioned.

The reason was that I could not get a search-tree insertion
technique to work that can be implemented in e.g., Pascal, C, and
Forth, but not in Java (because in Java I cannot produce references
to a field inside an object).

I think what you mean to say is that you couldn't find a way to
implement that in the manner you were accustomed to thinking
about the problem, given your prior experience.

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal,

I suppose, you mean some extended Pascal dialect here, because I can not imagine how you code an example below in Standard Pascal.
Then again, I learned Pascal ~40 years ago and didn't use it in
practice since 1989 or 1990, so can easily miss something.

I would think that it is possible to code your example in Standard
Ada83, but not in "checked" subset of it.

C or Forth (and in contrast to Java), ideally
in safe Rust. Here it is in C (untested):

struct tree {
int key; /* or some other key type */
int val; /* or some other value type */
struct tree *left;
struct tree *right;
};

struct tree **search(struct tree **rootp, int key)
{
while ((root=*rootp)!=NULL && key != root->key) {
if (key < root->key)
rootp = &(root->left);
else
rootp = &(root->right);
}
return rootp;
}

void insert(struct tree **rootp, int key, int val)
{
struct tree **nodep = **search(rootp, key);
struct tree *node = *nodep;
if (node == NULL) {
node = malloc(sizeof(tree));
node->key = key;
node->left = NULL;
node->right = NULL;
*nodep = node;
}
node->val = val;
}

Passing a reference to a mutable field is what is done in these
languages, and I don't know an efficient and similarly compact
technique that does not pass a reference to a mutable field.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Terje Mathisen <[email protected]> schrieb:

My old asm/C brain _knows_ that a slice of something with a known
address and total length is effectively the same thing as an unmutable array.

Even if it isn't, the fact that I start by verifying that the slice
extends at least 7 bytes past the p index means that all of p,
p+1,p+2...p+6 must be valid, right?

Range checking is very difficult for a compiler, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=VRP .
--
This USENET posting was made without artificial intelligence,
artificial impertinence, artificial arrogance, artificial stupidity,
artificial flavorings or artificial colorants.
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

Michael S <[email protected]> writes:

On Tue, 06 Oct 2026 08:29:19 GMT
[email protected] (Anton Ertl) wrote:

My goal was to implement search tree insertion as efficiently and
compactly as in Pascal,

I suppose, you mean some extended Pascal dialect here, because I can not >imagine how you code an example below in Standard Pascal.
Then again, I learned Pascal ~40 years ago and didn't use it in
practice since 1989 or 1990, so can easily miss something.

Page 75 and 76 of my copy of "Programming in Modula-2" (Second Edition)
contain this:

TreePtr = POINTER TO TreeNode;
TreeNode =
Record
key: CARDINAL;
data: ...
left, right: TreePtr;
END;

PROCEDURE search(VAR p: TreePtr; x: CARDINAL): TreePtr;
BEGIN
IF p # NIL THEN
IF p^.key < x THEN
RETURN search(p^.right,x)
ELSIF p^.key > x THEN
RETURN search(p^.left, x)
ELSE
RETURN p
END
ELSE (* not found, hence insert *)
NEW(p);
WITH p^ DO
key := x;
left := NIL;
right := NIL;
END;
RETURN p
END
END search

You would invoke this with

search(root,needle)^.data := ...;

in order to actually change the field "data", performing the insert functionality.

One would not want to use this procedure for lookup, given that it
inserts a node with an uninitialized data field when the key is not
found. Wirth gives a loop implementation of lookup before the
PROCEDURE search.

Note that the "VAR" in front of the p makes p a reference parameter
rather than a value parameter (like x), which is key to making this
work for insertion. This language feature is also present in Pascal;
the Pascal syntax is different, but I don't think that prevents
implementing this approach.

Using recursion is necessary here because Modula-2 and Pascal support references to variables or fields only for parameters. But the
recursive calls are tail-recursive (I don't think that Wirth's
Modula-2 or Parcal compilers optimized tail recursion, though).

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.arch

[email protected] (Dan Cross) writes:

In article <[email protected]>,
Anton Ertl <[email protected]> wrote: >>[email protected] (Dan Cross) writes:

[Anton Ertl:]

I do not know what you are referring to when you write, the
"fact that you did not find it"; did you not notice that I gave
you _two_ programs, one of which was pretty much the same as the
C program you gave? What, exactly, are you referring to?

I was referring to your safe Rust solution. However, I did not look
at it closely enough, especially at your insert, to realize that what
you had done is to turn search into lookup, and that you do not call
search from insert, like the C version does.

I just saw that there is a similar match in your insert as in search
(and the non-recursive Java version would also have that) and set out
to refine an existing linked-list implementation with insertion at the
end into a tree insertion that does not repeat the match, and I used
your match code from search for the parts that the linked-list
implementation does not do.

The list variant has the walk to the end separated from the actual
insertion, and the C tree variant also does it that way, and I wanted
the Rust version to do the same, but could not get it past the Rust
compiler. The insertion code did not look particularly nice, either,
checking for something that is alreadu known in the search code. so
to work around the compiler problem, I eventually decided to inline
the search code into insert, and I could get that to compile.

For testing I then added a lookup, which was derived from the search
part of insert, without mut stuff, so it's full circle back at your
search.

Anyway, yes, your insert does not work the Java version, but like the
C version with search() inlined into insert(), and like the insert I
finally arrived at.

Which leads to the question? Can an experienced Rust programmer do a
search that works like the C search(), and an insert that calls
search() and then uses the reference to either update a node or insert
a new one?

Like your code and Java code, this has a separate type Tree with a
field root and with its own new function, while in C a "struct tree *" >>variable can serve as root pointer; and this leads to an additional
line each in insert and lookup. Can we do without most of that
(havibf a constructor is useful) and just use Subtree instead of Tree?

Sure. I do not think it is an interesting exercise, though.

I tried it for a while, and did not get anything but more and more
compiler errors.

The integration of search in insert led to a duplication of most of
the search code in lookup. However, requiring a mutable reference is
not necessary for the lookup code, so a search that takes a mutable >>reference and returns a mutable reference is too restrictive for
lookup. But maybe a more experienced Rust programmer can write a
generic search that takes an &mut tree for insert, and a & for lookup.

If it offends you that much, you could use a macro.

Good to know that there is this option.

By analogy, in your C, how would it affect things if you wanted
to `const` qualify the tree pointer for lookups?

C works perfectly fine without "const", so why would I want to do that?

By contrast, Rust is picky about "mut". If I add it everywhere where
the syntax allows it (which might be the analogon of leaving "const"
away), the borrow checker will complain about programs that it
accepted before adding all the "mut"s.

I think that, in order to be the rightful heir, safe Rust should be
able to do everything one can do in the other language that's not >>inherently unsafe, and do it without needing to duplicate code of
other nastyness.

I think that criteria is both silly and arbitrary, and has no
basis in actual practice. You are asserting that an arbitrary
implementation detail of this one program is a useful yardstick
by which to measure a language's applicability to an entire
problem domain,

Not one detail, the collection of all the details. This is one.

You may wonder about "inherently unsafe": I have no
definition for that yet, but I would not kno why inserting a node into
a search tree would ever fall into that category,

Actually, I think perhaps it's the other way around: you do not
seem to know what "unsafe" means in a Rust context. It is
merely a statement that the compiler cannot infer that the
"unsafe" code meets the language's memory safety criteria, and
that the programmer is asserting that it does;

I understand that.

that is exactly
the same as every line in a C program.

The decisive difference is that in a C program there is no end to an
unsafe block, where I have to satisfy safety criteria that are beyond
my experience level.

I'm afraid that sounds like a problem for you to deal with, not
a problem with Rust.

Sure, and the way I deal with that is to not use unsafe Rust.

What I mean is the automatic dropping, and the fact that the Box stuff
only occurs in the type declarations, but is automatically
dereferenced or otherwise automatically handled; "let x = ..."
produces a type automatically (but I guess you could put a type
declaration there, though).

Drop and box as a smart pointer is simply "RAII", which has been
in C++ since the 1980s. Hindley and Milner created the type
inference rules you are referring to here in the 1970s.

And?

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <[email protected]>
--- Synchronet 3.22a-Linux NewsLink 1.2