Nicolas Bock | 8 Feb 20:26 2013
Picon

performance question

Hi list,

I wrote a script that reads matrix elements from standard input, parses the input using a regular expression, and then bins the matrix elements by magnitude. I wrote the same script in python (just to be sure :) ) and find that the python version vastly outperforms the Haskell script.

To be concrete:

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
real    0m2.655s
user    0m2.677s
sys     0m0.095s

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
real    0m0.445s
user    0m0.615s
sys     0m0.032s

The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

Could you have a look at the script and give me some pointers as to where I could improve it, both in terms of performance and also generally, as I am very new to Haskell.

Thanks already,

nick

Attachment (printMatrixDecay.hs): application/octet-stream, 2731 bytes
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Aleksey Khudyakov | 8 Feb 21:23 2013
Picon

Re: performance question

On 08.02.2013 23:26, Nicolas Bock wrote:
> Hi list,
>
> I wrote a script that reads matrix elements from standard input, parses
> the input using a regular expression, and then bins the matrix elements
> by magnitude. I wrote the same script in python (just to be sure :) )
> and find that the python version vastly outperforms the Haskell script.
>
General performance hints

1) Strings are slow. Fast alternatives are text[1] for textual data and 
bytestrings[2] for binary data. I can't say anything about performance 
of Text.Regex.Posix.

2) Appending list wrong operation to do in performance sensitive code.
(++) traverses its first argument so it's O(n) in its length.

What exactly are you tryeing to do? Create a histogram?

> The Haskell script was compiled with "ghc --make printMatrixDecay.hs".
>
If you want performance you absolutely should use -O2.

[1] http://hackage.haskell.org/package/text
[2] http://hackage.haskell.org/package/bytestring
Nicolas Bock | 8 Feb 22:02 2013
Picon

Re: performance question




On Fri, Feb 8, 2013 at 1:23 PM, Aleksey Khudyakov <alexey.skladnoy <at> gmail.com> wrote:
On 08.02.2013 23:26, Nicolas Bock wrote:
Hi list,

I wrote a script that reads matrix elements from standard input, parses
the input using a regular expression, and then bins the matrix elements
by magnitude. I wrote the same script in python (just to be sure :) )
and find that the python version vastly outperforms the Haskell script.

General performance hints

1) Strings are slow. Fast alternatives are text[1] for textual data and bytestrings[2] for binary data. I can't say anything about performance of Text.Regex.Posix.

Thanks for the suggestion, I will try that.

 
2) Appending list wrong operation to do in performance sensitive code.
(++) traverses its first argument so it's O(n) in its length.


What exactly are you tryeing to do? Create a histogram?

Yes, a histogram. The binning code is really a little awkward. I haven't gotten used to thinking in terms of inmutable objects yet and this list appending is really a pretty bad hack to kind of allow me to increment the bin counts. How would one do this more haskellishish?

 


The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

If you want performance you absolutely should use -O2.

I'll try that.

 

[1] http://hackage.haskell.org/package/text
[2] http://hackage.haskell.org/package/bytestring

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Aleksey Khudyakov | 8 Feb 22:34 2013
Picon

Re: performance question

On 09.02.2013 01:02, Nicolas Bock wrote:
> Yes, a histogram. The binning code is really a little awkward. I haven't
> gotten used to thinking in terms of inmutable objects yet and this list
> appending is really a pretty bad hack to kind of allow me to increment
> the bin counts. How would one do this more haskellishish?
>
Histogramming is a bit awkward in haskell. If we want to stick to 
immutable data types best choice is to have map bin → number of entries. 
For every new entry select bin and add 1 to its content.

But if we want to store data in array we have to deal with mutable 
state. It's not realistic to copy array on every update. For that case I 
wrote I library histogram-fill[1]. Below is program which does 
approximately same thing.

 > import Data.Histogram.Fill
 > import Data.Histogram      (Histogram)
 >
 > hb :: HBuilder String (Histogram LogBinD Int)
 > hb = forceInt -<< mkSimple (logBinDN 1e-8 10 10) <<- read
 >
 > main :: IO ()
 > main = do
 >   l <- getContents
 >   print $ fillBuilder hb $ lines l

I cheated and used sed to strip unused data. It uses String so it's 
still slower than python.

$ time (python gen.py -N 300 | sed 's/.*=//' | ./printMatrixDecay )
real    0m0.958s
user    0m2.096s
sys     0m0.052s

$ time (python gen.py -N 300 | python printMatrixDecay.py -)
real    0m0.590s
user    0m0.952s
sys     0m0.016s

[1] http://hackage.haskell.org/package/histogram-fill

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicolas Bock | 9 Feb 23:30 2013
Picon

Re: performance question




On Fri, Feb 8, 2013 at 1:23 PM, Aleksey Khudyakov <alexey.skladnoy <at> gmail.com> wrote:
On 08.02.2013 23:26, Nicolas Bock wrote:
Hi list,

I wrote a script that reads matrix elements from standard input, parses
the input using a regular expression, and then bins the matrix elements
by magnitude. I wrote the same script in python (just to be sure :) )
and find that the python version vastly outperforms the Haskell script.

General performance hints

1) Strings are slow. Fast alternatives are text[1] for textual data and bytestrings[2] for binary data. I can't say anything about performance of Text.Regex.Posix.

Hi Aleksey,

could you show me how I would use ByteString? I can't get the script to compile. It's complaining that:

No instance for (RegexContext
                       Regex Data.ByteString.ByteString (AllTextSubmatches [] a0))

which is too cryptic for me. Is it not able to form a regular expression with a ByteString argument? From the documentation of Text.Regex.Posix it seems that it should be. Maybe it's because I am trying to "read (r!!1) :: Double" which I am having issues with also. Is (r!!1) a ByteString? And if so, how would I convert that to a Double?

Thanks,

nick

 
2) Appending list wrong operation to do in performance sensitive code.
(++) traverses its first argument so it's O(n) in its length.


What exactly are you tryeing to do? Create a histogram?



The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

If you want performance you absolutely should use -O2.


[1] http://hackage.haskell.org/package/text
[2] http://hackage.haskell.org/package/bytestring

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Aleksey Khudyakov | 13 Feb 22:20 2013
Picon

Re: performance question

On 10.02.2013 02:30, Nicolas Bock wrote:
> Hi Aleksey,
>
> could you show me how I would use ByteString? I can't get the script to
> compile. It's complaining that:
>
> No instance for (RegexContext
>                         Regex Data.ByteString.ByteString
> (AllTextSubmatches [] a0))
>
> which is too cryptic for me. Is it not able to form a regular expression
> with a ByteString argument? From the documentation of Text.Regex.Posix
> it seems that it should be. Maybe it's because I am trying to "read
> (r!!1) :: Double" which I am having issues with also. Is (r!!1) a
> ByteString? And if so, how would I convert that to a Double?
>
It's error message from regex library you use. I can't say what exactly 
it means, I never used it. But most likely it cannot work with bytestrings.

Most other languages rely on regexp as go to tool for parsing. In 
haskell main parsing tools are parser combinators such as parsec[1] or
attoparsec[2]. Parsec is more generic and attoparsec is much faster.

In attachment program which uses attoparsec for parsing it's about 
2times slower than C++ example posted in the thread.

[1] http://hackage.haskell.org/package/parsec
[2] http://hackage.haskell.org/package/attoparsec
Attachment (printMatrixDecay.hs): text/x-haskell, 955 bytes
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicolas Bock | 9 Feb 23:35 2013
Picon

Re: performance question




On Fri, Feb 8, 2013 at 1:23 PM, Aleksey Khudyakov <alexey.skladnoy <at> gmail.com> wrote:
On 08.02.2013 23:26, Nicolas Bock wrote:
Hi list,

I wrote a script that reads matrix elements from standard input, parses
the input using a regular expression, and then bins the matrix elements
by magnitude. I wrote the same script in python (just to be sure :) )
and find that the python version vastly outperforms the Haskell script.

General performance hints

1) Strings are slow. Fast alternatives are text[1] for textual data and bytestrings[2] for binary data. I can't say anything about performance of Text.Regex.Posix.

2) Appending list wrong operation to do in performance sensitive code.
(++) traverses its first argument so it's O(n) in its length.


What exactly are you tryeing to do? Create a histogram?



The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

If you want performance you absolutely should use -O2.

Another question: When I compile the code with --make and -O2, and then run it on a larger matrix, I get this error message:

$ ./createMatrixDump.py -N 512 | ./printMatrixDecay
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

When I use "runghc" instead, I don't get an error. What does this error mean, and how do I fix it?

Thanks,

nick

 

[1] http://hackage.haskell.org/package/text
[2] http://hackage.haskell.org/package/bytestring

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Bob Ippolito | 10 Feb 00:12 2013

Re: performance question

I've been playing with your example to optimize it a bit, I have to run but here's what I have so far. It's about as fast as the Python code, I'll make it faster when I have more time over the next few days.



On Sat, Feb 9, 2013 at 2:35 PM, Nicolas Bock <nicolasbock <at> gmail.com> wrote:



On Fri, Feb 8, 2013 at 1:23 PM, Aleksey Khudyakov <alexey.skladnoy <at> gmail.com> wrote:
On 08.02.2013 23:26, Nicolas Bock wrote:
Hi list,

I wrote a script that reads matrix elements from standard input, parses
the input using a regular expression, and then bins the matrix elements
by magnitude. I wrote the same script in python (just to be sure :) )
and find that the python version vastly outperforms the Haskell script.

General performance hints

1) Strings are slow. Fast alternatives are text[1] for textual data and bytestrings[2] for binary data. I can't say anything about performance of Text.Regex.Posix.

2) Appending list wrong operation to do in performance sensitive code.
(++) traverses its first argument so it's O(n) in its length.


What exactly are you tryeing to do? Create a histogram?



The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

If you want performance you absolutely should use -O2.

Another question: When I compile the code with --make and -O2, and then run it on a larger matrix, I get this error message:

$ ./createMatrixDump.py -N 512 | ./printMatrixDecay
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

When I use "runghc" instead, I don't get an error. What does this error mean, and how do I fix it?

Thanks,

nick



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Bob Ippolito | 8 Feb 21:45 2013

Re: performance question

Do you mind posting createMatrixDump.py and printMatrixDecay.py? That would certainly make it easier to help you.


On Fri, Feb 8, 2013 at 11:26 AM, Nicolas Bock <nicolasbock <at> gmail.com> wrote:
Hi list,

I wrote a script that reads matrix elements from standard input, parses the input using a regular expression, and then bins the matrix elements by magnitude. I wrote the same script in python (just to be sure :) ) and find that the python version vastly outperforms the Haskell script.

To be concrete:

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
real    0m2.655s
user    0m2.677s
sys     0m0.095s

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
real    0m0.445s
user    0m0.615s
sys     0m0.032s

The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

Could you have a look at the script and give me some pointers as to where I could improve it, both in terms of performance and also generally, as I am very new to Haskell.

Thanks already,

nick


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicolas Bock | 8 Feb 21:56 2013
Picon

Re: performance question

Sorry, should have done this right away. Here are the other two scripts.


On Fri, Feb 8, 2013 at 1:45 PM, Bob Ippolito <bob <at> redivi.com> wrote:
Do you mind posting createMatrixDump.py and printMatrixDecay.py? That would certainly make it easier to help you.


On Fri, Feb 8, 2013 at 11:26 AM, Nicolas Bock <nicolasbock <at> gmail.com> wrote:
Hi list,

I wrote a script that reads matrix elements from standard input, parses the input using a regular expression, and then bins the matrix elements by magnitude. I wrote the same script in python (just to be sure :) ) and find that the python version vastly outperforms the Haskell script.

To be concrete:

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
real    0m2.655s
user    0m2.677s
sys     0m0.095s

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
real    0m0.445s
user    0m0.615s
sys     0m0.032s

The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

Could you have a look at the script and give me some pointers as to where I could improve it, both in terms of performance and also generally, as I am very new to Haskell.

Thanks already,

nick


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe



Attachment (createMatrixDump.py): application/octet-stream, 624 bytes
Attachment (printMatrixDecay.py): application/octet-stream, 1811 bytes
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Branimir Maksimovic | 9 Feb 00:57 2013
Picon

Re: performance question

Heh, I have wrote c++ version and that is much faster than python ;)
 
bmaxa <at> maxa:~/haskell$ time ./createMatrixDump.py -N 128 > output.txt

real    0m0.041s
user    0m0.040s
sys     0m0.000s
bmaxa <at> maxa:~/haskell$ time ./printMatrixDecay.py - < output.txt
(-) read 16384 matrix elements (128x128 = 16384)
[0.00e+00, 1.00e-08) = 0 (0.00%) 0
[1.00e-08, 1.00e-07) = 0 (0.00%) 0
[1.00e-07, 1.00e-06) = 0 (0.00%) 0
[1.00e-06, 1.00e-05) = 0 (0.00%) 0
[1.00e-05, 1.00e-04) = 1 (0.00%) 1
[1.00e-04, 1.00e-03) = 15 (0.00%) 16
[1.00e-03, 1.00e-02) = 149 (0.00%) 165
[1.00e-02, 1.00e-01) = 1425 (0.00%) 1590
[1.00e-01, 1.00e+00) = 14794 (0.00%) 16384
[1.00e+00, 2.00e+00) = 0 (0.00%) 16384

real    0m0.081s
user    0m0.072s
sys     0m0.008s
bmaxa <at> maxa:~/haskell$ time ./printMatrixDecay < output.txt
read 16384 matrix elements (128x128 = 16384)
[0.00e+00, 1.00e-08) = 0 (0.00%) 0
[1.00e-08, 1.00e-07) = 0 (0.00%) 0
[1.00e-07, 1.00e-06) = 0 (0.00%) 0
[1.00e-06, 1.00e-05) = 0 (0.00%) 0
[1.00e-05, 1.00e-04) = 1 (0.01%) 1
[1.00e-04, 1.00e-03) = 15 (0.09%) 16
[1.00e-03, 1.00e-02) = 149 (0.91%) 165
[1.00e-02, 1.00e-01) = 1425 (8.70%) 1590
[1.00e-01, 1.00e+00) = 14794 (90.30%) 16384
[1.00e+00, 2.00e+00) = 0 (0.00%) 16384

real    0m0.018s
user    0m0.012s
sys     0m0.004s

unfortunately g++ does not have regex implemented yet so I used libpcre ...

#include <pcre.h>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <stdexcept>
#include <vector>

template <class F>
void regex(const std::string& in, const std::string& pattern,int n,F f)
{
    int ovec[3*n],position;
    const char* error;   
    int errorpos;

    pcre* pe = pcre_compile(pattern.c_str(),0,&error,&errorpos,0);
    if(!pe)throw std::runtime_error(error);

    pcre_extra* extra=pcre_study(pe,0,&error);

    for(position = 0;
        pcre_exec(pe,extra,in.c_str(),in.size(),position,0,ovec,3*n)>=0;
        position = ovec[1])f(position,ovec);
    f(position,ovec);
    pcre_free(extra);
    pcre_free(pe);   
}

int main()
{
  std::ios::sync_with_stdio(false);
  std::ostringstream oss;
  oss << std::cin.rdbuf();
  const std::string& in = oss.str();
  std::vector<double> strataBounds = { 0.0, 1.0e-8, 1.0e-7, 1.0e-6, 1.0e-5, 1.0e-4, 1.0e-3, 1.0e-2, 1.0e-1, 1.0, 2.0 };
  std::vector<int> strataCounts(strataBounds.size());
  unsigned N = 0;
  auto f = [&](int position,int* ovec)
  {
    if(int(position) > ovec[0])return;
    
    ++N;
    double aij = 0.0;
    std::istringstream iss(in.substr(ovec[2],ovec[3]-ovec[2]));
    iss >> aij;
    aij=fabs(aij);
    for(unsigned i = 0; i < strataBounds.size() - 1; ++i)
    {
      if(aij >= strataBounds[i] && aij < strataBounds[i+1])
      {
        ++strataCounts[i];
        break;
      }
    }
  };
  regex(in,"matrix.*= ([0-9.eE+-]+)\n",2,f);
  printf("read %d matrix elements (%dx%d = %d)\n",N,int(sqrt(N)),int(sqrt(N)),N);
  int total = 0;
  for(unsigned i = 0; i< strataBounds.size()-1;++i)
  {
    total += strataCounts[i];
    printf("[%1.2e, %1.2e) = %d (%1.2f%%) %d\n", strataBounds[i], strataBounds[i+1],
    strataCounts[i], 100*(double(strataCounts[i])/N), total);
  }
}



From: nicolasbock <at> gmail.com
Date: Fri, 8 Feb 2013 12:26:09 -0700
To: haskell-cafe <at> haskell.org
Subject: [Haskell-cafe] performance question

Hi list,

I wrote a script that reads matrix elements from standard input, parses the input using a regular expression, and then bins the matrix elements by magnitude. I wrote the same script in python (just to be sure :) ) and find that the python version vastly outperforms the Haskell script.

To be concrete:

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
real    0m2.655s
user    0m2.677s
sys     0m0.095s

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
real    0m0.445s
user    0m0.615s
sys     0m0.032s

The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

Could you have a look at the script and give me some pointers as to where I could improve it, both in terms of performance and also generally, as I am very new to Haskell.

Thanks already,

nick


_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Branimir Maksimovic | 10 Feb 07:54 2013
Picon

Re: performance question

Here is haskell version that is faster than python, almost as fast as c++.
You need to install bytestring-lexing package for readDouble.

bmaxa <at> maxa:~/haskell$ time ./printMatrixDecay - < output.txt
read 16384 matrix elements (128x128 = 16384)
[0.00e0, 1.00e-8) = 0 (0.00%) 0
[1.00e-8, 1.00e-7) = 0 (0.00%) 0
[1.00e-7, 1.00e-6) = 0 (0.00%) 0
[1.00e-6, 1.00e-5) = 0 (0.00%) 0
[1.00e-5, 1.00e-4) = 1 (0.01%) 1
[1.00e-4, 1.00e-3) = 17 (0.10%) 18
[1.00e-3, 1.00e-2) = 155 (0.95%) 173
[1.00e-2, 1.00e-1) = 1434 (8.75%) 1607
[1.00e-1, 1.00e0) = 14777 (90.19%) 16384
[1.00e0, 2.00e0) = 0 (0.00%) 16384

real    0m0.031s
user    0m0.028s
sys     0m0.000s
bmaxa <at> maxa:~/haskell$ time ./printMatrixDecay.py - < output.txt
(-) read 16384 matrix elements (128x128 = 16384)
[0.00e+00, 1.00e-08) = 0 (0.00%) 0
[1.00e-08, 1.00e-07) = 0 (0.00%) 0
[1.00e-07, 1.00e-06) = 0 (0.00%) 0
[1.00e-06, 1.00e-05) = 0 (0.00%) 0
[1.00e-05, 1.00e-04) = 1 (0.00%) 1
[1.00e-04, 1.00e-03) = 17 (0.00%) 18
[1.00e-03, 1.00e-02) = 155 (0.00%) 173
[1.00e-02, 1.00e-01) = 1434 (0.00%) 1607
[1.00e-01, 1.00e+00) = 14777 (0.00%) 16384
[1.00e+00, 2.00e+00) = 0 (0.00%) 16384

real    0m0.081s
user    0m0.080s
sys     0m0.000s

Program follows...

import System.Environment
import Text.Printf
import Text.Regex.PCRE
import Data.Maybe
import Data.Array.IO
import Data.Array.Unboxed
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Lex.Double (readDouble)

strataBounds :: UArray Int Double
strataBounds = listArray (0,10) [ 0.0, 1.0e-8, 1.0e-7, 1.0e-6, 1.0e-5, 1.0e-4, 1.0e-3, 1.0e-2, 1.0e-1, 1.0, 2.0 ]

newStrataCounts :: IO(IOUArray Int Int)
newStrataCounts = newArray (bounds strataBounds) 0

main = do
    l <- B.getContents
    let a = B.lines l
    strataCounts <- newStrataCounts
    n <- calculate strataCounts a 0
    let
        printStrataCounts :: IO ()
        printStrataCounts = do
            let s = round $ sqrt (fromIntegral n::Double) :: Int
            printf "read %d matrix elements (%dx%d = %d)\n" n s s n
            printStrataCounts' 0 0
        printStrataCounts' :: Int -> Int -> IO ()
        printStrataCounts' i total 
            | i < (snd $ bounds strataBounds) = do
                count <- readArray strataCounts i
                let 
                    p :: Double
                    p = (100.0*(fromIntegral count) :: Double)/(fromIntegral n :: Double)
                printf "[%1.2e, %1.2e) = %i (%1.2f%%) %i\n" (strataBounds ! i) (strataBounds ! (i+1)) 
                                                                count p (total + count)
                printStrataCounts' (i+1) (total+count)
            | otherwise = return ()
    printStrataCounts

calculate :: IOUArray Int Int -> [B.ByteString] -> Int -> IO Int
calculate _ [] n = return n
calculate counts (l:ls) n = do
    let 
        a = case getAllTextSubmatches $ l =~ B.pack "matrix.*= ([0-9eE.+-]+)$" :: [B.ByteString] of
                [_,v] -> Just (readDouble v) :: Maybe (Maybe (Double,B.ByteString))
                _ -> Nothing
        b = (fst.fromJust.fromJust) a
        loop :: Int -> IO()
        loop i
            | i < (snd $ bounds strataBounds) = 
                if (b >= (strataBounds ! i)) && (b < (strataBounds ! (i+1)))
                then do
                    c <- readArray counts i
                    writeArray counts i (c+1)
                else 
                    loop (i+1)
            | otherwise = return ()
    if isNothing a
        then 
            calculate counts ls n
        else do
            loop 0
            calculate counts ls (n+1)


From: nicolasbock <at> gmail.com
Date: Fri, 8 Feb 2013 12:26:09 -0700
To: haskell-cafe <at> haskell.org
Subject: [Haskell-cafe] performance question

Hi list,

I wrote a script that reads matrix elements from standard input, parses the input using a regular expression, and then bins the matrix elements by magnitude. I wrote the same script in python (just to be sure :) ) and find that the python version vastly outperforms the Haskell script.

To be concrete:

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
real    0m2.655s
user    0m2.677s
sys     0m0.095s

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
real    0m0.445s
user    0m0.615s
sys     0m0.032s

The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

Could you have a look at the script and give me some pointers as to where I could improve it, both in terms of performance and also generally, as I am very new to Haskell.

Thanks already,

nick


_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicolas Bock | 12 Feb 23:57 2013
Picon

Re: performance question

Thanks so much for your efforts, this really helped!

Thanks again,

nick



On Sat, Feb 9, 2013 at 11:54 PM, Branimir Maksimovic <bmaxa <at> hotmail.com> wrote:
Here is haskell version that is faster than python, almost as fast as c++.
You need to install bytestring-lexing package for readDouble.

bmaxa <at> maxa:~/haskell$ time ./printMatrixDecay - < output.txt
read 16384 matrix elements (128x128 = 16384)
[0.00e0, 1.00e-8) = 0 (0.00%) 0
[1.00e-8, 1.00e-7) = 0 (0.00%) 0
[1.00e-7, 1.00e-6) = 0 (0.00%) 0
[1.00e-6, 1.00e-5) = 0 (0.00%) 0
[1.00e-5, 1.00e-4) = 1 (0.01%) 1
[1.00e-4, 1.00e-3) = 17 (0.10%) 18
[1.00e-3, 1.00e-2) = 155 (0.95%) 173
[1.00e-2, 1.00e-1) = 1434 (8.75%) 1607
[1.00e-1, 1.00e0) = 14777 (90.19%) 16384
[1.00e0, 2.00e0) = 0 (0.00%) 16384

real    0m0.031s
user    0m0.028s
sys     0m0.000s
bmaxa <at> maxa:~/haskell$ time ./printMatrixDecay.py - < output.txt
(-) read 16384 matrix elements (128x128 = 16384)
[0.00e+00, 1.00e-08) = 0 (0.00%) 0
[1.00e-08, 1.00e-07) = 0 (0.00%) 0
[1.00e-07, 1.00e-06) = 0 (0.00%) 0
[1.00e-06, 1.00e-05) = 0 (0.00%) 0
[1.00e-05, 1.00e-04) = 1 (0.00%) 1
[1.00e-04, 1.00e-03) = 17 (0.00%) 18
[1.00e-03, 1.00e-02) = 155 (0.00%) 173
[1.00e-02, 1.00e-01) = 1434 (0.00%) 1607
[1.00e-01, 1.00e+00) = 14777 (0.00%) 16384
[1.00e+00, 2.00e+00) = 0 (0.00%) 16384

real    0m0.081s
user    0m0.080s
sys     0m0.000s

Program follows...

import System.Environment
import Text.Printf
import Text.Regex.PCRE
import Data.Maybe
import Data.Array.Unboxed
import qualified Data.ByteString.Char8 as B
import Data.ByteString.Lex.Double (readDouble)

strataBounds :: UArray Int Double
strataBounds = listArray (0,10) [ 0.0, 1.0e-8, 1.0e-7, 1.0e-6, 1.0e-5, 1.0e-4, 1.0e-3, 1.0e-2, 1.0e-1, 1.0, 2.0 ]

newStrataCounts :: IO(IOUArray Int Int)
newStrataCounts = newArray (bounds strataBounds) 0

main = do
    l <- B.getContents
    let a = B.lines l
    strataCounts <- newStrataCounts
    n <- calculate strataCounts a 0
    let
        printStrataCounts :: IO ()
        printStrataCounts = do
            let s = round $ sqrt (fromIntegral n::Double) :: Int
            printf "read %d matrix elements (%dx%d = %d)\n" n s s n
            printStrataCounts' 0 0
        printStrataCounts' :: Int -> Int -> IO ()
        printStrataCounts' i total 
            | i < (snd $ bounds strataBounds) = do
                count <- readArray strataCounts i
                let 
                    p :: Double
                    p = (100.0*(fromIntegral count) :: Double)/(fromIntegral n :: Double)
                printf "[%1.2e, %1.2e) = %i (%1.2f%%) %i\n" (strataBounds ! i) (strataBounds ! (i+1)) 
                                                                count p (total + count)
                printStrataCounts' (i+1) (total+count)
            | otherwise = return ()
    printStrataCounts

calculate :: IOUArray Int Int -> [B.ByteString] -> Int -> IO Int
calculate _ [] n = return n
calculate counts (l:ls) n = do
    let 
        a = case getAllTextSubmatches $ l =~ B.pack "matrix.*= ([0-9eE.+-]+)$" :: [B.ByteString] of
                [_,v] -> Just (readDouble v) :: Maybe (Maybe (Double,B.ByteString))
                _ -> Nothing
        b = (fst.fromJust.fromJust) a
        loop :: Int -> IO()
        loop i
            | i < (snd $ bounds strataBounds) = 
                if (b >= (strataBounds ! i)) && (b < (strataBounds ! (i+1)))
                then do
                    c <- readArray counts i
                    writeArray counts i (c+1)
                else 
                    loop (i+1)
            | otherwise = return ()
    if isNothing a
        then 
            calculate counts ls n
        else do
            loop 0
            calculate counts ls (n+1)


From: nicolasbock <at> gmail.com
Date: Fri, 8 Feb 2013 12:26:09 -0700
To: haskell-cafe <at> haskell.org
Subject: [Haskell-cafe] performance question

Hi list,

I wrote a script that reads matrix elements from standard input, parses the input using a regular expression, and then bins the matrix elements by magnitude. I wrote the same script in python (just to be sure :) ) and find that the python version vastly outperforms the Haskell script.

To be concrete:

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
real    0m2.655s
user    0m2.677s
sys     0m0.095s

$ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
real    0m0.445s
user    0m0.615s
sys     0m0.032s

The Haskell script was compiled with "ghc --make printMatrixDecay.hs".

Could you have a look at the script and give me some pointers as to where I could improve it, both in terms of performance and also generally, as I am very new to Haskell.

Thanks already,

nick


_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe <at> haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
briand | 13 Feb 05:32 2013

Re: performance question

On Tue, 12 Feb 2013 15:57:37 -0700
Nicolas Bock <nicolasbock <at> gmail.com> wrote:

> >  Here is haskell version that is faster than python, almost as fast as c++.
> > You need to install bytestring-lexing package for readDouble.

I was hoping Branimir could comment on how the improvements were allocated.

how much is due to text.regex.pcre (which looks to be a wrapper to libpcre) ?

how much can be attributed to using data.bytestring ?

you have to admit, it's amazing how well a byte-compiled, _dynamically typed_ interpreter can do against
an actualy native code compiler.  Can't regex be done effectively in haskell ?  Is it something that can't be
done, or is it just such minimal effort to link to pcre that it's not worth the trouble ?

Brian

> > import Text.Regex.PCRE
> > import Data.Maybe
> > import Data.Array.IO
> > import Data.Array.Unboxed
> > import qualified Data.ByteString.Char8 as B
> > import Data.ByteString.Lex.Double (readDouble)
> >
> > strataBounds :: UArray Int Double
> > strataBounds = listArray (0,10) [ 0.0, 1.0e-8, 1.0e-7, 1.0e-6, 1.0e-5,
> > 1.0e-4, 1.0e-3, 1.0e-2, 1.0e-1, 1.0, 2.0 ]
> >
> > newStrataCounts :: IO(IOUArray Int Int)
> > newStrataCounts = newArray (bounds strataBounds) 0
> >
> > main = do
> >     l <- B.getContents
> >     let a = B.lines l
> >     strataCounts <- newStrataCounts
> >     n <- calculate strataCounts a 0
> >     let
> >         printStrataCounts :: IO ()
> >         printStrataCounts = do
> >             let s = round $ sqrt (fromIntegral n::Double) :: Int
> >             printf "read %d matrix elements (%dx%d = %d)\n" n s s n
> >             printStrataCounts' 0 0
> >         printStrataCounts' :: Int -> Int -> IO ()
> >         printStrataCounts' i total
> >             | i < (snd $ bounds strataBounds) = do
> >                 count <- readArray strataCounts i
> >                 let
> >                     p :: Double
> >                     p = (100.0*(fromIntegral count) ::
> > Double)/(fromIntegral n :: Double)
> >                 printf "[%1.2e, %1.2e) = %i (%1.2f%%) %i\n" (strataBounds
> > ! i) (strataBounds ! (i+1))
> >                                                                 count p
> > (total + count)
> >                 printStrataCounts' (i+1) (total+count)
> >             | otherwise = return ()
> >     printStrataCounts
> >
> > calculate :: IOUArray Int Int -> [B.ByteString] -> Int -> IO Int
> > calculate _ [] n = return n
> > calculate counts (l:ls) n = do
> >     let
> >         a = case getAllTextSubmatches $ l =~ B.pack "matrix.*=
> > ([0-9eE.+-]+)$" :: [B.ByteString] of
> >                 [_,v] -> Just (readDouble v) :: Maybe (Maybe
> > (Double,B.ByteString))
> >                 _ -> Nothing
> >         b = (fst.fromJust.fromJust) a
> >         loop :: Int -> IO()
> >         loop i
> >             | i < (snd $ bounds strataBounds) =
> >                 if (b >= (strataBounds ! i)) && (b < (strataBounds !
> > (i+1)))
> >                 then do
> >                     c <- readArray counts i
> >                     writeArray counts i (c+1)
> >                 else
> >                     loop (i+1)
> >             | otherwise = return ()
> >     if isNothing a
> >         then
> >             calculate counts ls n
> >         else do
> >             loop 0
> >             calculate counts ls (n+1)
> >
> >
> > ------------------------------
> > From: nicolasbock <at> gmail.com
> > Date: Fri, 8 Feb 2013 12:26:09 -0700
> > To: haskell-cafe <at> haskell.org
> > Subject: [Haskell-cafe] performance question
> >
> > Hi list,
> >
> > I wrote a script that reads matrix elements from standard input, parses
> > the input using a regular expression, and then bins the matrix elements by
> > magnitude. I wrote the same script in python (just to be sure :) ) and find
> > that the python version vastly outperforms the Haskell script.
> >
> > To be concrete:
> >
> > $ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
> > real    0m2.655s
> > user    0m2.677s
> > sys     0m0.095s
> >
> > $ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
> > real    0m0.445s
> > user    0m0.615s
> > sys     0m0.032s
> >
> > The Haskell script was compiled with "ghc --make printMatrixDecay.hs".
> >
> > Could you have a look at the script and give me some pointers as to where
> > I could improve it, both in terms of performance and also generally, as I
> > am very new to Haskell.
> >
> > Thanks already,
> >
> > nick
> >
> >
> > _______________________________________________ Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
Bob Ippolito | 13 Feb 06:16 2013

Re: performance question

On Tuesday, February 12, 2013, wrote:

On Tue, 12 Feb 2013 15:57:37 -0700
Nicolas Bock <nicolasbock <at> gmail.com> wrote:

> >  Here is haskell version that is faster than python, almost as fast as c++.
> > You need to install bytestring-lexing package for readDouble.


I was hoping Branimir could comment on how the improvements were allocated.

how much is due to text.regex.pcre (which looks to be a wrapper to libpcre) ?

how much can be attributed to using data.bytestring ?

you have to admit, it's amazing how well a byte-compiled, _dynamically typed_ interpreter can do against an actualy native code compiler.  Can't regex be done effectively in haskell ?  Is it something that can't be done, or is it just such minimal effort to link to pcre that it's not worth the trouble ?

I think that there are two bottlenecks: the regex engine, and converting a bytestring to a double. There doesn't appear to be a fast and accurate strtod implementation for Haskell, and the faster regex implementations that I could find appear to be unmaintained. 
 


Brian

> > import Text.Regex.PCRE
> > import Data.Maybe
> > import Data.Array.IO
> > import Data.Array.Unboxed
> > import qualified Data.ByteString.Char8 as B
> > import Data.ByteString.Lex.Double (readDouble)
> >
> > strataBounds :: UArray Int Double
> > strataBounds = listArray (0,10) [ 0.0, 1.0e-8, 1.0e-7, 1.0e-6, 1.0e-5,
> > 1.0e-4, 1.0e-3, 1.0e-2, 1.0e-1, 1.0, 2.0 ]
> >
> > newStrataCounts :: IO(IOUArray Int Int)
> > newStrataCounts = newArray (bounds strataBounds) 0
> >
> > main = do
> >     l <- B.getContents
> >     let a = B.lines l
> >     strataCounts <- newStrataCounts
> >     n <- calculate strataCounts a 0
> >     let
> >         printStrataCounts :: IO ()
> >         printStrataCounts = do
> >             let s = round $ sqrt (fromIntegral n::Double) :: Int
> >             printf "read %d matrix elements (%dx%d = %d)\n" n s s n
> >             printStrataCounts' 0 0
> >         printStrataCounts' :: Int -> Int -> IO ()
> >         printStrataCounts' i total
> >             | i < (snd $ bounds strataBounds) = do
> >                 count <- readArray strataCounts i
> >                 let
> >                     p :: Double
> >                     p = (100.0*(fromIntegral count) ::
> > Double)/(fromIntegral n :: Double)
> >                 printf "[%1.2e, %1.2e) = %i (%1.2f%%) %i\n" (strataBounds
> > ! i) (strataBounds ! (i+1))
> >                                                                 count p
> > (total + count)
> >                 printStrataCounts' (i+1) (total+count)
> >             | otherwise = return ()
> >     printStrataCounts
> >
> > calculate :: IOUArray Int Int -> [B.ByteString] -> Int -> IO Int
> > calculate _ [] n = return n
> > calculate counts (l:ls) n = do
> >     let
> >         a = case getAllTextSubmatches $ l =~ B.pack "matrix.*=
> > ([0-9eE.+-]+)$" :: [B.ByteString] of
> >                 [_,v] -> Just (readDouble v) :: Maybe (Maybe
> > (Double,B.ByteString))
> >                 _ -> Nothing
> >         b = (fst.fromJust.fromJust) a
> >         loop :: Int -> IO()
> >         loop i
> >             | i < (snd $ bounds strataBounds) =
> >                 if (b >= (strataBounds ! i)) && (b < (strataBounds !
> > (i+1)))
> >                 then do
> >                     c <- readArray counts i
> >                     writeArray counts i (c+1)
> >                 else
> >                     loop (i+1)
> >             | otherwise = return ()
> >     if isNothing a
> >         then
> >             calculate counts ls n
> >         else do
> >             loop 0
> >             calculate counts ls (n+1)
> >
> >
> > ------------------------------
> > From: nicolasbock <at> gmail.com
> > Date: Fri, 8 Feb 2013 12:26:09 -0700
> > To: haskell-cafe <at> haskell.org
> > Subject: [Haskell-cafe] performance question
> >
> > Hi list,
> >
> > I wrote a script that reads matrix elements from standard input, parses
> > the input using a regular expression, and then bins the matrix elements by
> > magnitude. I wrote the same script in python (just to be sure :) ) and find
> > that the python version vastly outperforms the Haskell script.
> >
> > To be concrete:
> >
> > $ time ./createMatrixDump.py -N 128 | ./printMatrixDecay
> > real    0m2.655s
> > user    0m2.677s
> > sys     0m0.095s
> >
> > $ time ./createMatrixDump.py -N 128 | ./printMatrixDecay.py -
> > real    0m0.445s
> > user    0m0.615s
> > sys     0m0.032s
> >
> > The Haskell script was compiled with "ghc --make printMatrixDecay.hs".
> >
> > Could you have a look at the script and give me some pointers as to where
> > I could improve it, both in terms of performance and also generally, as I
> > am very new to Haskell.
> >
> > Thanks already,
> >
> > nick
> >
> >
> > _______________________________________________ Haskell-Cafe mailing list
> > Haskell-Cafe <at> haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Branimir Maksimovic | 13 Feb 11:39 2013
Picon

Re: performance question

ByteString gains most improvements as String must be converted o CString
first, internaly, in regex (this is warpper for libpcre), while ByteString not.
libpcre is much faster than posix (I guess posix is also wrapper).
Interface for libpcre is same as for Posix, there is no real effort
in replacing it.

> Date: Tue, 12 Feb 2013 20:32:01 -0800
> From: briand <at> aracnet.com
> To: nicolasbock <at> gmail.com
> CC: bmaxa <at> hotmail.com; bob <at> redivi.com; haskell-cafe <at> haskell.org
> Subject: Re: [Haskell-cafe] performance question
>
> On Tue, 12 Feb 2013 15:57:37 -0700
> Nicolas Bock <nicolasbock <at> gmail.com> wrote:
>
> > > Here is haskell version that is faster than python, almost as fast as c++.
> > > You need to install bytestring-lexing package for readDouble.
>
>
> I was hoping Branimir could comment on how the improvements were allocated.
>
> how much is due to text.regex.pcre (which looks to be a wrapper to libpcre) ?
>
> how much can be attributed to using data.bytestring ?
>
> you have to admit, it's amazing how well a byte-compiled, _dynamically typed_ interpreter can do against an actualy native code compiler. Can't regex be done effectively in haskell ? Is it something that can't be done, or is it just such minimal effort to link to pcre that it's not worth the trouble ?
>
>
> Brian
>

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Brandon Allbery | 13 Feb 16:12 2013
Picon

Re: performance question

On Tue, Feb 12, 2013 at 11:32 PM, <briand <at> aracnet.com> wrote:
actualy native code compiler.  Can't regex be done effectively in haskell ?  Is it something that can't be done, or is it just such minimal effort to link to pcre that it's not worth the trouble ?

PCRE is pretty heavily optimized.  POSIX regex engines generally rely on vendor regex libraries which my not be well optimized; there is a native Haskell implementation as well, but that one runs into a different issue, namely a lack of interest (regexes are often seen as "foreign" to Haskell-think, so there's little interest in making them work well; people who *do* need them for some reason usually punt to pcre).

--
brandon s allbery kf8nh                               sine nomine associates
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicolas Bock | 13 Feb 17:32 2013
Picon

Re: performance question

Since I have very little experience with Haskell and am not used to Haskell-think yet, I don't quite understand your statement that regexes are seen as foreign to Haskell-think. Could you elaborate? What would a more "native" solution look like? From what I have learned so far, it seems to me that Haskell is a lot about clear, concise, and well structured code. I find regexes extremely compact and powerful, allowing for very concise code, which should fit the bill perfectly, or shouldn't it?

Thanks,

nick



On Wed, Feb 13, 2013 at 8:12 AM, Brandon Allbery <allbery.b <at> gmail.com> wrote:
On Tue, Feb 12, 2013 at 11:32 PM, <briand <at> aracnet.com> wrote:
actualy native code compiler.  Can't regex be done effectively in haskell ?  Is it something that can't be done, or is it just such minimal effort to link to pcre that it's not worth the trouble ?

PCRE is pretty heavily optimized.  POSIX regex engines generally rely on vendor regex libraries which my not be well optimized; there is a native Haskell implementation as well, but that one runs into a different issue, namely a lack of interest (regexes are often seen as "foreign" to Haskell-think, so there's little interest in making them work well; people who *do* need them for some reason usually punt to pcre).

--
brandon s allbery kf8nh                               sine nomine associates
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
David Thomas | 13 Feb 17:39 2013
Picon

Re: performance question

One way in which regexps are "foreign to Haskell-think" is that, if they break, they generally break at run-time.  This could be ameliorated with template haskell, but a substantial portion of Haskell coders find that a smell itself.


On Wed, Feb 13, 2013 at 8:32 AM, Nicolas Bock <nicolasbock <at> gmail.com> wrote:
Since I have very little experience with Haskell and am not used to Haskell-think yet, I don't quite understand your statement that regexes are seen as foreign to Haskell-think. Could you elaborate? What would a more "native" solution look like? From what I have learned so far, it seems to me that Haskell is a lot about clear, concise, and well structured code. I find regexes extremely compact and powerful, allowing for very concise code, which should fit the bill perfectly, or shouldn't it?

Thanks,

nick



On Wed, Feb 13, 2013 at 8:12 AM, Brandon Allbery <allbery.b <at> gmail.com> wrote:
On Tue, Feb 12, 2013 at 11:32 PM, <briand <at> aracnet.com> wrote:
actualy native code compiler.  Can't regex be done effectively in haskell ?  Is it something that can't be done, or is it just such minimal effort to link to pcre that it's not worth the trouble ?

PCRE is pretty heavily optimized.  POSIX regex engines generally rely on vendor regex libraries which my not be well optimized; there is a native Haskell implementation as well, but that one runs into a different issue, namely a lack of interest (regexes are often seen as "foreign" to Haskell-think, so there's little interest in making them work well; people who *do* need them for some reason usually punt to pcre).

--
brandon s allbery kf8nh                               sine nomine associates
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Nicolas Trangez | 13 Feb 17:43 2013

Re: performance question

On Wed, 2013-02-13 at 08:39 -0800, David Thomas wrote:
> One way in which regexps are "foreign to Haskell-think" is that, if
> they
> break, they generally break at run-time.  This could be ameliorated
> with
> template haskell

Care to elaborate on the "ameliorate using TH" part? I figure regexes
would be mostly used to parse some runtime-provided string, so how could
compile-TH provide any help?

Nicolas
MigMit | 13 Feb 18:34 2013
Picon

Re: performance question

Well, this runtime errors are actually type errors. Regexps are actually a DSL, which is not embedded in
Haskell. But it could be. Strings won't work for that, but something like that would:

filter (match $ "a" <> many anyChar <> ".txt") filenames

and this certainly can be produced by TH like that:

filter (match $(regexp "a.*\\.txt")) filenames

On Feb 13, 2013, at 8:43 PM, Nicolas Trangez <nicolas <at> incubaid.com> wrote:

> On Wed, 2013-02-13 at 08:39 -0800, David Thomas wrote:
>> One way in which regexps are "foreign to Haskell-think" is that, if
>> they
>> break, they generally break at run-time.  This could be ameliorated
>> with
>> template haskell
> 
> Care to elaborate on the "ameliorate using TH" part? I figure regexes
> would be mostly used to parse some runtime-provided string, so how could
> compile-TH provide any help?
> 
> Nicolas
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
David Thomas | 13 Feb 18:43 2013
Picon

Re: performance question

I don't think you can do much about "fails to match the input string" - indeed, that's often desired behavior...  and "matches the wrong thing" you can only catch with testing.

The simplest place template haskell could help with is when the expression isn't a valid expression in the first place, and will fail to compile.  If you're just validating, I don't think you can do better; in order to improve your confidence of correctness, your only option is testing against a set of positives and negatives.

If you're capturing, you might be able to do a little better, if you are able to get some of that info into the types (number of capture groups expected, for instance) - then, if your code expects to deal with a different number of captured pieces than your pattern represents, it can be caught at compile time.

If you're capturing strings that you intend to convert to other types, and can decorate regexp components with the type they're going to capture (which can then be quickchecked - certainly a pattern should never match and then fail to read, &c), and if you are able to propagate this info during composition, you might actually be able to catch a good chunk of errors.

Note that much of this works quite a bit different than most existing regexp library APIs, where you pass a bare string and captures wind up in some kind of list, which I expect is much of the reason no one's done it yet (so far as I'm aware).


On Wed, Feb 13, 2013 at 8:43 AM, Nicolas Trangez <nicolas <at> incubaid.com> wrote:
On Wed, 2013-02-13 at 08:39 -0800, David Thomas wrote:
> One way in which regexps are "foreign to Haskell-think" is that, if
> they
> break, they generally break at run-time.  This could be ameliorated
> with
> template haskell

Care to elaborate on the "ameliorate using TH" part? I figure regexes
would be mostly used to parse some runtime-provided string, so how could
compile-TH provide any help?

Nicolas



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
David Thomas | 13 Feb 18:46 2013
Picon

Re: performance question

The fact that parsec and attoparsec exist and can be pressed into service with reasonable performance (I think?) on tasks for which regexps are suitable is probably another big part of the reason no one's done it yet.  I expect much of the plumbing would wind up looking a lot like those, actually.


On Wed, Feb 13, 2013 at 9:43 AM, David Thomas <davidleothomas <at> gmail.com> wrote:
I don't think you can do much about "fails to match the input string" - indeed, that's often desired behavior...  and "matches the wrong thing" you can only catch with testing.

The simplest place template haskell could help with is when the expression isn't a valid expression in the first place, and will fail to compile.  If you're just validating, I don't think you can do better; in order to improve your confidence of correctness, your only option is testing against a set of positives and negatives.

If you're capturing, you might be able to do a little better, if you are able to get some of that info into the types (number of capture groups expected, for instance) - then, if your code expects to deal with a different number of captured pieces than your pattern represents, it can be caught at compile time.

If you're capturing strings that you intend to convert to other types, and can decorate regexp components with the type they're going to capture (which can then be quickchecked - certainly a pattern should never match and then fail to read, &c), and if you are able to propagate this info during composition, you might actually be able to catch a good chunk of errors.

Note that much of this works quite a bit different than most existing regexp library APIs, where you pass a bare string and captures wind up in some kind of list, which I expect is much of the reason no one's done it yet (so far as I'm aware).


On Wed, Feb 13, 2013 at 8:43 AM, Nicolas Trangez <nicolas <at> incubaid.com> wrote:
On Wed, 2013-02-13 at 08:39 -0800, David Thomas wrote:
> One way in which regexps are "foreign to Haskell-think" is that, if
> they
> break, they generally break at run-time.  This could be ameliorated
> with
> template haskell

Care to elaborate on the "ameliorate using TH" part? I figure regexes
would be mostly used to parse some runtime-provided string, so how could
compile-TH provide any help?

Nicolas



_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Brandon Allbery | 13 Feb 19:17 2013
Picon

Re: performance question

On Wed, Feb 13, 2013 at 12:46 PM, David Thomas <davidleothomas <at> gmail.com> wrote:
The fact that parsec and attoparsec exist and can be pressed into service with reasonable performance (I think?) on tasks for which regexps are suitable is probably another big part of the reason no one's done it yet.  I expect much of the plumbing would wind up looking a lot like those, actually.

When I started out with Haskell, one of my early thoughts was about designing a DSL for Icon-style pattern matching; I dropped it when I realized I was reinventing (almost identically, at least for its lower level combinators) Parsec.  Nothing really to be gained except from a tutelary standpoint.  And the mapping from Icon patterns to regex patterns is pretty much mechanical if you phrase it so you aren't executing code in the middle.
 
--
brandon s allbery kf8nh                               sine nomine associates
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Brandon Allbery | 13 Feb 18:41 2013
Picon

Re: performance question

On Wed, Feb 13, 2013 at 11:32 AM, Nicolas Bock <nicolasbock <at> gmail.com> wrote:
Since I have very little experience with Haskell and am not used to Haskell-think yet, I don't quite understand your statement that regexes are seen as foreign to Haskell-think. Could you elaborate? What would a more "native" solution look like? From what I have learned so far, it seems to me that Haskell is a lot about clear,

The native solution is a parser like parsec/attoparsec.  The problem with regexes is that you can't at compile time verify that, for example, you have as many matching groups in the regex as the code using it expects, nor does an optional matching group behave as a Maybe like it should; nor are there nice ways to recover.  A parser gives you full control and better compile time checking, and is generally recommended.

--
brandon s allbery kf8nh                               sine nomine associates
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Aleksey Khudyakov | 13 Feb 22:24 2013
Picon

Re: performance question

On 13.02.2013 21:41, Brandon Allbery wrote:
> On Wed, Feb 13, 2013 at 11:32 AM, Nicolas Bock <nicolasbock <at> gmail.com
> <mailto:nicolasbock <at> gmail.com>> wrote:
>
>     Since I have very little experience with Haskell and am not used to
>     Haskell-think yet, I don't quite understand your statement that
>     regexes are seen as foreign to Haskell-think. Could you elaborate?
>     What would a more "native" solution look like? From what I have
>     learned so far, it seems to me that Haskell is a lot about clear,
>
>
> The native solution is a parser like parsec/attoparsec.  The problem
> with regexes is that you can't at compile time verify that, for example,
> you have as many matching groups in the regex as the code using it
> expects, nor does an optional matching group behave as a Maybe like it
> should; nor are there nice ways to recover.  A parser gives you full
> control and better compile time checking, and is generally recommended.
>
Regexps only have this problem if they are compiled from string. Nothing 
prevents from building them using combinators. regex-applicaitve[1] uses 
this approach and quite nice to use.

[1] http://hackage.haskell.org/package/regex-applicative
ok | 13 Feb 23:45 2013
Picon

Re: performance question

> On 13.02.2013 21:41, Brandon Allbery wrote:
>> The native solution is a parser like parsec/attoparsec.

"Aleksey Khudyakov" <alexey.skladnoy <at> gmail.com> replied

> Regexps only have this problem if they are compiled from string. Nothing
> prevents from building them using combinators. regex-applicative[1] uses
> this approach and quite nice to use.
>
> [1] http://hackage.haskell.org/package/regex-applicative

That _is_ a nice package, but
  it _is_ 'a parser like parsec/attoparsec'.
Brandon Allbery | 14 Feb 00:09 2013
Picon

Re: performance question

On Wed, Feb 13, 2013 at 5:45 PM, <ok <at> cs.otago.ac.nz> wrote:
> On 13.02.2013 21:41, Brandon Allbery wrote:
>> The native solution is a parser like parsec/attoparsec.

"Aleksey Khudyakov" <alexey.skladnoy <at> gmail.com> replied

> Regexps only have this problem if they are compiled from string. Nothing
> prevents from building them using combinators. regex-applicative[1] uses
> this approach and quite nice to use.
>
> [1] http://hackage.haskell.org/package/regex-applicative

That _is_ a nice package, but
  it _is_ 'a parser like parsec/attoparsec'.

Well, yes; it's a case in point.
 
--
brandon s allbery kf8nh                               sine nomine associates
allbery.b <at> gmail.com                                  ballbery <at> sinenomine.net
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
wren ng thornton | 14 Feb 05:18 2013

Re: performance question

On 2/13/13 11:32 AM, Nicolas Bock wrote:
> Since I have very little experience with Haskell and am not used to
> Haskell-think yet, I don't quite understand your statement that regexes are
> seen as foreign to Haskell-think. Could you elaborate? What would a more
> "native" solution look like? From what I have learned so far, it seems to
> me that Haskell is a lot about clear, concise, and well structured code. I
> find regexes extremely compact and powerful, allowing for very concise
> code, which should fit the bill perfectly, or shouldn't it?

Regexes are powerful and concise for recognizing regular languages. They 
are not, however, very good for *parsing* regular languages; nor can 
they handle non-regular languages (unless you're relying on the badness 
of pcre). In other languages people press regexes into service for 
parsing because the alternative is using an external DSL like lex/yacc, 
javaCC, etc. Whereas, in Haskell, we have powerful and concise tools for 
parsing context-free languages and beyond (e.g., parsec, attoparsec).

--

-- 
Live well,
~wren
Erik de Castro Lopo | 14 Feb 05:50 2013

Re: performance question

wren ng thornton wrote:

> Regexes are powerful and concise for recognizing regular languages. They 
> are not, however, very good for *parsing* regular languages; nor can 
> they handle non-regular languages (unless you're relying on the badness 
> of pcre). In other languages people press regexes into service for 
> parsing because the alternative is using an external DSL like lex/yacc, 
> javaCC, etc. Whereas, in Haskell, we have powerful and concise tools for 
> parsing context-free languages and beyond (e.g., parsec, attoparsec).

This cannot be emphasized heavily enough.

Once you have learnt how to use one or more of these parsec libraries they
will become your main tool for parsing everything from complex input languages
like haskell itself, all the way down to relatively simple config files.

Parsec style parsers are built up out of small composable (and more
importantly reusable) combinators, that are easier to read and easier
to maintain than anything other than the most trivial regex.

Erik
--

-- 
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/
Nicolas Bock | 14 Feb 19:59 2013
Picon

Re: performance question

I have to agree that reading and maintaining regular expressions can be challenging :)


On Wed, Feb 13, 2013 at 9:50 PM, Erik de Castro Lopo <mle+hs <at> mega-nerd.com> wrote:
wren ng thornton wrote:

> Regexes are powerful and concise for recognizing regular languages. They
> are not, however, very good for *parsing* regular languages; nor can
> they handle non-regular languages (unless you're relying on the badness
> of pcre). In other languages people press regexes into service for
> parsing because the alternative is using an external DSL like lex/yacc,
> javaCC, etc. Whereas, in Haskell, we have powerful and concise tools for
> parsing context-free languages and beyond (e.g., parsec, attoparsec).

This cannot be emphasized heavily enough.

Once you have learnt how to use one or more of these parsec libraries they
will become your main tool for parsing everything from complex input languages
like haskell itself, all the way down to relatively simple config files.

Parsec style parsers are built up out of small composable (and more
importantly reusable) combinators, that are easier to read and easier
to maintain than anything other than the most trivial regex.

Erik
--
----------------------------------------------------------------------
Erik de Castro Lopo
http://www.mega-nerd.com/

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Richard A. O'Keefe | 14 Feb 23:43 2013
Picon

Re: performance question

Just to play devil's advocate:
  100% agreed that there are better things to do in Haskell _source code_ than regexps.
  The thing about regexps is that they can be accepted at run time as _data_.
  This means, for example, that they can be put in whatever you use for localisation.
  See for example YESEXPR/NOEXPR in <langinfo.h>
wren ng thornton | 15 Feb 00:07 2013

Re: performance question

On 2/13/13 11:18 PM, wren ng thornton wrote:
> On 2/13/13 11:32 AM, Nicolas Bock wrote:
>> Since I have very little experience with Haskell and am not used to
>> Haskell-think yet, I don't quite understand your statement that
>> regexes are
>> seen as foreign to Haskell-think. Could you elaborate? What would a more
>> "native" solution look like? From what I have learned so far, it seems to
>> me that Haskell is a lot about clear, concise, and well structured
>> code. I
>> find regexes extremely compact and powerful, allowing for very concise
>> code, which should fit the bill perfectly, or shouldn't it?
>
> Regexes are powerful and concise for recognizing regular languages. They
> are not, however, very good for *parsing* regular languages; nor can
> they handle non-regular languages (unless you're relying on the badness
> of pcre). In other languages people press regexes into service for
> parsing because the alternative is using an external DSL like lex/yacc,
> javaCC, etc. Whereas, in Haskell, we have powerful and concise tools for
> parsing context-free languages and beyond (e.g., parsec, attoparsec).

Just to be clear, the problem isn't that proper regexes are only good 
for regular languages (many files have regular syntax afterall). The 
problem is that regexes are only good for recognition. They're an 
excellent tool for deciding whether a given string is "good" or "bad"; 
but they're completely unsuitable for the task of parsing/interpreting a 
string into some structure or semantic response. If you've ever used 
tools like yacc or javaCC, one of the crucial things they offer is the 
ability to add these semantic responses. Parser combinator libraries in 
Haskell are similar, since the string processing is integrated into a 
programming language so we can say things like:

     myParser = do
         x <- blah
         guard (p x)
         y <- blargh
         return (f x y)

where p and f can be an arbitrary Haskell functions. Perl extends on 
regular expressions to try and do things like this, but it's extremely 
baroque, hard to get right, and impossible to maintain. (N.B., I was 
raised on Perl and still love it.) And at some point we have to call 
into question the idea of regexes as an embedded DSL when we then turn 
around and try to have Perl be a DSL embedded into the regex language.

One of the big things that makes regexes so nice is that they identify 
crucial combinators like choice and repetition. However, once those 
combinators have been identified, we can just offer them directly as 
functions in the host language. No need for a special DSL or special 
syntax. The big trick is doing this efficiently. Parser combinators were 
an academic curiosity for a long time until Parsec came around and made 
them efficient. And we've come a long way since then: with things like 
attoparsec, PEG parsing, and non-monadic applicative parsers (which can 
perform more optimizations because they can identify the structure of 
the grammar).

The theory of regular expressions is indeed beautiful and elegant. 
However, it's a theory of recognition, not a theory of parsing; and 
that's a crucial distinction. Haskell is about clear, concise, and 
well-structured code; but to be clear, concise, and well-structured we 
have to choose the right tool for the job.

--

-- 
Live well,
~wren
David Thomas | 15 Feb 00:27 2013
Picon

Re: performance question

(I'll be brief because my head is hurting, but please don't interpret that as an intent to offend)

A few points:

1) Capture groups are all you need to do some meaningful interpretation of data; these were around long before perl.

2) Yacc is typically used in conjunction with lex, partly for (a) efficiency and partly for (b) ease of use (compared to writing out [a-z] as production rules).

3) I've actually used lex without yacc (well, flex without bison) when faced with dealing with a language that's regular (and easy enough to express that way - cf. an enormous finite subset of a context-free language).


2b is mostly irrelevant in Haskell, as Parsec already provides functions that can easily match the same things a regexp would.

2a, if it stands up to testing, is the best argument for ripping things apart in Haskell using a DFA.  Parsec and cousins are efficient, but it's hard to beat a single table lookup per character.  The questions are 1) is the difference enough to matter in many cases, and 2) is there a way to get this out of parsec without touching regexps?  (It's not impossible that parsec already recognizes when a language is regular, although I'd be weakly surprised).





On Thu, Feb 14, 2013 at 3:07 PM, wren ng thornton <wren <at> freegeek.org> wrote:
On 2/13/13 11:18 PM, wren ng thornton wrote:
On 2/13/13 11:32 AM, Nicolas Bock wrote:
Since I have very little experience with Haskell and am not used to
Haskell-think yet, I don't quite understand your statement that
regexes are
seen as foreign to Haskell-think. Could you elaborate? What would a more
"native" solution look like? From what I have learned so far, it seems to
me that Haskell is a lot about clear, concise, and well structured
code. I
find regexes extremely compact and powerful, allowing for very concise
code, which should fit the bill perfectly, or shouldn't it?

Regexes are powerful and concise for recognizing regular languages. They
are not, however, very good for *parsing* regular languages; nor can
they handle non-regular languages (unless you're relying on the badness
of pcre). In other languages people press regexes into service for
parsing because the alternative is using an external DSL like lex/yacc,
javaCC, etc. Whereas, in Haskell, we have powerful and concise tools for
parsing context-free languages and beyond (e.g., parsec, attoparsec).


Just to be clear, the problem isn't that proper regexes are only good for regular languages (many files have regular syntax afterall). The problem is that regexes are only good for recognition. They're an excellent tool for deciding whether a given string is "good" or "bad"; but they're completely unsuitable for the task of parsing/interpreting a string into some structure or semantic response. If you've ever used tools like yacc or javaCC, one of the crucial things they offer is the ability to add these semantic responses. Parser combinator libraries in Haskell are similar, since the string processing is integrated into a programming language so we can say things like:

    myParser = do
        x <- blah
        guard (p x)
        y <- blargh
        return (f x y)

where p and f can be an arbitrary Haskell functions. Perl extends on regular expressions to try and do things like this, but it's extremely baroque, hard to get right, and impossible to maintain. (N.B., I was raised on Perl and still love it.) And at some point we have to call into question the idea of regexes as an embedded DSL when we then turn around and try to have Perl be a DSL embedded into the regex language.

One of the big things that makes regexes so nice is that they identify crucial combinators like choice and repetition. However, once those combinators have been identified, we can just offer them directly as functions in the host language. No need for a special DSL or special syntax. The big trick is doing this efficiently. Parser combinators were an academic curiosity for a long time until Parsec came around and made them efficient. And we've come a long way since then: with things like attoparsec, PEG parsing, and non-monadic applicative parsers (which can perform more optimizations because they can identify the structure of the grammar).

The theory of regular expressions is indeed beautiful and elegant. However, it's a theory of recognition, not a theory of parsing; and that's a crucial distinction. Haskell is about clear, concise, and well-structured code; but to be clear, concise, and well-structured we have to choose the right tool for the job.


--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
brandon s allbery kf8nh | 15 Feb 00:33 2013
Picon

Re: performance question

It's worth remembering that the main gain from lex/yacc had originally to do with making the generated programs fit into 64K address space on a PDP11 more than with any direct performance efficiency.

-- 
brandon s allbery kf8nh
Sent with Sparrow

On Thursday, February 14, 2013 at 6:27 PM, David Thomas wrote:

(I'll be brief because my head is hurting, but please don't interpret that as an intent to offend)

A few points:

1) Capture groups are all you need to do some meaningful interpretation of data; these were around long before perl.

2) Yacc is typically used in conjunction with lex, partly for (a) efficiency and partly for (b) ease of use (compared to writing out [a-z] as production rules).

3) I've actually used lex without yacc (well, flex without bison) when faced with dealing with a language that's regular (and easy enough to express that way - cf. an enormous finite subset of a context-free language).


2b is mostly irrelevant in Haskell, as Parsec already provides functions that can easily match the same things a regexp would.

2a, if it stands up to testing, is the best argument for ripping things apart in Haskell using a DFA.  Parsec and cousins are efficient, but it's hard to beat a single table lookup per character.  The questions are 1) is the difference enough to matter in many cases, and 2) is there a way to get this out of parsec without touching regexps?  (It's not impossible that parsec already recognizes when a language is regular, although I'd be weakly surprised).





On Thu, Feb 14, 2013 at 3:07 PM, wren ng thornton <wren <at> freegeek.org> wrote:
On 2/13/13 11:18 PM, wren ng thornton wrote:
On 2/13/13 11:32 AM, Nicolas Bock wrote:
Since I have very little experience with Haskell and am not used to
Haskell-think yet, I don't quite understand your statement that
regexes are
seen as foreign to Haskell-think. Could you elaborate? What would a more
"native" solution look like? From what I have learned so far, it seems to
me that Haskell is a lot about clear, concise, and well structured
code. I
find regexes extremely compact and powerful, allowing for very concise
code, which should fit the bill perfectly, or shouldn't it?

Regexes are powerful and concise for recognizing regular languages. They
are not, however, very good for *parsing* regular languages; nor can
they handle non-regular languages (unless you're relying on the badness
of pcre). In other languages people press regexes into service for
parsing because the alternative is using an external DSL like lex/yacc,
javaCC, etc. Whereas, in Haskell, we have powerful and concise tools for
parsing context-free languages and beyond (e.g., parsec, attoparsec).


Just to be clear, the problem isn't that proper regexes are only good for regular languages (many files have regular syntax afterall). The problem is that regexes are only good for recognition. They're an excellent tool for deciding whether a given string is "good" or "bad"; but they're completely unsuitable for the task of parsing/interpreting a string into some structure or semantic response. If you've ever used tools like yacc or javaCC, one of the crucial things they offer is the ability to add these semantic responses. Parser combinator libraries in Haskell are similar, since the string processing is integrated into a programming language so we can say things like:

    myParser = do
        x <- blah
        guard (p x)
        y <- blargh
        return (f x y)

where p and f can be an arbitrary Haskell functions. Perl extends on regular expressions to try and do things like this, but it's extremely baroque, hard to get right, and impossible to maintain. (N.B., I was raised on Perl and still love it.) And at some point we have to call into question the idea of regexes as an embedded DSL when we then turn around and try to have Perl be a DSL embedded into the regex language.

One of the big things that makes regexes so nice is that they identify crucial combinators like choice and repetition. However, once those combinators have been identified, we can just offer them directly as functions in the host language. No need for a special DSL or special syntax. The big trick is doing this efficiently. Parser combinators were an academic curiosity for a long time until Parsec came around and made them efficient. And we've come a long way since then: with things like attoparsec, PEG parsing, and non-monadic applicative parsers (which can perform more optimizations because they can identify the structure of the grammar).

The theory of regular expressions is indeed beautiful and elegant. However, it's a theory of recognition, not a theory of parsing; and that's a crucial distinction. Haskell is about clear, concise, and well-structured code; but to be clear, concise, and well-structured we have to choose the right tool for the job.


--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
haskell | 26 Feb 11:07 2009
Picon

Re: Performance question

>> But you can remove sqrt from the C++ implementation as well, so it only
>> improves the relative performance if the C++ implementation of sqrt is
>> worse than its Haskell counterpart.
>
>Oops, of course I mean, you only improve if Haskell's implementation is
>worse than C++'s implementation :)

Actually i intend to compare real life performance of comparable algorithms. If sqrt is a problem in
GHC/Haskell then this would be a valuable result. I want to know about these problems and not work around
them at this point.

Thanks,
lenny
haskell | 26 Feb 11:27 2009
Picon

Re: Performance question

Hi,

thanks for your input.

>You can get reasonable numeric performance out of GHC, but you need to  
>work at it. There is some advice in the GHC manual at 
>http://www.haskell.org/ghc/docs/latest/html/users_guide/faster.html 

I am using -O2 and strictness already.
Currently i can only imagine to define a data type in order to use unboxed Ints instead of the accumulator tuple.

The thing is that i don't see in the profile output yet what to improve.
There are some allocations going on in "main", but i don't know what causes it.

>The first thing I would do is replace your
>isInCircle :: (Floating a, Ord a)  => (a,a) -> Bool
>with
>isInCircle :: (Double, Double) -> Bool

Can you point me to why that matters?

>
>Ben.
>
>
>
>On 26/02/2009, at 8:53 PM, haskell <at> kudling.de wrote:
>
>> Hi,
>>
>> i have compared a C++ implementation with a Haskell implementation  
>> of the Monte Carlo Pi approximation:
>>
>> http://lennart.kudling.de/haskellPi/
>>
>> The Haskell version is 100 times slower and i wonder whether i do  
>> something obvious wrong.
>>
>> Profiling says that the majority of the time is spend in "main". But  
>> i have no idea where.
>>
>> Can someone give me a hint?
>>
>> Thanks,
>> Lenny
>>
>>
>
Ben Lippmeier | 26 Feb 11:44 2009
Picon
Picon

Re: Performance question


On 26/02/2009, at 9:27 PM, haskell <at> kudling.de wrote:
>
> Currently i can only imagine to define a data type in order to use  
> unboxed Ints instead of the accumulator tuple.

That would probably help a lot. It would also help to use two separate  
Double# parameters instead of the tuple.

> The thing is that i don't see in the profile output yet what to  
> improve.
> There are some allocations going on in "main", but i don't know what  
> causes it.
>
>> The first thing I would do is replace your
>> isInCircle :: (Floating a, Ord a)  => (a,a) -> Bool
>> with
>> isInCircle :: (Double, Double) -> Bool
>
> Can you point me to why that matters?

At the machine level, GHC treats the (Floating a, Ord a) as an extra  
argument to the function. This argument holds function pointers that  
tell it how to perform multiplication and <= for the unknown type 'a'.  
If you use Double instead of 'a', then it's more likely to use the  
actual machine op.

Ben.
Sittampalam, Ganesh | 26 Feb 11:46 2009

RE: Performance question

Ben Lippmeier wrote:

>>> The first thing I would do is replace your isInCircle :: (Floating
>>> a, Ord a)  => (a,a) -> Bool with isInCircle :: (Double, Double) ->
>>> Bool 
>> 
>> Can you point me to why that matters?
> 
> At the machine level, GHC treats the (Floating a, Ord a) as an extra
> argument to the function. This argument holds function pointers that
> tell it how to perform multiplication and <= for the unknown type
> 'a'. If you use Double instead of 'a', then it's more likely to use
> the actual machine op.   

I'd recommend use of a SPECIALIZE pragma instead of rewriting the code
itself:

http://www.haskell.org/ghc/docs/latest/html/users_guide/pragmas.html
(section 8.13.8)

Ganesh

=============================================================================== 
 Please access the attached hyperlink for an important electronic communications disclaimer: 
 http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html 
 =============================================================================== 
Eugene Kirpichov | 26 Feb 11:56 2009
Picon

Re: Performance question

Here is a variant that uses mersenne-random-pure64 and works less than
2x slower than C++:

 - You don't need to compute samples count an extra time
 - You don't need to assemble double pairs from a list
 - Notice the strictness in randomDoublePairs: it doubled performance

{-# LANGUAGE BangPatterns #-}

import System.Random.Mersenne.Pure64
import System( getArgs )
import Data.List( foldl' )

isInCircle :: (Double,Double) -> Bool
isInCircle (!x,!y) = sqrt (x*x + y*y) <= 1.0

accumulateHit :: Int -> (Double,Double) -> Int
accumulateHit !hits pair = if isInCircle pair then hits + 1 else hits

monteCarloPi :: Int -> [(Double,Double)] -> Double
monteCarloPi n xs = 4.0 * fromIntegral hits / fromIntegral n
    where hits = foldl' accumulateHit 0 . take n $ xs

randomDoublePairs g = let
    !(!x,!g') = randomDouble g
    !(!y,!g'') = randomDouble g'
    in (x,y):randomDoublePairs g''

main = do
    samples       <- (read . head) `fmap` getArgs
    randomNumbers <- randomDoublePairs `fmap` newPureMT
    putStrLn . show $ monteCarloPi samples randomNumbers

jkff <at> *****:~/montecarlo$ time ./mc-hs 10000000
3.1417088

real    0m1.141s
user    0m1.140s
sys     0m0.000s
jkff <at> *****:~/montecarlo$ time ./mc 10000000
10000000
3.14113

real    0m0.693s
user    0m0.690s
sys     0m0.000s

2009/2/26 Ben Lippmeier <Ben.Lippmeier <at> anu.edu.au>:
>
> On 26/02/2009, at 9:27 PM, haskell <at> kudling.de wrote:
>>
>> Currently i can only imagine to define a data type in order to use unboxed
>> Ints instead of the accumulator tuple.
>
> That would probably help a lot. It would also help to use two separate
> Double# parameters instead of the tuple.
>
>> The thing is that i don't see in the profile output yet what to improve.
>> There are some allocations going on in "main", but i don't know what
>> causes it.
>>
>>> The first thing I would do is replace your
>>> isInCircle :: (Floating a, Ord a)  => (a,a) -> Bool
>>> with
>>> isInCircle :: (Double, Double) -> Bool
>>
>> Can you point me to why that matters?
>
> At the machine level, GHC treats the (Floating a, Ord a) as an extra
> argument to the function. This argument holds function pointers that tell it
> how to perform multiplication and <= for the unknown type 'a'. If you use
> Double instead of 'a', then it's more likely to use the actual machine op.
>
> Ben.
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

--

-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru
Felipe Lessa | 26 Feb 12:37 2009
Picon

Re: Performance question

On Thu, Feb 26, 2009 at 7:56 AM, Eugene Kirpichov <ekirpichov <at> gmail.com> wrote:
> Here is a variant that uses mersenne-random-pure64 and works less than
> 2x slower than C++:

And I would like to notice that rand() is incredibly dumber than the
Mersenne twister, so probably if we took rand()'s code from glibc and
rewrote it in Haskell, there would be another performance increase.

--

-- 
Felipe.
Lennart Augustsson | 26 Feb 13:01 2009
Picon

Re: Performance question

C's rand() function is very bad and should never be used really.

On Thu, Feb 26, 2009 at 11:37 AM, Felipe Lessa <felipe.lessa <at> gmail.com> wrote:
> On Thu, Feb 26, 2009 at 7:56 AM, Eugene Kirpichov <ekirpichov <at> gmail.com> wrote:
>> Here is a variant that uses mersenne-random-pure64 and works less than
>> 2x slower than C++:
>
> And I would like to notice that rand() is incredibly dumber than the
> Mersenne twister, so probably if we took rand()'s code from glibc and
> rewrote it in Haskell, there would be another performance increase.
>
> --
> Felipe.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Ketil Malde | 27 Feb 07:50 2009

Re: Performance question

Lennart Augustsson <lennart <at> augustsson.net> writes:

> C's rand() function is very bad and should never be used really.

On Linux (really GNU libc, I suppose) it is the same as random().  But
for portability, one is encouraged to spend the two extra letters.  I
don't understand the details, but I think the Mersenne twister is much
better in any case.  

-k
--

-- 
If I haven't seen further, it is by standing in the footprints of giants
Lennart Augustsson | 27 Feb 11:08 2009
Picon

Re: Performance question

The random() function is only marginally better than rand().

On Fri, Feb 27, 2009 at 6:50 AM, Ketil Malde <ketil <at> malde.org> wrote:
> Lennart Augustsson <lennart <at> augustsson.net> writes:
>
>> C's rand() function is very bad and should never be used really.
>
> On Linux (really GNU libc, I suppose) it is the same as random().  But
> for portability, one is encouraged to spend the two extra letters.  I
> don't understand the details, but I think the Mersenne twister is much
> better in any case.
>
> -k
> --
> If I haven't seen further, it is by standing in the footprints of giants
>
Brandon S. Allbery KF8NH | 28 Feb 22:01 2009
Picon

Re: Performance question

On 2009 Feb 27, at 1:50, Ketil Malde wrote:
> Lennart Augustsson <lennart <at> augustsson.net> writes:
>> C's rand() function is very bad and should never be used really.
>
> On Linux (really GNU libc, I suppose) it is the same as random().  But
> for portability, one is encouraged to spend the two extra letters.  I
> don't understand the details, but I think the Mersenne twister is much
> better in any case.

Yes, much better than any LC PRNG including rand(), random(), and the  
System V/POSIX lrand48() family.  That said, Linux making rand() ==  
random() breaks portability in the case where you want a repeatable  
stream for testing purposes; as usual, Linux chucks portability out  
the window at any opportunity.  (Sadly, POSIX permits this because of  
POSIX implementations for non-Unix hosts, although it does include a  
fixed-behavior PRNG as documentation for this case.)

--

-- 
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery <at> kf8nh.com
system administrator [openafs,heimdal,too many hats] allbery <at> ece.cmu.edu
electrical and computer engineering, carnegie mellon university    KF8NH

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
David Leimbach | 26 Feb 18:54 2009
Picon

Re: Performance question

How about an FFI call to rand() and then measure the performance

On Thu, Feb 26, 2009 at 3:37 AM, Felipe Lessa <felipe.lessa <at> gmail.com> wrote:
On Thu, Feb 26, 2009 at 7:56 AM, Eugene Kirpichov <ekirpichov <at> gmail.com> wrote:
> Here is a variant that uses mersenne-random-pure64 and works less than
> 2x slower than C++:

And I would like to notice that rand() is incredibly dumber than the
Mersenne twister, so probably if we took rand()'s code from glibc and
rewrote it in Haskell, there would be another performance increase.

--
Felipe.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Don Stewart | 26 Feb 17:23 2009

Re: Performance question

Ben.Lippmeier:
>
> On 26/02/2009, at 9:27 PM, haskell <at> kudling.de wrote:
>>
>> Currently i can only imagine to define a data type in order to use  
>> unboxed Ints instead of the accumulator tuple.
>
> That would probably help a lot. It would also help to use two separate  
> Double# parameters instead of the tuple.

    data T = T !Double !Double

should be enough.
Eugene Kirpichov | 26 Feb 17:28 2009
Picon

Re: Performance question

I looked at the core and the tuples were already unboxed IIRC.

2009/2/26 Don Stewart <dons <at> galois.com>:
> Ben.Lippmeier:
>>
>> On 26/02/2009, at 9:27 PM, haskell <at> kudling.de wrote:
>>>
>>> Currently i can only imagine to define a data type in order to use
>>> unboxed Ints instead of the accumulator tuple.
>>
>> That would probably help a lot. It would also help to use two separate
>> Double# parameters instead of the tuple.
>
>    data T = T !Double !Double
>
> should be enough.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

--

-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru
haskell | 26 Feb 12:11 2009
Picon

Re: Performance question

>accumulateHit because it doesn't need to count to total. That is
>already known.

Well in theory i agree. But somone could feed a non-infite number of doubles. Then the argument "n" would not
necessarily be the same as the number of random number pairs really used.
haskell | 26 Feb 12:33 2009
Picon

Re: Performance question

Do you think it would be feasable to replace the GHC implementation of System.Random with something like System.Random.Mersenne?

>Here is a variant that uses mersenne-random-pure64 and works less than
>2x slower than C++:
>
> - You don't need to compute samples count an extra time
> - You don't need to assemble double pairs from a list
> - Notice the strictness in randomDoublePairs: it doubled performance
>
>{-# LANGUAGE BangPatterns #-}
>
>import System.Random.Mersenne.Pure64
>import System( getArgs )
>import Data.List( foldl' )
>
>isInCircle :: (Double,Double) -> Bool
>isInCircle (!x,!y) = sqrt (x*x + y*y) <= 1.0
>
>accumulateHit :: Int -> (Double,Double) -> Int
>accumulateHit !hits pair = if isInCircle pair then hits + 1 else hits
>
>monteCarloPi :: Int -> [(Double,Double)] -> Double
>monteCarloPi n xs = 4.0 * fromIntegral hits / fromIntegral n
>    where hits = foldl' accumulateHit 0 . take n $ xs
>
>randomDoublePairs g = let
>    !(!x,!g') = randomDouble g
>    !(!y,!g'') = randomDouble g'
>    in (x,y):randomDoublePairs g''
>
>main = do
>    samples       <- (read . head) `fmap` getArgs
>    randomNumbers <- randomDoublePairs `fmap` newPureMT
>    putStrLn . show $ monteCarloPi samples randomNumbers
>
>jkff <at> *****:~/montecarlo$ time ./mc-hs 10000000
>3.1417088
>
>real    0m1.141s
>user    0m1.140s
>sys     0m0.000s
>jkff <at> *****:~/montecarlo$ time ./mc 10000000
>10000000
>3.14113
>
>real    0m0.693s
>user    0m0.690s
>sys     0m0.000s
>
>
>
>2009/2/26 Ben Lippmeier <Ben.Lippmeier <at> anu.edu.au>:
>>
>> On 26/02/2009, at 9:27 PM, haskell <at> kudling.de wrote:
>>>
>>> Currently i can only imagine to define a data type in order to use unboxed
>>> Ints instead of the accumulator tuple.
>>
>> That would probably help a lot. It would also help to use two separate
>> Double# parameters instead of the tuple.
>>
>>> The thing is that i don't see in the profile output yet what to improve.
>>> There are some allocations going on in "main", but i don't know what
>>> causes it.
>>>
>>>> The first thing I would do is replace your
>>>> isInCircle :: (Floating a, Ord a)  => (a,a) -> Bool
>>>> with
>>>> isInCircle :: (Double, Double) -> Bool
>>>
>>> Can you point me to why that matters?
>>
>> At the machine level, GHC treats the (Floating a, Ord a) as an extra
>> argument to the function. This argument holds function pointers that tell 
>it
>> how to perform multiplication and <= for the unknown type 'a'. If you use
>> Double instead of 'a', then it's more likely to use the actual machine op.
>>
>> Ben.
>>
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe <at> haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>
>
>
>
>-- 
>Eugene Kirpichov
>Web IR developer, market.yandex.ru
Eugene Kirpichov | 26 Feb 12:36 2009
Picon

Re: Performance question

I, personally, do, but I think that's more of a question to the GHC people :)

2009/2/26  <haskell <at> kudling.de>:
> Do you think it would be feasable to replace the GHC implementation of System.Random with something like System.Random.Mersenne?
>
>>Here is a variant that uses mersenne-random-pure64 and works less than
>>2x slower than C++:
>>
>> - You don't need to compute samples count an extra time
>> - You don't need to assemble double pairs from a list
>> - Notice the strictness in randomDoublePairs: it doubled performance
>>
>>{-# LANGUAGE BangPatterns #-}
>>
>>import System.Random.Mersenne.Pure64
>>import System( getArgs )
>>import Data.List( foldl' )
>>
>>isInCircle :: (Double,Double) -> Bool
>>isInCircle (!x,!y) = sqrt (x*x + y*y) <= 1.0
>>
>>accumulateHit :: Int -> (Double,Double) -> Int
>>accumulateHit !hits pair = if isInCircle pair then hits + 1 else hits
>>
>>monteCarloPi :: Int -> [(Double,Double)] -> Double
>>monteCarloPi n xs = 4.0 * fromIntegral hits / fromIntegral n
>>    where hits = foldl' accumulateHit 0 . take n $ xs
>>
>>randomDoublePairs g = let
>>    !(!x,!g') = randomDouble g
>>    !(!y,!g'') = randomDouble g'
>>    in (x,y):randomDoublePairs g''
>>
>>main = do
>>    samples       <- (read . head) `fmap` getArgs
>>    randomNumbers <- randomDoublePairs `fmap` newPureMT
>>    putStrLn . show $ monteCarloPi samples randomNumbers
>>
>>jkff <at> *****:~/montecarlo$ time ./mc-hs 10000000
>>3.1417088
>>
>>real    0m1.141s
>>user    0m1.140s
>>sys     0m0.000s
>>jkff <at> *****:~/montecarlo$ time ./mc 10000000
>>10000000
>>3.14113
>>
>>real    0m0.693s
>>user    0m0.690s
>>sys     0m0.000s
>>
>>
>>
>>2009/2/26 Ben Lippmeier <Ben.Lippmeier <at> anu.edu.au>:
>>>
>>> On 26/02/2009, at 9:27 PM, haskell <at> kudling.de wrote:
>>>>
>>>> Currently i can only imagine to define a data type in order to use unboxed
>>>> Ints instead of the accumulator tuple.
>>>
>>> That would probably help a lot. It would also help to use two separate
>>> Double# parameters instead of the tuple.
>>>
>>>> The thing is that i don't see in the profile output yet what to improve.
>>>> There are some allocations going on in "main", but i don't know what
>>>> causes it.
>>>>
>>>>> The first thing I would do is replace your
>>>>> isInCircle :: (Floating a, Ord a)  => (a,a) -> Bool
>>>>> with
>>>>> isInCircle :: (Double, Double) -> Bool
>>>>
>>>> Can you point me to why that matters?
>>>
>>> At the machine level, GHC treats the (Floating a, Ord a) as an extra
>>> argument to the function. This argument holds function pointers that tell
>>it
>>> how to perform multiplication and <= for the unknown type 'a'. If you use
>>> Double instead of 'a', then it's more likely to use the actual machine op.
>>>
>>> Ben.
>>>
>>>
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe <at> haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>
>>
>>
>>
>>--
>>Eugene Kirpichov
>>Web IR developer, market.yandex.ru
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

--

-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru
Bertram Felgenhauer | 26 Feb 13:08 2009

Re: Performance question

haskell <at> kudling.de wrote:
> Do you think it would be feasable to replace the GHC implementation
> of System.Random with something like System.Random.Mersenne?

There's a problem with using the Mersenne Twister: System.Random's
interface has a split method:

class RandomGen g where
   split    :: g -> (g, g)

The Mersenne Twister is good at producing a single stream of random
numbers - in fact it works by generating a whole block of random
numbers in one go, then consuming the block, and only then generating
the next block.

I have no idea how to implement a split method that produces
independent streams. Even if I did, using split a lot would likely
spoil the performance benefit of the generator.

(System.Random.Mersenne.Pure64 provides a RandomGen instance for
PureMT, but it cheats:)

   split = error "System.Random.Mersenne.Pure: unable to split the mersenne twister"

Bertram
Lennart Augustsson | 26 Feb 13:17 2009
Picon

Re: Performance question

You can implement a reasonable split if you can fast-forward the generator.
There's no known method to fast-forward the MT, but other generators
like MRG32k3a can handle it.

  -- Lennart

On Thu, Feb 26, 2009 at 12:08 PM, Bertram Felgenhauer
<bertram.felgenhauer <at> googlemail.com> wrote:
> haskell <at> kudling.de wrote:
>> Do you think it would be feasable to replace the GHC implementation
>> of System.Random with something like System.Random.Mersenne?
>
> There's a problem with using the Mersenne Twister: System.Random's
> interface has a split method:
>
> class RandomGen g where
>   split    :: g -> (g, g)
>
> The Mersenne Twister is good at producing a single stream of random
> numbers - in fact it works by generating a whole block of random
> numbers in one go, then consuming the block, and only then generating
> the next block.
>
> I have no idea how to implement a split method that produces
> independent streams. Even if I did, using split a lot would likely
> spoil the performance benefit of the generator.
>
> (System.Random.Mersenne.Pure64 provides a RandomGen instance for
> PureMT, but it cheats:)
>
>   split = error "System.Random.Mersenne.Pure: unable to split the mersenne twister"
>
> Bertram
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Tracy Wadleigh | 26 Feb 17:02 2009
Picon

Re: Performance question

On Thu, Feb 26, 2009 at 7:17 AM, Lennart Augustsson <lennart <at> augustsson.net> wrote:

You can implement a reasonable split if you can fast-forward the generator.
There's no known method to fast-forward the MT, but other generators
like MRG32k3a can handle it.

Are you aware of any existing (C/C++/Haskell) library implementing this algorithm? A cursory google search didn't turn anything up for me, aside from something implemented in Java, and another in Lisp.

--Tracy
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Felipe Lessa | 26 Feb 17:07 2009
Picon

Re: Performance question

2009/2/26 Tracy Wadleigh <tracy.wadleigh <at> gmail.com>:
> On Thu, Feb 26, 2009 at 7:17 AM, Lennart Augustsson <lennart <at> augustsson.net>
> wrote:
>>
>> You can implement a reasonable split if you can fast-forward the
>> generator.
>> There's no known method to fast-forward the MT, but other generators
>> like MRG32k3a can handle it.
>
> Are you aware of any existing (C/C++/Haskell) library implementing this
> algorithm? A cursory google search didn't turn anything up for me, aside
> from something implemented in Java, and another in Lisp.

Maybe http://www.iro.umontreal.ca/~lecuyer/myftp/streams00/ ?

--

-- 
Felipe.
Tracy Wadleigh | 26 Feb 17:10 2009
Picon

Re: Performance question

Awesome, Felipe. Thanks.

--Tracy

On Thu, Feb 26, 2009 at 11:07 AM, Felipe Lessa <felipe.lessa <at> gmail.com> wrote:
2009/2/26 Tracy Wadleigh <tracy.wadleigh <at> gmail.com>:
> On Thu, Feb 26, 2009 at 7:17 AM, Lennart Augustsson <lennart <at> augustsson.net>
> wrote:
>>
>> You can implement a reasonable split if you can fast-forward the
>> generator.
>> There's no known method to fast-forward the MT, but other generators
>> like MRG32k3a can handle it.
>
> Are you aware of any existing (C/C++/Haskell) library implementing this
> algorithm? A cursory google search didn't turn anything up for me, aside
> from something implemented in Java, and another in Lisp.

Maybe http://www.iro.umontreal.ca/~lecuyer/myftp/streams00/ ?

--
Felipe.

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Stijn De Saeger | 17 Jan 10:47 2005
Picon

performance question

Hello all,

A question on that most elusive of subjects.... performance in haskell (GHC 6.2)
Using the GHC profiler, I obtained the following analysis results (i
hope the code doesn't come out too ugly by mail):

	total time  =        0.92 secs   (46 ticks  <at>  20 ms)
	total alloc =  83,373,032 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

isIn                               Main                  50.0   22.8
getCon                          Main                  13.0   16.7
o'                                  Main                   8.7    6.6
satisfies                        Main                   6.5    0.0
powerList                      Main                   6.5   46.9
CAF                             Main                   6.5    0.1
showCon                      Main                   4.3    0.3
MAIN                           MAIN                   4.3    0.0
a'                                 Main                   0.0    6.7

The problem child, that isIn function, has got about 78000 entries in
the profile log.
I should probably mention that this is an incredibly dumbed down
version of the program, the dimensions of the data it is supposed to
handle are such that, on a trial run I killed the process after about
15 minutes, when I found out it hadn't even completed 3% of its task.
sad stuff, really.

Anyways, 'isIn'  is a predicate that checks whether a given Double
lies within an interval, where intervals are defined as
...
define an interval bound, either inclusive (I) or exclusive (E)
> data Bound = I Double | E Double deriving (Eq, Show, Ord)  
> data Interval = Il Bound Bound | Nil Bound Bound deriving (Eq,Ord)  

where Nil acts as the complement of an interval, this is reflected in
the isIn function.
....
> isIn :: Double -> Interval -> Bool
> isIn r (Nil x y) = not (isIn r (Il x y))
> isIn r (Il (I x) (I y)) = r >= x && r <= y
> isIn r (Il (I x) (E y)) = r >= x && r < y
> isIn r (Il (E x) (I y)) = r > x && r <= y
> isIn r (Il (E x) (E y)) = r > x && r < y 

I tried rewriting it to something that intuitively 'feels' like it
should be faster, but i have no real idea about the cost of the
respective haskell expressions:

... version 2
> isIn :: Double -> Interval -> Bool
> isIn r (Nil x y) = not (isIn r (Il x y))
> isIn r (Il x y) = case x of 
>   (I x') -> if r >= x' then case y of 
>        (I y') -> r <= y'
>        (E y') -> r < y'
>	      else False	     
>   (E x') -> if r > x' then case y of 
>        (I y') -> r <= y'
>	 (E y') -> r < y'
>	      else False 

... which indeed turns out to be a tad bit faster, according to the
new profile log.

	total time  =        0.80 secs   (40 ticks  <at>  20 ms)
	total alloc =  64,404,104 bytes  (excludes profiling overheads)

COST CENTRE                    MODULE               %time %alloc

isIn                           Main                  30.0    0.0
getCon                      Main                  25.0   21.6
powerList                   Main                  15.0   60.7
showCon                    Main                   7.5    0.3
o'                               Main                   7.5    8.6
CAF                           Main                   7.5    0.1
MAIN                         MAIN                   5.0    0.0
a'                               Main                   2.5    8.6

But it can hardly be called impressive. 
Can anyone see another obvious optimization, or have I just hit the
ceiling because of the sheer number of function calls to isIn? I am
still pretty new to haskell, and I find it hard to wrap my head around
the way the compiler deals with my code.
If someone has a few leads on general performance heuristics in
haskell/GHC, I would be happy to read them too...

thanks for your time.

stijn
Ben Rudiak-Gould | 18 Jan 05:54 2005
Picon
Picon

Re: performance question

Stijn De Saeger wrote:

 >>data Bound = I Double | E Double deriving (Eq, Show, Ord)  
 >>data Interval = Il Bound Bound | Nil Bound Bound deriving (Eq,Ord)  
 >
 >>isIn :: Double -> Interval -> Bool
 >>isIn r (Nil x y) = not (isIn r (Il x y))
 >>isIn r (Il (I x) (I y)) = r >= x && r <= y
 >>isIn r (Il (I x) (E y)) = r >= x && r < y
 >>isIn r (Il (E x) (I y)) = r > x && r <= y
 >>isIn r (Il (E x) (E y)) = r > x && r < y

If performance is the main concern, I would flatten the data structure:

    data Interval = IlII Double Double
                  | IlIE Double Double
                  | IlEI Double Double
                  | IlEE Double Double
                  | NilII Double Double
                  | NilIE Double Double
                  | NilEI Double Double
                  | NilEE Double Double

    isIn :: Double -> Interval -> Bool
    isIn r (IlII x y) = r >= x && r <= y
    isIn r (IlIE x y) = r >= x && r < y
    isIn r (IlEI x y) = r > x && r <= y
    isIn r (IlEE x y) = r > x && r < y
    isIn r (NilII x y) = r < x || r > y
    isIn r (NilIE x y) = r < x || r >= y
    isIn r (NilEI x y) = r <= x || r > y
    isIn r (NilEE x y) = r <= x || r >= y

Depending on your application you might not need all of those cases.

Another neat trick you can pull is to take advantage of the fact that 
Double is actually a discrete type, like Int, and you can therefore get 
away with closed intervals only:

    data Interval = Il Double Double | Nil Double Double

    isIn :: Double -> Interval -> Bool
    isIn r (Il x y) = r >= x && r <= y
    isIn r (Nil x y) = r < x || r > y

But this requires nextLargestDouble and nextSmallestDouble functions. I 
don't know if Haskell provides them. Also, you could run into trouble 
with wider-than-Double intermediate values.

Finally, if you never do anything with intervals except pass them to 
isIn, you can do this:

    type Interval = Double -> Bool

    isIn r i = i r

-- Ben
John Meacham | 18 Jan 11:15 2005
Picon

Re: performance question

On Mon, Jan 17, 2005 at 08:54:38PM -0800, Ben Rudiak-Gould wrote:
> If performance is the main concern, I would flatten the data structure:
> 
>    data Interval = IlII Double Double
>                  | IlIE Double Double
>                  | IlEI Double Double
>                  | IlEE Double Double
>                  | NilII Double Double
>                  | NilIE Double Double
>                  | NilEI Double Double
>                  | NilEE Double Double

I would go even further 

>    data IntervalType = IlII 
>                  | IlIE 
>                  | IlEI 
>                  | IlEE 
>                  | NilII
>                  | NilIE
>                  | NilEI
>                  | NilEE
>    data Interval = Interval IntervalType {-# UNPACK #-} !Double {-# UNPACK #-} !Double

now, the doubles can be stored in their native form and are not under a
union data type (which always must be represented by a pointer) so
accessing them can be very fast.

        John

--

-- 
John Meacham - ⑆repetae.net⑆john⑈ 

Gmane