Quicksort using Crystal, the speed is not as fast as expected compare to Ruby 3.1.1

Help & Support
1

Following is quicksort i reference from Haskell.

def quicksort(list : Array(T)) forall T
  return [] of Array(T) if list.empty?

  first = list.pop
  x1, x2 = list.partition { |x| x < first }

  quicksort(x1) + [first] + quicksort(x2)
end

x = (1..3_000_000).to_a.shuffle

quicksort(x)

After build it with --release, i test it on my laptop, the average time is about:

real    0m1.674s
user    0m2.174s
sys     0m0.131s

When i switch to use Ruby 3.1.1, the average time is about:

def quicksort(list)
  return [] if list.empty?

  first = list.pop
  x1, x2 = list.partition { |x| x < first }

  quicksort(x1) + [first] + quicksort(x2)
end

x = (1..3_000_000).to_a.shuffle

quicksort(x)

real    0m8.141s
user    0m8.016s
sys     0m0.125s

As you can see, Crystal with --release flag enabled only 4.8X quickly than Ruby 3.1.1, did i do something wrong?

Thank you.

2

If just for sort number, use x.sort { |x, y| x <=> y } is more faster~

3

And the number of (1..3_000_000).to_a.shuffle in crystal code and ruby code are not equal because of shuffle .

4

depends on the workload, Ruby warms up and is eventually running basically C code
Crystal might be closer to Ruby times if you time compile + execute

the difference is no type safety, higher memory usage and in my opinion, worse syntax.

5

I think an almost 5x speed improvement is actually significant for such an algorithmic use case that can easily benefit from Ruby’s JIT performance optimizations.

2 Likes
6

I don’t have any --jit option enabled.

I run both of them like this:

  1. crystal
$: crystal build --release test.cr
$: time ./test  # run several times to get average time
  1. Ruby
$: ruby test.rb   # run several times to get average time.
7

shuffle may affect performance, but, because it only invoke once, impact is very limited, at least, I estimate Crystal should be 20-30 times faster than Ruby, it won’t affect that much.

After check pref data, it should impact not more than 10%.

8

Why?

The sorting algorithm for Ruby is written in C. The only Ruby parts of the algorithm is when the C code needs to call Ruby code for doing the comparison between elements. That part could be slower than Crystal. But the overall algorithm should be as fast as Crystal. So, as @straight-shoota said, if Crystal is 4~5 times faster than Ruby, that seems reasonable and something to expect.

2 Likes
9

Okay, Probably based on my abilities, I gave Crystal an unrealistic expectation.

as mention by @straight-shoota and @asterite , this result should be reasonable.

:grin: