Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16937

Re: Rust (was: Optimization by programmers)

Cross-posted to 2 groups.

Show key headers only | View raw

In article <2026Oct10.161800@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>cross@spitfire.i.gajendra.net (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 <2026Oct6.102919@mips.complang.tuwien.ac.at>,
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> 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.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Rust (was: Optimization by programmers) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-07 18:29 +0000
  Re: Rust (was: Optimization by programmers) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-10-10 14:18 +0000
    Re: Rust (was: Optimization by programmers) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-10 17:31 +0000
      Re: Rust (was: Optimization by programmers) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-10-11 15:40 +0000
        Re: Rust Stefan Monnier <monnier@iro.umontreal.ca> - 2026-10-11 14:26 -0400
          Re: Rust cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 19:14 +0000
          Re: Rust Lawrence D’Oliveiro <ldo@nz.invalid> - 2026-10-12 21:15 +0000
        Re: Rust (was: Optimization by programmers) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-12 19:13 +0000

csiph-web