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

Groups > comp.programming > #16932

Re: Rust (was: Optimization by programmers)

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show all headers | View raw

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

In article <2026Oct6.102919@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>cross@spitfire.i.gajendra.net (Dan Cross) writes:
>>In article <2026Oct3.131214@mips.complang.tuwien.ac.at>,
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>Tim Rentsch <tr.17687@z991.linuxsc.com> 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.

Back to comp.programming | Previous | Next — 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