Top 5

[Sergey Gromov]

Sat, 11 Oct 2008 15:00:20 -0400,
Benji Smith wrote:
> Sergey Gromov wrote:
> > I took the trouble to port your Appender to DMD 1.033 and fixed Benji's 
> > benchmark to use it.  Here's my timings, best of 5 runs each:
> 
> Hey, would you mind sending me a copy of that Appender? I was about to 
> start backporting it myself, but then I figured it'd be a better 
> apples-to-apples comparison if I use the version you've already written.

Here's everything.  Sorry for a long post!  :D

module d1;

template Const(T) {
    version (D_Version2)
        mixin("alias const(T) Const;");
    else
        alias T Const;
}

template Invariant(T) {
    version (D_Version2)
        mixin("alias invariant(T) Invariant;");
    else
        alias T Invariant;
}

module appender;

import std.gc: capacity;
import d1;

struct Appender(A : T[], T)
{
    private T[] * pArray;
    private size_t _capacity;

    version (D_Version2)
    {
        this(T[] * p)
        {
            pArray = p;
            if (!pArray) pArray = (new typeof(*pArray)[1]).ptr;
            _capacity = .capacity(pArray.ptr) / T.sizeof;
        }
    }
    else
    {
        static Appender opCall(T[] * p)
        {
            Appender r;
            r.pArray = p;
            if (!r.pArray) r.pArray = (new typeof(*r.pArray)[1]).ptr;
            r._capacity = .capacity(r.pArray.ptr) / T.sizeof;
            return r;
        }
    }

    T[] data()
    {
        return pArray ? *pArray : null;
    }

    size_t capacity() /+ const +/ { return _capacity; }

    void write(T item)
    {
        if (!pArray) pArray = (new typeof(*pArray)[1]).ptr;
        if (pArray.length < _capacity)
        {
            // Should do in-place construction here
            pArray.ptr[pArray.length] = item;
            *pArray = pArray.ptr[0 .. pArray.length + 1];
        }
        else
        {
            // Time to reallocate, do it and cache capacity
            *pArray ~= item;
            _capacity = .capacity(pArray.ptr) / T.sizeof;
        }
    }

    static if (is(Const!(T) : T))
    {
        alias Const!(T) AcceptedElementType;
    }
    else
    {
        alias T AcceptedElementType;
    }

    void write(AcceptedElementType[] items)
    {
        while (items.length)
        {
            write(items[0]);
            items = items[1..$];
        }
    }

    void clear()
    {
        if (!pArray) return;
        pArray.length = 0;
        _capacity = .capacity(pArray.ptr) / T.sizeof;
    }
}

module StringTest2;

import tango.io.FileConduit;
import tango.io.Stdout;
import tango.time.StopWatch;
import Util = tango.text.Util;
import appender;

void main() {

   StopWatch overallWatch;
   overallWatch.start();

   StopWatch loadWatch;
   loadWatch.start();

   auto file = new FileConduit("shakespeare.txt");
   char[] text = new char[cast(size_t)file.length];
   file.input.read(text);

   Stdout.formatln("time to load file: {0:f6} seconds", loadWatch.stop());

   runCharIterateTest(text);
   runWordFindTest(text);
   runWordReplaceTest(text);
   char[][] splitWords = runWordSplitTest(text);
   runConcatenateTest(splitWords);

   Stdout.formatln("overall test duration: {0:f6} seconds", overallWatch.stop());
}

private static void runCharIterateTest(char[] text) {
   StopWatch watch;
   watch.start();
   int spaceCount = 0;
   foreach (dchar c; text) {
     if (c == ' ') spaceCount++;
   }
   Stdout.formatln("iterated through {0} characters, and found {1} spaces in {2:f6} seconds", text.length, spaceCount, watch.stop());
}

private static void runWordFindTest(char[] text) {
   StopWatch watch;
   watch.start();
   int wordInstanceCount = -1;
   int position = 0;
   do {
      wordInstanceCount++;
      position = Util.locatePattern(text, "the", position + 1);
   } while (position < text.length);
   Stdout.formatln("String.indexOf(): found {0} instances of 'the' in {1:f6} seconds", wordInstanceCount, watch.stop());
}

private static void runWordReplaceTest(char[] text) {
   int oldLength = text.length;
   StopWatch watch;
   watch.start();
   char[] replaced = Util.substitute(text, "the", "XXXX");
   int newLength = replaced.length;
   int replacementCount = newLength - oldLength;
   Stdout.formatln("replaced {0} instances of 'the' with 'XXXX' in {1:f6} seconds", replacementCount, watch.stop());
}

private static char[][] runWordSplitTest(char[] text) {
   StopWatch watch;
   watch.start();
   Appender!(char[][]) splitWords;
   foreach (segment; Util.patterns (text, " "))
      splitWords.write(segment);
   Stdout.formatln("split text into {0} words in {1:f6} seconds", splitWords.data.length, watch.stop());
   return splitWords.data;
}

private static void runConcatenateTest(char[][] splitWords) {
   StopWatch watch;
   watch.start();
   Appender!(char[]) buffer;
   foreach (char[] word; splitWords) {
      buffer.write(word);
      buffer.write(" ");
   }
   Stdout.formatln("concatenated {0} words (with {1} chars) in {2:f6} seconds", splitWords.length, buffer.data.length, watch.stop());
}