Clojure Keyword.intern

gistfile1.diff

commit 8e51c34ca4d97e48750850d5ba09956f89783b4e
Author: Kyle Kingsbury <aphyr@aphyr.com>
Date:   Wed May 7 19:06:15 2014 -0700

    Improve Keyword.intern performance
    
    Keyword interning is an expensive factor in many Clojure
    serialization/deserialization paths, especially where the same set of
    keywords are created and freed repeatedly; e.g. iterating over records
    with similar structure. There are two principle costs to keyword
    interning--which dominates depends on the workload.
    
    1. If any keyword has been garbage collected, a subsequent interning
    thread performs an O(n) traversal of the entire keyword cache, searching
    for any expired WeakReferences to GC'ed keywords. When the keyword table
    is large, this can become quite costly. It's also common where keyword
    churn is high for multiple threads to traverse the table simultaneously;
    a significant duplication of work.
    
    This patch introduces a global counter of freed keywords
    (Keyword.orphans) since the last sweep was initiated, and triggers a
    sweep iff the orphaned count comprises a significant (10%) fraction of
    the keyword cache. It also prevents multiple threads from simultaneously
    cleaning the cache. This reduces the impact of cache cleaning in my
    benchmarks to essentially zero, at the cost of moderately increased
    variability in .999 latencies
    
    2. Regardless of whether a keyword exists or not, every intern() call
    *must* intern a Symbol, which *must* intern two strings--the namespace
    and name. The keyword is then used as the keyword cache key.  JVM
    String.intern performance is improving but remains costly; often
    consuming 50--70% of JSON decode time with Cheshire.
    
    This patch changes the keyword cache to index by interned strings--the
    same strings used by the underlying symbols--but we can search them
    without interning as a symbol would. This makes equality comparison more
    expensive, but drastically reduces the impact of String.intern. Wherever
    we intern a keyword which is still retained, we can avoid the symbol
    intern costs altogether. This fast path drastically reduces allocations
    and median latencies.
    
    Runtime performance is dramatically improved. I've measured a ~2x
    speedup in JSON decoding throughput via Cheshire, ~2.5x speedup in
    creating/releasing vectors of 100,00 keywords, ~3x speedup in
    creating/releasing vectors of 1000 keywords, and ~1.6x speedup in
    repeated creation/release of the same keyword; all via 4 threads on a
    quad-core Core II. Median latencies are dramatically decreased. .999
    latencies exhibit more variability but are, on average, slightly faster.

diff --git a/src/jvm/clojure/lang/Keyword.java b/src/jvm/clojure/lang/Keyword.java
index 7b71d44..01e6aec 100644
--- a/src/jvm/clojure/lang/Keyword.java
+++ b/src/jvm/clojure/lang/Keyword.java
@@ -16,41 +16,120 @@ import java.io.ObjectStreamException;
 import java.io.Serializable;
 import java.lang.ref.Reference;
 import java.lang.ref.WeakReference;
+import java.util.Iterator;
+import java.util.Map;
+import java.util.concurrent.atomic.AtomicInteger;
 import java.util.concurrent.ConcurrentHashMap;
 import java.lang.ref.ReferenceQueue;
 import java.lang.ref.SoftReference;
 
-
 public class Keyword implements IFn, Comparable, Named, Serializable, IHashEq {
 
-private static ConcurrentHashMap<Symbol, Reference<Keyword>> table = new ConcurrentHashMap();
+// Table of all extant keywords
+private static ConcurrentHashMap<String, Reference<Keyword>> table = new ConcurrentHashMap();
 static final ReferenceQueue rq = new ReferenceQueue();
+// Approximate upper bound on the fraction of dead references in the kw cache?
+public static final float MAX_ORPHAN_RATIO = 0.1f;
+// How many references have been GC'ed since our last cache refresh?
+public static final AtomicInteger orphans = new AtomicInteger(0);
+
 public final Symbol sym;
 final int hasheq;
 String _str;
 
-public static Keyword intern(Symbol sym){
-	if(sym.meta() != null)
-		sym = (Symbol) sym.withMeta(null);
-	Util.clearCache(rq, table);
-	Keyword k = new Keyword(sym);
-	Reference<Keyword> existingRef = table.putIfAbsent(sym, new WeakReference<Keyword>(k,rq));
-	if(existingRef == null)
-		return k;
-	Keyword existingk = existingRef.get();
-	if(existingk != null)
-		return existingk;
-	//entry died in the interim, do over
-	table.remove(sym, existingRef);
-	return intern(sym);
+public static void clearCache() {
+  // Fast path; no expired references
+  if (rq.poll() == null) {
+    return;
+  }
+
+  // Each reference reclaimed by the GC counts towards our orphan fraction
+  orphans.incrementAndGet();
+  while (rq.poll() != null) {
+    orphans.incrementAndGet();
+  }
+
+  // No sense in scanning an empty table
+  final int tableSize = table.size();
+  if (tableSize == 0) { return; };
+
+  // When enough of the table could be orphans, we scan and remove
+  final int orphansCount = orphans.get();
+  if (MAX_ORPHAN_RATIO < (((float) orphansCount) / tableSize)) {
+    // Chances are several other threads have simultaneously decided to scan
+    // the cache, but one of those threads will reset the orphan count first.
+    final int orphansNew = orphans.getAndSet(0);
+    if (orphansNew < orphansCount) {
+      // We are *not* the winner.
+      return;
+    }
+
+    final Iterator<Reference<Keyword>> iter = table.values().iterator();
+    while (iter.hasNext()) {
+      final Reference<Keyword> ref = iter.next();
+      if (ref != null && ref.get() == null) {
+        iter.remove();
+      }
+    }
+  }
+}
+
+// Once we've paid the interning cost for a symbol and wrapped it with a
+// keyword, we can conditionally update the table.
+protected static Keyword intern(final String key, final Keyword kw) {
+  final Reference<Keyword> existingRef =
+    table.putIfAbsent(key, new WeakReference<Keyword>(kw,rq));
+  if (existingRef == null)
+    return kw;
+  Keyword existingkw = existingRef.get();
+  if (existingkw != null)
+    return existingkw;
+  // Entry died in the interim, do over
+  table.remove(key, existingRef);
+  return intern(key, kw);
+}
+
+// Fast path: where the symbol is already available, we can skip symbol
+// creation.
+public static Keyword intern(final Symbol sym) {
+  clearCache();
+
+  // Optimistically, this keyword is already present in the table
+  final String key = Symbol.nsName(sym.ns, sym.name);
+  Keyword kw = find(key);
+  if (kw != null)
+    return kw;
+
+  if (sym.meta() != null) {
+    // If a symbol was provided for us, we need to ensure we have the canonical
+    // representation, without metadata
+    kw = new Keyword((Symbol) sym.withMeta(null));
+  } else {
+    kw = new Keyword(sym);
+  }
+
+  // Switch to using the intern'ed string to save memory
+  return intern(key.intern(), kw);
+}
+
+// Slow path: we have to intern the symbol ourselves
+public static Keyword intern(final String key) {
+  clearCache();
+
+  // Optimistically, this keyword is already present in the table
+  Keyword kw = find(key);
+  if (kw != null)
+    return kw;
+
+  // Intern the symbol and construct a new keyword.
+  kw = new Keyword(Symbol.intern(key));
+
+  // Switch to using the intern'ed string to save memory
+  return intern(key.intern(), kw);
 }
 
 public static Keyword intern(String ns, String name){
-	return intern(Symbol.intern(ns, name));
-}
-
-public static Keyword intern(String nsname){
-	return intern(Symbol.intern(nsname));
+	return intern(Symbol.nsName(ns, name));
 }
 
 private Keyword(Symbol sym){
@@ -58,20 +137,20 @@ private Keyword(Symbol sym){
 	hasheq = sym.hasheq() + 0x9e3779b9;
 }
 
-public static Keyword find(Symbol sym){
-    Reference<Keyword> ref = table.get(sym);
+public static Keyword find(final String k){
+    final Reference<Keyword> ref = table.get(k);
     if (ref != null)
         return ref.get();
     else
         return null;
 }
 
-public static Keyword find(String ns, String name){
-    return find(Symbol.intern(ns, name));
+public static Keyword find(final Symbol sym) {
+  return find(sym.toString());
 }
 
-public static Keyword find(String nsname){
-    return find(Symbol.intern(nsname));
+public static Keyword find(String ns, String name){
+    return find(Symbol.nsName(ns, name));
 }
 
 public final int hashCode(){
diff --git a/src/jvm/clojure/lang/Symbol.java b/src/jvm/clojure/lang/Symbol.java
index 1efc38e..44c739d 100644
--- a/src/jvm/clojure/lang/Symbol.java
+++ b/src/jvm/clojure/lang/Symbol.java
@@ -24,8 +24,19 @@ private int _hasheq;
 final IPersistentMap _meta;
 String _str;
 
+// Given a namespace string and a name string, construct the normalized
+// string representation of the symbol, "name" if ns is null, "ns/name"
+// otherwise. Does *not* intern.
+static public String nsName(final String ns, final String name) {
+  if (ns == null) {
+    return name;
+  } else {
+    return ns + "/" + name;
+  }
+}
+
 public String toString(){
-	if(_str == null){
+	if(_str == null) {
 		if(ns != null)
 			_str = (ns + "/" + name).intern();
 		else

(ns clojure-perf.core
  (:import [java.io PushbackReader])
  (:require [schadenfreude.core :as s]
            [incanter.core :as incanter]
            [cheshire.core :as json]
            [clojure.java.io :as io]
            [clojure.edn :as edn]
            [clojure.pprint :refer [pprint]]))

(def suite
  {:runs [{:name    "single keyword created and released"
           :f       (fn [_] (keyword "rgfhs89egj9j4"))
           :threads 4
           :n       1e8}
          {:name    "thousand keywords created and released"
           :before  (fn [_] (mapv (partial str "test-kw-") (range 1000)))
           :f       #(mapv keyword %)
           :threads 4
           :n       1e5}
          {:name    "100K keywords created and released"
           :before  (fn [_] (mapv (partial str "test-kw-") (range 100000)))
           :f       #(mapv keyword %)
           :threads 4
           :n       1e3}
;          ]})
;(def suite
;  {:runs [
          {:name    "JSON parsing"
           :before  (fn [_] (slurp "data/test.json"))
           :f       #(json/parse-string % true)
           :threads 4
           :n       1e6}
          ]})

(defn serialize!
  "Write a term as edn to disk"
  [filename x]
  (with-open [f (io/writer filename)]
    (binding [*print-dup* true]
      (pprint x f))))

(defn deserialize
  "Read an EDN term from disk"
  [filename]
  (with-open [f (PushbackReader. (io/reader filename))]
    (edn/read f)))

(defn suite-path
  [path]
  (str "suites/" path))

(defn ->suite
  "Reconstitute a suite from an EDN structure"
  [suite]
  (->> (:runs suite)
       (map (fn [run]
              (if-let [r (:record run)]
                (assoc run :record (incanter/dataset
                                     (:column-names r)
                                     ; Drop final row; we don't want artifacts
                                     ; from termination time here.
                                     (butlast (:rows r))))
                run)))
       (assoc suite :runs)))

(defn suites
  "All suites on disk"
  []
  (->> "suites"
       io/file
       .listFiles
       (map deserialize)
       (map ->suite)))

(defn rebuild-graphs!
  "Rebuild graphs from all suites"
  []
  (->> (suites)
       (mapcat (fn [suite]
                 (map (fn [run]
                        (assoc run
                               :name  (:name suite)
                               :graph (:name run)))
                      (:runs suite))))
       (group-by :graph)
       (map (fn [[graph-name runs]]
              (incanter/save (s/latency-plot runs)
                             (str "graphs/" graph-name " latency 0.5.png")
                             :width 1024)
              (incanter/save (s/latency-plot 0.999 runs)
                             (str "graphs/" graph-name " latency 0.999.png")
                             :width 1024)
              (incanter/save (s/throughput-plot runs)
                             (str "graphs/" graph-name " throughput.png")
                             :width 1024)))
       dorun))

(defn -main [version & args]
  (->> suite
       s/record-suite
       :runs
       (map #(select-keys % [:record :name :threads :n]))
       (array-map :name version :runs)
       (serialize! (suite-path version)))
  (rebuild-graphs!)
  (println)
  (System/exit 0))

Beautiful! I'll try it out in https://github.com/galdolber/clojure-objc

return (name.equals(k.name) && ((ns == k.ns) || ns.equals(k.ns)));
It seems to me that with this.ns=null and k.ns="foo", there is an issue in the line above. Did I miss something?