Optimized str function

Question

Opimized version of str function:

(defn my-str
  (^String [] "")
  (^String [^Object x]
   (if (nil? x) "" (. x (toString))))
  (^String [^Object x & ys]
   (let [sb (StringBuilder. (if (nil? x) "" (. x (toString))))]
     (loop [ys (seq ys)]
       (if-not (nil? ys)
         (let [x (.first ys)]
           (if-not (nil? x)
             (.append sb (.toString ^Object x)))
           (recur (.next ys)))))
     (.toString sb))))

Benchmarks:

(let [xs (vec (range 1000))]
    (criterium/bench
      (apply my-str xs)))

Evaluation count : 2577840 in 60 samples of 42964 calls.

         Execution time mean : 23.611394 µs

(let [xs (vec (range 1000))]
    (criterium/bench
      (apply str xs)))

Evaluation count : 1375200 in 60 samples of 22920 calls.

         Execution time mean : 42.015320 µs

Answer 1

There are multiple changes here - which ones matter?

Comments

I suppose that it's not a final function, and in any case, someone from the Clojure core team will still need to measure and check those results if you decide to improve the function.

There are also other variants to consider, like:

public static IFn strFn = new AFn() {
        @Override
        public String call() {
            return "";
        }

        @Override
        public String invoke() {
            return "";
        }

        @Override
        public String invoke(Object arg1) {
            return arg1 == null ? "" : arg1.toString();
        }

        @Override
        public String invoke(Object arg1, Object arg2) {
            StringBuilder sb = new StringBuilder();
            if (arg1 != null) sb.append(arg1.toString());
            if (arg2 != null) sb.append(arg2.toString());
            return sb.toString();
        }
        // override other methods

        @Override
        public Object applyTo(ISeq arglist) {
            StringBuilder sb = new StringBuilder();
            while (arglist != null) {
                var x = arglist.first();
                if (x != null) {
                    sb.append(x.toString());
                }
                arglist = arglist.next();
            }
            return sb.toString();
        }
}


(defn str-
  (^String [] "")
  (^String [^Object x]
   (if (nil? x) "" (. x (toString))))
  (^String [x1 x2]
   (let [sb (StringBuilder. (str- x1))] (.append sb (str- x2)) (str- sb)))
  (^String [x1 x2 x3]
   (let [sb (StringBuilder. (str- x1))] (.append sb (str- x2)) (.append sb (str- x3)) (str- sb)))
  (^String [x1 x2 x3 x4]
   (let [sb (StringBuilder. (str- x1))] (.append sb (str- x2)) (.append sb (str- x3)) (.append sb (str- x4)) (str- sb)))
  (^String [x1 x2 x3 x4 & ys]
   ((fn [^StringBuilder sb more]
      (if more
        (recur (. sb (append (str- (first more)))) (next more))
        (str- sb)))
    (let [sb (StringBuilder. (str- x1))] (.append sb (str- x2)) (.append sb (str- x3)) (.append sb (str- x4)) sb)
    ys)))

---

and there are far more exotic options available in the JDK using invokedynamic, doing this for reals is a significant project that we're not taking on right now.

Answer 2

I've done some independent exploration of the options space for optimizing str which does not involve anything ground shattering but still gives good performance improvements

• variadic arities (up to 20, yuck) will probably give the best performance. Can settle for common cases like up to 5 (apply str will still suck but whatever)
• using reduce instead of a loop (would probably require redefining str or providing a str1 with the old impl for bootstrap purposes)
• using inline meta, orthogonal to all other options

Additionally, having a function like str which only takes a sequence and reduces over it could provide a better code path than (apply str xs)

Similar work has been done in spork and stringer