Re: Vs. Alioth binary-trees

[The Anh Tran]

dsimcha wrote:
== Quote from The Anh Tran ([EMAIL PROTECTED])'s article
Hi,
Could you measure spinlock with this bench?
http://shootout.alioth.debian.org/u32q/benchmark.php?test=binarytrees&lang=all
Thanks.

I tried to reply to your post last night with my modified gcx.d, but apparently
posting attachments of that size (~80kb) silently fails.

There is no multithreaded implementation of the binary trees benchmark for D 
that
I was able to find.  As far as the single-threaded version, spinlocks would make
absolutely no difference because the druntime GC uses thread_needLock() to avoid
any kind of lock on single-threaded code.

If you or anyone else wants to play around w/ my modified gcx.d code and try it
under different use cases, I've posted it to http://cis.jhu.edu/~dsimcha/gcx.d.

I've failed to recompile druntime with your gcx.d. I'm still a D newbie 
:|. Ie: need someone to hold my hand and guide steps by steps ;)

This is my multithread alloc implementation.
If it uses std.gc, and runs with 2 threads; it is 5 times slower than 1 
thread !???
// The Computer Language Benchmarks Game
// http://shootout.alioth.debian.org/
// By bearophile, optimized for simplicity, quite slow

// Run: testgc.exe xx yy
// xx: alloc depth, default is 14
// yy: how many threads, default is 1
// Ex: testgc.exe 18 4

import core.thread;
import core.memory;

import std.perf;
import std.stdio;
import std.conv;
import std.string;

import std.c.time;
import std.c.stdio;

class TreeNode 
{
    int item;
    TreeNode left, right;

    this(int item, TreeNode left =null, TreeNode right =null) 
        {
        this.item = item;
        this.left = left;
        this.right = right;
    }
        ~this()
        {
                if (left !is null)
                {
                        delete left;
                        delete right;
                }
        }

    int check() const
        {
        if (left !is null)
                        return (item + left.check - right.check);
                else
                        return item;
    }

        static TreeNode makeTree(int item, int depth)
        {
            if (depth > 0)
                return new TreeNode(    item, 
                                                                        
makeTree(2*item-1, depth-1), 
                                                                        
makeTree(2*item, depth-1)       );
            else
                return new TreeNode(item);
        }
}

int fetch_job(int step)(int*)
{
        asm
        {
                naked;
                mov             ECX,    EAX;    // last var pass on EAX
                mov             EAX,    step;
                lock;
                xadd    [ECX],  EAX;    // EAX = old value
                ret;
        }
}

void main(string[] args) 
{
    int n = (args.length >= 2) ? toInt(args[1]) : 14;
        int nthreads = (args.length >= 3) ? toInt(args[2]) : 1;

    const minDepth = 4;
    int maxDepth = (minDepth + 2) > n ? minDepth + 2 : n;

    GC.disable;

    scope pc = new PerformanceCounter;
    pc.start;

        {
                scope stretchTree = TreeNode.makeTree(0, maxDepth + 1);
                writefln("stretch tree of depth ", maxDepth + 1, "\t check: ", 
stretchTree.check);
        }

        {
            scope longLivedTree = TreeNode.makeTree(0, maxDepth);

                {
                        scope string[] result = new string[maxDepth +1];
                        scope Thread[] threads = new Thread[nthreads];
                        int current_depth = minDepth;
                        
                        foreach (ref t; threads)
                        {
                                t = new Thread(
                                {
                                        int depth;
                                        while ((depth = 
fetch_job!(2)(&current_depth)) <= maxDepth)
                                    //for (int depth = minDepth; depth <= 
maxDepth; depth += 2) 
                                        {
                                        int iterations = 1 << (maxDepth - depth 
+ minDepth);
                                        int check = 0;

                                        for (int i = 1; i <= iterations; i++)
                                                {
                                                        scope lt = 
TreeNode.makeTree(i, depth);
                                                        scope rt = 
TreeNode.makeTree(-i, depth);
                                            check += lt.check + rt.check;
                                                }

                                                result[depth] = format("%d\t 
trees of depth %d\t check: %d\n", iterations * 2, depth, check);
                                    }
                                });
                                
                                t.start;
                        }

                        foreach (t; threads)
                                t.join();
                        
                        foreach (str; result)
                                writef(str);
                }
                
            writefln("long lived tree of depth ", maxDepth, "\t check: ", 
longLivedTree.check);
        }

    pc.stop;
    writefln("\nTiming: ", pc.milliseconds, " ms with ", nthreads, " threads");
}