These are chat archives for rust-lang/rust

3rd
Feb 2017
Kibeom Kim
@kkimdev
Feb 03 2017 00:24
Q: sometimes I want to do self.some_function(self.some_u32_var) but can't do due to the borrow checker and had to split lines, is there a way to just do it in one line?
Jarred Nicholls
@jnicholls
Feb 03 2017 00:29
@kkimdev unless some_function is used with public inputs too, put the use of the owned u32 inside the function..?
Kibeom Kim
@kkimdev
Feb 03 2017 00:30
@jnicholls yeah some_function is a generic version that can be used with public arguments, and I'm writing a special case function that shortens typing
Jarred Nicholls
@jnicholls
Feb 03 2017 00:41
Since borrows happen within an statement, splitting to two lines is the only way to tell the compiler you want to move (copy) the u32, and then move it again into the call to the function.
Jonas Platte
@jplatte
Feb 03 2017 07:11
@kkimdev That's not currently possible, but making exactly the kind of thing you pasted legal is on this years roadmap: rust-lang/rust-roadmap#16
VJ
@00imvj00
Feb 03 2017 07:31


fn main() {
    let mut tree = BTree::new(5);
    println!("{:?}",tree);
    // tree.insert(5);
}

#[derive(Debug)]
struct BTree<'a> {
    root: &'a mut Node<'a>,
    degree: u32,
}


#[derive(Debug)]
enum Node<'a>{
    Nil,
    Value{
        keys:   Vec<u32>,
        childs: Vec<&'a mut Node<'a>>,
        degree: u32,
        is_leaf: bool,
        no_of_ele: u32,
    }
}

impl<'a> BTree<'a> {
     fn new(deg: u32) -> BTree<'a> {
         BTree{root: &mut Node::Nil, degree: deg }
     }
}
Output :
error: borrowed value does not live long enough
  --> src/main.rs:30:27
   |
30 |          BTree{root: &mut Node::Nil, degree: deg }
   |                           ^^^^^^^^^ does not live long enough
31 |      }
   |      - temporary value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the body at 29:35...
  --> src/main.rs:29:36
   |
29 |        fn new(deg: u32) -> BTree<'a> {
   |  ____________________________________^ starting here...
30 | |          BTree{root: &mut Node::Nil, degree: deg }
31 | |      }
   | |______^ ...ending here

error: aborting due to previous error

error: Could not compile `btree`.
i don't know what is wrong here, can any one help ?
Aleksey Kladov
@matklad
Feb 03 2017 07:33
@i-m-v-j the general problem here is that BTree and Node store references to the nodes, but nobody stores the actual nodes.
In particular, in the new method, the node is a temporary variable, so it is dropped when you return from the function, and Rust rightfully disallows this code.
I think you need BTree { node: Node } and Node { children: Vec<Node> }, without references.
Denis Lisov
@tanriol
Feb 03 2017 07:38
I'd also remove the enum from node in favour of Option<Node>
VJ
@00imvj00
Feb 03 2017 07:50
so i can write new method in node and return node instead of node reference , will that work @matklad ?
VJ
@00imvj00
Feb 03 2017 08:09
'''
struct BTree<'a> {
    root: Node<'a>,
    degree: u32,
}

This worked.

i got the point. upper most struct should own the value. other wise if there is no owner then value is always temp. so it will get de referenced. that is why above error.

here, BTree owns the Node, so there is root node which will be always there, inside that i can have vector or child node references.
@matklad thank you.
Denis Lisov
@tanriol
Feb 03 2017 08:13
The children also need to be owned by something, so most likely not references.
Aleksey Kladov
@matklad
Feb 03 2017 08:15
@i-m-v-j If you are interested, I happen to write a BTree implementation in safe Rust a while ago: https://github.com/matklad/tree_bench/tree/master/src/btree. And of course you can take a look at the BTree from std::collections, but it has a rather cleaver and optimized unsafe implementation.
VJ
@00imvj00
Feb 03 2017 08:18
sure i will sure check it out.
so instead of using direct references , i can use Box for pointers right ? @matklad
Denis Lisov
@tanriol
Feb 03 2017 08:22
I'd use either
children: Vec<Option<Node>>
or
children: [Option<Box<Node>>; NODE_CAPACITY]
VJ
@00imvj00
Feb 03 2017 08:24
children: Vec<Box<Node>>
why not this ?
Box is good right for these sort of things ?
Denis Lisov
@tanriol
Feb 03 2017 08:25
You'll need to chase two pointers to get to a child - one is Box, and the other is inside the Vec
Sergey Noskov
@Albibek
Feb 03 2017 08:25
it's less cache-effective due to memory fragmentation of Boxes
VJ
@00imvj00
Feb 03 2017 08:26
@tanriol you also suggested Box only. @Albibek can you please suggest any alternative then ? i really need to crack this thing.
Sergey Noskov
@Albibek
Feb 03 2017 08:27
@i-m-v-j , Vec<Option<Node>> seems better to me, but it depends of Node implementation
VJ
@00imvj00
Feb 03 2017 08:28
the thing is, it is recursive, so if i want to push it to other node then i need to copy whole thing right ?
instead of just coping pointer ?
Sergey Noskov
@Albibek
Feb 03 2017 08:29
Vec is a few-bytes pointer to heap area
VJ
@00imvj00
Feb 03 2017 08:29
ohhh, it is pointer ???
so Vec will have pointers of the actual value ??
Denis Lisov
@tanriol
Feb 03 2017 08:30
Vec is a smart pointer to a dynamically-allocated array of values
VJ
@00imvj00
Feb 03 2017 08:30
ok.
Sergey Noskov
@Albibek
Feb 03 2017 08:30
it's pointer to beginning of the area + length + some additional data
VJ
@00imvj00
Feb 03 2017 08:31
so now i need to transfer node with 5 MB memory, to other node, if i use Vec<Option<Node>>, i need to copy full data to other node, instead of just point to that node.
Node can be fixed size, but nodes will have childs, so if i store it directly instead of pointers , then at the time of promotion, i need to cope whole node to parent and when spliting i need to copy whole node, that seems kinda expensive op.
that is why i am looking for something , like keeping that Vec of pointers to actual data in child nodes, so when i need to transfer or promote those nodes, i just copy pointers to that nodes.
Sergey Noskov
@Albibek
Feb 03 2017 08:36
If you want to have the independent copy of data, you cannot avoid copying. If you mean moving a node, only few words are copied when copying a vector.
Aleksey Kladov
@matklad
Feb 03 2017 08:37
@i-m-v-j if you want to do shallow copies, then you'll have to use Rc. Cloning a Box copies its contents as well, recursively. But you don't have to actually copy anything when implementing B-Tree, moving nodes should be enough.
Denis Lisov
@tanriol
Feb 03 2017 08:45
Do you know the maximum number of a Node's children? Is there such a limit?
I assume that your node is itself (without its children) fixed-size.
So you need to have a pointer somewhere between a node and its child...
...and it's either a pointer to an array of children
```
Vec<Option<Node>>
Denis Lisov
@tanriol
Feb 03 2017 08:50
...or an array of pointers to children, which (if there's a limit) can be stored inline
[Option<Box<Node>>; NODE_CAPACITY_LIMIT]
@i-m-v-j and the second variant looks better in my opinion
@i-m-v-j thinking furtherer, with Vec you probably don't need an Option, while with array you do.
Aleksey Kladov
@matklad
Feb 03 2017 08:57
For the second option one can use array-vec crate: https://docs.rs/arrayvec/
VJ
@00imvj00
Feb 03 2017 09:29
guys thank you for awesome response, i am bit not sure about move sementics in rust. can it be used in my example case of btrees ?
Denis Lisov
@tanriol
Feb 03 2017 09:33
@i-m-v-j Move semantics should not be a problem. However, ownership is known to become a problem with trees in some cases.
Also, are you sure you need to write one more tree structure and nothing already published is okay for your purposes?
VJ
@00imvj00
Feb 03 2017 09:37
@tanriol i am actually learning to write very efficient and complex rust code. i want to contribute to writing storage engines in pure rust , so people who wants to build databases in rust can use it. i thought this might be a good idea to do it.
Aleksey Kladov
@matklad
Feb 03 2017 09:40
@i-m-v-j I think a good start would be to implement a plain binary search tree, without any balancing procedures. It will help you to get the feeling of the Rust ownership model and move semantics.
VJ
@00imvj00
Feb 03 2017 09:40
sure.
i think that would be great.
i know that if any type implements Copy, then it will be copy sementics, means whole data in memory will be copied, but i am confused about move sementics, how it works, ? just pointer of those data will be transfered or ??
Denis Lisov
@tanriol
Feb 03 2017 09:42
The whole data will be moved to its new place (i.e. copied and the old place logically cleaned)
VJ
@00imvj00
Feb 03 2017 09:43
hmm.
Denis Lisov
@tanriol
Feb 03 2017 09:43
So if you move something often, you probably want it to be compact.
VJ
@00imvj00
Feb 03 2017 09:43
than what is the difference between copy and move semantics ??
ohh i got it.
Denis Lisov
@tanriol
Feb 03 2017 09:44
When you copy, both the original and the copy are valid afterwards. When you move, only the copy is valid and the original is not.
Ed Lewis
@ninjabear
Feb 03 2017 09:45
Move doesn't necessarily move some memory
VJ
@00imvj00
Feb 03 2017 09:45
ok. so if my node size is 100kb, then in move semantics , it will move 100kb to new location every time ??
Denis Lisov
@tanriol
Feb 03 2017 09:46
Unless the optimizer finds some trick. So yes, if the node is large, you want it behind a pointer. In a Box.
VJ
@00imvj00
Feb 03 2017 09:46
yes.
Denis Lisov
@tanriol
Feb 03 2017 09:46
Or Rc if you need it :-)
VJ
@00imvj00
Feb 03 2017 09:47
what do you think would be efficient.
Denis Lisov
@tanriol
Feb 03 2017 10:00
Node with an inline array (maybe ArrayVec, but not required) of pointers to children and a pointer to payload. A total size of maybe 128 or 256 bytes. However, I'm not an expert in databases and storage engines and don't know their requirements well.
Also you will need to think about whether you need the structure to be threadsafe.
VJ
@00imvj00
Feb 03 2017 10:01
right now i am building in memory only, then it will be backed by disk.
yes, we can use some sort of structure where multiple threads can read and single thread will be writing. will that be thread safe ?
Denis Lisov
@tanriol
Feb 03 2017 10:03
Thread safety requires separate considerations - at least to stop the optimizer from breaking it.
VJ
@00imvj00
Feb 03 2017 10:03
yup. i will be thinking that a lot.
how about message passing for all the operations ?
reads from file can be thread safe.
Denis Lisov
@tanriol
Feb 03 2017 10:06
You're going to have an in-memory cache and you'll need to ensure that the writes from your writer process go to memory in the right order to avoid races. The standard synchronization primitives already do this.
VJ
@00imvj00
Feb 03 2017 10:06
yes...
i am following you on github. i will send you repo once i will have something to show.
:)
Jarred Nicholls
@jnicholls
Feb 03 2017 13:42
Under what condition(s) would one hit this unreachable block while using mpsc channel? https://github.com/rust-lang/rust/blob/1.12.0/src/libstd/sync/mpsc/mod.rs#L880
Jarred Nicholls
@jnicholls
Feb 03 2017 13:52
Is this related to a possible reason one would hit this condition? rust-lang/rust#36934
Denis Lisov
@tanriol
Feb 03 2017 13:58
Looks rather likely for me... this unreachable looks like "we were woken up to receive a message, but there's no message in our queue"...
Jarred Nicholls
@jnicholls
Feb 03 2017 14:07
How can that happen with a single consumer? This is kind of a recent issue...surely spurious wake ups would have caused massive issues from day one.
Recent to me that is. App is running from 1.12.
Denis Lisov
@tanriol
Feb 03 2017 14:19
Well, that seems to be exactly why it's been tagged unreachable!(). IIUC the linked issue, it may have caused races between pushing the message into queue and notifying the receiver.
Jarred Nicholls
@jnicholls
Feb 03 2017 14:20
Roger that, thanks.
Denis Lisov
@tanriol
Feb 03 2017 14:22
Not an expert in this area, however, so may certainly be missing something.