6 ms·

"so closures can be, and are, used to implement very effective objects with multiple methods" I don't really believe this to be efficient. The linked text by K

by beza1e1 16y ago

"so closures can be, and are, used to implement very effective objects with multiple methods" I don't really believe this to be efficient. The linked text by Kiselyov implements the dispatch via Scheme's (case ...) expression. Efficient dynamic dispatch means one indirection through a vtable, so one load instruction more compared to a normal function call. Which compilers for functional languages can perform this optimization? Since we are talking about Scheme here, we could compare the dispatch to dynamic languages like Python or Ruby, where the dispatch means looking up a string in a hashmap. I'm willing to believe that Scheme's case can keep up with that.

swannodette 16y ago
Clojure. Clojure has a fairly interesting feature called reify: (defprotocol Foo (bar [this]) (baz [this])) (defn make-foo [a] (reify Foo (bar [this] a) (baz [this] a))) (dotimes [_ 10] (let [x (make-foo 'x)] (time (dotimes [_ 1e8] (bar x) (baz x)))) So 2 methods called 1 billion times only takes about ~500ms on my 2.66ghz i7 MacbookPro. (of course, Clojure prefers values+behaviors, aka objects, without mucking it up with state)
- supersillyus 16y ago
  It seems very likely to me that the JVM is recognizing that "bar" and "baz" don't do anything and (after some warm-up) optimizing them away. Microbenchmarking JVM is hard.
  - swannodette 16y ago
    Not true. Timings are completely different if you take a method out. I'm not saying that the JVM is not doing any magic here - but here is a closure that gets method dispatch as fast as the host can provide.
    - supersillyus 16y ago
      You're probably right. I took 500ms for 1B iterations and saw that you're looking at ~0.25ns a call, and that seemed a bit low. However, based on your code, you ran it 100M times, not 1B (1e8 vs 1e9). That changes it to 2.5ns per call. I ran the code on my machine (similar to yours, Macbook Pro 2.66ghz) with Clojure 1.2.0, and I got just over 2500ms for 1e8 iterations, which is about 12.5ns per call. For comparison, looping 1e8 times with two calls to empty functions in a static language takes ~639ms, gives me ~3ns per call. So, you can see why my first suspicion was that the JVM was doing something like just inlining the methods and avoiding the call altogether. Considering the differences in our reported numbers, you may have a newer JVM than me, and if it is beating simple CALL instructions, it must be inlining them or avoiding some of the looping.
anon_d 16y ago
(define (error . args) #f) (define (class x y z) (lambda (d) (case d ('x x) ('y y) ('z z) (else (error "Invalid slot ~a" d))))) (define obj (class 'this 'is-a 'test)) (display (obj (read))) (newline) The Stalin scheme compiler, if I read the output correctly, makes a separate type for 'x, 'y, and 'z. Then it does the dispatch using a switch statement (in the c code) over the three symbol types. This seems quite resonable to me; The C compiler will probably produce a jump table. Note that I was unable to get the compiler to produce dispatch code at all without dispatching on the result of READ.
jpr 16y ago
Sufficiently Smart Compiler(tm) should be able to optimize `case` that switches only on a known set of symbols pretty well. Certainly not necessary to do hash-lookup.

by beza1e1 16y ago

swannodette 16y ago

Clojure. Clojure has a fairly interesting feature called reify: (defprotocol Foo (bar [this]) (baz [this])) (defn make-foo [a] (reify Foo (bar [this] a) (baz [this] a))) (dotimes [_ 10] (let [x (make-foo 'x)] (time (dotimes [_ 1e8] (bar x) (baz x)))) So 2 methods called 1 billion times only takes about ~500ms on my 2.66ghz i7 MacbookPro. (of course, Clojure prefers values+behaviors, aka objects, without mucking it up with state)

supersillyus 16y ago
It seems very likely to me that the JVM is recognizing that "bar" and "baz" don't do anything and (after some warm-up) optimizing them away. Microbenchmarking JVM is hard.
- swannodette 16y ago
  Not true. Timings are completely different if you take a method out. I'm not saying that the JVM is not doing any magic here - but here is a closure that gets method dispatch as fast as the host can provide.
  - supersillyus 16y ago
    You're probably right. I took 500ms for 1B iterations and saw that you're looking at ~0.25ns a call, and that seemed a bit low. However, based on your code, you ran it 100M times, not 1B (1e8 vs 1e9). That changes it to 2.5ns per call. I ran the code on my machine (similar to yours, Macbook Pro 2.66ghz) with Clojure 1.2.0, and I got just over 2500ms for 1e8 iterations, which is about 12.5ns per call. For comparison, looping 1e8 times with two calls to empty functions in a static language takes ~639ms, gives me ~3ns per call. So, you can see why my first suspicion was that the JVM was doing something like just inlining the methods and avoiding the call altogether. Considering the differences in our reported numbers, you may have a newer JVM than me, and if it is beating simple CALL instructions, it must be inlining them or avoiding some of the looping.

anon_d 16y ago

(define (error . args) #f) (define (class x y z) (lambda (d) (case d ('x x) ('y y) ('z z) (else (error "Invalid slot ~a" d))))) (define obj (class 'this 'is-a 'test)) (display (obj (read))) (newline) The Stalin scheme compiler, if I read the output correctly, makes a separate type for 'x, 'y, and 'z. Then it does the dispatch using a switch statement (in the c code) over the three symbol types. This seems quite resonable to me; The C compiler will probably produce a jump table. Note that I was unable to get the compiler to produce dispatch code at all without dispatching on the result of READ.

jpr 16y ago

Sufficiently Smart Compiler(tm) should be able to optimize `case` that switches only on a known set of symbols pretty well. Certainly not necessary to do hash-lookup.