www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Fast switching..

reply Regan Heath <regan netmail.co.nz> writes:
Hi all,

I've been AWOL from this NG for a while but recently a friend of mine 
sent me a link to this:
http://blogs.msdn.com/jomo_fisher/archive/2007/03/28/fast-switching-with-linq.aspx

and my first thought was; can something similar (or even better) be done 
in D. :)

I admit, I haven't even spent 5 mins thinking about how I might do it, 
but I've never been particularly good with the compile time features of 
D so I figured I'd post something here and see what the people who are 
good at it can come up with.

So, consider this a little challenge .. it may turn out to be trivial, 
it might not, I have no idea.

R
Jun 11 2008
next sibling parent reply Georg Wrede <georg nospam.org> writes:
Regan Heath wrote:

 Hi all,
 
 I've been AWOL from this NG for a while but recently a friend of mine 
 sent me a link to this:
 http://blogs.msdn.com/jomo_fisher/archive/2007/03/28/fast-swit
hing-with-linq.aspx 
 
 and my first thought was; can something similar (or even better) be done 
 in D. :)
 
 I admit, I haven't even spent 5 mins thinking about how I might do it, 
 but I've never been particularly good with the compile time features of 
 D so I figured I'd post something here and see what the people who are 
 good at it can come up with.
 
 So, consider this a little challenge .. it may turn out to be trivial, 
 it might not, I have no idea.


A language that allows you to write switch statements with strings 
should have this built-in. But that is actually a quality of 
implementation issue, and therefore transparent to the spec.

In real life, if I were to tackle this and there were less than two 
dozen words, I'd figure it out manually. This would also allow for 
optimizations, like if I expect some of the words to occur more often 
than others.

If this is something I expect to come across regularly, I'd write a 
small D program that takes as input a list of words with their number 
and another number that hints at how often I expet the word. This 
program would output the bit of D source code that I'd paste into my 
application.

---

There ought to be a site collecting code snippets, idioms, and tiny 
utility programs that help in programming. And with good search 
capabilities.
Jun 11 2008
next sibling parent Robert Fraser <fraserofthenight gmail.com> writes:
Georg Wrede wrote:

 If this is something I expect to come across regularly, I'd write a 
 small D program that takes as input a list of words with their number 
 and another number that hints at how often I expet the word. This 
 program would output the bit of D source code that I'd paste into my 
 application.


Which can be done with a string mixin + CTFE function ;-P. String 
mixins, IMO, are the most powerful concept in D.
Jun 11 2008
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
== Quote from Georg Wrede (georg nospam.org)'s article

 Regan Heath wrote:

 Hi all,

 I've been AWOL from this NG for a while but recently a friend of mine
 sent me a link to this:
 http://blogs.msdn.com/jomo_fisher/archive/2007/03/28/fast-switching-with-linq.aspx

 and my first thought was; can something similar (or even better) be done
 in D. :)

 I admit, I haven't even spent 5 mins thinking about how I might do it,
 but I've never been particularly good with the compile time features of
 D so I figured I'd post something here and see what the people who are
 good at it can come up with.

 So, consider this a little challenge .. it may turn out to be trivial,
 it might not, I have no idea.


 A language that allows you to write switch statements with strings
 should have this built-in. But that is actually a quality of
 implementation issue, and therefore transparent to the spec.
 In real life, if I were to tackle this and there were less than two
 dozen words, I'd figure it out manually. This would also allow for
 optimizations, like if I expect some of the words to occur more often
 than others.


I've done this quite often with simple parsers:

switch( token[0] )
{
case 'o':
    if( strcmp( token, "one" ) )
        throw new ParseFailure();
    // blah
    break;
case 't':
    if( !strcmp( token, "two" ) )
        // stuff for "two"
    else if( !strcmp( token, "three" ) )
        // stuff for "three"
    break;
}

It's easy enough to do it all with switch statements as well, but I
like the insurance that checking the entire string provides.  It would
be nice if DMD optimized string-based switch statements this way.
I'll admit to being a bit old-school in this respect--I've never actually
used string switch statements in D.


Sean
Jun 11 2008
parent reply janderson <askme me.com> writes:
Sean Kelly wrote:

 == Quote from Georg Wrede (georg nospam.org)'s article

 Regan Heath wrote:

 Hi all,

 I've been AWOL from this NG for a while but recently a friend of mine
 sent me a link to this:
 http://blogs.msdn.com/jomo_fisher/archive/2007/03/28/fast-switching-with-linq.aspx

 and my first thought was; can something similar (or even better) be done
 in D. :)

 I admit, I haven't even spent 5 mins thinking about how I might do it,
 but I've never been particularly good with the compile time features of
 D so I figured I'd post something here and see what the people who are
 good at it can come up with.

 So, consider this a little challenge .. it may turn out to be trivial,
 it might not, I have no idea.


 A language that allows you to write switch statements with strings
 should have this built-in. But that is actually a quality of
 implementation issue, and therefore transparent to the spec.
 In real life, if I were to tackle this and there were less than two
 dozen words, I'd figure it out manually. This would also allow for
 optimizations, like if I expect some of the words to occur more often
 than others.


 
 I've done this quite often with simple parsers:
 
 switch( token[0] )
 {
 case 'o':
     if( strcmp( token, "one" ) )
         throw new ParseFailure();
     // blah
     break;
 case 't':
     if( !strcmp( token, "two" ) )
         // stuff for "two"
     else if( !strcmp( token, "three" ) )
         // stuff for "three"
     break;
 }
 
 It's easy enough to do it all with switch statements as well, but I
 like the insurance that checking the entire string provides.  It would
 be nice if DMD optimized string-based switch statements this way.
 I'll admit to being a bit old-school in this respect--I've never actually
 used string switch statements in D.
 
 
 Sean



I thought in a discussion earlier with Walter (a few years back) that 
DMD would generate a string hash and then jump to that hash when you use 
a string as the input.  In many cases the branching will be the 
expensive part so I guess a hash is pretty close to optimal performance 
for the general case.  Although with optimisation you can always make 
things run faster.

-Joel
Jun 11 2008
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"janderson" <askme me.com> wrote in message 
news:g2q2bp$13ef$3 digitalmars.com...

 I thought in a discussion earlier with Walter (a few years back) that DMD 
 would generate a string hash and then jump to that hash when you use a 
 string as the input.  In many cases the branching will be the expensive 
 part so I guess a hash is pretty close to optimal performance for the 
 general case.  Although with optimisation you can always make things run 
 faster.

 -Joel


Guessing won't be necessary :)  The implementation of string switches is in 
dmd/src/phobos/internal/switch.d.  The compiler puts the case names into a 
sorted array of strings, and the string switch just does a binary search on 
it.  It's somewhat optimized though -- it won't actually do a string 
comparison unless the strings are of the same length and their first 
character is the same.
Jun 12 2008
parent janderson <askme me.com> writes:
Jarrett Billingsley wrote:

 "janderson" <askme me.com> wrote in message 
 news:g2q2bp$13ef$3 digitalmars.com...

 I thought in a discussion earlier with Walter (a few years back) that DMD 
 would generate a string hash and then jump to that hash when you use a 
 string as the input.  In many cases the branching will be the expensive 
 part so I guess a hash is pretty close to optimal performance for the 
 general case.  Although with optimisation you can always make things run 
 faster.

 -Joel


 
 Guessing won't be necessary :)  The implementation of string switches is in 
 dmd/src/phobos/internal/switch.d.  The compiler puts the case names into a 
 sorted array of strings, and the string switch just does a binary search on 
 it.  It's somewhat optimized though -- it won't actually do a string 
 comparison unless the strings are of the same length and their first 
 character is the same. 
 
 


ic.  I guess I should have just looked.  I guess if anyone wanted to 
write a faster one they could send an updated version to Walter (after 
they had run many benchmark tests).

-Joel
Jun 12 2008
prev sibling next sibling parent reply "Lionello Lunesu" <lionello lunesu.remove.com> writes:
"Regan Heath" <regan netmail.co.nz> wrote in message 
news:g2o13n$1oka$1 digitalmars.com...

 Hi all,

 I've been AWOL from this NG for a while but recently a friend of mine sent 
 me a link to this:
 http://blogs.msdn.com/jomo_fisher/archive/2007/03/28/fast-switching-with-linq.aspx


Isn't the internet great? I started on that page (interesting read) and a 
few clicks later I ended up at
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

"Purely Functional Data Structures", it's a paper from 1996! Some quotes:

"[S]trict languages can describe worst-case data structures, but not
amortized ones, and lazy languages can describe amortized data structures, 
but not worst-case
ones. To be able to describe both kinds of data structures, we need a 
programming language
that supports both evaluation orders."

"Functional programmers have long debated the relative
merits of strict and lazy evaluation. This thesis shows that both are 
algorithmically im-
portant and suggests that the ideal functional language should seamlessly 
integrate both."
Jun 11 2008
parent Fawzi Mohamed <fmohamed mac.com> writes:
On 2008-06-12 04:56:33 +0200, "Lionello Lunesu" 
<lionello lunesu.remove.com> said:


 
 "Regan Heath" <regan netmail.co.nz> wrote in message 
 news:g2o13n$1oka$1 digitalmars.com...

 Hi all,
 
 I've been AWOL from this NG for a while but recently a friend of mine 
 sent me a link to this:
 http://blogs.msdn.com/jomo_fisher/archive/2007/03/28/fast-switching-with-linq.aspx




Isn't 

 


 the internet great? I started on that page (interesting read) and a few 
 clicks later I ended up at
 http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
 
 "Purely Functional Data Structures", it's a paper from 1996! Some quotes:
 
 "[S]trict languages can describe worst-case data structures, but not
 amortized ones, and lazy languages can describe amortized data 
 structures, but not worst-case
 ones. To be able to describe both kinds of data structures, we need a 
 programming language
 that supports both evaluation orders."
 
 "Functional programmers have long debated the relative
 merits of strict and lazy evaluation. This thesis shows that both are 
 algorithmically im-
 portant and suggests that the ideal functional language should 
 seamlessly integrate both."


He also wrote a very nice book taken from his papers:
Chris Okasaki
Purely Functional Data Structures

http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=sr_1_1?ie=UTF8&s=books&qid=1213262984&sr=8-1

Fawzi
Jun 12 2008
prev sibling parent bearophile <bearophileHUGS lycos.com> writes:
Fawzi Mohamed:

 He also wrote a very nice book taken from his papers:
 Chris Okasaki
 Purely Functional Data Structures
 http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=sr_1_1?ie=UTF8&s=books&qid=1213262984&sr=8-1


Oh, you have found the book I was talking about here:
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=72494
I think the author wants to write a new edition of that book soon.

Bye,
bearophile
Jun 12 2008