{"action":"created","issue":{"url":"https://api.github.com/repos/softdevteam/lspace/issues/16","labels_url":"https://api.github.com/repos/softdevteam/lspace/issues/16/labels{/name}","comments_url":"https://api.github.com/repos/softdevteam/lspace/issues/16/comments","events_url":"https://api.github.com/repos/softdevteam/lspace/issues/16/events","html_url":"https://github.com/softdevteam/lspace/pull/16","id":110993989,"number":16,"title":"Element reference type benchmark","user":{"login":"Britefury","id":897534,"avatar_url":"https://avatars.githubusercontent.com/u/897534?v=3","gravatar_id":"","url":"https://api.github.com/users/Britefury","html_url":"https://github.com/Britefury","followers_url":"https://api.github.com/users/Britefury/followers","following_url":"https://api.github.com/users/Britefury/following{/other_user}","gists_url":"https://api.github.com/users/Britefury/gists{/gist_id}","starred_url":"https://api.github.com/users/Britefury/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Britefury/subscriptions","organizations_url":"https://api.github.com/users/Britefury/orgs","repos_url":"https://api.github.com/users/Britefury/repos","events_url":"https://api.github.com/users/Britefury/events{/privacy}","received_events_url":"https://api.github.com/users/Britefury/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":14,"created_at":"2015-10-12T15:08:28Z","updated_at":"2015-10-13T13:42:26Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/softdevteam/lspace/pulls/16","html_url":"https://github.com/softdevteam/lspace/pull/16","diff_url":"https://github.com/softdevteam/lspace/pull/16.diff","patch_url":"https://github.com/softdevteam/lspace/pull/16.patch"},"body":"Implemented a benchmark for measuring the performance of various types of element reference. The benchmark can be run with `cargo bench`, although you need to comment and uncomment various blocks of code to try the different reference types. A generics based approach was attempted, but a variety of implementations of it were all failed by the borrow/lifetime checker.\r\n\r\nTo save time, here are the results:\r\n\r\n`Box<TElement>`: ~49,940,000 ns                *(Base case; boxed trait)*\r\n`Box<Box<TElement>>`: ~53,300,000 ns           *(1 additional pointer indirection)*\r\n`RefCell<Box<TElement>>`: ~62,260,000 ns       *(interior mutability)*\r\n`Rc<Box<TElement>>`: ~62,100,000 ns            *(multiple ownership, mutate via `Rc::get_mut`)*\r\n`Rc<RefCell<Box<TElement>>>`: ~76,880,000 ns   *(everything)*\r\n\r\nThese results are approximately reflected in the War and Peace demo, where layout with the `Box<TElement>` reference type takes ~133ms, and ~200ms with the `Rc<RefCell<Box<TElement>>>` reference type; approximately an increase of 50%."},"comment":{"url":"https://api.github.com/repos/softdevteam/lspace/issues/comments/147717482","html_url":"https://github.com/softdevteam/lspace/pull/16#issuecomment-147717482","issue_url":"https://api.github.com/repos/softdevteam/lspace/issues/16","id":147717482,"user":{"login":"Britefury","id":897534,"avatar_url":"https://avatars.githubusercontent.com/u/897534?v=3","gravatar_id":"","url":"https://api.github.com/users/Britefury","html_url":"https://github.com/Britefury","followers_url":"https://api.github.com/users/Britefury/followers","following_url":"https://api.github.com/users/Britefury/following{/other_user}","gists_url":"https://api.github.com/users/Britefury/gists{/gist_id}","starred_url":"https://api.github.com/users/Britefury/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Britefury/subscriptions","organizations_url":"https://api.github.com/users/Britefury/orgs","repos_url":"https://api.github.com/users/Britefury/repos","events_url":"https://api.github.com/users/Britefury/events{/privacy}","received_events_url":"https://api.github.com/users/Britefury/received_events","type":"User","site_admin":false},"created_at":"2015-10-13T13:42:26Z","updated_at":"2015-10-13T13:42:26Z","body":"Sadly, this is turning out to be trickier than first expected.\r\nThe current (sort of) plan is to have an abstract `NodeTrait` that is the base type for all nodes. This requires a `Box` for ownership since its a trait not a struct, a `RefCell` for interior mutability and `Rc` for multiple ownership. This therefore leads us to create `NodeRef` that wraps all that so that we have a node reference type.\r\n\r\nSince mutating tree structure requires that we refer to nodes via wrapped references, e.g. `NodeRef`, we put methods that don't deal with tree structure in the node type (e.g. `NodeTrait` or some such) and methods that do in `NodeRef`. This leads us to the conclusion that given there are some node types that are leaf nodes (e.g. a text node for displaying a token) and some that have children in a list (e.g. a paragraph or a column) or others have only once child or children in specific slots, (e.g. a fraction node might have a numerator and a denominator) etc, the methods available for mutating a node's children would vary depending on its type. Since these methods are implemented on the node reference type rather than the node type, this suggests that we need to define an abstract trait type for node references too, e.g. `NodeRefTrait`. This leaves the node reference types that correspond to various node types, e.g. `TextNodeRef` and `ColumnNodeRef`, etc., to implement whichever tree mutation methods are needed. This of course means, that the type used by a node to refer to other nodes in the tree (e.g. child nodes) - which was `NodeRef` - must now be `Box<NodeRefTrait>`.\r\n\r\nSo:\r\n\r\n```\r\ntrait NodeTrait {\r\n    // various functions common to all elements...\r\n}\r\n\r\nstruct ColumnNode {\r\n    children: Vec<Box<TNodeRef>>,\r\n    // other fields...\r\n}\r\n\r\nimpl NodeTrait for ColumnNode {\r\n    // implementation...\r\n}\r\n\r\ntrait NodeRefTrait {\r\n   fn get(&self) -> Ref<Box<NodeTrait>>;   // borrow ref to the node\r\n   fn get_mut(&mut self) -> RefMut<Box<NodeTrait>>;   /// borrow mut ref to node\r\n}\r\n\r\nstruct ColumnNodeRef {\r\n    n: Rc<RefCell<Box<NodeTrait>>>\r\n}\r\n\r\nimpl ColumnNodeRef {\r\n    fn new(node: ColumnNode) -> Box<NodeRefTrait> {\r\n        return Box::new(ColumnNodeRef{n: node});\r\n    }\r\n\r\n    fn set_children(&self, children: Vec<Box<NodeRefTrait>>) {\r\n        let node = self.get_mut();\r\n        // clear parents of existing children\r\n        for child in node.children {\r\n            child.set_parent(None);\r\n        }\r\n        node.children = children;\r\n        // set parents of new children\r\n        for child in node.children {\r\n            child.set_parent(Some(self));   // assume set_parent takes an Option<&NodeRefTrait> parameter\r\n        }\r\n    }\r\n}\r\n\r\nimpl NodeRefTrait for ColumnNodeRef {\r\n    fn get(&self) ->  Ref<Box<NodeTrait>> {\r\n        return self.n.borrow();\r\n    }\r\n\r\n    fn get_mut(&self) ->  RefMut<Box<NodeTrait>> {\r\n        return self.n.borrow_mut();\r\n    }\r\n}\r\n```\r\n\r\nNow this is all fine and good. The extra `Box` around the `NodeRefTrait` adds another pointer indirection and probably another allocation (one alloc for the node itself, one for the `Rc` shared box and another for the reference box), but the overhead is probably manageable. Things look a little worse however when we consider that the borrow methods defined by the `NodeRefTrait` now involve a virtual call (AFAICT; the drop in performance in the benchmark certainly suggests this). This virtual call each time we ask a node reference for a reference to its contained node seems to add quite a bit of overhead. It would seem that in terms of layout, all these extra indirections add an overhead of almost 100%."}}