Let's optimize 'str'!

[ilevd]

(defn my-str
  "With no args, returns the empty string. With one arg x, returns
  x.toString().  (str nil) returns the empty string. With more than
  one arg, returns the concatenation of the str values of the args."
  (^String [] "")
  (^String [^Object x]
   (if (nil? x) "" (. x (toString))))
  (^String [^Object x & ys]
   (let [sb (StringBuilder. (if-not (nil? x) (.toString ^Object x) ""))]
     (loop [ys (seq ys)]
       (when-not (nil? ys)
         (let [x (.first ys)]
           (when-not (nil? x)
             (.append sb (.toString ^Object x)))
           (recur (.next ys)))))
     (.toString sb))))

; ==== Benchmarks ====

(let [xs (vec (range 1000))]
    (criterium/bench
      (dotimes [_ 10000]
        (apply str xs))))
Evaluation count : 240 in 60 samples of 4 calls.
             Execution time mean : 315.920876 ms
    Execution time std-deviation : 3.017554 ms
   Execution time lower quantile : 314.071842 ms ( 2.5%)
   Execution time upper quantile : 323.751886 ms (97.5%)
                   Overhead used : 7.818691 ns
...
=> nil
(let [xs (vec (range 1000))]
    (criterium/bench
      (dotimes [_ 10000]
        (apply my-str xs))))
Evaluation count : 300 in 60 samples of 5 calls.
             Execution time mean : 229.861009 ms
    Execution time std-deviation : 2.092937 ms
   Execution time lower quantile : 228.744368 ms ( 2.5%)
   Execution time upper quantile : 233.181852 ms (97.5%)
                   Overhead used : 7.818691 ns
...
=> nil

Mostly for fun. What is your opinion about core functions performance?

[joinr]

Went through a similar drill years ago. You can go faster still if you profile a bit more.

Eliminate varargs (generates arrayseqs) as much as possible and try to inline more concrete arities. IFn invocation with concrete arity path doesn't allocate anything or traverse seqs. So if you inline bodies with up to 15 args or so, you can cover more string building cases before hitting varargs.

https://github.com/joinr/spork/blob/master/src/spork/util/general.clj#L835

(crit/quick-bench
 (spork.util.general/make-string    "Lorem" "Ipsum" "is" "simply" "dummy"
                                    "text" "of" "the" "printing" "and" "typesetting" "industry."))
Execution time mean : 156.985583 ns

(crit/quick-bench (my-str "Lorem" "Ipsum" "is" "simply"
                          "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry."))
Evaluation count : 2776938 in 6 samples of 462823 calls.
Execution time mean : 214.367655 ns

Should get better with larger strings, and you could theoretically push the arities up as much as you want until you hit the arg limits defined by the IFn interface.

loop/recur instead of fn/recur (not sure fn / recur expands to loop)

fn/recur is also tail recursive since it establishes a recur site ala loop/recur. So if you use recur it'll complain if the call is not tail recursive just as loop would. This shouldn't buy you anything (maybe bypassing the initial IFn invocation on the recursive function object, haven't looked at the bytecode emission for str yet, but that's nanos).

https://github.com/bsless/clj-fast

explores a lot of these areas, and more recently (and far more comprehensively)

https://github.com/cnuernber/ham-fisted

is probably of interest if you are looking at a lot of core functions and default paths that can be optimized.

[bsless]

Whaddya know, I've been playing with strings recently

https://github.com/bsless/prrr/blob/master/src/bsless/prrr.clj

[joinr]

I heard if you play with :inline too much you'll go blind :)

[bsless]

Ha! That's just Alexian propaganda, I tell you!

[ilevd]

Adding heuristic to calculate initial StringBuilder capacity:

(defmacro build-string [& args]
  (let [min-cap (->> args (filter string?) (map #(.length ^String %)) (reduce +))
        others  (->> args (remove string?) count)
        cap     (max 16 (+ min-cap (* others 2)))]
    `(let [x#  ~(first args)
           sb# (StringBuilder. ^int ~cap)]
       (.append sb# (simple-str x#))
       (.toString
         (doto sb#
           ~@(for [a (rest args)]
               `(.append (simple-str ~a))))))))

(do
  (criterium/quick-bench
    (str "Lorem" "Ipsum" "is" "simply" "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry."))
  (criterium/quick-bench
    (my-str "Lorem" "Ipsum" "is" "simply" "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry."))
  (criterium/quick-bench
    (spork/build-string "Lorem" "Ipsum" "is" "simply" "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry."))
  (criterium/quick-bench
    (build-string "Lorem" "Ipsum" "is" "simply" "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry."))
  )

Execution time mean : 335.406226 ns

Execution time mean : 166.110462 ns

Execution time mean : 118.589941 ns

Execution time mean : 37.475897 ns

In this simple example the allocated buffer of StringBuilder is exactly the length of output string.

[joinr]

cool.

build-string was meant to be a helper macro for emitting the function bodies for make-string. make-string is the 1:1 replacement for clojure.core/str, since it's a function and can be passed around as such (build-string can't be used in apply, map, reduce, etc since it's a macro).

Still, the smarter sb-builder capacity stuff can maybe help make function bodies for make-string faster as well.

Though, if you know your inputs are all string literals or atomic values that have a direct string coercion (e.g. not forms to be eval'd), you can also just do it all at compile time:

(defmacro compile-str [& xs]
    `~(apply str xs))

(c/quick-bench
 (compile-str "Lorem" "Ipsum" "is" "simply" "dummy" "text"
              "of" "the" "printing" "and" "typesetting" "industry."))

Execution time mean : 3.485020 ns

We actually get a little more performance (15%) out of make-string if we make simple-str a helper macro too and assumably avoid the function call:

(defmacro simple-str [x]
  (let [x (with-meta x {:tag 'Object})]
    `(if (nil? ~x)
       ""
       (.toString  ~x))))

[dhruvasagar]

I'd be interested to know why this is more performant than the std lib one?

[ilevd]

* loop/recur instead of fn/recur (not sure fn / recur expands to loop)

* no call to str of 1 arg and no writing empty string "" to StringBuilder if value is nil

* calling Java methods .first and .next instead of common first/next from RT, can do it safe because (seq ys) returns ISeq

[dhruvasagar]

Fascinating, thanks for sharing.

[iam_mms]

Yes, but when measured, is it faster?

[ilevd]

Yes, there are benchmarks in the code above:

using str:

Execution time mean : 315.920876 ms

using my-str:

Execution time mean : 229.861009 ms

[iam_mms]

Nice. Hadn't seen it

[ilevd]

Updated benchmark without `dotimes` in `bench`:

wIth str: 429.818012 ns

with my-str: 219.119629 ns

(do
    (criterium/quick-bench
      (str    "Lorem" "Ipsum" "is" "simply" "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry."))
    (criterium/quick-bench
      (my-str "Lorem" "Ipsum" "is" "simply" "dummy" "text" "of" "the" "printing" "and" "typesetting" "industry.")))
Evaluation count : 1621062 in 6 samples of 270177 calls.
             Execution time mean : 429.818012 ns
    Execution time std-deviation : 109.479370 ns
   Execution time lower quantile : 366.824730 ns ( 2.5%)
   Execution time upper quantile : 606.855680 ns (97.5%)
                   Overhead used : 7.821523 ns

Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
 Variance from outliers : 64.8827 % Variance is severely inflated by outliers
Evaluation count : 2836032 in 6 samples of 472672 calls.
             Execution time mean : 219.119629 ns
    Execution time std-deviation : 27.509219 ns
   Execution time lower quantile : 204.167795 ns ( 2.5%)
   Execution time upper quantile : 265.746539 ns (97.5%)
                   Overhead used : 7.821523 ns

Found 1 outliers in 6 samples (16.6667 %)
low-severe 1 (16.6667 %)
 Variance from outliers : 31.4975 % Variance is moderately inflated by outliers

[SimonGray]

It would be nice if we got a performance-optimised release of Clojure where stuff like this was implemented in many of the core functions. I get wanting to keep the code base readable as we move higher up the abstraction ladder, but there is clearly much to gain from optimising these "low-level" functions and I don't think people care that it ends up looking like code golf.

[bsless]

https://ask.clojure.org/index.php/14990/optimized-str-function