ツリーの構造にBoxを使ったほうがいいのかどうか

[o-jill]

今はVecでやっているんだけど、Vec<Box>のほうがいい説がある。 何がどこまでどう違うのかはよくわからない。 変えたほうがいいかどうかもよくわからない。

[o-jill]

推測としては、BoxならVecに入れるものがポインタになるのでアクセスが簡単になる(サイズが小さくなるので追加削除がしやすい)と思われる。 今はこれごとpushしている。vecの拡張が起きやすい？

pub struct Node {
    child : Vec<Node>,
    hyoka : Option<f32>,
    pub kyokumen : usize,
    pub best : Option<Best>,
    pub x : usize,
    pub y : usize,
    depth : usize,
}

Boxの変数の解放のタイミングを全く理解していない。Rcとか使わないとだめな気がしている。

[o-jill]

boxを使わないほうが速いのか？

node: (ry
Time elapsed in expensive_function() is: 25.591µs
nodeb: (ry
Time elapsed in expensive_function() is: 29.441µs

use std::time::{Duration, Instant};

#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : i32,
    o : i32,
    p : f32,
    q : i8,
    r : i8,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : n,
            o : 0,
            p : 0.0,
            q : 0,
            r : 0,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : i32,
    o : i32,
    p : f32,
    q : i8,
    r : i8,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : n,
            o : 0,
            p : 0.0,
            q : 0,
            r : 0,
        }
    }
    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 200;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }

    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed in expensive_function() is: {:?}", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }

    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed in expensive_function() is: {:?}", duration);
}

[o-jill]

もうちょっと現実に近くしてみた。 ここまで来ると大差ない感じ。 現実はもっとchildが少なくて深い(今はdepth:3)のでそのパターンの計測をしたい。

node:
Time elapsed in expensive_function() is: 43.661µs
nodeb:
Time elapsed in expensive_function() is: 42.481µs

use std::time::Instant;

// pub struct Node {
//     child : Vec<Node>,
//     hyoka : Option<f32>,
//     pub kyokumen : usize,
//     pub best : Option<Best>,
//     pub x : usize,
//     pub y : usize,
//     depth : usize,
// }

#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }
    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 200;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }

    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed in expensive_function() is: {:?}", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }

    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed in expensive_function() is: {:?}", duration);
}

[o-jill]

clearもしてみた。 clearはBoxのほうが明らかに速いっぽい。 Heapに確保された実態が破棄されるのはいつなのかは不明。Vec::clear()で参照がなくなるからその時に破棄してくれると嬉しい。

node: Node { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None }
Time elapsed in expensive_function() is: 46.811µs
nodeb: NodeB { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None }
Time elapsed in expensive_function() is: 25.58µs

use std::time::Instant;

// pub struct Node {
//     child : Vec<Node>,
//     hyoka : Option<f32>,
//     pub kyokumen : usize,
//     pub best : Option<Best>,
//     pub x : usize,
//     pub y : usize,
//     depth : usize,
// }

#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }

    fn clear(self : &mut Node) {
        self.child.clear();
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }

    fn clear(self : &mut NodeB) {
        self.child.clear();
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 200;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }
    n.clear();
    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed in expensive_function() is: {:?}", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }
    nb.clear();
    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed in expensive_function() is: {:?}", duration);
}

[o-jill]

もうちょい深くしてみた。 一応boxのほうが速そう。

node:
Time elapsed in expensive_function() is: 59.731µs
nodeb:
Time elapsed in expensive_function() is: 46.452µs

use std::time::Instant;

// pub struct Node {
//     child : Vec<Node>,
//     hyoka : Option<f32>,
//     pub kyokumen : usize,
//     pub best : Option<Best>,
//     pub x : usize,
//     pub y : usize,
//     depth : usize,
// }

#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }

    fn clear(self : &mut Node) {
        self.child.clear();
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }

    fn clear(self : &mut NodeB) {
        self.child.clear();
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 100;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }
    for i in n.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Node::new(idx as i32));
        }
    }
    for i in n.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Node::new(idx as i32));
            }
        }
    }
    // n.clear();
    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed in expensive_function() is: {:?}", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }
    for i in nb.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Box::new(NodeB::new(idx as i32)));
        }
    }
    for i in nb.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Box::new(NodeB::new(idx as i32)));
            }
        }
    }
    // nb.clear();
    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed in expensive_function() is: {:?}", duration);
}

[o-jill]

clearもしてみた。 やっぱりclearはBoxのほうが明らかに速いっぽい。 Heapに確保された実態が破棄されるのはいつなのかは不明。Vec::clear()で参照がなくなるからその時に破棄してくれると嬉しい。

node: Node { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None }
Time elapsed in expensive_function() is: 76.712µs
nodeb: NodeB { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None }
Time elapsed in expensive_function() is: 40.221µs

use std::time::Instant;

// pub struct Node {
//     child : Vec<Node>,
//     hyoka : Option<f32>,
//     pub kyokumen : usize,
//     pub best : Option<Best>,
//     pub x : usize,
//     pub y : usize,
//     depth : usize,
// }

#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }

    fn clear(self : &mut Node) {
        self.child.clear();
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<String>,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }

    fn clear(self : &mut NodeB) {
        self.child.clear();
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 100;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }
    for i in n.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Node::new(idx as i32));
        }
    }
    for i in n.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Node::new(idx as i32));
            }
        }
    }
    n.clear();
    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed in expensive_function() is: {:?}", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }
    for i in nb.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Box::new(NodeB::new(idx as i32)));
        }
    }
    for i in nb.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Box::new(NodeB::new(idx as i32)));
            }
        }
    }
    nb.clear();
    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed in expensive_function() is: {:?}", duration);
}

[o-jill]

Heapに確保された実態が破棄されるのはいつなのかは不明。Vec::clear()で参照がなくなるからその時に破棄してくれると嬉しい。

Box\は所有権がなくなったら(所有者が居なくなったら)破棄される。 らしいので、Vec::clear()で消えるはず。

[o-jill]

struct Bestを入れて再測定。 Boxのほうが速い。

node: Time elapsed is: 56.811µs nodeb: Time elapsed is: 48.221µs

use std::time::Instant;

// pub struct Node {
//     child : Vec<Node>,
//     hyoka : Option<f32>,
//     pub kyokumen : usize,
//     pub best : Option<Best>,
//     pub x : usize,
//     pub y : usize,
//     depth : usize,
// }

#[derive(Debug)]
struct Best {
    val : f32,
    x : usize,
    y : usize,
    teban : i8,
}

impl Best {
    fn new() -> Best {
        Best {
            val : 0.0,
            x : 0,
            y : 0,
            teban : 0,
        }
    }
}
#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<Best>,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }

    fn clear(self : &mut Node) {
        self.child.clear();
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<Best>,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }

    fn clear(self : &mut NodeB) {
        self.child.clear();
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 100;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }
    for i in n.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Node::new(idx as i32));
        }
    }
    for i in n.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Node::new(idx as i32));
            }
        }
    }
    // n.clear();
    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed  is: **{:?}**", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }
    for i in nb.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Box::new(NodeB::new(idx as i32)));
        }
    }
    for i in nb.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Box::new(NodeB::new(idx as i32)));
            }
        }
    }
    // nb.clear();
    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed  is: **{:?}**", duration);
}

[o-jill]

↑のclear()有りだとこんな感じ、そんな(Box有利は)変わらん。

node: Node { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None } Time elapsed is: 82.702µs nodeb: NodeB { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None } Time elapsed is: 77.032µs

[o-jill]

もう一階層追加。 平均的にBoxのほうが速い。

node: Time elapsed is: 79.063µs nodeb: Time elapsed is: 60.742µs

use std::time::Instant;

// pub struct Node {
//     child : Vec<Node>,
//     hyoka : Option<f32>,
//     pub kyokumen : usize,
//     pub best : Option<Best>,
//     pub x : usize,
//     pub y : usize,
//     depth : usize,
// }

#[derive(Debug)]
struct Best {
    val : f32,
    x : usize,
    y : usize,
    teban : i8,
}

impl Best {
    fn new() -> Best {
        Best {
            val : 0.0,
            x : 0,
            y : 0,
            teban : 0,
        }
    }
}
#[derive(Debug)]
struct Node {
    child : Vec<Node>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<Best>,
}

impl Node {
    fn new(n : i32) -> Node {
        Node {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut Node, nd : Node) {
        self.child.push(nd);
    }

    fn clear(self : &mut Node) {
        self.child.clear();
    }
}

#[derive(Debug)]
struct NodeB {
    child : Vec<Box<NodeB>>,
    n : Option<i32>,
    o : usize,
    p : usize,
    q : usize,
    r : usize,
    s : Option<Best>,
}

impl NodeB {
    fn new(n : i32) -> NodeB {
        NodeB {
            child : Vec::new(),
            n : Some(n),
            o : 0,
            p : 0,
            q : 0,
            r : 0,
            s : None,
        }
    }

    fn add(self : &mut NodeB, nd : Box<NodeB>) {
        self.child.push(nd);
    }

    fn clear(self : &mut NodeB) {
        self.child.clear();
    }
}

fn main() {
    let 日本語 = "japanese";
    let bt : Box<i32> = Box::new(8);
    println!("Hello, world! {}, {bt}", 日本語);

    let start = Instant::now();
    const N : i32 = 100;

    let mut n = Node::new(0);
    // println!("node: {:?}", n);
    for i in 0..N {
        n.add(Node::new(i));
    }
    // println!("node: {:?}", n);
    for (idx, i) in n.child.iter_mut().enumerate() {
        i.add(Node::new(idx as i32));
    }
    for i in n.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Node::new(idx as i32));
        }
    }
    for i in n.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Node::new(idx as i32));
            }
        }
    }
    for h in n.child.iter_mut() {
        for i in h.child.iter_mut() {
            for j in i.child.iter_mut() {
                for (idx, k) in j.child.iter_mut().enumerate() {
                    k.add(Node::new(idx as i32));
                }
            }
        }
    }
    // n.clear();
    let duration = start.elapsed();

    println!("node: {:?}", n);
    println!("Time elapsed  is: **{:?}**", duration);

    let start = Instant::now();

    let mut nb = NodeB::new(0);
    // println!("nodeb: {:?}", nb);
    for i in 0..N {
        nb.add(Box::new(NodeB::new(i)));
    }
    // println!("nodeb: {:?}", nb);
    for (idx, i) in nb.child.iter_mut().enumerate() {
        i.add(Box::new(NodeB::new(idx as i32)));
    }
    for i in nb.child.iter_mut() {
        for (idx, j) in i.child.iter_mut().enumerate() {
            j.add(Box::new(NodeB::new(idx as i32)));
        }
    }
    for i in nb.child.iter_mut() {
        for j in i.child.iter_mut() {
            for (idx, k) in j.child.iter_mut().enumerate() {
                k.add(Box::new(NodeB::new(idx as i32)));
            }
        }
    }
    for h in nb.child.iter_mut() {
        for i in h.child.iter_mut() {
            for j in i.child.iter_mut() {
                for (idx, k) in j.child.iter_mut().enumerate() {
                    k.add(Box::new(NodeB::new(idx as i32)));
                }
            }
        }
    }
    // nb.clear();
    let duration = start.elapsed();
    println!("nodeb: {:?}", nb);
    println!("Time elapsed  is: **{:?}**", duration);
}

[o-jill]

clear()有りでもそんな変わらん。

node: Node { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None } Time elapsed is: 93.822µs nodeb: NodeB { child: [], n: Some(0), o: 0, p: 0, q: 0, r: 0, s: None } Time elapsed is: 58.621µs

[o-jill]

Nodeの初期値のbestをNone->Some()にしてもあんまり変わんなかった。

[o-jill]

簡単な確認では10~20%ぐらい速くなるといいなぁ、といった結果でした。

[o-jill]

usizeをu8に出来そうなところをu8に変えて測定。 Boxを使わないほうが良さそう。structのサイズにしきい値がありそう。 node: Time elapsed is: 53.051µs nodeb: Time elapsed is: 60.542µs

[o-jill]

頑張って実装中。 Arcはimmutableなので、Vec<Arc<RefCell\>>に落ち着きそうです。 RefCellはシングルスレッド用だって。 Arcはimmutableなので、Vec<Arc<Mutex\>>に落ち着きそうです。 コードが行数的にシンプルになりそうです。 RefCellのせいでBorrowとか増えてめんどくさくなりました。

[o-jill]

デッドロック?している所まで来たｗ

[o-jill]

とりあえず動いているっぽい所まで来た。 ShNode::dump()がちゃんと出来てない(読み筋が出力できていない、Lockと子を辿るタイミング？)。 RwLockのほうがdump()には楽なのかなぁ？

dump()が出来たら、

• ab探索とか、
• eval()がちゃんと動いていないやつとか
• (置換表とか)

[o-jill]

shnode thinkall: val:-3.506 val:None, 4486313 nodes. @@d1@@d1 1208msec

nodebb thinkall: val:-3.506 val:Some(-3.5055861), 4486313 nodes. @@d1[]c6@@d2[]f5@@f4[]f3@@g4 535msec

遅いけどvalがNoneなのは何？dump()と関係がある？ →値を入れてなかった。 よくわからんけど1208msが800msぐらいにはなった。 bb51f08

[o-jill]

ShNode::dump()のテストを作ったけど通ってしまったのに、実際に使うとダメなのはツリーの生成にミスっている？

[o-jill]

一旦シングルスレッドで作ってみてはいかが？

[o-jill]

これおかしくないか？

        let sub =
                thread::spawn(move || {
            for leaf in leaves1.iter_mut() {
                let x;
                let y;
                {
                    let lf = leaf.lock().unwrap();
                    x = lf.x;
                    y = lf.y;
                }
                let newban = ban2.r#move(x, y).unwrap();
                let val = ShNode::think_internal(leaf, &newban);
                leaf.lock().unwrap().hyoka = val;
                leaf.lock().unwrap().best = Some(Best::new(val.unwrap(), x, y, teban));  // <-------
            }
        });

Bestは入っているはず?で、ここで代入する必要なし。 評価は入れてないので今のまま入れれば良い。 →やってみた。1手だけ出力されるようになった。たまにバグって?長めに読み筋が表示されることがあるが同じ手番が2連続して出力されるのでなにかおかしい。

[o-jill]

ここもおかしい。 Bestのxyはleafのxyを入れないといけない。

                let lb = lf.best.as_ref();
                if be.is_none() {
                    be = Some(lb.unwrap().clone());  // <----- 誤
                    be = Some(Best::new(lf.hyoka.unwrap(), lf.x, lf.y, teban));  // 正
                } else if lb.is_none() {
                    // nothing to do.
                } else if be.as_ref().unwrap().hyoka * fteban < lb.as_ref().unwrap().hyoka * fteban {
                    be = Some(lb.unwrap().clone());  // <----- 誤
                    be = Some(Best::new(lf.hyoka.unwrap(), lf.x, lf.y, teban));  // 正
                }

これを直したらそれっぽい読み筋が出るようになった。 終盤で何か落ちるのでまだどっかおかしい。 →良くない読み筋を解放するようにしたら落ちなくなった。メモリ容量のせいっぽい。

[o-jill]

• dump()を正しく出すために
  • bestに不要な代入をしない。
    各スレッドの末尾。
  • bestに子のxyを入れる。
    探索結果の統合時。
  • 良くない読み筋を解放する 反復深化の末尾。
• ab探索とか
• eval()がちゃんと動いていないやつとか デバッグコンパイルだとうまくsimd版が動かない。メモリーのアライメントのせい？
• 置換表とか

[o-jill]

ShNode::dump()は直った。 04d7ee6f8 max 8Mnpsぐらいは出てるっぽい。平均6Mnpsぐらいかな？ もう1手展開したら分担がより半分に近くなりそう。

[o-jill]

ab探索を実装してみた。 shnode:15min/duel nodebb:9min/duel duelの結果がちょっと違うので何か問題があるかもしれない。

[o-jill]

2手展開をしてみた。 あと1手のときにバグるので何とかしたい。

[o-jill]

バグるのは直った。 22min/duelになった。分担ができてない？

[o-jill]

分担を変えてみた。 15min/duelになった。 27min / 15min / 2 = 0.9 CPUの使用効率は良いけど結局あんま変わらん。

c.f. 1手展開 24min / 15min / 2 = 0.8

[o-jill]

RwLockにしてみた。 14min/duelになった。26min / 14min / 2 = 0.92

[o-jill]

Boxでなんとか出来ないかとやってみたけど RefCellだとスレッドを跨がせてもらえないようだ。 Box<Mutex>なら行けたりする？

[o-jill]

Boxが無理でした。

ポインタに手を出しますか？ その場合、Boxでいいんでしょうか？

[o-jill]

このやり方ならスレッド境界を超えられる？？？

fn main() {
    println!("Hello, world!");

    let mut a = Box::new(19);
    println!("a:{}", a);

    let p = Box::into_raw(a);
    let pp = unsafe{p.as_mut().unwrap()};
    let sub = std::thread::spawn(move || {
        let mut q = pp;  // unsafe {Box::from_raw(pp)};
        *q = 1;
    });
    sub.join().unwrap();

    println!("a:{}", unsafe{Box::from_raw(p)});
}

[o-jill]

グローバル変数＋１つのツリー作戦でやってみた。 よくわかんないけど初手の生成に失敗している模様。 → 無駄に初期化してた。

static mut ND_ROOT : Option<NodeBB> = None;

impl NodeBB {
    pub fn thinko(ban : &bitboard::BitBoard, mut depth : u8)
            -> Option<(f32, &NodeBB)> {
        if depth == 0 {
            return None;
        }
        if ban.is_passpass() {
            return None;
        }

        // let sum = 0;
        let moves = ban.genmove();

        // no more empty cells
        if moves.is_none() {
            return None;
        }

        let node;
        unsafe {
            ND_ROOT = Some(NodeBB::new(0, 0, depth));
            node = ND_ROOT.as_mut().unwrap();
        }
        let mut moves = moves.unwrap();
        if moves.len() == 0 {  // pass
            moves.push((0, 0));
            node.depth += 1;
            depth += 1;
        }
        let n = moves.len();
        for (mvx, mvy) in moves.iter() {
            node.child.push(NodeBB::new(*mvx, *mvy, depth - 1));
        }
        // let moves1 = &moves[0..n/2];
        let moves1 = Vec::from_iter(moves[0..n/2].iter().cloned());
        let moves2 = Vec::from_iter(moves[n/2..].iter().cloned());
        let ban2 = ban.clone();

        let sub = thread::spawn(move || {
            let node2;
            unsafe {
                node2 = ND_ROOT.as_mut().unwrap();
            }
            for (mvx, mvy) in moves1 {
                let nd = node2.child.iter_mut().find(|a| {
                        a.x == mvx && a.y == mvy
                    });
                if nd.is_none() {
                    panic!("node2.child.iter_mut().find(|a|");
                }
                let mut nd = nd.unwrap();
                let newban = ban2.r#move(mvx, mvy).unwrap();
                let val = NodeBB::think_internal(nd, &newban);
                nd.hyoka = val;
            }
            });

        for (mvx, mvy) in moves2 {
            let nd = node.child.iter_mut().find(|a|
                    a.x == mvx && a.y == mvy
                ).unwrap();
            let newban = ban.r#move(mvx, mvy).unwrap();
            let val = NodeBB::think_internal(nd, &newban);

            nd.hyoka = val;
        }
        sub.join().unwrap();
        // tt.dumpsz();
        let mut hyoka = None;
        let mut be = None;
        let mut km = 0;
        let teban = ban.teban;
        let fteban = teban as f32;
        for c in node.child.iter() {
            km += c.kyokumen;
            if c.hyoka.is_none() {
                continue;
            }
            if hyoka.is_none() || hyoka.unwrap() * fteban < c.hyoka.unwrap() * fteban {
                hyoka = c.hyoka;
                be = Some(Best::new(hyoka.unwrap(), c.x, c.y, teban));
            }
        }
        node.hyoka = hyoka;
        node.best = be;
        node.kyokumen = km;
        Some((hyoka.unwrap(), node))
    }
}

[o-jill]

最高速度的には今までのNodeBB::think()とNodeBB::thinko()は大差なさそう。 NodeBB::thinko()のほうがコードとかはシンプル。2手展開もやりやすそう。

[o-jill]

あんま変わらん、むしろちょい遅？0.8 sec/game(=13 msec/move)ぐらい遅い。

NodeBB::think() real 48m9.902s user 82m22.103s sys 0m15.970s 82:22 / 48:10 / 2 = 0.855

NodeBB::thinko() real 49m44.773s user 84m57.579s sys 0m23.443s 84:58 / 49:45 / 2 = 0.854

[o-jill]

トップのところでalpha, betaをスレッド間で共有したらええんちゃうん？

[o-jill]

スレッド間共有はあんまり効果はない？ one treeは良さげ？

shared + ext2ab + interleave + shared-ab:
real    21m2.122s
user    39m24.289s
sys     0m23.157s

shared + ext2ab + shared-ab:
real    39m1.482s
user    41m10.117s
sys     0m23.400s

shared
real    12m26.898s
user    19m50.518s
sys     0m13.230s

shared + shared-ab:
real    13m44.010s
user    22m23.915s
sys     0m16.378s

mpsc-ab + shared-ab:
real    9m53.304s
user    15m50.810s
sys     0m17.021s
0.802
mpsc-ab + individual-ab:
real    9m46.342s
user    13m22.011s
sys     0m33.670s
0.684
one tree + shared-ab:
real    9m42.401s
user    15m33.454s
sys     0m15.063s
0.811
one tree + individual-ab:
real    8m57.910s
user    14m11.714s
sys     0m14.758s
0.792

[o-jill]

爆速になったんだがどうした？！ 裏で重い処理をしていたのが悪さしてたか？ ghaでも動かすようにしたので様子見。 98a872d

one tree + ext2ab + interleave + individual-ab:
real   less than 3min
user   less than 5min
sys     --

• duel
  • before with Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz: 23m 17s
  • after with Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz: 8m 23s (x2.78 faster)
• rust
  • before 1h 36m 59s (= 96m 59s)
  • after 34m 37s (x2.80 faster)

[o-jill]

Boxは使わなくて良いということでclose?