www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Implementation of C++0x's "future" syntax

reply Daniel Keep <daniel.keep+lists gmail.com> writes:
I was poking around the stuff on C++0x (which I was led to because I was 
poking around STL (because I was poking around for a good D container 
library)) when I found out about "future".

For those that don't know, the idea is to make asynchronous function 
calls nice and easy.  The syntax on Wikipedia is this:


 int function( int parameter ) ;
 // Calls the function and immediately returns.
 IdThreadType<function> IdThread = future function(parameter) ;
 // Waits for the function result.
int ret = wait IdThread ;


Anyway, I had a similar idea a while back, and figured now would be the 
time to see if I could do it.  So I did.  Here's the equivalent in D:


 int func( int parameter ); // "function"'s a keyword :P
 // Calls the function and immediately returns.
 FutureResult!(func) result = future(&func, parameter); // "auto" helps
 // Waits for the function result.
 int ret = result.value;


(It also works for functions that have no return type: you would use 
"result.wait" instead.)

Not too shabby considering that C++0x is set to be released in 2009. 
That makes us at least two years ahead of the game :)

There are only two improvements I can think of off the top of my head:

1) Investigate whether "future!(func)(args)" is more efficient.
2) Use a thread pool (if the standard library ever gets one).

Enjoy.

	-- Daniel

P.S.  Kinda OT: has anyone else ever thought that being able to declare 
void variables would be *really* handy in templates?  I keep having to 
put in special cases for void... *grumble, grumble*

future.d:
--------------------

/**
  * future -- Simple concurrent execution
  * Written by Daniel Keep.
  * Released to the Public Domain.
  */
module future;

import std.thread : Thread;

/**
  * This structure is what we'll use to store the results of our "future"
  * calls in.  All that nasty private stuff is basically just bookkeeping
  * for the thread we'll spawn off, which allows us to kick off the
  * thread, and then store the result when it's finished.
  */
struct FutureResult(tFn, tArgs...)
{
     private
     {
         alias tTaskResult!(tFn) tResult; // result type of future call

         tFn fn; // function to call
         tArgs args; // arguments to pass to it
         bool got_result = false; // have we got a result yet?
         Thread thread; // which thread are we using?

         static if( !is( tResult == void ) )
             tResult result; // what is the result?

         // start is used as the entry point to the thread
         int start()
         {
             static if( !is( tResult == void ) )
                 result = fn(args);
             else
                 fn(args);

             got_result = true;
             return 0;
         }
     }

     static if( !is( tResult == void ) )
     {
         /**
          * Either returns the value if we already know what it is, or
          * else block until we do.
          */
         tResult value()
         {
             while( !got_result )
                 Thread.yield();
             return result;
         }
     }
     else
     {
         /**
          * Wait until the function call has returned.
          */
         void wait()
         {
             while( !got_result )
                 Thread.yield();
         }
     }
}

private template tTaskResult(tFn)
{
     alias tiTaskResult!(tFn).result tTaskResult;
}

private template tiTaskResult(tFn)
{
     static if( is( tFn tRealFn == delegate ) )
         alias tiTaskResult!(tRealFn).result result;

     else static if( is( tFn tReturn == return ) )
         alias tReturn result;

     else
         static assert("Cannot derive result from function type.");
}

/**
  * Performs a function call asynchronously.  The "future" refers both
  * the fact that the result of this function is intended to be used at
  * some time in the future, and that its' basically what the "future"
  * keyword in C++0x is supposed to do.
  *
  * The way it works is quite simple: when you have some lengthy function
  * call to make, call the function as early as possible, and store away
  * the return.  Then, when you actually need the result, you ask for it.
  * If the function call completed in the background, it will return the
  * result immediately.  If it hasn't, then it will block until the
  * result is available.  For example:
  *
  * ---------------------------------------------------------------------
  * import std.stdio;
  * import etc.future;
  *
  * int meaningOfLife()
  * {
  *     // Some long, complex calculations.
  *     return 42;
  * }
  *
  * void main()
  * {
  *     auto meaning = future(meaningOfLife);
  *
  *     // More complicated computations.
  *
  *     writefln("Meaning of life is: %d", meaning.value);
  * }
  * ---------------------------------------------------------------------
  */
FutureResult!(tFn, tArgs) future(tFn, tArgs...)(tFn fn, tArgs args)
{
     FutureResult!(tFn, tArgs) result;

     result.fn = fn;

     foreach( i,a ; args )
         result.args[i] = a;

     result.thread = new Thread(&result.start);
     result.thread.start();

     return result;
}

unittest
{
     int meaningOfLife(int init)
     {
         int result = init;
         for( int i=1; i<10_000; i++ )
             result = (result * i) + (i << 1) - (result >> 1);

         // Bah; stuff that!
         return 42;
     }

     void shortPause(int loops)
     {
         while( loops )
             loops--;
     }

     auto life = future(&meaningOfLife, 0xBeef);
     assert( life.value == 42 );

     auto pause = future(&shortPause, 1_000);
     pause.wait();
}

version( future_main )
{
     import std.stdio;

     void main()
     {
         writefln("Tests complete.");
     }
}
Jan 14 2007
next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Daniel Keep wrote:
...

Cool stuff! I'm pretty much a multithreading newbie but it looks nice to 
me.


 P.S.  Kinda OT: has anyone else ever thought that being able to declare 
 void variables would be *really* handy in templates?  I keep having to 
 put in special cases for void... *grumble, grumble*


Yes very annoying, I had the same in my signal-slots implementation.


  *     auto meaning = future(meaningOfLife);


So true, haha.
Jan 14 2007
prev sibling next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Daniel Keep wrote:

 struct FutureResult(tFn, tArgs...)
 {


[snip]

         // start is used as the entry point to the thread
         int start()
         {
             static if( !is( tResult == void ) )
                 result = fn(args);
             else
                 fn(args);
 
             got_result = true;
             return 0;
         }


[snip]

 FutureResult!(tFn, tArgs) future(tFn, tArgs...)(tFn fn, tArgs args)
 {
     FutureResult!(tFn, tArgs) result;
 
     result.fn = fn;
 
     foreach( i,a ; args )
         result.args[i] = a;
 
     result.thread = new Thread(&result.start);
     result.thread.start();
 
     return result;
 }


So you create a struct on the stack, use a delegate to a member function 
as a thread entry-point, then return the struct?
Does that strike anyone else as a Bad Idea(TM)?

The named return value optimization that was recently introduced will 
probably keep this from breaking in typical code, but if 'result' is 
ever returned without that optimization being made this seems likely to 
corrupt stack-based data of new stackframes created afterwards...

I _really_ think FutureResult!() should be heap-allocated. If you want, 
you can even make it a class derived from Thread so no extra allocations 
need to be made.
Jan 14 2007
parent Daniel Keep <daniel.keep+lists gmail.com> writes:
Frits van Bommel wrote:

 I _really_ think FutureResult!() should be heap-allocated. If you want, 
 you can even make it a class derived from Thread so no extra allocations 
 need to be made.


*Bangs head*

Of course, you're absolutely right.  *Curses.*  I suppose the easiest 
way to solve it is to turn FutureResult into a class so that it's 
heap-allocated.  You're right I could use a subclass of Thread, but I 
don't want to expose anything other than the .value/.wait method

Pity, too, since thanks to that optimisation, this would have actually 
been pretty efficient :3

	-- Daniel
Jan 14 2007
prev sibling next sibling parent reply Kevin Bealer <kevinbealer gmail.com> writes:
Dang, you beat me to it.

I've been working on this for couple of weeks myself.  I have an implementation
I
was thinking of putting up on dsource or somewhere in the next day or two.  Its
a
bit different though, I wrote a thread pool and some other stuff for it.  I'll
mention something here when I get it posted.

Kevin
Jan 14 2007
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
Kevin Bealer wrote:

 Dang, you beat me to it.


Yesss; finally, I beat someone to something :3


 I've been working on this for couple of weeks myself.  I have an
implementation I
 was thinking of putting up on dsource or somewhere in the next day or two. 
Its a
 bit different though, I wrote a thread pool and some other stuff for it.  I'll
 mention something here when I get it posted.
 
 Kevin


Sounds good.  Mine was just a quick little proof of concept.  I think 
that for something like this to be really efficient, it does need a 
thread pool.  Honestly, I've been waiting to see what Tango contains 
before I go and write my own :P

Since I'm going to have to move over to heap allocation (bangs head 
again), I was wondering: do you use stack allocation, or a custom 
allocator for small objects?

	-- Daniel
Jan 14 2007
parent Kevin Bealer <kevinbealer gmail.com> writes:
== Quote from Daniel Keep (daniel.keep+lists gmail.com)'s article

 Kevin Bealer wrote:

 Dang, you beat me to it.


 Yesss; finally, I beat someone to something :3

 I've been working on this for couple of weeks myself.  I have an
implementation I
 was thinking of putting up on dsource or somewhere in the next day or two. 
Its a
 bit different though, I wrote a thread pool and some other stuff for it.  I'll
 mention something here when I get it posted.

 Kevin


 Sounds good.  Mine was just a quick little proof of concept.  I think
 that for something like this to be really efficient, it does need a
 thread pool.  Honestly, I've been waiting to see what Tango contains
 before I go and write my own :P
 Since I'm going to have to move over to heap allocation (bangs head
 again), I was wondering: do you use stack allocation, or a custom
 allocator for small objects?
 	-- Daniel


I had not gotten into the efficiency angle (yet).  Right now, the user calls
"new"
for the 'future' object and it calls new for another 'task' object that
represents
the work itself.  These two classes could be merged to reduce calls to new().  I
hadn't thought of this as a critical area since I was thinking that this would
be
for larger tasks like parsing an input file, sorting large arrays, and so on.

I didn't look at your code too deeply but I think your design has some things
like
capturing the inputs for the delegate, and handling void delegates that mine did
not include yet.

I have a bug that I want to fix, plus I need to ask my company before releasing
the code, but I'm told thats just a formality as long as it doesn't relate to
work.

Of course there are additional features to consider for later on.

Kevin
Jan 16 2007
prev sibling next sibling parent =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
Daniel Keep kirjoitti:

 
 I was poking around the stuff on C++0x (which I was led to because I was
 poking around STL (because I was poking around for a good D container
 library)) when I found out about "future".
 
 For those that don't know, the idea is to make asynchronous function
 calls nice and easy.  The syntax on Wikipedia is this:
 


There are also some interesting possibilities implemented in Fortress:

http://research.sun.com/projects/plrg/PLDITutorialSlides9Jun2006.pdf

Sun just released it partly under an open source license.

Should the next version of D implement some of the asynchronous /
parallel functionality as a core language feature or as a library
add-on. Well, Bill Baxter already opened a thread about this on
digitalmars.D.
Jan 16 2007
prev sibling parent reply BCS <BCS pathlink.com> writes:
Do you have anyplace to host this? If you want I'll let you put it into 
"scrapple" on dsource.

Daniel Keep wrote:

 
 I was poking around the stuff on C++0x (which I was led to because I was 
 poking around STL (because I was poking around for a good D container 
 library)) when I found out about "future".
 
 For those that don't know, the idea is to make asynchronous function 
 calls nice and easy.  The syntax on Wikipedia is this:
 
  > int function( int parameter ) ;
  > // Calls the function and immediately returns.
  > IdThreadType<function> IdThread = future function(parameter) ;
  > // Waits for the function result.
  >int ret = wait IdThread ;
 
 Anyway, I had a similar idea a while back, and figured now would be the 
 time to see if I could do it.  So I did.  Here's the equivalent in D:
 
  > int func( int parameter ); // "function"'s a keyword :P
  > // Calls the function and immediately returns.
  > FutureResult!(func) result = future(&func, parameter); // "auto" helps
  > // Waits for the function result.
  > int ret = result.value;
 
 (It also works for functions that have no return type: you would use 
 "result.wait" instead.)
 
 Not too shabby considering that C++0x is set to be released in 2009. 
 That makes us at least two years ahead of the game :)
 
 There are only two improvements I can think of off the top of my head:
 
 1) Investigate whether "future!(func)(args)" is more efficient.
 2) Use a thread pool (if the standard library ever gets one).
 
 Enjoy.
 
     -- Daniel
Jan 16 2007
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
BCS wrote:

 Do you have anyplace to host this? If you want I'll let you put it into 
 "scrapple" on dsource.


That would be great :)

	-- Daniel
Jan 16 2007
parent reply BCS <ao pathlink.com> writes:
Reply to Daniel,


 BCS wrote:
 

 Do you have anyplace to host this? If you want I'll let you put it
 into "scrapple" on dsource.
 


 That would be great :)
 
 -- Daniel
 


Give me a username and I'll give you dev access (or I can put it in myself 
if you want)
Jan 17 2007
parent reply Daniel Keep <daniel.keep+lists gmail.com> writes:
BCS wrote:

 Reply to Daniel,
 

 BCS wrote:


 Do you have anyplace to host this? If you want I'll let you put it
 into "scrapple" on dsource.


 That would be great :)

 -- Daniel


 
 Give me a username and I'll give you dev access (or I can put it in 
 myself if you want)
 
 


I'm pretty sure I signed up on the forums a while back as DRK.  I know I 
checked some stuff for cairo bindings in a while back, but buggered if I 
can remember what the username and password for that were :P

	-- Daniel
Jan 17 2007
next sibling parent BCS <BCS pathlink.com> writes:
Daniel Keep wrote:

 BCS wrote:
 

 Reply to Daniel,


 BCS wrote:


 Do you have anyplace to host this? If you want I'll let you put it
 into "scrapple" on dsource.


 That would be great :)

 -- Daniel


 Give me a username and I'll give you dev access (or I can put it in 
 myself if you want)


 
 I'm pretty sure I signed up on the forums a while back as DRK.  I know I 
 checked some stuff for cairo bindings in a while back, but buggered if I 
 can remember what the username and password for that were :P
 
     -- Daniel


Looks like it is DRK (I searched for posts under that name). The login 
has a "forgot password" link that might be of assistance.
Jan 18 2007
prev sibling parent reply BCS <BCS pathlink.com> writes:
Daniel Keep wrote:
[...]

You'r in as a dev. Please follow the structure that is being used.
Jan 18 2007
parent Daniel Keep <daniel.keep+lists gmail.com> writes:
BCS wrote:

 Daniel Keep wrote:
 [...]
 
 You'r in as a dev. Please follow the structure that is being used.


domo arigatou gozaimasu! (hopefully that's spelt right :P)
Jan 18 2007