Performance

[bsless]

Hello,
I have a bad habit of finding cool project and looking under the hood for performance lying on the floor.
After doing some poking around and running benchmarks I can share some findings:

• There is about 10% easy improvement which can be gained by using loop-unrolled versions of update/assoc/get-in (tested using clj-fast with the dungeon use case)
• A less trivial issue is where vectors are used as map keys. I think the main culprit is id+attrs in left-activate-memory-node. Every time collections are looked up as keys in a map it forces an equality check that walks both of them. This causes an otherwise disproportionate amount of CPU to be wasted on associng. I'm not sure about the best way to mitigate that. If you find a way to represent id+attr as a keyword it would probably help, but will surely take some thinking. There's about 15% CPU left there after the previous optimization

I'll be happy to keep digging if you're interested.

Keep up the amazing work :)

[oakes]

These are great suggestions -- i haven't used clj-fast before. As for id+attrs, maybe i could calculate a keyword based on it and use that instead...but that feels like just implementing a second layer of hashing for map keys. Gotta think about it more...

[bsless]

Thank you 🙏
I've done some more thinking myself since opening this issue:
One issue I did not consider when running my benchmarks is that odoyle-rules is cljc and clj-fast targets JVM Clojure specifically.
Also, odoyle-rules provided me with a good opportunity to find a few subtle bugs in my code, so if you plan to play with clj-fast let me know first so I'll release a new version with the fixes.
Regarding the second layer of hashing, it may be worth it. Almost all CPU was wasted hashing and comparing id+attrs.
I'm not sure generating a keyword from them would help as iirc id's type is any.
Another solution is using a nested map of id->attr instead of a tuple id+attr. This is still faster. It does not, however, solve the bit where you use id+attrs (plural) as a key. Haven't figured out how to work around that one yet.
Another approach to id+attr is generating a type with explicit equality and hashing semantics, some abomination like:

(deftype IdAttr [id attr ^:unsynchronized-mutable ^int _hasheq]
  java.lang.Object
  clojure.lang.ILookup
  clojure.lang.IHashEq
  clojure.lang.IKeywordLookup
  clojure.lang.IPersistentMap
  java.util.Map
  (equals [this that]
    (boolean
     (or (identical? this that)
         (and (instance? IdAttr that)
              (= id (.id ^IdAttr that))
              (= attr (.attr ^IdAttr that))))))
  (equiv
    [this that]
    (boolean
     (or (identical? this that)
         (and (instance? IdAttr that)
              (= id (.id ^IdAttr that))
              (= attr (.attr ^IdAttr that))))))
  (valAt
    [_ k else]
    (condp identical? k
      :id id
      :attr attr
      else))
  (valAt [this k] (.valAt this k nil))
  (get [this k] (.valAt this k))
  (seq [_] (seq [id attr]))
  (hasheq [_]
    (let [hq _hasheq]
      (if (zero? hq)
        (let [h (int
                 (bit-xor
                  968592507
                  (Murmur3/mixCollHash (unchecked-add-int (int (Util/hasheq id)) (int (Util/hasheq attr))) (int 2))))]
          (set! _hasheq h)
          h)
        hq))))

Which works (really works, tests pass and all), but no one wants to look at or maintain

[oakes]

That is really neat, i'll try it when i get the chance. Maybe one way to avoid the complexity and maintenance burden would be to just provide a way to supply an id+attr constructor function to ->session as an option. That way, code like this could live in your project and be open to tweaking, if you need the extra performance.

[bsless]

On the other hand, when you open that door someone will use it to blow their own foot off.
I'll play around with this some more until I reach a satisfactory solution. Even by unrolling Records' hash and equality semantics there's a huge gain to be had.

[oakes]

That is true...and this id+attr thing would be a weird internal detail to expose, now that i think of it.