Huge performance gap

ruby-talk
1

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.

sudoku-solver.rb (1.36 KB)

sudoku-solver.cpp (1.87 KB)

2

Alexis Reigel 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

···

--
Posted via http://www.ruby-forum.com/\.

3

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 Reigel <mail@koffeinfrei.org> 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.

4

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

···

On 2/23/06, Alexis Reigel <mail@koffeinfrei.org> 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

[...]

5

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, Alexis Reigel <mail@koffeinfrei.org> 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.

Thanks for comments.

Alexis.

--
Blog >>> http://spaces.msn.com/members/skyincookoo

6

Ruby *is* relatively slow, but the algorithm is the problem. This Ruby
program I wrote a while ago can solve it in under half a second:

http://po-ru.com/files/sudoku/1.0/sudoku.tar.gz

It's quite a bit more complicated, however.

Paul.

···

On 23/02/06, Alexis Reigel <mail@koffeinfrei.org> 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

7

Here is a simple graph of performance by different platforms.

http://www.usenetbinaries.com/doc/Web_Platform_Benchmarks.html

···

--
Posted via http://www.ruby-forum.com/.

8

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

9

>
> 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
>
> [...]
>

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.

···

On 2/23/06, Meinrad Recheis <meinrad.recheis@gmail.com> wrote:

On 2/23/06, Alexis Reigel <mail@koffeinfrei.org> wrote:

-- henon

--
thanks,
-pate
-------------------------

10

I can't think of a more useless "test" other than anything put out by
the Alioth shootout.

The numbers have limited interest because they're not necessarily
using the *power* of the frameworks and merely measure the response to
what is essentially a static return value. It would be more
interesting to benchmark a simple guestbook in all of the things they
did. Guestbooks are relatively easy to write and would be
significantly more "test-worthy" than a "hello world" implementation.

-austin

···

On 7/1/06, Reggie Mr <buppcpp@yahoo.com> wrote:

Here is a simple graph of performance by different platforms.

http://www.usenetbinaries.com/doc/Web_Platform_Benchmarks.html

--
Austin Ziegler * halostatue@gmail.com * http://www.halostatue.ca/
               * austin@halostatue.ca * You are in a maze of twisty little passages, all alike. // halo • statue
               * austin@zieglers.ca

11

Stephen Waits 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

···

--
Posted via http://www.ruby-forum.com/\.

12

Stephen Waits 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.

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

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++.

13

Austin Ziegler wrote:

I can't think of a more useless "test" other than anything put out by
the Alioth shootout.

The numbers have limited interest because they're not necessarily
using the *power* of the frameworks and merely measure the response to
what is essentially a static return value. It would be more
interesting to benchmark a simple guestbook in all of the things they
did. Guestbooks are relatively easy to write and would be
significantly more "test-worthy" than a "hello world" implementation.

My experience with web application benchmarks (nearly all
Windows/IIS/ASP/SQL Server and Linux/Apache 1.3/PostgreSQL/PHP) has
shown that the two most likely bottlenecks in a *real* web application
are the network bandwidth and the database. If the application generates
too much network traffic, or if its database design is poorly done, it
doesn't matter all that much whether the underlying glue logic is in C,
Perl, PHP, Python, Java or Ruby, whether the OS is Windows or Linux or
some other, or what the web server itself is. The database, on the other
hand, does matter -- a *lot*. And that, my friends, explains why Larry
Ellison is such a rich man. :slight_smile:

Having said that, the benchmark in the original poster's link, on the
other hand, measures the web server and a single module within it. I
think it's a perfectly valid benchmark for the specific web server/glue
language *component* of a web application, and I think there is a lesson
or two in the results for all of us:

1. C scales better than Perl, PHP, Python and Ruby, all other things
being equal. Make sure your C skills are up to date. :slight_smile:

2. You probably want to hold off upgrading from PHP 4 to PHP 5, and you
want to performance test before you do.

3. Unless there is some compelling *business* reason to use one of the
other technologies, you probably want to avoid anything below PHP 4 in
this chart. Programmer time to implement the application is certainly a
compelling business reason. :slight_smile:

4. The Ruby community needs to get Ruby's performance up where PHP 4 is
on benchmarks like this. It would be wonderful if it was better than
Perl and PHP, but a bare minimum is to be competitive with PHP 4.

On 4, I'm not sure a "virtual machine" is the answer, by the way.
"Virtual machines", or as I prefer to call them, "abstract machines",
were primarily intended for portability, not performance. C happens to
be a great abstract machine, and GCC happens to be a great way to
achieve portability and performance.

···

--
M. Edward (Ed) Borasky

http://linuxcapacityplanning.com

14

Austin Ziegler wrote:

···

On 7/1/06, Reggie Mr <buppcpp@yahoo.com> wrote:

Here is a simple graph of performance by different platforms.

http://www.usenetbinaries.com/doc/Web_Platform_Benchmarks.html

I can't think of a more useless "test" other than anything put out by
the Alioth shootout.

I would agree...except Ruby did VERY poorly in this "useless" test.

--
Posted via http://www.ruby-forum.com/\.

15

Alexis Reigel wrote:

Stephen Waits 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(tm).

You could try to run your script on YARV[1] to see if it helps.

[1] YARV: Yet Another Ruby VM

E

···

--
Posted via http://www.ruby-forum.com/\.

16

Alexis Reigel wrote:

Stephen Waits 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.

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

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++.

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

17

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?

···

On Feb 23, 2006, at 5:55 PM, Alexis Reigel 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++.

18

Alexis Reigel wrote:

Stephen Waits 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.
>
> 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
>
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

More ignorance. Java has a JIT compiler which produces
machine code.

19

Alexis Reigel wrote:

Stephen Waits 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.

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

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++.

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).

···

--
John W. Kennedy
"But now is a new thing which is very old--
that the rich make themselves richer and not poorer,
which is the true Gospel, for the poor's sake."
   -- Charles Williams. "Judgement at Chelmsford"

20

amen!

-a

···

On Sun, 2 Jul 2006, M. Edward (Ed) Borasky wrote:

On 4, I'm not sure a "virtual machine" is the answer, by the way. "Virtual
machines", or as I prefer to call them, "abstract machines", were primarily
intended for portability, not performance. C happens to be a great abstract
machine, and GCC happens to be a great way to achieve portability and
performance.

--
suffering increases your inner strength. also, the wishing for suffering
makes the suffering disappear.
- h.h. the 14th dali lama