How expensive is Rc<RefCell<...>> + .borrow_mut()?

#1
  1. I admit upfront I am not sure what is even the right thing to measure.

  2. I’m building a small GC-less scheme-like in Rust. To handle recursive functions, I’ve basically decided to go with the approach of Rc<RefCell<...>>

  3. This will end up incurring a .borrow_mut() on every function cal… Unfortunately, because this is a scheme-like, every ( is a function call. :frowning:

  4. For those who have done something similar, how expensive is .borrow_mut() are we talking “so cheap taht the memory indirection cost overshadows it” or “as expensive as locking” or … ?

#2

Worst case: it is as expensive as a panic!
Best case: it does some pointer manipulation to create the guard and then sets a flag assigning the value as already taken

Any case: it checks if it is already taken

1 Like
#3

I was hoping the answer would be: very cheap, don’t worry about it. This sounds expensive but is very helpful. Thanks!

#4

.borrow_mut() branches based on the read-write of a isize and compares it to a given UNUSED constant (currently const UNUSED: isize = 0) before lending the RefMut struct.

It is not that expensive, imho (it’s similar to writing one value of a slice: a bound check + a write)

.borrow_mut() should never panic, unless you violate the usage contract, such as when you index out of bounds.

Now, an interesting question regarding the branching would be, if instead of

        match borrow.get() {
            UNUSED => {
                borrow.set(UNUSED - 1);
                Some(BorrowRefMut { borrow })
            },
            _ => None,
        }

we could have:

#![feature(core_intrinsics)]
use ::std::intrinsics::unlikely;

unsafe {
    if unlikely(borrow.get() != UNUSED) {
        None
    } else {
        borrow.set(UNUSED - 1);
        Some(BorrowRefMut { borrow })
    }
}
3 Likes
#5

It depends on the workload. If you are doing mostly reads from that cell, plus having a lot of accesses, then it may be relatively expensive. However you are doing a borrow_mut, so most likely you have at least one write during access.

Borrowing incurs two writes to memory for each access, for the RefCell's fields. A write puts the related cache line (64 bytes) in an exclusive state where it would later be flushed back to main memory, utilizing memory bandwidth. You may get away with only a single cache line flush if the second write happened quickly enough.

The size_of::<T> may also play a factor. If it is small enough, hopefully with the added Rc + RefCell wrapping causing the entire backing store of Rc<RefCell<T>> to fit in a single cache line, then all writes may unite into a single cache line flush. Otherwise, you may causing more cache lines to be come exclusive and invalidated.

1 Like