Performance of Clojure lazy structures vs hashes/sets/vectors?

Question

I am using Clojure data structures all over the place but I am not using any lazy evaluation. Is there a performance penalty for using lazy structures everywhere?

Answer 1

From the source code:

clojure.lang.Cons (strict list element, clojure.lang.PersistentList is very similar), https://github.com/clojure/clojure/blob/1.2.0/src/jvm/clojure/lang/Cons.java#L34

public Object first(){
    return _first;
}

clojure.lang.LazySeq (lazy sequence element), https://github.com/clojure/clojure/blob/1.2.0/src/jvm/clojure/lang/LazySeq.java#L77

public Object first(){
    seq();
    if(s == null)
        return null;
    return s.first();
}

where

final synchronized Object sval(){
    if(fn != null)
        {
        try
            {
            sv = fn.invoke();
            fn = null;
            }
        catch(Exception e)
            {
            throw new RuntimeException(e);
            }
        }
    if(sv != null)
        return sv;
    return s;
}

final synchronized public ISeq seq(){
    sval();
    if(sv != null)
        {
        Object ls = sv;
        sv = null;
        while(ls instanceof LazySeq)
            {
            ls = ((LazySeq)ls).sval();
            }
        s = RT.seq(ls);
        }
    return s;
}

So you're definitely paying a price. It depends very much on each particular use case how much that price affects you and whether it's offset by the memory savings and lack of wasted computation that lazy evaluation buys you.

Answer 2

There is an overhead of lazy structures (pmjordan's answer is great for giving you the gory details.....). My very rough estimate is that you pay a 2-5x penalty.

However, there are also some upsides:

• Lazy evaluation means that your working set of data may be smaller, since it is only created when needed. This may improve your cache utilisation and hence performance in some cases
• Lazy evaluation helps you write simpler, cleaner code. So you can focus your attention on writing better algorithms. The benefit from having a better algorithm (e.g. O(n log n) vs O(n^2)) may be worth a lot more than the overhead of lazy evaluation

My advice would be to use lazy evaluation freely unless you are sure you are in a situation where you really need high performance and can't afford the overhead (e.g. image processing or something like that....)