14 ms·

Ruby is too slow for programming competitions

• VeejayRampay 13y ago
  Maybe the result would vary with JRuby or Rubinius (I'd be interested in benchmarks) because not only is Ruby itself not the fastest language, but its main implementation (MRI) is also not the best for speed.
  • ClifReeder 13y ago
    This is a good point that I didn't consider. Running the 'just iterate over the range version' of this code with jruby: [master] clifff@fair_and_square: ruby -v jruby 1.7.3 (1.9.3p385) 2013-02-21 dac429b on Java HotSpot(TM) 64-Bit Server VM 1.6.0_43-b01-447-11M4203 [darwin-x86_64] [master] clifff@fair_and_square: time ruby fair_and_square.rb C-large-1.in.bak real 6m39.105s user 6m37.762s sys 0m19.009s
    • aghoreyshi 13y ago
      What is sys time? The amount of time it's actually run on the processor?
      • eatitraw 13y ago
        No, it is the amount of time your program spent in system calls: http://stackoverflow.com/questions/556405/what-do-real-user-and-sys-mean-in-the-output-of-time1 http://stackoverflow.com/questions/556405/what-do-real-user-...
      • jmah 13y ago
        The amount of time spent in system calls (i.e. the kernel).
    • digger250 13y ago
      When I run the benchmark in C-ruby (2.0.0) I get: real 2m35.450s user 2m35.257s sys 0m0.139s On jruby with invokedynamic: time ruby -Xcompile.invokedynamic=true file2.rb C-large-1.in real 1m17.711s user 1m15.618s sys 0m0.830s In jruby without invokedynamic time ruby file2.rb C-large-1.in real 1m37.856s user 1m39.260s sys 0m0.854s
• ngoel36 13y ago
  Did you need to check `&& (start..finish).cover?(square)` on Line 17?
  • bvdbijl 13y ago
    nope, iterating up to the square root of finish covers that
• krubby 13y ago
  Duh, Captain Obvious is on duty.
• g3rald 13y ago
  There is a huge difference between Ruby and Go, in terms of performance. I wonder if anyone has any experience with Python, considering that both are interpreted programming languages.
  • gtaylor 13y ago
    CPython is a bit faster than Ruby, but I'm not sure it'd be drastic enough of a difference for it to be much better in the author's case. Porting his code to PyPy would be very interesting, though.
  • bvdbijl 13y ago
    In my experience the speed decrease isn't worth it during competitions. I heard some talk about allowing Python at the International Olympiad in Informatics http://www.ioinformatics.org/index.shtml http://www.ioinformatics.org/index.shtml (in addition to Pascal and C(++)) but that's probably far off
  • jdotjdot 13y ago
    I've has decent experiences with Python in Google Code Jam, with two exceptions. (1) Python can't handle large numbers, so the mere existence of huge integer inputs for the large prime number problem blew up my code since Python could not convert numbers that large. (2) Python is fine with math, but at a certain point of data accumulation, performance just plummets, no matter how good your algorithm is. Overall, though, I haven't had the experience the parent comment did. Either Python works beautifully or it literally just doesn't work, rather than take an hour. I treat it as a challenge, though, as it forces me to be smarter about my implementation.
    • minopret 13y ago
      (1) In what sense do you mean "Python can't handle large numbers"? time python -c 'print (5**(5**5))*(3**(3**3))' \ | python -c 'import sys; print hex(int(sys.stdin.read()))' \ | wc -c 1829 real 0m0.091s user 0m0.149s sys 0m0.027s
    • Luyt 13y ago
• hayksaakian 13y ago
  * competitions based on speed of computation. I'm sure if the competition was based on speed of implementation there would be different conclusions.
  • jdotjdot 13y ago
    It sort of is, there is a submission time penalty.
  • schmrz 13y ago
    Given two developers, one proficient in Ruby and one in Go there would be probably no difference in implementation time for such a trivial problem.
  • yen223 13y ago
    It is, in a sense. The later rounds only give you 2.5 hours to implement and execute your solution to the problems. Thing is, you are competing against folks who can write complex C++ algos in under 10 minutes!
• electrograv 13y ago
  Wow, 5 minutes in Ruby, and less than a second in Go? I know scripting languages are slow, but it's easy to forget just how much slower. (EDIT: Corrected misread number thanks to dljsjr). I don't want to detract from the article's main point with a cliche "algorithmic optimization beats fine tuning", but I think it's worth mentioning. Unless I'm mistaken, this particular problem can be solved about 10,000,000x more efficiently. > Given two numbers X and Y, return how many numbers in that range > (inclusive) are palindromes, and also the square of a palindrome. I would just count the digits of X and Y, then ranging between those counts, apply the following algorithm: For N digits, enumerate all numbers of N/2 digits satisfying the bounds X and Y. If N is even then simply mirror the first N/2 digits. If N is odd, mirror the first N/2-1. Finally, check the bounds of the resulting number against X and Y to filter out edge cases. If the original algorithm runs in 10^N time, this would be 10^(N/2). For N=14 as mentioned, that's roughly a speedup of 10,000,000. Edit: It seems I misinterpreted the question (which sounds like you're supposed to enumerate all palindrome numbers X>=N>=Y, and also print out the squares of those numbers). This is actually asking for a particular type of palindromes -- those which are palindromic squares of palindromes. As macobo helpfully points out, you can drastically optimize mathematically from this additional filter.
  • dljsjr 13y ago
    No, 5 minutes in Ruby vs < 1s in Go. OP's last benchmark was only for the iteration part. Look just above it and he posts the Ruby times at around 5m. Still, pretty drastic.
  • macobo 13y ago
    This problem has a quite elegant solution - Suppose you know the fair palindromes (is a palindrome and a root of a palindrome) of length 2*k. Then you can add either a single digit or double that to the center, and test if it's fair. This algorithm generates all the fair palindromes. https://gist.github.com/macobo/5430510 https://gist.github.com/macobo/5430510 By memory, there were under 50000 such palindromes in range 0..10^100.
    • anonymoushn 13y ago
• jt2190 13y ago
  The article doesn't actually say that performance was one of the judging criteria, and I'm unable to find anything in the code jam rules about this. Can anyone here clarify?
  • chengsun 13y ago
    Once you request to download the input data there is only a short (8 minutes IIRC) window of time during which you can upload your output data. Therefore your program must run within that time period.
  • ClifReeder 13y ago
    Performance isn't a judging criteria, other than you need to be able to provide the proper output from a given input within a certain number of minutes. For this problem, it had to be within eight minutes.
  • mrgordon 13y ago
    Performance is not technically a criteria but you have eight minutes from the time you download the input data until you have to be done uploading the output data. So if you spend 50 minutes incrementing integers, then you'll get 0 points no matter what :)
    • jt2190 13y ago
      Thanks!
  • yen223 13y ago
    Not for the qualification rounds, but in later rounds, the winner is the person who gets the most number of points first. It won't come to any surprise that the finals tend to be dominated by C++.
• macobo 13y ago
  In this context, no it's not. One thing that Code Jam does differently (and imho better) is that they give you an input set and you have 8 minutes (or so) to upload the solution. This is expected to give more than enough space for language speed variance. Instead of execution time, coding time is much more precious in such competitions, and Micro-optimizing has it's place, but it's usually not in a programming competition. that's what using ruby instead of C gives you leverage for that, as you can express more complex ideas and algorithms more easily (which should be the focus point). This doesn't mean you shouldn't know the cost of operations.
  • mrgordon 13y ago
    Coding time was actually not precious here. They gave about a day to do the qualification round but only eight minutes to run your program once you downloaded the input data, so the round was optimized for writing highly performant code at your leisure and then downloading the data when you are all set to go.
  • yen223 13y ago
    "Instead of execution time, coding time is much more precious in such competitions" Unfortunately, in such competitions you'll be competing against people who write C++ algos faster than normal people writing Python.
    • macobo 13y ago
      That's because most contests (but not all) are limited to C, C++ and Java and they've practiced hundreds if not thousands of hours on solving those kinds of problems. Of course they will be more efficient in c++ than a person who is spending most of their time wondering how costly string operations are. That doesn't mean that there aren't also people who have done the same and still prefer python (or some other language) not for execution, but development speed (and bignum, larger standard library...)
• andrewcooke 13y ago
  most numbers are not palindromes. so generate palindromes, and then test.
  • mrgordon 13y ago
    yes exactly, this is how a friend did it in jruby (he got a perfect score)
• dllu 13y ago
  It is true that Ruby tends to be slow for programming competitions, especially if the computation is done serverside such as Codeforces.com. Notice that your solution runs in O(sqrt(N)) time. If N were up to 10^14, with 10^3 test cases, then your solution could have to deal with up to 10^10 iterations... which is dangerous even for a fast language (since your CPU can only do about 10^9 things per second). As a rule of thumb, one should only ever deal with at most 10^8 things. Even just incrementing an integer 10^10 times can take some time (fortunately, not every one of the test cases were 10^14 so your Go solution took under a second). However, Problem C of Google Code Jam qualification 2013 can be easily solved, even with a slow language, by making some observations: 1) Instead of iterating through numbers and checking if they are palindromic, you can just iterate through the numbers with half the number of digits and generate the palindrome by mirroring the half. A naive solution that uses this would run in O(N^(1/4) log(N)^1.6) instead of your O(N^(1/2) log(N)^1.6) solution. (The log(N)^1.6 is due to the time taken for multiplication, assuming the Karatsuba method). 2) With a small amount of math you can figure out that for any fair and square number N = MM, then for any digit s in M, we must have s(sum of all digits in M) < 10. Thus solutions are of the form: case 1) Contains up to nine digits 1. (e.g. 101, 111111111) case 2) Contains up one digit 2 and up to four digits 1. (e.g. 1002001, 2) case 3) Contains up to two digits 2 and up to one digit 1. (e.g. 200010002, 202) case 4) Contains one three. (i.e., just 3) A naive solution using observation 2 may run in O(log(N)^5.6) time. 3) Use combinatorics to figure out count the ways to arrange the digits in the 4 cases shown above, rather than iterating through them. As it turns out, it is unnecessary to do this since even using an O(log(N)^6) solution I passed the 10^100 input. Since there are only about 40,000 fair and square numbers from 1 to 10^100, you can easily precompute them and find them by binary search.
• anonymoushn 13y ago
  If you precompute the palindromes in the range, store a table of prefix sums, and calculate each of the 10,000 cases in constant time it will probably pass (in ruby). Edit: as electrograv pointed out, another optimization is to generate palindromes from sqrt(start) to sqrt(end) rather than testing each number in the range for palindrome-ness. This saves you a factor of 10^3.5.
• nikic 13y ago
  I also come to the conclusion that Ruby-like languages are just not the right tool for this kind of problem, but it should be pointed out that you would have been able to solve the 10^14 data set easily, even with Ruby. I was solving that problem with PHP and got it running reasonably fast (1s per range) for ranges up to around 10^60. PHP is probably faster than Ruby, but it's still in the same area. The first trick you can use is that you don't have to go through all numbers between start and end, rather you can directly only traverse the palindromes (i.e. you will only have to increment one half of the integer). The second trick is that only numbers consisting of 0s and 1s (and a 2 at the start/end or the middle) can satisfy the condition (exception: the number "3"). This further massively reduces the search space. There are more criteria that you can use to narrow down the numbers to consider (e.g. the number of non-zero digits can't be greater than 9). But in the end, cracking the 10^100 range is probably not possible in a language like Ruby or PHP. Using something like C++ on the other hand it becomes a triviality.
  • bvdbijl 13y ago
    Yep, in a competition you want a language that had as little magic as possible. Languages like Ruby (not necessarily dynamic languages!) are just not really suitable for it
    • nossralf 13y ago
      Wouldn't you want to use a language that is familiar in a competition? If Ruby is your forte, surely you should use it? I fail to see how "magic" properties of a language matter if you've got reasonable algorithmic chops and focus on solving the problems rather than trying to be clever.
      • trailfox 13y ago
        > Wouldn't you want to use a language that is familiar in a competition? If Ruby is your forte, surely you should use it? If you're familiar with knives why not bring a knife to a gun fight? If knives are your forte, surely you should use it?
• bambax 13y ago
  I'm not a rubyist but it appears the OP was doing something like this: for each range (start to sqr(end)) for each number in the range check if the number is fair and square If you do this you're checking the same numbers many times (total count of numbers checked is over 3 hundred million calls...) The right approach is to first compute all fair and square numbers between 0-10^14, store the result, and then simply check how many are found in each range. It turns out there are only 39 fair and square numbers between 0 and 10^14. I participated in Code Jam 2013 and passed the qualification round using Python; after precomputing the fair and square numbers, checking ranges was pretty much instantaneous (for large input 1).
  • eric970 13y ago
    Sounds right to me as well. But hey, isn't it much easier to blame the language and its VM? Or interpreted languages in general?
  • Luit 13y ago
    A slightly more interesting approach: find out all non-overlapping ranges you need to test, and then run the fair-and-square generator, testing each to check in which of the ranges it should be put, finally combining the sub-ranges to make the ranges asked for. My (not particularly optimized) Go solution ran through the C-large-1.in set in 3 odd seconds.
• deleted 13y ago
  [deleted]
• thinkpad20 13y ago
  This is a problem which is CPU-bound rather than IO-bound. Ruby, Python and the like won't typically show a great difference in speed when the majority of time is spent in IO operations (like web crawling, or text processing, running web apps, querying databases, etc), because the bottleneck on performance comes mostly from the slow reading of files and network sockets. In this case, though, the operations are mostly dependent on just doing computation, so a high-level interpreted language like Ruby really shows its limitations. This is one of the (many) reasons why although languages like Ruby and Python are great for rapid development, on-the-fly updates and other reasons, it can pay dividends to be fluent in a high-performance language. It wouldn't even need to be C (although this wouldn't be hard to do in C) -- a language like D would give you excellent performance and nearly as easy development as Ruby.
• xyzzyz 13y ago
  Sure, I knew Ruby wasn’t going to be zomg fast, but I always assumed that if I chose the right solution and wrote in an efficient manner (memoizing, storing values/lookups that would be used later, limiting search spaces, etc), my ability to write code quickly and concisely mattered more than sheer processing speed. I was wrong. Sure, the author is wrong, but not because Ruby is slow (it is, though). He's wrong, because he did not find the right solution for the problem. Instead, he wrote a brute-force solution with a simple optimization, and did not realize that this is the real cause of his code under-performing, blaming the Ruby's slowness for it, when he really should have blamed the Dunning-Kruger effect.
  • deleted 13y ago
    [deleted]
  • ConceitedCode 13y ago
    Even if he did brute force it, he did the same thing with Go and it was much faster. So by comparison Ruby is slow and his conclusion is sound. Yes he could have optimized it, but that just means he could of optimized the Go solution too.
    • klochner 13y ago
      Let's consider his conclusions: ruby is slow: sound ruby's slowness is his main problem: not-sound He's not going to win programming contests with brute-force solutions. Even his brute-force method makes unnecessary computations - why keep running after n^2 is out of range? > memoizing, storing values/lookups that would be used later, limiting search spaces, etc He did none of that. Kudos to OP for benchmarking & profiling though -- the speed of Go is impressive.
    • ekr 13y ago
      In fact I don't think his conclusion is sound. If you're into algorithmic competitions you most likely don't need to change the language. If you devise a solution with a good enough complexity, the competition (if well designed) should allow enough time for the execution of that (near-)optiumum solution, while not awarding points for solutions which are asymptotically worse. The time taken by algorithms with different complexities vary with the size of the input, as a nonconstant function, while implementing the same algorithm in different languages will give you a difference of a constant factor. What I'm trying to say, (stating the obvious): When the input is large enough, it doesn't matter what language you're programming in. And programming competitions should (and generally do) only focus on that. But I'll admit that I'm a huge fan of optimizing my algorithms with bit-level operators, extreme care of memory allocation and other tools C offers.
• deleted 13y ago
  [deleted]
• codeonfire 13y ago
  Ruby is too slow for brute force solutions for programming competitions. If you look at the third set of cases, the inputs could have a range 0..10^100. Even with the square root, any solution that is going to check 10^50 numbers/strings is going to take a very long time in any language.
• ClifReeder 13y ago
  Hey everyone, thanks for all the input on this. As I mentioned in the post, programming competitions aren't my forte, and I have a lot to learn in that arena. All the feedback on how this should have been done more efficiently is great. In the future, I obviously need to work on coming up with better algorithms for solving these kinds of problems, but I'll probably continue to try and use Go because it's nice to have that fallback to sheer speed when my algorithm isn't great.
  • anonymoushn 13y ago
    This is definitely a good idea. As the responses here demonstrate, there are many different and independent optimizations available for solving this problem, so it can be useful to fall back to a faster language if you are having a hard time improving your solution.
  • Lonny_Eachus 13y ago
    Just a suggestion, but I would also give some thought to efficient coding style, not just algorithms. For example, you could have speeded up your I/O dramatically.
    • Lonny_Eachus 13y ago
      Correction: I benchmarked the I/O improvement I was thinking about. It actually only resulted in an improvement of about 30%. Worthwhile, probably, but not as "dramatic" as I thought it would be. Mea culpa.
      • hsitz 13y ago
        I think that 30% improvement you're referring to must be for just the i/o itself. Given that the i/o for the problem amounts to less than 1/1000th of the processing time, a 30% improvement is basically irrelevant. It doesn't help much to speed up something that's not even close to being a bottleneck. I think many of the best algorithm contest coders just use whatever i/o method uses the least code, keeps their answers simple and clean.
      • 13y ago
• trailfox 13y ago
  From the post... Running time: Ruby: 3180 seconds Ruby (profiled and optimized): 342 seconds Go (first attempt): 0.7 seconds
• deleted 13y ago
  [deleted]
• mschuster91 13y ago
  So, please, would those who worship Ruby and flame against PHP now shut up when flaming for performance issues? I know that I'll lose my fresh 100 karma points for this, but it's time to lay the dogmatic flames aside and talk about the real issues and how to solve them. For example, a JIT compiler could greatly help core PHP.
• bajsejohannes 13y ago
  For comparison, I translated it pretty directly to Python: import sys from math import sqrt def string_palindrome(num): s = str(num) return s == s[::-1] sys.stdin.readline() # throw away first line (number of cases) for count, line in enumerate(sys.stdin): found = 0 start, finish = [int(num) for num in line.split(" ")] sqrt_start = int(sqrt(start )) sqrt_finish = int(sqrt(finish)) for x in xrange(sqrt_start, sqrt_finish+1): if string_palindrome(x): square = x * x if string_palindrome(square) and start <= square <= finish: found += 1 print("Case #%d: %d" % (count, found)) For the first 15 test cases I get the following run times: pypy 2.0-beta2: 1.6 seconds pypy 1.9: 2.1 seconds ruby 1.9.3p194: 3.7 seconds python 3.3.0: 5.9 seconds python 2.7.1: 6.2 seconds The integer version for checking palindromes was also much slower in python. Edit: Even though the interger version of _palindrome is slower in pypy, there's another optimization that works there, but is slow in cpython. It brings the run time down to 0.6 seconds! def half_string_palindrome(num): num_str = str(num) num_len = len(num_str) for i in xrange(0, num_len // 2): if num_str[i] != num_str[num_len - i - 1]: return False return True
  • raverbashing 13y ago
    Check with PyPy if you can
    • afeezaziz 13y ago
      I have tested PyPy and think that it is good that I would be able to use Python to write faster loops.
    • TillE 13y ago
      I just tested, and it should be about 6x faster than Python 2.7. About 1.0 second for the first fifteen cases.
    • bajsejohannes 13y ago
      Good idea! Updated results.
• MaxSize 13y ago
  EventMachine helps with performance critical Ruby code
  • atdt 13y ago
    It wouldn't have helped in this case.
  • clarle 13y ago
    You're right that EventMachine helps when you're dealing with IO-limitations (like those commonly found in web applications), but for CPU-limited functions like the ones that you see in programming competitions, it's not going to provide much of a benefit.
• deleted 13y ago
  [deleted]
• minwcnt5 13y ago
  The following site allows you to search for people's solutions by language: http://www.go-hero.net/jam/13/solutions http://www.go-hero.net/jam/13/solutions There are actually several people who solved this problem (including both large inputs) using Ruby. And for those asking about Python, most Code Jam problems are apparently calibrated to be solvable using Python. Keep in mind that it's one of the languages Google uses internally and Guido used to work there, so they probably want to support it. From https://code.google.com/codejam/problem-preparation.html https://code.google.com/codejam/problem-preparation.html: "Where possible, if you allow multiple programming languages, make it so that all languages are fast enough to solve the problem. Occasionally that's impossible; in Code Jam we generally calibrate by making sure a somewhat optimized Python program can solve a problem. Sometimes, though, there's just no way to have Python succeed with the best algorithm and C++ fail with a worse one. In those cases we'll typically decide that sometimes in life, you just need to use a faster programming language. We try to avoid making that decision if we can."
• moron4hire 13y ago
  These sort of contests are not tests of speed of computation, they are tests of algorithmic knowledge. The final data sets will (usually) all be designed to make even the most optimized implementations of the wrong algorithm fail.
• davidw 13y ago
  Great, so stop dicking around with some zero-sum game ( http://en.wikipedia.org/wiki/Zero%E2%80%93sum_game http://en.wikipedia.org/wiki/Zero%E2%80%93sum_game - a competition may only have one winner ) and go build a business, where no one cares what language you use as long as the solution works for your customers - and there can be more than one winner in many cases. Or even if you don't have a side project or startup or something, go build something cool and open source it and do that, rather than working on some artificial problem. You can click the little down arrow all you want, but it won't keep me from thinking you're mostly wasting your time with these competitions, and it won't put any money in your pocket.
  • Karunamon 13y ago
    You realize this is mostly a type of game right? "Do X task the best way you know how". If you think games are a waste of time, welp. I'm clicking the down arrow, because not only are you being a dick, you're adding nothing to the discussion.
    • davidw 13y ago
      I think it adds a lot to the discussion to point out that games are just games and that in the real world, the speed of a language's implementation may not be what actually matters, at all. No thanks for the name calling.
  • consz 13y ago
    Games are more interesting than businesses or open source. Have you never encountered someone with a different opinion?
  • geedy 13y ago
    Curious, would you call University education dicking around as well? Seems to me challenging the brain is never a waste of time. We would not have some of the medical technologies we have today if it were not for massively parallel GPUs, which of course were developed for the sole purpose of playing games.
    • 13y ago
• mseepgood 13y ago
  Idiomatic Go tip: you should use more type inference via := instead of declaring all variables at the beginning of a function. And use gofmt :)
• deleted 13y ago
  [deleted]
• joydeepdg 13y ago
  Remember PAPP[1] [1] Richard Buckland's awesomeness - http://www.youtube.com/watch?v=JTAkUs-NjxU#t=44m21s http://www.youtube.com/watch?v=JTAkUs-NjxU#t=44m21s
• RyanZAG 13y ago
  A lot of people are talking about the problem itself - which is interesting - but very often you run into real problems which cannot be simplified so easily (NP hard problems, many different other cases). In addition, when you need to do important calculations on a server for your product and you're using Ruby, you may very well end up requiring 10x as many servers. This is pretty massive when you consider an AWS server can be $350/month with Go (1 large instance), and then $3,500/month with Ruby - if you can even parallelize your problem that well - generally you can't. That's a lot of startup runway being eaten for not that much benefit. Of course, most products don't really need to do calculations outside of a database and this is why Ruby has taken off so well - but it's still important to realize that choosing Ruby over PyPy/Go/Whatever really can be a very expensive choice in the long run when your product suddenly relies on some unique math solutions, and having half your product in Ruby and half in C is awful to have to deal with. The solution to this is a project like PyPy for Ruby, but it doesn't seem to be coming...
  • nossralf 13y ago
    Topaz [1] is a Ruby implemented using RPython (so it uses the same JIT mechanisms as PyPy). [1] http://docs.topazruby.com/en/latest/blog/announcing-topaz/ http://docs.topazruby.com/en/latest/blog/announcing-topaz/
  • Derbasti 13y ago
    > having half your product in Ruby and half in C is awful to have to deal with. Why? In many cases, only a tiny fraction of your code needs to be fast. In my experience, it is very reasonable to code that part in some fast language while delegating the bigger (and often more complex) part in a higher level language such as Ruby.
    • danking00 13y ago
      Seconded. I recently wrote a image searching program (find a set of images as sub-images in another set of images) and I wrote most of it in Racket (Scheme dialect). I wrote the inner loop to calculate the correlation matrix in C and made an FFI call. I'm not familiar with Ruby's FFI, but I found making FFI calls dead simple in Racket.
• rsiqueira 13y ago
  Even using the same algorithm implementation, there is a huge speed processing difference between languages. For example the implementation of the Mandelbrot algorithm in RUBY takes 47 MINUTES to complete, while it takes LESS THAN 30 SECONDS when doing the same computation using much faster languages such as JAVA, SCALA, C or FORTRAN. According to this performance test, those languages are more than 100 times faster than Ruby, Python or Perl. Source: Computer Language Benchmarks http://benchmarksgame.alioth.debian.org/u32q/performance.php?test=mandelbrot http://benchmarksgame.alioth.debian.org/u32q/performance.php... Other benchmark speed comparisons between programming languages, showing similar results: http://benchmarksgame.alioth.debian.org/ http://benchmarksgame.alioth.debian.org/
  • igouy 13y ago
    > between languages Between specific programs, using specific programming language implementations.
• gnuvince 13y ago
  I'm sorry, but is the Go program correct? I ran it on my machine, and for Case #1, it reports a solution of 1, while there are actually 19. EDIT: I modified the Go program to use int64 instead of int (the upper bound of the first case is not a valid 32-bit integer), and the execution time is now much higher: 2 minutes 41 seconds on my laptop.
  • darkgray 13y ago
    Go 1.1 made int default to int64, so it may depend on how up-to-date your particular version is. God knows what the blog poster uses, though.
    • gnuvince 13y ago
      I'm still on Go 1.0.2. However, I strongly doubt that having 1.1 yields the correct result in the amount of time that the article boasts; I rewrote the program in C (direct translation), and with both clang and gcc, I get timings of around 2m05s. It's hard to believe that for a CPU-bound task, a Go program would be 200x faster than a C program.
      • darkgray 13y ago
        I'd agree it's dubious, but I was mostly commenting on the "correctness" of the code. It'd work on Go 1.1, so it's technically "correct". Sometimes. :)
        • gnuvince 13y ago
          Fair enough.
    • voidlogic 13y ago
      That is not quite right, before 1.1 int was 32-bit on all platforms and post 1.1 an int is 32-bit on 32-bit platforms and 64-bit on 64-bit platforms. You are supposed to use int when you don't care about its size (int = native word size). If you are writing a program where it matters you should explicitly use int32 or int64.
• sspiff 13y ago
  I have noticed a similar thing recently. A programming challenge with a 10s max time restriction, and just reading the input and storing it in an array takes over 7 seconds. I allocate the array ahead of time, as soon as I know the size. The equivalent C/C++ version took under a second.
  • yxhuvud 13y ago
    How did you read the input? All at once or one line at a time?
    • sspiff 13y ago
      One line at a time. Is that significantly slower for stdin? I would assume that this wouldn't make a difference, since we're talking about simple memory operations, and 20k method invocations shouldn't be that hard on a modern system.
      • yxhuvud 13y ago
        stdin? No, that shouldn't matter then, but it would if you were reading from file.
• voidlogic 13y ago
  Many people seem to be asserting just because the OP's algorithm was sub-optimal, that it means his Ruby code running slow vs Go is a non-issue. The problem is even well written Ruby vs Go has the same kind of performance divide: http://benchmarksgame.alioth.debian.org/u64/benchmark.php?test=all&lang=go&lang2=yarv&data=u64 http://benchmarksgame.alioth.debian.org/u64/benchmark.php?te... (All the usual benchmark disclaimers apply, your mileage may very, your app is always the best bench, etc etc.)
  • igouy 13y ago
    > All the usual benchmark disclaimers apply... The actual disclaimers shown on the benchmarks game website apply ;-)
  • estavaro 13y ago
    Ruby is said to be useful for text processing and such. In Japan they had a need for the language to deal with text files specified in a Japanese codeset. Some of the flexibility to support different codesets cost Ruby a little. For Ruby 1.9 and 2.0, Matz took a while in the transition to "Unicode" support in order to keep some flexibility, even though many people preferred the old way of UTF8 and so on. Ruby is best when it's used for the things it was meant for, but that hasn't kept people from trying to use it for more stuff. That's how Ruby found a good use in servicing web apps, first with CGI and then with dedicated instances in Rails and the like. Now with Dart I understand that people demand languages be architected in different ways to extract more performance from them. Dart doesn't have "eval", for example. Whereas Ruby and Javascript do. The question though is one of a divide, between the people who would never use Ruby or JavaScript and those who do use and love those languages that come with a lot of flexibility from the core. Python is like Ruby and JavaScript, even if the Python syntax could be borrowed for different languages that are more restricted in what they offer.
    • fosap 13y ago
      I don't see the point with eval. Every lisp has a eval, and most AOT Lisps are faster than ruby. Not including eval seems to be a "discipline and bondage" fetish of language designers. Yes, you can write pretty awful code with eval. But it allows metaprogramming aswell. I'd like to judge if something is awful or awesome.
• spyder 13y ago
  https://news.ycombinator.com/item?id=5304873 https://news.ycombinator.com/item?id=5304873
• isuckcocks 13y ago
  >Ruby is too slow for programming competitions You are too dumb for programming competitions.
• wting 13y ago
  First of all, there are plenty of people who solved both large inputs with Python/Ruby (with and without pre-computing all the fair and square numbers).[0][1] As others have stated, the contests are designed such that language shouldn't matter and problem sets are deemed solvable with Python as a baseline. For this particular question, the official contest analysis goes into detail on how to reduce the solution space: https://code.google.com/codejam/contest/2270488/dashboard#s=a&a=2 https://code.google.com/codejam/contest/2270488/dashboard#s=... Now the issue becomes the trade off between development speed vs runtime performance. Is it possible that you might solve the problem with a worse solution in a better performing language? Yes. Is it possible you might finish a solution within the time constraints in a more expressive language? Yes. If something is CPU bound in production, then going with a better performing language is a viable consideration.[2] However, my goal in programming contests is often to become a better programmer in the process. As a result, I choose to focus more on improving algorithmic complexity which is language agnostic. [0]: http://www.go-hero.net/jam/13/solutions/0/3/Ruby http://www.go-hero.net/jam/13/solutions/0/3/Ruby [1]: http://www.go-hero.net/jam/13/solutions/0/3/Python http://www.go-hero.net/jam/13/solutions/0/3/Python [2]: For the pedantic, I understand that language performance is different from implementation performance. Edit: Corrected links, thanks victorhn.
  • victorhn 13y ago
    Correct Link for [0] is http://www.go-hero.net/jam/13/solutions/0/3/Ruby http://www.go-hero.net/jam/13/solutions/0/3/Ruby And the most difficult version (L2) was solved by 19 contestants.
• Aaronneyer 13y ago
  The Go solution is incorrect. It's not using int64, and most of the finishes are bigger than a 32bit int. If you run it on the following input: """ 2 8 10000200002 1 500 """ You will see that the loop that runs from start to finish is not running on the first case, because it sees the finish as 0. Haven't tested it using int64, but I would imagine it would be much slower(Still a decent bit faster than Ruby presumably), because any heavy computation for this problem was removed.
  • gnuvince 13y ago
    I noticed that as well [1], and rewriting the code to use int64 (and thus cover the entire range) makes the Go code run in 2m40s. Still faster than Ruby, but not as incredible as the author thought it was. [1] https://news.ycombinator.com/item?id=5586152 https://news.ycombinator.com/item?id=5586152
  • dmm 13y ago
    As of golang 1.1 the size of "int" on 64bit archs is now 64bit. That's probably why it worked for him.
• pieguy 13y ago
  I participated in this contest, and solved this problem. The problem with the post is that it's basically saying "This correct ruby program is way slower than this incorrect go program, therefore ruby is bad for programming competitions". Obviously not a valid argument.
• deleted 13y ago
  [deleted]
• justplay 13y ago
  > TL;DR. Ruby is optimized for developer happiness, not machine happiness. sounds good . I am ruby happy developer .
• moron4hire 13y ago
  Also, if you ever think you need built-in support for large numbers in your programming language during one of these contests, then you're using the wrong algorithm. These contests are typically designed to be doable with very, very simple code using primitive data types.
• lectrick 13y ago
  Couldn't someone implement a Ruby CLANG dynamic runtime recompiler?
• bbwharris 13y ago
  He did everything right. Tried it in ruby, if it would have been fast enough this article wouldn't exist. Instead he applied good software engineering and found the right tool for the job. This doesnt say "don't use ruby it's too slow". It's says prototype in your comfort zone and optimize. Isn't this what we all agree on? Edit: auto correct fail.
• tonycoco 13y ago
  This whole, "Ruby is slow," diatribe is just ridic. Everyone here that has done any C/C++ or Ruby development would probably agree that if you're looking for number smashing, Ruby is just not cutting it unless you're into rockin' C extensions and getting what you want... for now. Ruby, within a few years, will probably have some VM action, whether the JVM with JRuby or Rubinius wins out, who cares. In any case, in like 5 or 6 years when we all have 50/100 core machines, Ruby's gonna be just fine for almost everything. Maybe by then we will be done arguing and just agree that Ruby is the nicest language to look at and develop in, even if it has subpar performance. Because if you're arguing something different, you've probably never gone from Ruby to C or Java or even Python... just so you all know, it blows.
  • mitchi 13y ago
    Tim Sweeney predicted that we'd all have 20 core machines with 80 hardware threads by 2009. Not really what happened. The whole point is that while Ruby is nice, it's just too slow. Someone is better off investing time learning a faster compiled/JIT language.
    • cheald 13y ago
      Too slow for what? Certainly not all classes of problems. Heavy mathematical work (every number in Ruby is an object! That's going to be much, much slower than a C primitive!), sure, but there are lots of folks using it quite happily to solve a wide range of problems.
      • tomrod 13y ago
        How does Ruby scale? - Not-a-Rubyista
• cbolat 13y ago
  Ruby is uber fast for hipsters..
• frogball 13y ago
  Isn't it obvious that there must be a better solution to the problem then your solution? You shouldn't try to find the palindromes, but rather generate them.
• calinet6 13y ago
  From the edits: "If you are like me and don’t always come up with the best solutions, you may want to consider other languages too." --> "You may always want to consider other languages too." No one should ever agree with an ultimatum on language choice: if you need hardcore speed, use a lower-level language, not an interpreted garbage-collected scripting language. Duh.
• deleted 13y ago
  [deleted]
• ksec 13y ago
  I am risking myself getting insanely downvoted for writing this. But I hope it at least gets some of the attention. I really hope the Ruby Communities do actually admit Ruby is Slow. Because until you actually admit there is a problem, there will never be any notion of wanting to fix it. Most of the time, they will come up with Rails Examples or serving dynamic web pages, and the bottleneck being in Database. And the higher amount of request you get, you can solve it with caching. This is, in my view a very limited scope of Ruby usage. They deny any wrong doing of Ruby, suggesting it is a dynamic languages, and it's wrong comparing to a compiled languages, or the algorithm are done wrong. They keep suggesting under xxx usage, Ruby is fast enough to get the job done. Then there is the argument of throwing more money and hardware to grow and scale. But the truth is most of time Ruby will require more then a few dedicated servers to keep going. While it is not as drastic as the iron.io 28 to 1, but for startup lowering running cost is important too. Then there is this arguments comes up which i hated most. You are not going to worry about the need of that many servers, or scaling that needs to change to another languages unless you are AirBnb, Twitter etc..... I mean what? I am sorry i may not have worded it correctly but most of the time those read like you are never going to be successfully that you are very unlikely to have to worry about. Performance is important!. And for most this isn't about pushing it to Javascript V8 or insane 1000x programmer Mike did with LuaJIT. It is just Ruby should have a more respectable performance VM. While Ruby is designed to make programmers happy, I am pretty sure there are many aren't happy with its basic performance.
  • camus 13y ago
    PHP and PYTHON are slow too. Like them Ruby can take advantage ) of C extensions. You cant write everything in ruby like PHP developpers use native drivers for database communication , compression , image manipulation ,etc ... that's normal. Scripted languages should be used for what they are for , a thin layer on the top of other more performant languages. Like Twitter , Ruby/Rails allowed them to bootstrap their idea ,"probe" a market, make it work , then they thought about performance and scaling. That's what scripted languages are for.
    • dmpk2k 13y ago
      Yes, but I think what ksec was driving at is there isn't an intrinsic reason what you said should be true. Why should Ruby (and scripting languages) be used for RAD and not performance? That's because implementations range from really slow to somewhat slow. Self, LuaJIT, V8 and IonMonkey, and increasingly PyPy are ample evidence that this need not be the case, and that's just listing the dynamically-typed languages. The bar has been raised the past few years. Increasingly we can pick three of: productivity, libraries, performance. Ruby lacks the last, which makes it a less interesting prospect for future greenfield projects compared to its competition.
• kyllo 13y ago
  So you wrote a brute-force algorithm in a slow, interpreted implementation of a dynamic language, and you were surprised that your solution took a long time to run? Using a faster language implementation could have allowed you to use the same brute-force algorithm and come in under the time limit, but your real problem is your algorithm, not your language implementation. You can write fast code in a fast language and get very fast running time. You can also write slow code in a fast language, or fast code in a slow language, and still have acceptably fast running time. But you wrote slow code in a slow language, the worst of both worlds.