Want to bring into discussion people that are not on Google+. Samuel recently has posted there some simple experiments with bioinformatics and bad performance of Phobos-based snippet has surprised me.

I did explore issue a bit and reported results in a blog post (snippets are really small and simple) : http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html

One open question remains though - can D/Phobos do better here? Can some changes be done to Phobos functions in question to improve performance or creating bioinformatics-specialized library is only practical solution?

On Thursday, 16 May 2013 at 10:35:12 UTC, Dicebot wrote:
> One open question remains though - can D/Phobos do better here? Can some changes be done to Phobos functions in question to improve performance or creating bioinformatics-specialized library is only practical solution?

Of course things can be improved. For a start, pattern could be a template parameter so that most of the checks are inlined and const-folded.

Using count!(c => c=='G' || c=='C')(line) from std.algorithm would probably perform better as well.

Simply put, countchars is just the obvious naive implementation of the algorithm. It hasn't been tuned at all, and isn't suitable for use in a small kernel like this.

Dicebot:

> I did explore issue a bit and reported results in a blog post (snippets are really small and simple) : http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html

In the first of his posts I don't see -noboundscheck used, and it compares different algorithms from C++ (a switch) and D (two nested ifs, that are not optimal).

From my experience if you have some care you are able to write D code for LDC that is about as fast as equivalent as C code, or better.


> One open question remains though - can D/Phobos do better here?

Of course.

Bye,
bearophile

On Thursday, 16 May 2013 at 10:35:12 UTC, Dicebot wrote:
> Want to bring into discussion people that are not on Google+. Samuel recently has posted there some simple experiments with bioinformatics and bad performance of Phobos-based snippet has surprised me.
>
> I did explore issue a bit and reported results in a blog post (snippets are really small and simple) : http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html
>
> One open question remains though - can D/Phobos do better here? Can some changes be done to Phobos functions in question to improve performance or creating bioinformatics-specialized library is only practical solution?

I bet the problem is in readln. Currently, File.byLine() and readln() are extremely slow, because they call fgetc() one char at a time.

I made an "byLineFast" implementation some time ago that is 10x faster than std.stdio.byLine. It reads lines through rawRead, and using buffers instead of char by char.

I don't have the time to make it phobos-ready (unicode, etc.). But I'll paste it here for any one to use (it works perfectly).

--jm

-------------------------------------

module ByLineFast;

import std.stdio;
import std.string: indexOf;
import std.c.string: memmove;


/**
  Reads by line in an efficient way (10 times faster than File.byLine
  from std.stdio).
  This is accomplished by reading entire buffers (fgetc() is not used),
  and allocating as little as possible.

  The char \n is considered as separator, removing the previous \r
  if it exists.

  The \n is never returned. The \r is not returned if it was
  part of a \r\n (but it is returned if it was by itself).

  The returned string is always a substring of a temporary
  buffer, that must not be stored. If necessary, you must
  use str[] or .dup or .idup to copy to another string.

  Example:

        File f = File("file.txt");
        foreach (string line; ByLineFast(f)) {
            ...process line...
            //Make a copy:
            string copy = line[];
        }

  The file isn't closed when done iterating, unless it was
  the only reference to the file (same as std.stdio.byLine).
  (example: ByLineFast(File("file.txt"))).
*/
struct ByLineFast {
    File file;
    char[] line;
    bool first_call = true;
    char[] buffer;
    char[] strBuffer;

    this(File f, int bufferSize=4096) {
        assert(bufferSize > 0);
        file = f;
        buffer.length = bufferSize;
    }

    @property bool empty() const {
        //Its important to check "line !is null" instead of
        //"line.length != 0", otherwise, no empty lines can
        //be returned, the iteration would be closed.
        if (line !is null) {
            return false;
        }
        if (!file.isOpen) {
            //Clean the buffer to avoid pointer false positives:
			(cast(char[])buffer)[] = 0;
            return true;
        }

        //First read. Determine if it's empty and put the char back.
        auto mutableFP = (cast(File*) &file).getFP();
        auto c = fgetc(mutableFP);
        if (c == -1) {
            //Clean the buffer to avoid pointer false positives:
			(cast(char[])buffer)[] = 0;
            return true;
        }
        if (ungetc(c, mutableFP) != c) {
            assert(false, "Bug in cstdlib implementation");
        }
        return false;
    }

    @property char[] front() {
        if (first_call) {
            popFront();
            first_call = false;
        }
        return line;
    }

    void popFront() {
        if (strBuffer.length == 0) {
            strBuffer = file.rawRead(buffer);
            if (strBuffer.length == 0) {
                file.detach();
                line = null;
                return;
            }
        }

        int pos = strBuffer.indexOf('\n');
        if (pos != -1) {
            if (pos != 0 && strBuffer[pos-1] == '\r') {
                line = strBuffer[0 .. (pos-1)];
            } else {
                line = strBuffer[0 .. pos];
            }
            //Pop the line, skipping the terminator:
            strBuffer = strBuffer[(pos+1) .. $];
        } else {
            //More needs to be read here. Copy the tail of the buffer
            //to the beginning, and try to read with the empty part of
            //the buffer.
            //If no buffer was left, extend the size of the buffer before
            //reading. If the file has ended, then the line is the entire
            //buffer.

            if (strBuffer.ptr != buffer.ptr) {
                //Must use memmove because there might be overlap
                memmove(buffer.ptr, strBuffer.ptr, strBuffer.length * char.sizeof);
            }
            int spaceBegin = strBuffer.length;
            if (strBuffer.length == buffer.length) {
                //Must extend the buffer to keep reading.
                assumeSafeAppend(buffer);
                buffer.length = buffer.length * 2;
            }
            char[] readPart = file.rawRead(buffer[spaceBegin .. $]);
            if (readPart.length == 0) {
                //End of the file. Return whats in the buffer.
                //The next popFront() will try to read again, and then
                //mark empty condition.
                if (spaceBegin != 0 && buffer[spaceBegin-1] == '\r') {
                    line = buffer[0 .. spaceBegin-1];
                } else {
                    line = buffer[0 .. spaceBegin];
                }
                strBuffer = null;
                return;
            }
            strBuffer = buffer[0 .. spaceBegin + readPart.length];
            //Now that we have new data in strBuffer, we can go on.
            //If a line isn't found, the buffer will be extended again to read more.
            popFront();
        }
    }
}

On Thursday, 16 May 2013 at 10:35:12 UTC, Dicebot wrote:
> Want to bring into discussion people that are not on Google+. Samuel recently has posted there some simple experiments with bioinformatics and bad performance of Phobos-based snippet has surprised me.
>
> I did explore issue a bit and reported results in a blog post (snippets are really small and simple) : http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html
>
> One open question remains though - can D/Phobos do better here? Can some changes be done to Phobos functions in question to improve performance or creating bioinformatics-specialized library is only practical solution?


May I also recommend my tool "avgtime" to make simple benchmarks, instead of "time" (you can see an ascii histogram as the output):

     https://github.com/jmcabo/avgtime/tree/

For example:

$ avgtime -r10 -h -q  ls
------------------------
Total time (ms): 27.413
Repetitions    : 10
Sample mode    : 2.6 (4 ocurrences)
Median time    : 2.6695
Avg time       : 2.7413
Std dev.       : 0.260515
Minimum        : 2.557
Maximum        : 3.505
95% conf.int.  : [2.2307, 3.2519]  e = 0.510599
99% conf.int.  : [2.07026, 3.41234]  e = 0.671041
EstimatedAvg95%: [2.57983, 2.90277]  e = 0.161466
EstimatedAvg99%: [2.5291, 2.9535]  e = 0.212202
Histogram      :
    msecs: count  normalized bar
      2.5:     2  ####################
      2.6:     4  ########################################
      2.7:     3  ##############################
      3.5:     1  ##########

--jm

> May I also recommend my tool "avgtime" to make simple benchmarks, instead of "time" (you can see an ascii histogram as the output):
> 
>      https://github.com/jmcabo/avgtime/tree/
> 
> For example:
> 
> $ avgtime -r10 -h -q  ls
> ------------------------
> Total time (ms): 27.413
> Repetitions    : 10
> Sample mode    : 2.6 (4 ocurrences)
> Median time    : 2.6695
> Avg time       : 2.7413
> Std dev.       : 0.260515
> Minimum        : 2.557
> Maximum        : 3.505
> 95% conf.int.  : [2.2307, 3.2519]  e = 0.510599
> 99% conf.int.  : [2.07026, 3.41234]  e = 0.671041
> EstimatedAvg95%: [2.57983, 2.90277]  e = 0.161466
> EstimatedAvg99%: [2.5291, 2.9535]  e = 0.212202
> Histogram      :
>     msecs: count  normalized bar
>       2.5:     2  ####################
>       2.6:     4  ########################################
>       2.7:     3  ##############################
>       3.5:     1  ##########
> 
> --jm
> 

Thank you for self-promotion, I miss that tool.

On Thursday, 16 May 2013 at 10:35:12 UTC, Dicebot wrote:
> Want to bring into discussion people that are not on Google+. Samuel recently has posted there some simple experiments with bioinformatics and bad performance of Phobos-based snippet has surprised me.
>
> I did explore issue a bit and reported results in a blog post (snippets are really small and simple) : http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html
>
> One open question remains though - can D/Phobos do better here? Can some changes be done to Phobos functions in question to improve performance or creating bioinformatics-specialized library is only practical solution?

Very nice blog post.

Something similar should go into D wiki database so it won't get lost in "In 80s we had..." topics.

For sure there is a space for improvements in Phobos but such articles are good start to prevent wave of "D is slow and sucks" and force people to rethink if they are using right tools (functions in this case ie UTF8 aware vs plain ASCII ones) for their job.

Btw, you've got nice articles on your blog in overall. Bookmarked ;)

On Thu, 16 May 2013 12:35:11 +0200
"Dicebot" <m.strashun@gmail.com> wrote:
> 
> I did explore issue a bit and reported results in a blog post (snippets are really small and simple) : http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html
> 

For anyone else who has trouble viewing that like I did, there
appears to be an HTML version of it here:
http://dicebot.blogspot.com/2013/05/short-performance-tuning-story.html?m=1

On Thu, 16 May 2013 09:03:36 -0500
1100110 <0b1100110@gmail.com> wrote:

> > May I also recommend my tool "avgtime" to make simple benchmarks, instead of "time" (you can see an ascii histogram as the output):
> > 
> >      https://github.com/jmcabo/avgtime/tree/
> > 
> > For example:
> > 
> > $ avgtime -r10 -h -q  ls
> > ------------------------
> > Total time (ms): 27.413
> > Repetitions    : 10
> > Sample mode    : 2.6 (4 ocurrences)
> > Median time    : 2.6695
> > Avg time       : 2.7413
> > Std dev.       : 0.260515
> > Minimum        : 2.557
> > Maximum        : 3.505
> > 95% conf.int.  : [2.2307, 3.2519]  e = 0.510599
> > 99% conf.int.  : [2.07026, 3.41234]  e = 0.671041
> > EstimatedAvg95%: [2.57983, 2.90277]  e = 0.161466
> > EstimatedAvg99%: [2.5291, 2.9535]  e = 0.212202
> > Histogram      :
> >     msecs: count  normalized bar
> >       2.5:     2  ####################
> >       2.6:     4  ########################################
> >       2.7:     3  ##############################
> >       3.5:     1  ##########
> > 
> > --jm
> > 
> 
> Thank you for self-promotion, I miss that tool.
> 
> 

Indeed. I had totally forgotten about that, and yet it *should* be the first thing I think of when I think "timing a program". IMO, that should be a standard tool in any unixy installation.

On 5/16/13 9:48 AM, Juan Manuel Cabo wrote:
> I bet the problem is in readln. Currently, File.byLine() and readln()
> are extremely slow, because they call fgetc() one char at a time.

Depends on the OS.

Andrei