Asp Forum - Re: Huge performance gap

Kroeger, Simon (ext)

2/24/2006 9:08:00 AM

Hi Alexis,

> Hi all
>
> I've ported the following c++ code to ruby. It is a recursive
> (backtracking) sudoku-solving algorithm. Well, I was rather
> surprised by
> the execution time I got:
>
> c++ code: 0.33 seconds
> ruby code: 27.65 seconds

Nothing to bad here, it looks awfull at first sight but it doesn't
get in your way as often as you would think.

> The implementation should do the same, at least they run through the
> method/function "next_state"/"nextone" both 127989 times.

I wouldn't doubt you did it 'right'.

> Now how can it be that the ruby code is so awfully slow?
> Is that normal for ruby?

You got some answers and the short one is 'yes'. The long would be
'yes, but..' (as allways). Yes, but because you tend to write 'better'
(and often faster) code after a while using ruby. I think the main
reason is that writing 'better' code in C is so painfull. You write
code that is easy to write in C and this code isn't 'good' (it's
still fast enough because C is fast).

> Or is my implementation so horribly bad?

Not bad, but not especialy clever.

> I am aware that the non-native and object-oriented ruby code
> won't be as
> fast as the c++ one, but I didn't expect such a gap.

Let's look at some numbers:

>ruby -rubygems sudoku-solver.rb
time elapsed: 29.703 sec.
count: 127989
3 6 2 4 9 5 7 8 1
9 7 1 6 2 8 5 3 4
8 5 4 1 3 7 9 6 2
2 9 3 5 6 4 1 7 8
5 1 7 3 8 2 4 9 6
6 4 8 9 7 1 2 5 3
7 2 9 8 1 3 6 4 5
1 8 5 7 4 6 3 2 9
4 3 6 2 5 9 8 1 7

>ruby -rubygems quiz43.rb
time elapsed: 0.156 sec.
+-------+-------+-------+
| 8 3 2 | 4 9 5 | 7 6 1 |
| 9 7 5 | 6 1 2 | 8 3 4 |
| 1 6 4 | 7 3 8 | 9 5 2 |
+-------+-------+-------+
| 2 9 3 | 5 7 4 | 1 8 6 |
| 6 1 7 | 8 2 3 | 4 9 5 |
| 5 4 8 | 9 6 1 | 2 7 3 |
+-------+-------+-------+
| 3 2 9 | 1 5 7 | 6 4 8 |
| 7 8 1 | 3 4 6 | 5 2 9 |
| 4 5 6 | 2 8 9 | 3 1 7 |
+-------+-------+-------+

So ruby is 3 times faster than C. *g*
No bad.

(look at my last solution on http://www.rubyquiz.com/q...
for the code, but this last one is realy only optimized for speed
so its ugly - perhaps look at the other ones also)

> Thanks for comments.
>
> Alexis.

cheers

Simon

2 Answers

Cameron McBride

2/24/2006 3:58:00 PM

Simon,

On 2/24/06, Kroeger, Simon (ext) <simon.kroeger.ext@siemens.com> wrote:
> > Now how can it be that the ruby code is so awfully slow?
> > Is that normal for ruby?
...
> You got some answers and the short one is 'yes'. The long would be
> 'yes, but..' (as allways). Yes, but because you tend to write 'better'
> (and often faster) code after a while using ruby. I think the main
> reason is that writing 'better' code in C is so painfull. You write
> code that is easy to write in C and this code isn't 'good' (it's
> still fast enough because C is fast).
>
> > Or is my implementation so horribly bad?
>
> Not bad, but not especialy clever.
...
> So ruby is 3 times faster than C. *g*
> No bad.
>
> (look at my last solution on http://www.rubyquiz.com/q...
> for the code, but this last one is realy only optimized for speed
> so its ugly - perhaps look at the other ones also)

Thanks for the clear and educational response. Us lurkers appreciate it.

Cameron

Alexis Reigel

2/25/2006 3:17:00 AM

> Not bad, but not especialy clever.
>
>
>>I am aware that the non-native and object-oriented ruby code
>>won't be as
>>fast as the c++ one, but I didn't expect such a gap.
>
>
> Let's look at some numbers:
>
>
>>ruby -rubygems sudoku-solver.rb
>
> time elapsed: 29.703 sec.
> count: 127989
> 3 6 2 4 9 5 7 8 1
> 9 7 1 6 2 8 5 3 4
> 8 5 4 1 3 7 9 6 2
> 2 9 3 5 6 4 1 7 8
> 5 1 7 3 8 2 4 9 6
> 6 4 8 9 7 1 2 5 3
> 7 2 9 8 1 3 6 4 5
> 1 8 5 7 4 6 3 2 9
> 4 3 6 2 5 9 8 1 7
>
>
>>ruby -rubygems quiz43.rb
>
> time elapsed: 0.156 sec.
> +-------+-------+-------+
> | 8 3 2 | 4 9 5 | 7 6 1 |
> | 9 7 5 | 6 1 2 | 8 3 4 |
> | 1 6 4 | 7 3 8 | 9 5 2 |
> +-------+-------+-------+
> | 2 9 3 | 5 7 4 | 1 8 6 |
> | 6 1 7 | 8 2 3 | 4 9 5 |
> | 5 4 8 | 9 6 1 | 2 7 3 |
> +-------+-------+-------+
> | 3 2 9 | 1 5 7 | 6 4 8 |
> | 7 8 1 | 3 4 6 | 5 2 9 |
> | 4 5 6 | 2 8 9 | 3 1 7 |
> +-------+-------+-------+
>
>
> So ruby is 3 times faster than C. *g*
> No bad.
>
> (look at my last solution on http://www.rubyquiz.com/q...
> for the code, but this last one is realy only optimized for speed
> so its ugly - perhaps look at the other ones also)
>
>
>>Thanks for comments.
>>
>>Alexis.
>
>
> cheers
>
> Simon
>

Sure I know that my recursive algorithm is the simplest and most
unefficient way to solve a sudoku, but it was not my intention to do it
as optimal as possible. I just wanted to see if such a deep recursion
can be done by ruby within reasonable time. And as stated, at first
sight I was surprised about the results.
Thanks for all your comments (thanks to the "mean" ones too :-) ), it
now makes perfect sense.

Alexis.

comp.lang.ruby

Re: Huge performance gap

Kroeger, Simon (ext)

Cameron McBride

Alexis Reigel

x Login to ForumsZone