Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Group Borrowing: Zero-cost memory safety with fewer restrictions

verdagon.dev

Post reply on HN
Print view View original

81–87 of 87 posts

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#81

Post by thomasmg »

Dagonfly wrote: post #80
thomasmg wrote: post #78

Earlier quoted context omitted.

Yes, I see your point. In Rust, the owner, and the mutable borrower can change the pointer itself (like C realloc). If multiple "mut" borrows are allowed, then this would be unsafe, so I understand "unstable mut" would solve this problem - but result in a new colouring problem. My solution to this would be: in a new language, do not allow reallocation. Not for owners, and not for mut borrow. This is what Java does: a…

> ArrayList is a wrapper around an array, and so adding entries will not move the ArrayList object, just the (wrapped) private array. That's also how Vec works in Rust. Vec is just (buf_ptr, capacity, len) where capacity is the allocated size of the buffer. The problem still exists though. ``` let mut v = vec![1, 2 ,3]; let x: &i32 = &v[0]; v.push(4); println!("First element {x}"); ``` The `push` might realloc the ar…

In Rust, a vector is a "fat pointer" (with pointer to the array and length / capacity) which lives on the stack. In Java, the pointer to the array and length / capacity lives in the heap. So in Java, there is an indirection, and it is allowed to have multiple pointers to the ArrayList object.

> A language without realloc sounds painful. Any growing container would lead to stale data.

I think it's not so much about realloc, but about whether it's a fat pointer or not. (I could imagine that Java uses something like realloc for the array, if there is only one pointer to the array for sure).

Fat pointers have some advantages and some disadvantages. Rust chose fat pointers, I assume for performance reasons. That's fine. Java doesn't. But I don't think that's a _huge_ performance disadvantage for Java. What I'm arguing is not so much that one is better and the other is worse, just that there are advantages and disadvantages. Rust might be slightly faster, but a language without (this kind of) fat pointers could potentially be easier to use.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#82

Post by Measter »

codedokode wrote: post #64
kbolino wrote: post #55

Earlier quoted context omitted.

Yes, that's how Cell works. If you want to work with the data in place, you need a RefCell instead.

But it is expensive, because it does run-time checks? Or they are optimized out?

RefCell does do runtime checks, but the cost is checking the counter, a conditional branch, then incrementing/decrementing the counter twice.

Because the counter is non-atomic and non-volatile the optimiser can sometimes optimise out the actual modification of the counter. It's not free, but it's not also not a huge expense.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#83

Post by kibwen »

modulared wrote: post #17
kibwen wrote: post #2

> In any language, when we hand a function a reference to an object, that function can't destroy the object, nor change its type This isn't quite true. While Rust doesn't currently support this, people have proposed the concept of `&own` references that take ownership of the object and free it when the reference goes out of scope (consider that Rust's standard destructor signature, `fn drop(&mut)`, should probably ta…

> I believe that languages with typestate can cause types to change as a result of function calls Do you have any specific languages?

I've only heard of this concept in academic languages, I don't feel knowledgeable enough to recommend any specific one. In terms of mainstream languages, I think an analogous concept is the use-before-initialization analysis that languages like Rust employ, e.g. if I have a variable defined like this:

    let x: u8;
I can't actually do anything with this variable:

    foo(x); // error
Except I can apply the initialization operator:

    x = 42;
And now I can do things with this variable as usual.

But consider that the type of x hasn't changed as a result of the initialization. Beforehand it was a u8, and afterward it was still a u8, and yet something about the state of the variable changed my ability to use it in various contexts. I believe that typestate is something like this, generalized to allow variables to flow through states (like a compile-time state machine) to ensure that things happen in the correct order.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#84

Post by Dagonfly »

thomasmg wrote: post #81
Dagonfly wrote: post #80

Earlier quoted context omitted.

> ArrayList is a wrapper around an array, and so adding entries will not move the ArrayList object, just the (wrapped) private array. That's also how Vec works in Rust. Vec is just (buf_ptr, capacity, len) where capacity is the allocated size of the buffer. The problem still exists though. ``` let mut v = vec![1, 2 ,3]; let x: &i32 = &v[0]; v.push(4); println!("First element {x}"); ``` The `push` might realloc the ar…

In Rust, a vector is a "fat pointer" (with pointer to the array and length / capacity) which lives on the stack. In Java, the pointer to the array and length / capacity lives in the heap. So in Java, there is an indirection, and it is allowed to have multiple pointers to the ArrayList object. > A language without realloc sounds painful. Any growing container would lead to stale data. I think it's not so much about re…

That's true.

Though, for my example, the storage location of the array metadata/fat pointer is not relevant.

In Rust you can hold references directly into the buffer backing the array (`&v[0]`).

My Java knowledge is quite rusty at this point. AFAIK, a `ArrayList` in Java stores pointers to MyType in the buffer. So, when indexing into a ArrayList, you never hold references into the actual buffer. Instead you get a shared-pointer to the class data. It's the indirection of the array entry that saves you during reallocation of the buffer.

Also because Java is a GC'ed VM, it wont dealloc the elements references by the array, as long as there are other references to an element.

The equivalent in Rust is `Vec>` where holding an `&Rc` referencing into the vec's buffer is problematic during reallocation. But, cloning the Rc and holding on to it is perfectly fine.

The initial point of this thread was that you can have a Rust-like language where you can hold multiple mutating (aliasing) references and prevent use-after-free. This won't work. Without a GC or RC, you can use one reference to "rug-pull" the memory that is aliases by the other reference.

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#85

Post by thomasmg »

Dagonfly wrote: post #84
thomasmg wrote: post #81

Earlier quoted context omitted.

In Rust, a vector is a "fat pointer" (with pointer to the array and length / capacity) which lives on the stack. In Java, the pointer to the array and length / capacity lives in the heap. So in Java, there is an indirection, and it is allowed to have multiple pointers to the ArrayList object. > A language without realloc sounds painful. Any growing container would lead to stale data. I think it's not so much about re…

That's true. Though, for my example, the storage location of the array metadata/fat pointer is not relevant. In Rust you can hold references directly into the buffer backing the array (`&v[0]`). My Java knowledge is quite rusty at this point. AFAIK, a `ArrayList ` in Java stores pointers to MyType in the buffer. So, when indexing into a ArrayList, you never hold references into the actual buffer. Instead you get a sh…

> In Rust you can hold references directly into the buffer backing the array

Yes! But I am arguing that this prevents having multiple mutable references

> My Java knowledge is quite rusty > Also because Java is a GC'ed VM ...

Your Java knowledge is fine :-) But I'm arguing that you don't strictly need a GC'ed, or RC'ed language: if done "correctly", multiple mutable references are possible. Just not with fat pointers! The programming language I'm building allows this even today. You can try it in the playground [1]:

    fun main()
        list := List+(int[4]) # = array.len
            n : int[array.len * 2]
            for i := until(array.len)
                n[i] = array[i]
            array = n
        array[size] = x
        size += 1
So "List+" is owned type (just "List" without "+" would be reference counted). You may want to look at the generated C code at the end of the page.

[1]: https://thomasmueller.github.io/bau-lang/

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#86

Post by john-h-k »

thomasmg wrote: post #85
Dagonfly wrote: post #84

Earlier quoted context omitted.

That's true. Though, for my example, the storage location of the array metadata/fat pointer is not relevant. In Rust you can hold references directly into the buffer backing the array (`&v[0]`). My Java knowledge is quite rusty at this point. AFAIK, a `ArrayList ` in Java stores pointers to MyType in the buffer. So, when indexing into a ArrayList, you never hold references into the actual buffer. Instead you get a sh…

> In Rust you can hold references directly into the buffer backing the array Yes! But I am arguing that this prevents having multiple mutable references > My Java knowledge is quite rusty > Also because Java is a GC'ed VM ... Your Java knowledge is fine :-) But I'm arguing that you don't strictly need a GC'ed, or RC'ed language: if done "correctly", multiple mutable references are possible. Just not with fat pointers…

You are borrowing the entire list. That’s fine. The problem occurs if you borrow a reference into the list. Java/C# solve this by making that operation impossible. You cannot hold a reference into a vector/list

Re: Group Borrowing: Zero-cost memory safety with fewer restrictions

#87

Post by ntrel »

codedokode wrote: post #27
estebarb wrote: post #9

I'm not sure if I understand it correctly. So, if I have a hashtable, adding or removing an element would invalidate existing pointers to any other element in the hashtable? I guess it makes sense from a memory release POV, but... I end up thinking that for databases using GC or RC is a better approach. Maybe I'm biased, but I have found far easier to work on databases written in C or C#. For that kind of programs I…

Rc is slightly expensive and Gc is super expensive. I would prefer a memory safety for free. As for C, it leaves verifying the safety up to you, it is not easy at all and I would rather spend time on something else using safe languages.

My understanding is that RC is relatively expensive in time (especially for atomic RC) but uses a lot less memory than state of the art fast GC. And RC doesn't handle cycles.
Post reply on HN