Arc Forumnew | comments | leaders | submitlogin
Calculations in Arc 5 x faster than in Python and a little faster than in mzscheme
8 points by sacado 5859 days ago | 10 comments
The discussions around Arc as fast as CL and almkglor's suggestion about an optimzing compiler taking data type into consideration (http://arclanguage.org/item?id=4869) made me try something interesting. Actually, it worked even better than I thought (hence the title).

Currently, when you write, e.g., (< n 2), it is translated as (ar-funcall2 __< __n 2). Furthermore, < is a polymorphic function (it deals with numbers, strings, ...). Hence a visible slowdown when you do calculations. This is still true (but a little less) when you use the FFI trick I gave in http://arclanguage.org/item?id=4812 : it is still translated as above (with ar-funcall2) and the conversions Scheme <-> C take quite a time.

I defined a new set of numeric functions (n+, n-, n, n/, n<, nis, ...) that are hard-wired into their mzscheme counterpart : when (< n 2)* becomes (ar-funcall2 __< __n 2), (n< n 2) becomes (< n 2). Well that's an amazing speedup.

(fib 36) in Arc, with <, + and - ->108 s.

fib (36) with Python -> 20 s.

(fib 36) in Mzscheme -> 8 s.

(fib 36) in Arc with n<, n= and n- -> 5 s.

Python psyco takes a little more than 1 s.

Wow. The idea now would be to automatically translate

  (type-declaration n 'num
    (if (< n 2) ...
into (if (n< n 2) ...

Not that easy, but it should be doable.



5 points by almkglor 5859 days ago | link

Hmm. Idea, idea.

How about co-opting bits of Haskell type system.... Hmm.

Basically 'num here would be a specific "is-a" type, not necessarily the "has-a" type I was thinking. But it should be doable. Basically you just need to redefine 'defm to put stuff in a table as well as into the symbol, and have type-declaration scan through the code for stuff in the table that's declared with specific types.

But we need to figure out first how to handle types: "is-a" or "has-a". Does 'defm dispatch off a "is-a" relationship or "has-a" relationship? Possibly as in Haskell, with a "is-a" type having "has-a" set of interfaces/typeclasses/baseclasses.

-----

6 points by nex3 5859 days ago | link

Oh please no! Static typing and Lisp - especially a Lisp like Arc that puts even more emphasis on being as dynamic as possible - don't mix. If we want performance improvements like this, that's what type annotations are for. Those work fine in CL for gaining performance, and integrate well into dynamic languages.

If we add Haskell's type system, we'll just end up with an ad hoc, informally-specified, bug-ridden, slow implementation of half of Haskell. That's not what anyone wants.

-----

3 points by almkglor 5859 days ago | link

Err. The idea is that these are the "type annotations" you are looking for. I never said anything about making this mandatory; it's merely the implementation layer for type annotations.

-----

2 points by dido 5859 days ago | link

I wonder if some of the work in optimizing Self, such as polymorphic inline caches [1] might be applicable for non-object oriented dynamically-typed languages such as Arc.

[1] http://research.sun.com/self/papers/pics.html

-----

5 points by offby1 5859 days ago | link

Now why on Earth would arc be _faster_ than mzscheme?!

-----

3 points by sacado 5859 days ago | link

Hmm... I confirm what I said. In a silly benchmark involving fibonacci, prime numbers and factorial (only real world examples as you can see ;), mzscheme took about 1mn35s and Arc (with fast numerical operations) only 58s. No doubt time is not broken as I used the Unix command this time. It also means that these 58s. include the 3s. on Arc startup. The actual time is closer to 55 s. No, if anyone has an idea about why a given code can be faster in Arc...

-----

1 point by kens1 5859 days ago | link

When I did the earlier Fibonacci benchmarking, I found it useful to take the code generated by ac, and run it inside mzscheme. (Note that :a will drop you from Arc to Scheme.) That is, running the exact same code that Arc does, just from the Scheme REPL. (This should take the same time as running in Arc, or else something is very wrong.) Then I could tweak the code a function at a time evolving from the Arc-generated code to the Scheme code, and see where the time was going.

Overall, it makes no sense that Arc would be faster. But it would be very interesting to find out why you're getting those results. Could there be some subtle algorithm difference, maybe lack of tail recursion, in the Scheme version?

-----

1 point by sacado 5858 days ago | link

Ok, I tried that. Running the fib code in a mzscheme REPL is slower than in an Arc REPL. But, if once in Arc REPL you type :a (and get to the mzscheme REPL with Arc functions loaded), the same Scheme code is then a little faster than the Arc counterpart. That means there is something in ac.scm that speeds up mzscheme computations. Maybe the fact that it's embedded in a module ? I really don't know, but at least this is not an aberration anymore.

-----

3 points by sacado 5859 days ago | link

I really don't know. It just is... It might be a bug in the time function, or for some reason the ugly code produced by the ac function gets optimized better than the simple mzscheme code...

Anyway, that's only a micro-benchmark. I'm trying to confirm this with more tests... I guess mzscheme will eventually be slightly faster than Arc.

-----

1 point by sacado 5859 days ago | link

Btw, don't try this at home, it's not on the git yet :)

-----