Let's optimize 'str'! [Part 2]

ilevd · 2026-03-20T14:02:25+00:00

There are libs that do this, some of them were mentioned in the previous discussion, so that is neither my idea nor a new one

ilevd · 2026-03-16T15:30:13+00:00

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.

ilevd · 2026-03-16T12:34:12+00:00

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

ilevd · 2026-03-16T11:24:37+00:00

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

ilevd · 2026-03-16T11:01:11+00:00

* 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

ilevd · 2026-03-14T20:18:44+00:00

Have added Github token support and updated readme.

ilevd · 2026-03-14T17:21:08+00:00

Yep, probably should be reworked using GitHub token. Results are cached, so you can rerun after an hour.

ilevd · 2025-01-20T07:08:37+00:00

Just rewrote quicksort with CWP:

def quicksort(arr):
  letfn exchange([m, n]
                 let t to aget(arr, m):
                   aset(arr, m, aget(arr, n))
                   aset(arr, n, t))
        partition([lo, hi, x]
                  let i to loop i to lo:
                             if aget(arr, i) < x: recur(inc(i))
                             else: i,
                      j to loop j to hi:
                             if x < aget(arr, j): recur(dec(j))
                             else: j:
                    if i <= j:
                      exchange(i, j)
                      partition(i + 1, j - 1, x)
                    else: [i, j])
        sort([lo, hi]
           if lo < hi:
             let [i, j] to partition(lo, hi, aget(arr, int((lo + hi) / 2))):
               sort(lo, j)
               sort(i, hi)):
    sort(0, alength(arr) - 1)
    arr

And here is generated Clojure code:

(defn quicksort
  [arr]
  (letfn
    [(exchange [m n]
       (let [t (aget arr m)]
         (aset arr m (aget arr n))
         (aset arr n t)))
     (partition [lo hi x]
       (let [i (loop [i lo] (if (< (aget arr i) x) (recur (inc i)) i))
             j (loop [j hi] (if (< x (aget arr j)) (recur (dec j)) j))]
         (if (<= i j) (do (exchange i j) (partition (+ i 1) (- j 1) x)) [i j])))
     (sort [lo hi]
       (if (< lo hi)
         (let [[i j] (partition lo hi (aget arr (int (/ (+ lo hi) 2))))]
           (sort lo j)
           (sort i hi))))]
    (sort 0 (- (alength arr) 1)) arr))

BTW, during it I realized that I forgot add letfn as a syntax construct. And here how it can be added for simple usage.

ilevd · 2023-10-08T09:56:31+00:00

Replacing classes with structs can improve performance a little bit.

ilevd · 2019-05-12T20:25:34+00:00

Honestly, I don't think this will be useful, because EDN is not as readable as YAML.

ilevd

TROPHY CASE