Ruby is too slow for programming competitions • Hacker News Board

Re: Ruby is too slow for programming competitions

#211

Post by TikiTDO » Mon, Apr 22, 2013, 5:10 AM UTC

timr wrote: post #195

vidarh wrote: post #157

Earlier quoted context omitted.

I have tried it. My MSc dissertation required a lot of computation (weeks of runtime after I'd rewritten critical portions in C++), and I'd do it that way again. For many types of problems, putting the data into an efficient format before passing it to your C/C++ code is trivial in terms of both difficulty and time spent. I prototyped everything in Ruby, profiled, and then rewrote a handful of the critical parts in C…

I've done it too, and I think most of the responses to the GP are missing the point. Can it be done? Sure. But it's a pain in the ass. It's not nearly as trivial as people suggest. It's basically only worthwhile when you know you have the resources to build an infrastructure of re-usuable fast modules that get coupled with a scripting language interface. Even when you give up on writing true "hybrid" code (i.e. "just…

I would venture to say the triviality of writing hybrid code is a function of how often you have done something similar, and how well you understand the underlying principles. This is really the case with any software problem.

Ruby provides some very useful features, but a lot of those come at rather high costs. Those costs are exacerbated if you do not understand how the internal components of the language are laid out, and the purpose behind this layout.

Ruby tries to be a lot of things to a lot of people, so then when people learn how to use it for one task they automatically assume that their skills will carry over. This sort of approach might work reasonably well with a straight-forward compiled language, but this it simply can't be that easy for an interpreted language like ruby, with it's reams of special context sensitive behaviour.

For example, consider the "pointers to pointers to pointers" complaint. Nothing is stopping you from having a low level C struct for all your performance sensitive data. Granted, you would have to write a ruby wrapper for this data for when you need to export it back out to ruby, but wrapper generation could be automated.

Sure, you could just say, "You know what. I'm just going to use C" but what if your project could really use some of those ruby features outside of the performance sensitive parts of the code? It's always a tradeoff.

Re: Ruby is too slow for programming competitions

#212

Post by codygman » Mon, Apr 22, 2013, 5:10 AM UTC

bajsejohannes wrote: post #53

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_fin…

Done a bit hastily, let me know if I got something wrong. But here's a racket (formerly plt scheme) solution:

    #lang racket
    (define (palindrome? lst)
      (equal? lst (foldl cons empty lst)))
       
    (define ITERATIONS 10000000)
    (for ([i (in-range ITERATIONS)])
      (palindrome? '(i)))

    time racket palindrome.rkt
    real	0m0.893s
    user	0m0.864s
    sys	        0m0.024s

Here are some other solutions done in racket for those that are interested: http://www.go-hero.net/jam/13/solutions/0/3/Racket

Re: Ruby is too slow for programming competitions

#213

Post by TikiTDO » Mon, Apr 22, 2013, 5:24 AM UTC

lbrandy wrote: post #161

jonhohle wrote: post #146

Earlier quoted context omitted.

I agree with it and have implemented it. After profiling a backfill script which was looking like it was going to take about two weeks to run, I found an area where certain bit-twiddling was being done which was extremely slow in Ruby. I rewrote this section in C, and was able to make this section 1000x faster then the ruby equivalent (this was MRI 1.8.5 several years ago). The total runtime for the script was brough…

I didn't mean to imply it wasn't ever possible. Just that the subset of things that it works great for is smaller than people wish, or believed. That "I'll write in Ruby and optimize in C when I need to" is a myth on the order of the "sufficiently smart compiler". There are things for which it just plain doesn't work. Things that are quite common. Yes, you can make image transformations for your webapp fast by piping…

If your memory usage and gc speed are of critical concern, then you should really know that ruby is just not going to provide the tools you need to handle that. That's like using a hammer when you need a screwdriver. Even the most modifiable hammer is still meant for pounding, not screwing.

Whenever I see "I'll write in Ruby and optimize in C when I need to" I assume the context of "my program is well suited to be written in Ruby." For instance, I certainly wouldn't write embedded code in ruby. However, I would venture to say that these situations are the exception rather than the rule.

These days most software has access to fairly reasonable computational resources. If you're writting microcode for some industrial control system, or calculating stock price variations with micro-second resolution then certainly stick to C or ASM or what have you. However, in an age when even a fridge will have a few hundred MB of memory, and when a lot of code is meant to be just "good enough" I think even ruby will suffice.

Re: Ruby is too slow for programming competitions

#214

Post by jff » Mon, Apr 22, 2013, 5:25 AM UTC

KVFinn wrote: post #182

ClifReeder wrote: post #32

Earlier quoted context omitted.

To clarify, the Go program (which took under a second to run) was doing the same processing as the full Ruby program that took 50 minutes to run.

Others have asserted that they aren't doing the same processing and the GO program is not correct. https://news.ycombinator.com/item?id=5586152

Go is not an acronym

See also: "ham" (amateur radio) is not an acronym

Re: Ruby is too slow for programming competitions

#215

Post by ternaryoperator » Mon, Apr 22, 2013, 5:58 AM UTC

hellb88ned wrote: post #187

xyzzyz wrote: post #37

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, beca…

> when he really should have blamed the Dunning-Kruger effect. Going a layer deeper, blame the competitions themselves. They very rarely have good data sets to actually weed out algorithmically poor solutions, so you can often get away with brute force or mostly brute force solutions -- if you use a low-level programming language. For instance many times a O(N^2/100) will pass the test data just because it's written…

Not sure I agree, although I understand your point. Most algos have performance profiles that are significantly different when run on best-case and worst-case data sets. An algo implementation that works correctly for the data set of a particular problem is not invalidated b/c it does poorly when implemented in another language. If it works well only in C++ in this competition, and the developer chose C++ then it seems to me he has successfully answered the call.

Re: Ruby is too slow for programming competitions

#216

Post by macobo » Mon, Apr 22, 2013, 6:07 AM UTC

yen223 wrote: post #181

macobo wrote: post #11

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 compet…

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

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

Re: Ruby is too slow for programming competitions

#217

Post by rwallace » Mon, Apr 22, 2013, 6:21 AM UTC

lbrandy wrote: post #127

Derbasti wrote: post #84

Earlier quoted context omitted.

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

Everyone always agrees with this and, in my experience, has never really tried it. It works better in theory than in practice (or, at a minimum, it works only on a small subset of the types of problems that a naive view might otherwise lead you to believe). The problem is the data isn't organized in a way to be computation efficient, and all the C code in the world isn't going to make chasing pointers to pointers to…

Depends on how you go about it. I personally haven't encountered any cases where it would make sense to write a few functions in C and link them into a Python/Ruby program. But I have encountered a number of cases where what works well is to write the main program, the part that does the heavy crunching, in C++, and various ancillary scripts for preprocessing, postprocessing etc. in Python.

Re: Ruby is too slow for programming competitions

#218

Post by camus » Mon, Apr 22, 2013, 7:09 AM UTC

ksec wrote: post #206

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…

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.

Re: Ruby is too slow for programming competitions

#219

Post by vidarh » Mon, Apr 22, 2013, 7:10 AM UTC

yasth wrote: post #193

threeseed wrote: post #166

Earlier quoted context omitted.

Because I am being realistic. Ruby, C, Java etc have had decades to build a comprehensive set of developer libraries. Go hasn't. It's a "cute" platform that I am sure will beat Ruby in a few benchmarks. But I don't see any reason why anyone would seriously consider it for a real world app.

Well for one Go beats Ruby in every benchmark that I am aware of, and generally by quite some distance. Also realistically 60-70% of all libraries created for other languages are bitrotted to junk or pointlessness by this point. If you can't see why an app that fits within the worked problemspace of Go (and even with the current libraries plenty of things are wholly doable in Go) and will require much less server res…

The point is if you need the performance, C is the more natural choice for a lot of it at this point. I looked through one of the Go tutorials a while back, and it was WTF after WTF. If it works for you, fine, but Go has a long way to go to be interesting for a lot of us.

Re: Ruby is too slow for programming competitions

#220

Post by vidarh » Mon, Apr 22, 2013, 7:26 AM UTC

nostrademons wrote: post #51

xyzzyz wrote: post #37

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, beca…

One of the points of scripting languages is that you can solve the problem quicker, in terms of developer time, by not having to think about it as much. If you have to think about it more, and come up with clever solutions while a faster language just lets you brute-force it, then they haven't really let you solve the problem more quickly. (That said, programming competitions are a pretty unrealistic subset of what a…

Which solution is the obvious one? Why?

To me, the obvious solution is to generate the palindromes, not iterate through every number and check if it is a palindrome. Unless generating palindromes is a very hard problem, iterating over them should be the obvious solution, as it obviously will mean a substantially smaller set of iterations.

As it happens, generating a series of palindromes is easy, and is obviously massively faster, since as a first crude approximation of the difference you can take his example program, change it to step through the space with "step(10)", convert to string, replace the last digit with the first and check that the resulting number still falls within the range, and then check if it's a palindrome. Just this crude change cuts the number of iterations required to 1/10th, and it hints strongly at the effects of recursively applying the same method.

Having to handle varying length palindromes slightly complicates matters, but not much.