Re: Huge performance gap

Ruby
1

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 Ruby Quiz - Sodoku Solver (#43)
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

Simon,

On 2/24/06, Kroeger, Simon (ext) [email protected] 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 Ruby Quiz - Sodoku Solver (#43)
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

3

7 2 9 8 1 3 6 4 5
| 1 6 4 | 7 3 8 | 9 5 2 |

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 :slight_smile: ), it
now makes perfect sense.

Alexis.