DouKaku?beta

challenge リングノードベンチマーク

N個のノードを作り、1番目のノードに送られたメッセージは2番目のノードに、2番目のノードに送られたメッセージは3番目のノードに、・・・、N番目のノードに送られたメッセージは1番目のノードに送られるようにリングを形成し、そのリング上を一つのメッセージがM回まわるのにかかる時間を計測してください。

post comment

Posted feedbacks - Nested

Flatten Hidden

SQL Server 2008 で確認しました。

へっぽこノートで 20 秒程度かかりました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
DECLARE @start AS datetime = GETDATE();

DECLARE @results AS table(id int, n int, m int, msg varchar(max));

WITH
  Input(n, msg, m) AS (
    SELECT 1000, 'hoge', 10
  )
, Nodes(id, next_id, n) AS (
    SELECT
        0
      , 1 % n
      , n - 1
    FROM
        Input
    UNION ALL
    SELECT
        id + 1
      , (id + 2) % (id + 1 + n)
      , n - 1
    FROM
        Nodes
    WHERE
        n <> 0
  )
, LoopNodes(id, n, m, msg) AS (
    SELECT
        id
      , Input.n
      , m
      , msg
    FROM
        Nodes
      , Input
    WHERE
        id = 0
    UNION ALL
    SELECT
        Node.id
      , Own.n
      , CASE Node.id WHEN 0 THEN Own.m - 1 ELSE Own.m END
      , Own.msg
    FROM
        LoopNodes Own
          INNER JOIN Nodes Node ON ((Own.id + 1) % Own.n) = Node.id
    WHERE
        Own.m <> 0
  )
INSERT INTO @results
  SELECT * FROM LoopNodes
  OPTION (MAXRECURSION 32767);

SELECT CONVERT(varchar, GETDATE() - @start, 114);

ファイバを用いました。

N = 1000, M = 1000: 719 ms
N = 10000, M = 1000: 11521 ms
N = 1000, M = 10000: 11079 ms
N = 10000, M = 10000: 114837 ms

see: core.thread - D Programming Language - Digital Mars 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
module ringnode;
import core.thread, std.range, std.stdio, std.perf;

class Node: Fiber {
    private Message[] _msgs;
    private Node _next;
    
    this() {    
        super(&process);
    }
    
    void nextNode(Node value) {
        _next = value;
    }
    
    void post(Message msg) {
        _msgs ~= msg;
    }
    
    private void process() {
        for(;;) {
            if(!_msgs.empty) {
                auto msg = _msgs.front;
                _msgs.popFront;
                
                debug writefln("Node[%s] received message '%s' (hopLimit: %s)", cast(void*)this, msg.text, msg.hopLimit);
                msg.hopLimit--;
                if(!msg.hopLimit) {
                    yieldAndThrow(new Completed(msg));
                }
                _next.post(msg);
            }
            yield;
        }
    }
}

class Ring {
    Node[] _nodes;
    
    this(uint n) {
        _nodes.length = n;
        foreach(i, ref node; _nodes) node = new Node;
        foreach(i, _; _nodes) _nodes[i].nextNode = _nodes[(i + 1) % $];
    }
    
    auto nodes() {
        return cycle(_nodes);
    }
    
    alias nodes this;
}

class Message {
    uint hopLimit;
    string text;
    
    this(uint hopLimit, string text) {
        this.hopLimit = hopLimit;
        this.text = text;
    }
}

class Completed: Throwable {
    this(Message msg) {
        super("completed: '" ~ msg.text ~ "'");
    }
}


void benchmark(uint N, uint M)() {
    auto ring = new Ring(N);
    
    ring.front.post(new Message(N * M, "hello"));
    
    auto pc = new PerformanceCounter;
    pc.start;
    
    try {
        foreach(node; ring.nodes) {
            node.call;
        }
    } catch(Completed c) {
        debug writeln(c.msg);
    }
    
    pc.stop;
    
    writefln("N = %s, M = %s: %s ms", N, M, pc.milliseconds);
}

void main() {
    benchmark!(1000, 1000);
    benchmark!(10000, 1000);
    benchmark!(1000, 10000);
    benchmark!(10000, 10000);
}

Squeak Smalltalk で。

M = 1000 で固定して N を 100～10000 で振ってみました。2.4GHz Core 2 Duo, Vista です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| elapsedTime |
{1}, (5 to: 50 by: 5), (60 to: 100 by: 10) do: [:nn |
   Smalltalk garbageCollect.
   elapsedTime := [
      | numNodes numMsgs firstMailbox neighborMailbox |
      numNodes := nn * 100.
      numMsgs := 1000.
      firstMailbox := neighborMailbox := OrderedCollection new.

      (1 to: numNodes) do: [:idx |
         | myMailbox semaphore |
         myMailbox := neighborMailbox.
         neighborMailbox := (idx = numNodes) not
            ifTrue: [OrderedCollection new]
            ifFalse: [firstMailbox].
         semaphore := Semaphore new.

         [  | mutex numUnsent |
            mutex := Semaphore forMutualExclusion.
            numUnsent := numMsgs.
            [numUnsent > 0] whileTrue: [
               mutex critical: [
                  myMailbox ifNotEmpty: [
                     "Transcript cr; show: ('Pid = {1}, M = {2}'
                        format: {Processor activeProcess name. numUnsent})."
                     numUnsent := numUnsent - 1.
                     myMailbox removeFirst.
                     neighborMailbox add: #message]].
               Processor yield].
            (idx = numNodes) ifTrue: [semaphore signal]] fixTemps fork].

      firstMailbox add: #message.
      semaphore wait] timeToRun.

   World findATranscript: nil.
   Transcript cr; show: ('N = {1}, M = {2}; elapsed time = {3} milliseconds'
      format:  {numNodes. numMsgs. elapsedTime})]

"=> 
N = 100, M = 1000; elapsed time = 276 milliseconds
N = 500, M = 1000; elapsed time = 1661 milliseconds
N = 1000, M = 1000; elapsed time = 3317 milliseconds
N = 1500, M = 1000; elapsed time = 5495 milliseconds
N = 2000, M = 1000; elapsed time = 7394 milliseconds
N = 2500, M = 1000; elapsed time = 9482 milliseconds
N = 3000, M = 1000; elapsed time = 11590 milliseconds
N = 3500, M = 1000; elapsed time = 13526 milliseconds
N = 4000, M = 1000; elapsed time = 15473 milliseconds
N = 4500, M = 1000; elapsed time = 19731 milliseconds
N = 5000, M = 1000; elapsed time = 19566 milliseconds
N = 6000, M = 1000; elapsed time = 23861 milliseconds
N = 7000, M = 1000; elapsed time = 28079 milliseconds
N = 8000, M = 1000; elapsed time = 31738 milliseconds
N = 9000, M = 1000; elapsed time = 36308 milliseconds
N = 10000, M = 1000; elapsed time = 40090 milliseconds "

BegenInvokeで。
すごく遅いです

WinXP SP3 32bit
C2Q9300
N = 100 M = 100: 306ms
N = 1000 M = 100: 3149ms
N = 100 M = 1000: 3211ms
N = 1000 M = 1000: 32135ms
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;

namespace doukaku271
{
    class Program
    {
        static void Main(string[] args)
        {
            benchmark(100, 100);
            benchmark(1000, 100);
            benchmark(100, 1000);
            benchmark(1000, 1000);
        }
        static void benchmark(int N, int M)
        {
            Node[] n = new Node[N];
            for (int i = 0; i < N; i++) n[i] = new Node();
            for (int i = 1; i < N; i++) n[i - 1].Next = n[i];
            n[N-1].Next = n[0];
            EventWaitHandle ev = new ManualResetEvent(false);
            Message msg = new Message("msg", N * M, ev);
            Stopwatch sw = new Stopwatch();
            sw.Start();
            n[0].Post(msg);
            ev.WaitOne();
            sw.Stop();
            Console.WriteLine("N = {0} M = {1}: {2}ms", N, M, sw.ElapsedMilliseconds);
        }
    }
    class Message
    {
        public static Message EXITMESSAGE = new Message(null, int.MaxValue, null);

        public object msg;
        public int ttl;
        public EventWaitHandle ev;
        public Message(object msg, int ttl, EventWaitHandle ev)
        {
            this.msg = msg;
            this.ttl = ttl;
            this.ev = ev;
            if (ev!=null) ev.Reset();
        }
        public override string ToString()
        {
            return string.Format("[msg:{0} ttl:{1}]", msg, ttl);
        }
    }
    class Node
    {
        static int sid = 0;

        int id = sid++;
        Node next = null;

        public Node()
        {
            messageDelegate = new messageDelegateT(post);
        }
        public Node Next
        {
            get { return next; }
            set { next = value; }
        }

        void post(Message msg)
        {
            //Console.WriteLine("{0}: {1}", id, message);
            if (--msg.ttl == 0)
            {
                if (msg.ev != null) msg.ev.Set();
            }
            else
            {
                if (next != null) next.Post(msg);
            }
        }
        delegate void messageDelegateT(Message msg);
        messageDelegateT messageDelegate;
        public void Post(Message msg)
        {
            messageDelegate.BeginInvoke(msg, null, null);
        }
    }
}

ノードの実現方法に制限はないようなので、ノードをクロージャ、
メッセージの送信を手続き呼び出しとします :-)
ノードの数を決め打ちでなく、実行時に決まるようにするとちょっと
汚くなっちゃいますが、出力さえしなければかなり高速です。

N = 10000, M = 10000 で 6.50s くらいです。
$ time ./doukaku271.scm 10000 10000
./doukaku271.scm 10000 10000  6.42s user 0.05s system 97% cpu 6.619 total
$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env gosh

(use srfi-1)

(define-macro (define-nodes n)
  (let1 p (lambda (x)
            #;`(format #t "~a: ~a~%" ',x msg)
            #f) 
    `(begin
       (define (N0 msg m)
         (unless (= m 0)
           ,(p 'N0)
           (N1 msg (- m 1))))
       ,@(map (lambda (i)
                (let ([self (string->symbol #`"N,|i|")]
                      [next (string->symbol #`"N,(remainder (+ i 1) n)")])
                  `(define (,self msg m)
                     ,(p self)
                     (,next msg m))))
              (iota (- n 1) 1)))))

(eval `(define-nodes ,(string->number (cadr *argv*)))
      (current-module))

(N0 "Hello, world!" (string->number (car *argv*)))
MailboxProcessor を使用して実装しました。
m = 1000 で固定、n = 100, 1000, 10000 の場合のベンチマークをとっています。

環境：Core2Quad 2.5GHz, Windows Vista 32bit

> benchmark 100 1000 |> printfn "%d ms";;
825 ms
val it : unit = ()
> benchmark 1000 1000 |> printfn "%d ms";;
7770 ms
val it : unit = ()
> benchmark 10000 1000 |> printfn "%d ms";;
113861 ms
val it : unit = () 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#light

open System
open System.Diagnostics
open System.Threading

type Node(next, m, eventwait : AutoResetEvent) =
    let mailbox =
        MailboxProcessor.Start(fun inbox ->
            let rec loop l =
                async {
                    let! (nodes : Node[]) = inbox.Receive()
                    nodes.[next].Post(nodes)
                    if l < m then
                        return! loop (l + 1)
                    else
                        eventwait.Set() |> ignore
                        return ()
                }
            loop 0
        )
    member this.Post(msg) = mailbox.Post(msg)

let benchmark n m =
    let eventwait = new AutoResetEvent(false)
    let nodes = [|for i in 1..n -> new Node(i % n, m, eventwait)|]
    let stopwatch = Stopwatch.StartNew()
    nodes.[0].Post(nodes)
    eventwait.WaitOne() |> ignore
    stopwatch.Stop()
    stopwatch.ElapsedMilliseconds

時間計測はお題22で作成したprofileを利用。時間の単位は秒です。
CPU PentiumIII M 532MHzで動作

*Main> benchmark 1000 1000 -- 1000 nodes 1000 loops
0.456028 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import System.IO.Unsafe
import System.CPUTime

type Node = Message -> Message
type Message = ()

node :: Node
node = id

link :: Node -> Node -> Node
link = (.)

message :: Message
message = ()

benchmark :: Int -> Int -> ()
benchmark n m 
  = profile $
            ( foldr1 link . take m  -- m周まわっておわりにする
            $ cycle . (:[])         -- 輪にする
            $ foldr1 link           -- 連結
            $ replicate n node      -- n個のノード
            ) message

-- profile お題22で作成したもの

profile :: a -> a
profile e 
 = unsafePerformIO
 $ do { s <- getCPUTime
      ; r <- return $! e
      ; e <- getCPUTime
      ; putStrLn $ show $ fromInteger (e-s) / fromInteger (10^12)
      ; return r
      }

チャネルを使ってリングを表現しました。
計算時間に含めていないので数値には現れていませんが、
N=10000の場合、計算そのものより
プロセス生成(buildrings)に時間がかかります。

  100 times  1000 nodes    109 msec
 1000 times  1000 nodes    984 msec
 1000 times 10000 nodes  10609 msec
10000 times  1000 nodes   9547 msec
10000 times 10000 nodes 106313 msec
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
implement Bench;

include "sys.m";
    sys: Sys;
include "draw.m";
include "lists.m";
    lists: Lists;

Bench: module
{
    init: fn(ctxt: ref Draw->Context, argv: list of string);
};

Ring: adt
{
    cin, cout: chan of int;
};

N: con 10000;            # >0
M: con 10000;

init(nil: ref Draw->Context, nil: list of string)
{
    sys = load Sys Sys->PATH;
    lists = load Lists "/dis/lib/lists.dis";

    rings := buildrings(N);
    tick0 := sys->millisec();
    for(i := 0; i < M; i++){
        (hd rings).cin <- = i;
        <- (hd rings).cout;
    }
    tick1 := sys->millisec();
    sys->print("%d times %d nodes %d msec\n", M, N, tick1-tick0);
    destroyrings(rings);
}

buildrings(n: int): list of ref Ring
{
    rings: list of ref Ring;
    for(i := 0; i < n; i++)
        rings = lists->append(rings, ref Ring(nil, chan of int));
    last := lists->last(rings);
    for(p := rings; p != nil; p = tl p){
        (hd p).cin = last.cout;
        last = hd p;
    }

    for(p = rings; p != nil; p = tl p)
        spawn relay(hd p);
    return rings;
}

relay(r: ref Ring)
{
    while((n:=<-r.cin) >= 0)
        r.cout <- = n;
}

destroyrings(rings: list of ref Ring)
{
    for(p := rings; p != nil; p = tl p)
        (hd p).cin <- = -1;
}

#9269 は不評だったようなので、継続でコルーチンっぽいものを作って
#9266 を参考にしてやってみました。

継続を生成するのにかなり時間がかかっているようです。
$ time ./doukaku271.scm 10000 1000
./doukaku271.scm 10000 1000  43.23s user 0.36s system 98% cpu 44.303 total
$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#!/usr/bin/env gosh

(use util.queue)
(use gauche.parameter)

(define *nodes* (make-parameter #f))

(define (yield msg hop)
  (let/cc cc
    (enqueue! (*nodes*) cc)
    ((dequeue! (*nodes*)) msg hop)))

(define (make-node name)
  (lambda (msg hop)
    (let loop ([msg msg] [hop hop])
      (cond [(= hop 0) #f]
            [else
             #;(format #t "~a: ~a~%" name msg)
             (receive (msg hop) (yield msg (- hop 1))
               (loop msg hop))]))))

(define (init-nodes n)
  (*nodes* (make-queue))
  (dotimes (i n)
    (enqueue! (*nodes*) (make-node #`"N,|i|"))))

(define (run msg n m)
  (init-nodes n)
  ((dequeue! (*nodes*)) msg (* n m)))

(define (main args)
  (run "Hello, world!"
       (x->integer (car *argv*))
       (x->integer (cadr *argv*)))
  0)

Boost.Asioでやりました。bindとfunctionの多用が速度を落としている原因の1つにあると思います。

M N 時間(秒)
1000 1000 1.698
10000 1000 16.997
1000 10000 16.910
10000 10000 171.371 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <boost/function.hpp>
#include <boost/bind.hpp>
#include <boost/ref.hpp>
#include <boost/optional.hpp>
#include <boost/timer.hpp>
#include <boost/asio.hpp>
#include <iostream>
#include <vector>
#include <functional>

using boost::asio::io_service;

// 1番目のノード: 何周目かのカウント、経過時刻の表示を担当
class first
{
public:
    typedef void result_type;
    first(int m) : count(m) {}
    void operator ()(io_service& ios, boost::function<void (int)> const& next, int id)
    {
        if (id == last_id)
        {
            ++cur;
            if (count == cur)
            {
                std::cout << t.elapsed() << "秒かかりました" << std::endl;
                return;
            }
        }
        else
        {
            last_id = id;
            t.restart();
            cur = 0;
        }
        ios.post(boost::bind(next, id));
    }
private:
    boost::optional<int> last_id;
    boost::timer t;
    int cur;
    const int count;

    first(const first&);
    first& operator =(const first&);
};

// 2からN番目までのノード
void pass_to_next(io_service& ios, boost::function<void (int)> const& next, int id)
{
    ios.post(boost::bind(next, id));
}

int main()
{
    using boost::bind;
    io_service ios;
    int m, n;
    std::cin >> m >> n;
    first f(m);
    std::vector<boost::function<void (int)> > ring(n);
    ring[0] = (bind(boost::ref(f), boost::ref(ios), boost::cref(ring[1]), _1));
    for (int i = 1; i < n - 1; ++i)
    {
        ring[i] = bind(pass_to_next, boost::ref(ios), boost::cref(ring[i + 1]), _1);
    }
    ring[n - 1] = bind(pass_to_next, boost::ref(ios), boost::cref(ring[0]), _1);

    ring[0](42); // メッセージの送信開始
    ios.run();
}

とりあえず、Rubyで書いてみました。

しかし愚直に書いたので、あっと云う間にStack Overflow してしまいます……。むぅ。

$ time ruby1.9 ringnode.rb 100 77

ruby1.9 ringnode.rb 100 77 0.01s user 0.01s system 94% cpu 0.020 total

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Node
  attr_accessor :receiver
  @@insts = []
  
  def self.start(msg, count)
    @@insts[0].recv(msg, count * @@insts.size)
  end
  
  def initialize
    @id = @@insts.size
    @@insts << self
    @@insts[-1].receiver = @@insts[0]
    @@insts[-2].receiver = @@insts[-1] if @@insts.size >= 2
  end

  def recv(msg, count)
    return msg if count.zero?
    @receiver.recv(msg, count-1)
  end
end

m, n ,= ARGV.map(&:to_i)
n.times{Node.new}
Node.start("Hi, ", m)

Pen4 2.53Ghzのにおいて1000ノード1000周をやったとき、Firefox 3.5で1400-1700ms、Operaで600msちょいでした。

蛇足ですが、コメントアウト部はノード網羅の確認用。alertで表示できる文字数には限りがあるし、Firefoxでは最大10000文字で切り捨てるようなので、それにあわせてm,nを減らす必要があります。

see: memo: リングノードベンチマーク 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
var send;
var Node = function () {
    var id = 0;
    var relayDest, relayMsg;
    send = function (msg) {
        relayDest = this;
        relayMsg = msg; 
        while (relayDest.receive(relayMsg));
        return relayMsg;
    }
    return function () {
        this.id = id++;
        this.dest = this;
        this.receive = function (msg) {
            if (typeof this.count == "number") {
                if (this.count == 0) return false;
//                msg += "\n" + this.count + ": ";
                this.count--;
            }
//            msg += this.id + " ";
            relayDest = this.dest;
            relayMsg = msg;
            return true;
        };
    };
}();
Node.prototype.send = send;

var n = 1000, m = 1000;

var ring = [];
ring[0] = new Node();
for (var i = 1; i < n; i++) {
    ring[i] = new Node();
    ring[i - 1].dest = ring[i];
}
ring[n - 1].dest = ring[0];
ring[0].count = m;

var t = new Date();
var lastMsg = ring[0].send("read me in turn.");
t = new Date() - t;

alert("elapsed time:\n" + t + "[ms]\n\nmessage:\n" + lastMsg);

Threadにて実装。

Pentium M 1.30 GHzで、1000ノード1000周を実行したところ、約30,000msかかりました。

Threadで実装したせいか、時間がかかりすぎています。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
import java.util.Date;

public class RingNodeBenchMark {
    
    public static void main( String[] args ) {
        
        int n = 1000;    // ノードの数
        int m = 1000;    // 処理回数

        ///////////////////////////////////////////////////////////////////////
        // 前処理
        ///////////////////////////////////////////////////////////////////////

        // ノードを作成する。
        Node[] nodes = new Node[n];
        for ( int i = 0; i < nodes.length; ++i ) {
            nodes[i] = new Node();
        }

        // ノードをリング上に繋げる。
        nodes[nodes.length-1].nextNode = nodes[0];
        for ( int i = 0; i < nodes.length-1; ++i ) {
            nodes[i].nextNode = nodes[i+1];
        }

        // 各ノードのスレッドを開始する。
        for ( int i = 0; i < nodes.length; ++i ) {
            nodes[i].start();
        }
        
        // 処理回数を先頭のノードに指定する。
        nodes[0].max = 1000;

        ///////////////////////////////////////////////////////////////////////
        // 主処理
        ///////////////////////////////////////////////////////////////////////

        // 開始時刻を取得する。
        Date startTime = new Date();
        
        // 先頭のノードにメッセージを送信する。
        nodes[0].interrupt();
        
        // 先頭ノードが終了するまで待機する。
        // なお、先頭ノードは、一定回数処理を実行した時点で終了する。
        try {
            nodes[0].join();
        } catch ( InterruptedException e ) {}

        // 終了時刻を取得する。
        Date endTime = new Date();

        ///////////////////////////////////////////////////////////////////////
        // 後処理
        ///////////////////////////////////////////////////////////////////////
        
        // 経過時間を計算する。
        long result = endTime.getTime() - startTime.getTime();
        
        // 経過時間を表示する。
        System.out.println( result + " ms" );
    }
    
    // ノード
    // スレッドで実装する。
    private static class Node extends Thread {
        
        Node nextNode;    // 次のノード
        int max = -1;    // 処理回数
        
        public Node() {
            // ノードのスレッドはデーモンスレッドにする。
            // この結果、メインスレッドが終了すると、ノードのスレッドは自動的に終了する。
            setDaemon( true );
        }
        
        public void run() {
            
            int count = 0;    // 処理回数のカウンタ。先頭ノードでのみ使用する。
            
            while ( true ) {
                
                // メッセージを受信するまで待機する。
                try {
                    while ( true ) {
                        Thread.sleep( 1000 );
                    }
                } catch ( InterruptedException e ) {
                }

                // 先頭ノードの場合、処理回数をカウントする。
                if ( max >= 0 ) {
                    if ( count >= max ) {
                        // 処理回数が一定の回数を超えた:
                        
                        // 先頭ノードのスレッドを終了する。
                        return;
                    }
                    count = count + 1;
                }
                
                // 次のノードにメッセージを送信する。
                nextNode.interrupt();
            }
        }
    }
}

出題意図のなかで、ベンチマークというのがあまりピンときてないのですが、他の言語の例を見るに、こういうことなんでしょうか？

メッセージ送信でスタックを掘らないようにディスパッチループをつくり、メッセージを持っているノードを特定するコスト節約のために辞書を持つなどしています。…っていうような最適化やりだすと、何を計測するベンチマークテストなのかよくわからない、う～ん…

結果 terminated msg=1000000 8062ms

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import itertools, datetime

N = 1000
M = 1000

# quit signal in maggage dispatch loop
quit_mesage_posted = False

# nodes only which currently owns some message.
active_nodes = set()

# node
class Node:
    proc = lambda msg: None # set your function to this.
    msgbox = None
    
    def post(self, msg):
        self.msgbox = msg
        active_nodes.add(self)
        
    def consume(self):
        self.proc(self.msgbox)
        self.msgbox = None

# creating N nodes.
nodes = []
for i in range(0, N):
    nodes.append(Node())

# function generator for "proc" of Node object.
# passed message are delegated to the next node with increment.
def gen_send(node, break_at=None):
    if break_at is None:
        return lambda msg: node.post(msg + 1)
    else:
        def send(msg):
            global quit_mesage_posted
            send.c += 1
            if send.c < break_at:
                node.post(msg + 1)
            else:
                print "terminated with msg=%d" % (msg + 1)
                quit_mesage_posted = True
        send.c = 0
        return send

# building node chain for each (0, 1), (1, 2), (2, 3), ..., (N-2, N-1) pairs.
for node_from, node_to in itertools.izip(nodes[:-1], nodes[1:]):
    node_from.proc = gen_send(node_to)
# the last chain from N-1 to 0, (that would be tareminated at M times passed)
nodes[-1].proc = gen_send(nodes[0], break_at=M)

######################## start
time_start = datetime.datetime.now()

# 1st message
nodes[0].post(0)

# message dispatch loop
while (not quit_mesage_posted):
    acn = active_nodes.copy()
    active_nodes.clear()
    for n in acn:
        n.consume()

time_delta = (datetime.datetime.now() - time_start)
print "%dms" % (time_delta.seconds * 1000 + time_delta.microseconds / 1000.0)

このリングノードベンチというのは、Erlang のスレッドの“軽さ”を他の言語処理系と比較して誇示するためのベンチマークとして知られているものです。私は出題者ではありませんが、出題者の意図もそこからは大きく外れていないものと想像しています。

see: Erlang vs. Stackless python: a first benchmark 

Squirrel 3.0で。
末尾再起でぐるぐると。
1行目をconst usethread = 1;にするとスレッドを使うようになります。
所要時間は10倍くらいになります。

結果：（usethread=0）
N:1000 M:1000 time:0.594s
N:1000 M:10000 time:5.859s
N:10000 M:1000 time:5.875s
N:10000 M:10000 time:58.766s
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
const usethread = 0;
class Node
{
    next = null
    function process(msg, ttl)
    {
        if (--ttl)
        {
            if (usethread) suspend(ttl);
            return next.process(msg, ttl);
        }
    }
};

function test(n, m)
{
    local nodes = array(n);
    nodes.apply(@(a) Node());
    nodes.reduce(@(a,b) a.next = b);
    nodes[n-1].next = nodes[0];
    local start = clock();
    if (usethread)
    {
        local t = newthread(@() nodes[0].process("hello", n*m));
        t.call();
        while(t.wakeup()) {}
    }
    else
    {
        nodes[0].process("hello", n*m);
    }
    print(format("N:%d M:%d time:%.3fs\n", n, m, clock()-start));
}

test(1000, 1000);
test(1000, 10000);
test(10000, 1000);
test(10000, 10000);

Groovy用の並行処理記述DSL＆ライブラリであるところのGParallelizerで記述してみます。

GParallelizerは、Java 5のExecutorServiceやjsr166yなどをもとにして４つの並列計算モデル(Asynchronizer、Parallelizer、Actors、Dataflow Concurrency)を選んだり組み合わせたりして利用することができるわけであり、これらのモデルにはActor風な並行処理、データフロー処理などの特色があるわけですが、今回Event-driven actorsというのを用いてみました。

$ groovy ringnode.groovy

node9 received: 0

node8 received: 1

node7 received: 2

node6 received: 3

node5 received: 4

node4 received: 5

:

node0 received: 99

node9 received: 100

661

see: gparallelizer 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import org.gparallelizer.actors.pooledActors.AbstractPooledActor

class Node extends AbstractPooledActor {
  Node next
  def name
  def counter = 0
  def maxcount

  void act()
  {
    loop
    {
      react {
        println "$name received: $it"
        if (++counter > maxcount) {
          stop(); return
        }
        if (next != null) {
          next.send it+1
        }
      }
    }
  }
}


NUMBER_OF_NODE = 10
MAX_CYCLE=10
node0 = node = new Node(name:"node0", next:null, maxcount:MAX_CYCLE).start()
(1..<NUMBER_OF_NODE).each {
  node = new Node(name:"node$it", next:node, maxcount:MAX_CYCLE)
  node.start()
}
node0.next = node

start = System.currentTimeMillis()
node.send 0
node.join()
println (System.currentTimeMillis()-start)

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]