www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Intrinsics, std.bind problems, list comphrensions, recursivity test

reply bearophile <bearophileHUGS lycos.com> writes:
Some time ago I have tried to improve the Shootout nsieve-bits test, but I have
failed:
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=nsievebits&lang=all
On my PC that version that uses intrinsics is faster, but on the PC used by the
Shootout the version that uses local functions seems faster. Do you know how is
this possibile?
BTW, now that I know D a bit better I think my version of the program can be
improved some more with:
uint[] flags = void;
But probably the speed difference isn't enough to make it go up in the time
rank.

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

import std.stdio, std.bind, std.traits, std.random;

int randInt(int min, int max) {
  int k, n;
  n = (max - min) + 1;
  k = cast(int)(n * (rand() / (uint.max + 1.0)));
  return (k == n) ? k + min - 1 : k + min;
}

int randInt(int max) {
  int k, n;
  n = max + 1;
  k = cast(int)(n * (rand() / (uint.max + 1.0)));
  return (k == n) ? k - 1 : k;
}

void main() {
  // This line:
  // auto rnd = bind(&randInt, 100);

  // Raises:
  // ...\std\bind.d(395): static assert  is false

  // Line 394-395 of std.bind.d:
  // // make sure we'll copy all args the function is going to need
  // static assert (res >= minFuncArgs);

  auto rnd100 = bind(&randInt, 0, 99);

  writefln( typeid(typeof(rnd100)) , '\n');
  // Prints:
  // std.bind.BoundFunc!(int(*)(int min, int max),NullAlias,Tuple!(int,int)
).BoundFunc

  writefln(rnd100(), ' ', rnd100(), '\n'); // OK

  // This line:
  // ReturnType!(typeof(rnd100)) x;

  // Raises:
  // ...\std\traits.d(34): alias std.traits.ReturnType!(BoundFunc).ReturnType
recursive alias declaration

  static if (is(rnd100 TyOut == return)) {
    TyOut x;
    writefln(typeid(typeof(x)));
  } else
    writefln("No return"); // Prints this
}

(In the end I have simply solved the problem without std.bind, defining a
lambda function.)

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

I think D developers can take a look at ShedSkin, its type inferencing is among
the most powerful you can see around (but it's slow too, partially because it's
written in Python). It shows how some Python can be compiled to C++. Python
list comphrensions are a quite easy syntax to build various arrays (the latest
Javascript of Mozilla has them too), this is a little Python code that shows
few usages of LCs:

print [x*x for x in xrange(16) if x & 1]
# Prints: [1, 9, 25, 49, 81, 121, 169, 225]

print [x+y for x in xrange(5) if x & 1 for y in xrange(5)]
# Prints: [1, 2, 3, 4, 5, 3, 4, 5, 6, 7]

print [[x+y for x in xrange(3)] for y in xrange(3)]
# Prints: [[0, 1, 2], [1, 2, 3], [2, 3, 4]]

def odds():
  x = 0
  while x < 36:
    yield x
    x += 1

print [x*x for x in odds() if x > 30]
# Prints: [961, 1024, 1089, 1156, 1225]


This is how ShedSkin translates them to C++ (this is most of the produced code):

str *__name__;
int __12;

static inline list<int> *list_comp_0() {
  int x, __1, __0;
  list<int> *result = new list<int>();

  FAST_FOR(x,0,16,1,0,1)
    if ((x&1)) {
      result->append((x*x));
    }
  END_FOR

  return result;
}

static inline list<int> *list_comp_1() {
  int __5, __4, __3, __2, y, x;
  list<int> *result = new list<int>();

  FAST_FOR(x,0,5,1,2,3)
    if ((x&1)) {
      FAST_FOR(y,0,5,1,4,5)
        result->append((x+y));
      END_FOR

    }
  END_FOR

  return result;
}

static inline list<int> *list_comp_2(int y) {
  int x, __9, __8;
  list<int> *result = new list<int>();

  FAST_FOR(x,0,3,1,8,9)
    result->append((x+y));
  END_FOR

  return result;
}

static inline list<list<int> *> *list_comp_3() {
  int y, __7, __6;
  list<list<int> *> *result = new list<list<int> *>();

  FAST_FOR(y,0,3,1,6,7)
    result->append(list_comp_2(y));
  END_FOR

  return result;
}

static inline list<int> *list_comp_4(__iter<int> *__13) {
  __iter<int> *__11, *__10;
  int x;
  list<int> *result = new list<int>();

  FOR_IN(x,__13,11)
    if ((x>30)) {
      result->append((x*x));
    }
  END_FOR

  return result;
}

class __gen_odds : public __iter<int> {
public:
  int x;
  int __last_yield;

  __gen_odds() {
    __last_yield = -1;
  }

  int next() {
    switch(__last_yield) {
      case 0: goto __after_yield_0;
      default: break;
    }
    x = 0;

    while((x<36)) {
      __last_yield = 0;
      return x;
      __after_yield_0:;
      x = (x+1);
    }
    throw new StopIteration();
  }

};

__iter<int> *odds() {
  return new __gen_odds();
}

void __init() { // the main program
  __name__ = new str("__main__");

  print("%s\n", list_comp_0());
  print("%s\n", list_comp_1());
  print("%s\n", list_comp_3());
  print("%s\n", list_comp_4(odds()));
}


The list_comp_0 shows a small function and an if too.
list_comp_1 shows that LCs can be attached too.
list_comp_2 and list_comp_3 are nested, and list_comp_4 shows a case where you
don't know how much long the resulting array will become, so it is built with
successive appends.

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

In one of my recent emails I have tried to show some code that D executes
relatively slowly, but Walter has spotted a stupid error of mine. So I try
again (it's a bit of code that comes from the Shootout):

First D version:

import std.conv;
int ack(int m, int n) {
  if (m == 0) return n+1;
  if (n == 0) return ack(m-1, 1);
  return ack(m-1, ack(m, n-1));
}
void main(string[] args) {
  int n = args.length > 1 ? toInt(args[1]) : 11;
  printf("ack(3,%d): %d\n", n, ack(3, n));
}


Second D version (nested function):

import std.conv;
void main(string[] args) {
  int ack(int m, int n) {
    if (m == 0) return n+1;
    if (n == 0) return ack(m-1, 1);
    return ack(m-1, ack(m, n-1));
  }
  int n = args.length > 1 ? toInt(args[1]) : 11;
  printf("ack(3,%d): %d\n", n, ack(3, n));
}


C version:

#include <stdio.h>
#include <stdlib.h>
int ack(int m, int n) {
  if (m == 0) return n+1;
  if (n == 0) return ack(m-1, 1);
  return ack(m-1, ack(m, n-1));
}
int main(int argc, char *argv[]) {
  int n = argc > 1 ? atoi(argv[1]) : 11;
  printf("Ack(3,%d): %d\n", n, ack(3, n));
  return 0;
}


Object Pascal version:

*{$APPTYPE CONSOLE}
uses SysUtils;
// integer is signed 32-bit
function ack(m: integer; n: integer): integer;
  begin
    if m = 0 then
        ack := n+1
    else
       if n = 0 then
         ack := ack(m-1, 1)
       else
         ack := ack(m-1, ack(m, n-1));
  end;
var n, code: Integer;
begin
  if ParamCount > 0 then
    Val(ParamStr(1), n, code)
  else
    n := 6;
  writeln('ack(3,', n, '): ', ack(3, n));
end.



Running time, input n = 11 (Pentium3 CPU):
  C 1:           2.91 seconds
  C 2:           4.61 s
  ObjectPascal:  6.78 s
  D 1:           8.15 s
  D 2:          16.36 s

Compilers used and settings:
  C 1: MinGW -O3 -fomit-frame-pointer
  C 2: MinGW -O3 (same code as C 1).
  ObjectPascal: Delphi 5, runtime errors disabled
  D 1: dmd -O -inline -release
  D 2: dmd -O -inline -release, nested function

Bye,
bearophile
Aug 24 2007
next sibling parent Downs <default_357-line yahoo.de> writes:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

FWIW, you can express those in D in a similar fashion using the
tools.iter module I posted over in d.D ..

bearophile wrote:
 print [x*x for x in xrange(16) if x & 1]

 # Prints: [1, 9, 25, 49, 81, 121, 169, 225]
 
 print [x+y for x in xrange(5) if x & 1 for y in xrange(5)]

looks too ugly to post. But it works. writefln(Integers[0..5]~filters!("_&1") ~tscross({return Integers[0..5]; }) ~maps!("_.values[0]+_.values[1]")~toArray);
 # Prints: [1, 2, 3, 4, 5, 3, 4, 5, 6, 7]
 
 print [[x+y for x in xrange(3)] for y in xrange(3)]

writefln(Integers[0..3]~map((int e) { return Integers[0..3]~map((int f) { return f+e; })~toArray; })~toArray);
 # Prints: [[0, 1, 2], [1, 2, 3], [2, 3, 4]]
 
 def odds():
   x = 0
   while x < 36:
     yield x
     x += 1
 
 print [x*x for x in odds() if x > 30]

// We really need to come up with a way to do yield. // StackThreads, anyone? class odds : Iterator!(int) { int x=0; bool next(ref int foo) { if (x!<36) return false; foo=x; x+=1; return true; } } writefln((new odds)~filters!("_>30")~maps!("_*_")~toArray);
 # Prints: [961, 1024, 1089, 1156, 1225]

Still, despite the ugliness D is actually not that far off. --downs -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFGzp1KpEPJRr05fBERAjdNAJ9BLWgjjz/fiSMkZQm21ul8LPezOACfcwNr z3oUu+mF/ojlx2gkLIccSjg= =dpId -----END PGP SIGNATURE-----
Aug 24 2007
prev sibling next sibling parent Henning Hasemann <hhasemann web.de> writes:
This is untested:

/**
 * Resembles pythons list comprehensions
 * Read as
 * returns *apply* applied to each *iter* in *collection* where *where*
 *
 * for example:
 *
 * int i;
 * select(toString(i), i, [1,2,3,4,5,6,7], i % 2 == 0)
 *
 * would return:
 * ["2", "4", "6"]
 */
R[] select(R, I, C)(lazy R apply, ref I iter, C collection, lazy bool
where) { R[] r;
  foreach(x; collection) {
    iter = x;
    if(where())
      r ~= apply();
  }
  return r;
}



-- 
GPG Public Key:
http://keyserver.ganneff.de:11371/pks/lookup?op=get&search=0xDDD6D36D41911851
Fingerprint: 344F 4072 F038 BB9E B35D  E6AB DDD6 D36D 4191 1851
Aug 24 2007
prev sibling parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
bearophile wrote:
 import std.stdio, std.bind, std.traits, std.random;
 
 int randInt(int min, int max) {
   int k, n;
   n = (max - min) + 1;
   k = cast(int)(n * (rand() / (uint.max + 1.0)));
   return (k == n) ? k + min - 1 : k + min;
 }
 
 int randInt(int max) {
   int k, n;
   n = max + 1;
   k = cast(int)(n * (rand() / (uint.max + 1.0)));
   return (k == n) ? k - 1 : k;
 }
 
 void main() {
   // This line:
   // auto rnd = bind(&randInt, 100);
 
   // Raises:
   // ...\std\bind.d(395): static assert  is false

Yup, because Bind extracts type info from the passed delegate / function, and in this case it has two options. I'll try to see if I could somehow make it 'guess', basing on the number of parameters, which type to expect, but there might be problems with it. Anyway, the solution is to tell it which function pointer to choose, by using a cast.
 
   // Line 394-395 of std.bind.d:
   // // make sure we'll copy all args the function is going to need
   // static assert (res >= minFuncArgs);
 
   auto rnd100 = bind(&randInt, 0, 99);
 
   writefln( typeid(typeof(rnd100)) , '\n');
   // Prints:
   // std.bind.BoundFunc!(int(*)(int min, int max),NullAlias,Tuple!(int,int)
).BoundFunc

bind() doesn't return a delegate, it returns a BoundFunc object. Access the delegate by using .ptr(). Otherwise, opCall can be used on the object, but traits doesn't work on it
   writefln(rnd100(), ' ', rnd100(), '\n'); // OK
 
   // This line:
   // ReturnType!(typeof(rnd100)) x;
 
   // Raises:
   // ...\std\traits.d(34): alias std.traits.ReturnType!(BoundFunc).ReturnType
recursive alias declaration
 
   static if (is(rnd100 TyOut == return)) {
     TyOut x;
     writefln(typeid(typeof(x)));
   } else
     writefln("No return"); // Prints this
 }
 
 (In the end I have simply solved the problem without std.bind, defining a
lambda function.)

And here's the solution with Bind: // ---- import std.stdio, std.bind, std.traits, std.random; int randInt(int min, int max) { writefln(`rand1`); int k, n; n = (max - min) + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k + min - 1 : k + min; } int randInt(int max) { writefln(`rand2`); int k, n; n = max + 1; k = cast(int)(n * (rand() / (uint.max + 1.0))); return (k == n) ? k - 1 : k; } void main() { // This line: auto rnd = bind(cast(int function(int))&randInt, 100).ptr(); rnd(); auto rnd100 = bind(&randInt, 0, 99).ptr(); writefln( typeid(typeof(rnd100)) , '\n'); writefln(rnd100(), ' ', rnd100(), '\n'); // OK ReturnType!(typeof(rnd100)) x; writefln(typeid(typeof(x))); } // ---- Cheers! -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Aug 24 2007