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

Groups > comp.programming > #16936

Re: Rust (was: Optimization by programmers)

Cross-posted to 2 groups.

Show all headers | View raw

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.

>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'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, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

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