3 ms·
(author here) Haskell and Go just take a different approach. For some problems that approach is way better, so it is not a question of what the best way to do
by jlouis 14y ago
(author here)
Haskell and Go just take a different approach. For some problems that approach is way better, so it is not a question of what the best way to do this is. In fact, the code I have written in Haskell does not seem to have suffered at all, even though it was highly concurrent. Do note however, that the thing I wrote was throughput-oriented though.
It is not harder to do this with a compiled language. You just need to insert check points regularly in your generated code. This means you have to make sure that loops regularly checks. Some times though, you can compute the induction and then determine before loop execution if you have enough reductions left to enter the loop. If not you can jump to a slower version. Depending on the loop and architecture, incrementing a value on each iteration tend to be cheap.
As for the regular expressions: They are PCRE's written in C, but the library has been instrumented with points at which the computation can be stopped and preempted to avoid it to hog the core. The slowdown is very very low, but it will be split up and interleaved with other jobs.
- davidw 14y agoPerhaps I'm thinking of an older version or something. It's listed as being quite slow here: http://benchmarksgame.alioth.debian.org/u32/performance.php?test=regexdna#about http://benchmarksgame.alioth.debian.org/u32/performance.php?... And the Erlang code even has the comment "re module is damn slow.", but I admit to not following Erlang super closely and maybe that's no longer accurate. I'd be interesting to see if there are languages out there that compile to native code that do what you say. I know Erlang has "hipe", but I'm not sure how that works under the hood - maybe another blog post?:-) HiPE seems to make Erlang fast, but not quite in the same ballpark as JIT'ed languages: http://benchmarksgame.alioth.debian.org/u64/which-programs-are-fastest.php http://benchmarksgame.alioth.debian.org/u64/which-programs-a...
- jlouis 14y agoIt should be pretty obvious that something is amiss here. Erlang is usually not the fastest language for (purely) CPU-bound tasks, of which this is the case. But being 34 times slower than a Javascript engine tells you that something is not done right. In fact, there is an interesting alternative program which is only a factor of 2 slower. I would expect it to be slower since regular expression handling is something you rarely do in Erlang on critical paths. But 34 times slower is way above target - and that tells me something is going wrong in a deep way in that code. Also in the real world you are allowed to cheat on heavyweight computation, luckily. Write it in C, Ocaml, OpenCL, CUDA, GHC+DPH+REPA or what have you. Then use Erlang to manage the data as payload and move it around. I have no knowledge of HiPE. At least not enough to write a blog post on how it works right now. I would have to study it a bit before I can do that. There are plans for an alternative JIT'ed backend for Erlang though. That said, I don't think Erlang will ever be "fast" since the language isn't statically typed, and there is currently no provision for type annotations. The main reason for having a JIT for Erlang would be that more of the runtime can be written in Erlang, which makes the system more portable. This is almost always a win.
- knewter 14y agoSo javascript is actually the fastest implementation of regular expressions, so I'm not sure why something's "obviously amiss."
- ibotty 14y agothe factor of 34 is. (and that there is a program with only factor 2 suggests that as well.)
- igouy 14y agoHow does "the factor of 34" tell us that something's "obviously amiss"? Maybe that's more than you expected, but incredulity is a weak argument. Why does there being "a program with only factor 2" suggest that something's "obviously amiss"? Maybe that program does not use regular expressions for all the substitutions. https://alioth.debian.org/forum/forum.php?thread_id=14805&forum_id=999&group_id=30402 https://alioth.debian.org/forum/forum.php?thread_id=14805...
- igouy 14y ago>> It should be pretty obvious that something is amiss here. ... 34 times slower is way above target - and that tells me something is going wrong in a deep way in that code. << Please tell us what is "going wrong in a deep way".
- martinced 14y agoIntellectual dishonesty is certainly wrong in a deep way. Several of us here obviously have our jaws dropping thinking: "What!? 34 times slower when typically perfs are quit ok, what is going on here?!" Where do you put the limit? You realize that your "counter argument" makes no sense. 918 times slower? Would that be enough? What about 8734 times slower? Where do you draw the line? Why do you keep insisting saying that "34 times slower" is "nothing to see here, move along"? What about 1923408130294870918234 times slower? Would that be enough for you to consider something may be wrong?
- igor_bukanov 14y agoJavaScript engines compiles regexp down to machine code using the same JIT implementation they use for JS code. It is not surprising that the result is the fastest regexp matching.