Clojurians Log v2

I don't know how you can fix find - the Clojure implementation is that key/value pairs are stored flat. Find returns an entry. You have to allocate it somewhere. It's doubly unfortunate that in almost all cases where an entry is allocated in this manner it's immediately taken apart (kiss your cache lines goodbye)

The solution is to not use find This is ugly but achieves the same purpose

(defmacro if-get
  [m k v then else]
  `(let [~v (get ~m ~k ::not-found)]
     (if (identical? ~v ::not-found)
       ~else
       ~then)))

(if-get {:a 1} :a v (inc v) :aaa) 

Or, if you'd like to pretend it's a binding form

(defmacro if-get
  [[v [m k]] then else]
  `(let [~v (get ~m ~k ::not-found)]
     (if (identical? ~v ::not-found)
       ~else
       ~then)))

(if-get [v [{:a 1} :a]]
  (inc v)
  :aaa)

Should probably have an assert that v is a symbol but this is sufficient for demo purposes

I got confused by the RT/find and brain is in vacation mode

I remember taking a vacation once, I think it was five or six years ago

public IMapEntry entryAt(Object key){
	int i = indexOf(key);
	if(i >= 0)
		return (IMapEntry) MapEntry.create(array[i],array[i+1]);
	return null;
}

(also not super used to digging into the java sources)

This is the allocation. When you conj it, it's immediately taken apart, so it's thrashing the cache The "correct" solution, given the implementation, is

(defn select-keys*
  [m ks]
  (persistent!
   (reduce
    (fn [acc k]
      (if-get [found [m k]]
        (assoc! acc k found)
        acc))
    (transient {}) ks)))

But just to satisfy my something, here you’re creating an additional vector in [m k] right?

No, it's my macro from before, this is the expanded version:

Right, I read it too quickly

(defn select-keys*
  [m ks]
  (->> ks
       (reduce
        (fn [acc k]
          (let [found (get m k ::not-found)]
            (if (identical? found ::not-found)
              acc
              (assoc! acc k found))))
        (transient {}))
       persistent!))

Thank you for taking the time to explain this!

Gladly I think I managed to nail down the fastest possible implementations given the standard library here https://github.com/bsless/keys

This isn't faster if you work with a very small set of keys, btw, there is an overhead to transient/persistent

something like

(defn -select-transient
  [m ks]
  (->>
   ks
   (reduce
    (fn [acc k]
      (let [found (get m k ::not-found)]
        (if (identical? found ::not-found)
          acc
          (assoc! acc k found))))
    (transient {}))
   persistent!))

(defn -select-persistent
  [m ks]
  (reduce
   (fn [acc k]
     (let [found (get m k ::not-found)]
       (if (identical? found ::not-found)
         acc
         (assoc acc k found))))
   {}
   ks))

(defn select-keys*
  [m ks]
  (if (> (count ks) 2)
    (-select-transient m ks)
    (-select-persistent m ks)))

I was thinking if there was a series of optimization and removed allocations fixes and together they showed material benefits to realistic code bases. Maybe an ask could be made to specifically address those together. But I think it would need to be resulting in close to 10% improvement or something to be convincing.

Yes but I need proper benchmarks to show improvement

you can find usages of select-keys from https://cloogle.phronemophobic.com/name-search.html?q=clojure.core%2Fselect-keys&tables=var-usages. If you click on the results.json link, then it will give you all results as a json file. Just give it a sec since it's running on a dinky VPS 😛. It's interesting. There are actually a reasonable number of usages selecting 3 or fewer keys. See the https://github.com/clojure/clojurescript/blob/6c7a1680b29e9215e95d867c89f54f2107806220/src/main/clojure/cljs/analyzer.cljc#L4865, for example.

If you want to dive down the optimization well, you could special case when ks is counted and just 1, 2, or 3 items.

More than 2 will probably be a disaster - you'll need to emit 4 cases for for 2 keys case. It's an unordered selection from set, bleh