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
The implementation should do the same, at least they run through the
method/function “next_state”/“nextone” both 127989 times.
Now how can it be that the ruby code is so awfully slow?
Is that normal for ruby?
Or is my implementation so horribly bad?
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.
Thanks for comments.
Alexis.
Alexis R. wrote:
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
The implementation should do the same, at least they run through the
method/function “next_state”/“nextone” both 127989 times.
Now how can it be that the ruby code is so awfully slow?
Is that normal for ruby?
Or is my implementation so horribly bad?
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.
Post the code somewhere, there might be room for improvement
in the algorithm though it will still be considerably slower.
Thanks for comments.
Alexis.
E
On 2/23/06, Alexis R. [email protected] wrote:
method/function “next_state”/“nextone” both 127989 times.
Now how can it be that the ruby code is so awfully slow?
Is that normal for ruby?
Or is my implementation so horribly bad?
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.
Others can better speak on ruby specifics, but…
Ruby is interpreted (inefficiently?), C++ is compiled.
And the algorithm is something like O(n^3)? Or worse?
Seems like a reasonable difference to me…
On 2/23/06, Alexis R. [email protected] wrote:
[…]
ruby code may be up to 100 times slower than c++ binaries. i think it is
normal.
also i don’t see any common performance crimes (such as using += with
strings) in your code.
– henon
E. Saynatkari wrote:
Post the code somewhere, there might be room for improvement
in the algorithm though it will still be considerably slower.
It looks, to me, like he attached his code to the OP.
Regardless, it doesn’t matter. Algorithmic improvements may help both
the C++ and Ruby versions - but it’s not going to change the fact that
one is a relatively low-level language, compiled to native machine code,
and the other is an interpreted dynamic language. To compare them is
either ridiculous, or more likely in this case, simply ignorant.
–Steve
On 2/23/06, Meinrad R. [email protected] wrote:
[…]
ruby code may be up to 100 times slower than c++ binaries. i think it is
normal.
also i don’t see any common performance crimes (such as using += with
strings) in your code.
there are a couple of (really minor) things like using for loops instead
of uptos, but those won’t buy the kind of time Alexis wants to see.
RubyInline might be just the ticket though. Run the code through
the profiler (a long process) and Inline the method that’s making the
biggest hit.
Stephen W. wrote:
the C++ and Ruby versions - but it’s not going to change the fact that
one is a relatively low-level language, compiled to native machine code,
and the other is an interpreted dynamic language. To compare them is
either ridiculous, or more likely in this case, simply ignorant.
–Steve
Why should that be ridiculous or ignorant?
I stated that I was aware of the differences between interpreted and
compiled languages. But that does not change the fact that I believe
that this does not explain the performance gap. An execution time of
27.65 seconds against 0.33 seconds is not just nothing is it? It’s a
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code as well and runs in a virtual machine too,
and it executed in about the same time as c++.
Alexis R. wrote:
Stephen W. wrote:
the C++ and Ruby versions - but it’s not going to change the fact that
one is a relatively low-level language, compiled to native machine code,
and the other is an interpreted dynamic language. To compare them is
either ridiculous, or more likely in this case, simply ignorant.
–Steve
Why should that be ridiculous or ignorant?
I stated that I was aware of the differences between interpreted and
compiled languages. But that does not change the fact that I believe
that this does not explain the performance gap. An execution time of
27.65 seconds against 0.33 seconds is not just nothing is it? It’s a
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code as well and runs in a virtual machine too,
and it executed in about the same time as c++.
Well, Ruby is strictly interpreted using the parse tree instead
of VM opcodes which may or may not (depending on who you ask)
make a difference. Ruby is pretty slow but usually Fast Enough™.
You could try to run your script on YARV[1] to see if it helps.
[1] YARV: Yet Another Ruby VM
E
Stephen W. wrote:
E. Saynatkari wrote:
Post the code somewhere, there might be room for improvement
in the algorithm though it will still be considerably slower.
It looks, to me, like he attached his code to the OP.
Ah, caveat forum-user!
Regardless, it doesn’t matter. Algorithmic improvements may help both
the C++ and Ruby versions - but it’s not going to change the fact that
one is a relatively low-level language, compiled to native machine code,
and the other is an interpreted dynamic language. To compare them is
either ridiculous, or more likely in this case, simply ignorant.
In general, sure. Ruby will afford doing some things better
than most C++ coders would (or would bother to), so it might
be worth looking into.
Plus, if one were to get the Ruby time down to 15 seconds, it
would still be worth it even if the C+±version were cut to 0.15
seconds (mainly because it would probably take at least twice
as long to implement in C++).
–Steve
E
E. Saynatkari wrote:
You could try to run your script on YARV[1] to see if it helps.
[1] YARV: Yet Another Ruby VM
E
And turn the magic opcodes on 
http://eigenclass.org/hiki.rb?yarv+ueber+algorithmical+optimization
lopex
On Feb 23, 2006, at 5:55 PM, Alexis R. wrote:
Why should that be ridiculous or ignorant?
I stated that I was aware of the differences between interpreted and
compiled languages. But that does not change the fact that I believe
that this does not explain the performance gap. An execution time of
27.65 seconds against 0.33 seconds is not just nothing is it? It’s a
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code as well and runs in a virtual machine
too,
and it executed in about the same time as c++.
Ruby’s method (function) lookup is gonna be slower no matter what
because of the typing situation. That’s probably the biggest hit
here. The C++ code can for the most part turns function calls into
jumps at compile time (excluding virtual methods, although even there
there is less indirection than ruby). Similarly for Java. Have you
tried running it in YARV?
Alexis R. wrote:
one is a relatively low-level language, compiled to native machine code,
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code as well and runs in a virtual machine too,
and it executed in about the same time as c++.
Which version of java did you use ? Since 1.4 there is a JIT compiler so
java IS compiled into native code unless you disable it explicitly.
lopex
Alexis R. wrote:
Regardless, it doesn’t matter. Algorithmic improvements may help both
that this does not explain the performance gap. An execution time of
27.65 seconds against 0.33 seconds is not just nothing is it? It’s a
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code
More ignorance. Java has a JIT compiler which produces
machine code.
From: “William J.” [email protected]
compiled languages. But that does not change the fact that I believe
that this does not explain the performance gap. An execution time of
27.65 seconds against 0.33 seconds is not just nothing is it? It’s a
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code
More ignorance. Java has a JIT compiler which produces
machine code.
Alexis,
This is usually a friendly community, by the way. :rolleyes:
But yes, it’s harder to make a language like Ruby, which is highly
dynamic at runtime, fast like C++ and Java, which are primarily
statically compiled. The Smalltalk folks have reportedly done pretty
well though, so there exists the possiblilty that Ruby may get
substantially faster in the future. YARV is already making some
headway.
Regards,
Bill
Alexis R. wrote:
More ignorance. Java has a JIT compiler which produces
machine code.
Why are you being so mean? I wasn’t aware of that.
Calm down Alexis… nobody is being mean. When someone doesn’t
understand something because they aren’t educated about it, they are
considered ignorant. There’s nothing wrong with that.
Enough people have explained the reasons for the performance gap by this
point that it should be clear. If you still need more help with this
issue, please let us know.
Meanwhile, I’m certain that none of us intended to be mean, or otherwise
attack you in any way.
–Steve
More ignorance. Java has a JIT compiler which produces
machine code.
Why are you being so mean? I wasn’t aware of that.
I was just wondering why my results were so significantly different. All
I was asking was if someone had some explanations and comments on why
that is like that. I got some nice and reasonable answers, but I got
some unkind answers too… I didn’t ask for bitter and unconstructive
comments. Did I somehow offend your honor? I did not say that ruby is
crap compared to c++ or java. I find ruby is an absolute fantastic
language. I was just surprised about my results.
Yikes! What’s with the snarkiness guys?
One thing you should consider in particular, Alexis, is the
performance impact Ruby’s objects are causing. In your C++ code, it
appears that everything’s running on the stack. The Ruby interpreter
is allocating and disposing of every object in the Ruby code onto the
heap and running garbage collection on them.
It might be worth attempting to at least change the code into
accepting Sodoku puzzles of any size (bear in mind I haven’t looked at
Sodoku solvers very much myself, so this may have all sorts of
technical challenges I’m unaware of).
100 times is normal. Just use ruby for where it works well and use
compling
language for computation-intensive tasks. If you look at other
languages,
there’s still a gap (about 5 times) between VMs without JIT and ones
with
JIT. Good news is that now we have .Net ruby bridge. Prototyping in ruby
and
optimizing critical part in .net sounds very efficient and productive.
Sky
On 2/23/06, Bill K. [email protected] wrote:
It looks, to me, like he attached his code to the OP.
I stated that I was aware of the differences between interpreted and
This is usually a friendly community, by the way. :rolleyes:
But yes, it’s harder to make a language like Ruby, which is highly
dynamic at runtime, fast like C++ and Java, which are primarily
statically compiled. The Smalltalk folks have reportedly done pretty
well though, so there exists the possiblilty that Ruby may get
substantially faster in the future. YARV is already making some
headway.
Yep. YARV does do better on this test:
YARV 0.4.0
e:\yarv\bin\ruby sudoku-solver.rb
time elapsed: 18.953 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
Regular ruby 1.8.4
ruby sudoku-solver.rb
time elapsed: 27.812 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
Alexis R. wrote:
one is a relatively low-level language, compiled to native machine code,
factor of over 80 times. Besides, I implemented the same code in java
too, which isn’t native code as well and runs in a virtual machine too,
and it executed in about the same time as c++.
Most modern Java implementations (on full computers, not PDAs and the
like) are /not/ interpreted. The interpreter compiles the bytecode into
machine code.
Furthermore, even when interpreted, Java has typed variables. A Java int
is always a 32-bit 2’s-complement integer. “i = j + k;”, where each of
i, j, and k is an int, is a simple operation involving about three
instructions in either the Java Virtual Machine or the real machine. A
Ruby variable could be an integer, a big-integer, a floating-point
number, a character string, or even something to which “+” doesn’t
apply, and, every time an expression is evaluated, that all has to be
worked out.
The convenience of Ruby, Perl, REXX, JavaScript, and similar languages
is considerable. But it comes at a price. If the bottleneck in the
program is the speed of your disk, or of your IP connection, that price
probably doesn’t matter. But if you’re doing substantial calculations in
RAM, it may not be worth it.
You can’t always generalize, though. Ruby is faster than Java at finding
perfect numbers (probably because Ruby’s implementation of big integers
is faster than Java’s), and both are considerably faster than Perl
(probably because Perl forces /all/ numbers to be big integers, if any
are) (and GNU Common LISP is faster than Ruby).