Which Function is the best in terms of Stack Usage Efficiency and Time

Question

I wrote 3 functions that count the number of times an-element appears in a-list. I tried various inputs and profiled it but I still dont know which function is the best in terms of stack usage efficiency and time efficiency. Please Help me out.

;; Using an accumulator
    (defn count-instances1 [a-list an-element]
      (letfn [(count-aux [list-aux acc]
                         (cond
                           (empty? list-aux) acc
                           :else (if (= (first list-aux) an-element)  
                                   (count-aux (rest list-aux) (inc acc))
                                   (count-aux (rest list-aux) acc))))]
        (count-aux a-list 0)))

;; Normal counting 
    (defn count-instances2 [a-list an-element]
     (cond
       (empty? a-list) 0
       :else
          (if (= (first a-list) an-element )
              (+ 1 (count-instances2 (rest a-list) an-element))
              (count-instances2 (rest a-list) an-element))))

;; using loop. does this help at all?
   (defn count-instances3 [a-list an-element]
        (loop [mylist a-list acount 0]
            (if (empty? mylist)
                acount
                (if (= (first mylist) an-element)
                (recur (rest mylist)(inc acount))
                (recur (rest mylist) acount)))))

Nested `defn` probably doesn't do what you think. `defn` always defines a toplevel function. You can use `letfn` (or even `(let [f (fn ...)])`) if you want to define an inner function. — Brian Carper, Jul 22 '09 at 21:19
Thanks Brian. But I cant get the letfn to work. Could you edit my question with letfn? Thanks a lot. — unj2, Jul 22 '09 at 23:44
OK I edited it. Note also that you could have written this function a bit more concisely, `(defn count-4 [coll x] (count (filter #{x} coll)))`. — Brian Carper, Jul 23 '09 at 02:43

score 2 · Accepted Answer · edited May 21 '12 at 03:45

2

The loop/recur version is the right way. Clojure cannot optimize tail calls due to limitations of the JVM.

edited May 21 '12 at 03:45

mikera

105,238
25
256
415

answered Jul 22 '09 at 21:01

Svante

50,694
11
78
122

3

That's not accurate. You should say that Clojure *chooses* not to optimize tail calls, because that's pretty difficult to achieve in a language (Java) that doesn't already have them. In fact there are some implementations of languages (eg, SISC -- http://sisc-scheme.org/) on top of the JVM that do optimize tail calls. – Eli Barzilay Jul 23 '09 at 02:01
Thats really strange. Why would it not want to optimize tail calls? It would have saved us a lot of hassles? Are there trade offs? – unj2 Jul 23 '09 at 02:08
3

`recur` is nice because it's explicit and you can only use it from tail positions (the compiler complains otherwise) which catches instances where you think you're tail-recursing but you aren't. It could all be macro'd away automatically, but it's not that much hassle to replace your function name in the tail call with the symbol `recur`. – Brian Carper Jul 23 '09 at 02:53
My impression is that that "choice" is more or less forced on Clojure. I think that loop/recur is a nice construct, however real tail call optimization is a much more general concept than this. – Svante Jul 23 '09 at 06:46
SISC Scheme is interesting, maybe they have found some trick. I am sure that I read that Rich Hickey said it is difficult or impossible to optimize tail calls on the JVM. – Svante Jul 23 '09 at 06:49
1

"Difficult" is the right word. "Impossible" is just wrong. What SISC is doing is not new (and SISC itself is older than Clojure, IIRC). – Eli Barzilay Jul 23 '09 at 09:14
Good find, kunjaan, that explains it. – Svante Jul 23 '09 at 17:27
Here's a relevant discussion of Tail Calls in JVM here @ SO : http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations . – unj2 Jul 24 '09 at 14:14

score 0 · Answer 2 · answered Jul 22 '09 at 20:45

0

Writing your code so the compiler/interperter can optmize it for tail recursion, should result in some performance increase and stack usage reduction. I think your normal counting function could qualifies for tail recursion so that one should be pretty fast. Not sure since I only dabble in Lisp as a hobby.

http://en.wikipedia.org/wiki/Tail_recursion

answered Jul 22 '09 at 20:45

anio

8,903
7
35
53

Clojure cannot optimize tail calls due to limitations of the JVM. – Svante Jul 22 '09 at 20:59
1

Rich Hickey's comment on this was that it was better to have an explicit abstaction that works all the time (recur) than an implicit one that works almost all of the time (due to complexities of doing this on the JVM) – Arthur Ulfeldt Jul 24 '09 at 21:12
@Svante - Clojure can and does optimise tail calls. You just have to be explicit that you want it by using `recur` (which was a language design choice by Rich Hickey). It's perfectly possible to do TCO on the JVM most of the time. JVM limitations only affect mutual co-recursion (which is actually a pretty rare case). – mikera May 21 '12 at 03:44

Which Function is the best in terms of Stack Usage Efficiency and Time

2 Answers2

Linked