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