Optimizing nrepl-dict internals

[yuhan0]

nrepl-dict-get is probably the #1 called function in all of Cider, so I was surprised to find that its implementation has an inefficient call to nrepl-dict-contains, that turns from what should be a O(n) lookup into O(n²). (edit: see correction below)

cider/nrepl-dict.el

Line 69 in 05e7570

(if (nrepl-dict-contains dict key)

Note that this check has no effect when the optional default argument is nil, and really only serves to distinguish the case where the key's value is nil:

(let ((res '(dict "foo" nil)))
  (nrepl-dict-get res "foo" :not-found) ;; => nil
  (nrepl-dict-get res "bar" :not-found) ;; => :not-found

  ;; Note the subtle difference:
  (or (nrepl-dict-get res "foo") :not-found) ;; => :not-found
  (or (nrepl-dict-get res "bar") :not-found) ;; => :not-found
  )

One simple improvement would be to only perform the contains? check when default arg is non-nil, turning it back into O(n) in the 2-argument case.
... In fact as far as I can tell, the 3-argument call to nrepl-dict-get is not used at all in the entire Cider and clj-refactor codebases! I guess it was originally written to mirror the semantics of clojure.core/get, overlooking the fact that plist lookups don't have the same O(1) performance guarantees as in Clojure.

So another possible change might be to remove the optional argument entirely, or place a deprecation warning for future removal around its use. I believe nREPL responses can't even contain nils in the first place(?), so its usage would basically be equivalent to the regular Elisp idiom of (or (nrepl-dict-get ..) <default>).

[bbatsov]

... In fact as far as I can tell, the 3-argument call to nrepl-dict-get is not used at all in the entire Cider and clj-refactor codebases! I guess it was originally written to mirror the semantics of clojure.core/get, overlooking the fact that plist lookups don't have the same O(1) performance guarantees as in Clojure.

Yeah, you're probably right.

I believe nREPL responses can't even contain nils in the first place(?)

Indeed. Bencode has no representation for nil. It seems to me that this can just be removed, as I just can't see any uses for it. (and you not finding any kind of proves the point) @alexander-yakushev is our master of performance, so you he might have some other ideas about tweaking the performance of nrepl-dict.

[vemv]

Optimizing things SGTM - thanks!

The nrepl-dict-get name always felt awkwardly verbose to me, so if you found some nice naming, we could use that one and leave the old implementation untouched (which gives us some peace of mind)

[yuhan0]

I'm cautious both about introducing more API functions needlessly and about making breaking changes to such a internal part of the codebase.. probably the safe thing to do now is raise a deprecation warning on a 3-argument call, and then remove it in the future (Cider 2.0?)

In the meantime I'll remove the argument entirely on my local fork and make sure nothing goes wrong (so far all seems fine)

[alexander-yakushev]

No meaningful input from me. Deprecating 3-arity and improving the other one sounds perfect. I agree that adding another low-level function at this point is unnecessary.

[bbatsov]

Okay, I guess we have consensus then.

[yuhan0]

Oops, I was wrong about the complexity analysis - contains? is O(n) after all, not O(n^2) in the size of the dict.
But it does affect the worst vs average case performance, since it will always have to traverse the entire plist instead of being able to return early if the key is near the start of the list.

A quick benchmark shows an average speedup factor of ~0.7 (30% decrease) for dicts with 10 keys, and ~0.4 (60% decrease) for dicts with 100 keys.

In the worst-case comparison (key is at the start of dict, N=100), we get a 92% improvement, but I guess most response dicts are relatively small in practice.

[alexander-yakushev]

I actually like option number 1 better. Since CIDER always used these specialized nrepl-dict-* accessors, it was kinda implied to treat the data values underneath as a black box.

[bbatsov]

A Github code search turned up nothing, so it's probably safe? Being buffer-local variables in the REPL connection buffer, one can consider them as private-ish internal vars, even if they aren't named with the -- convention.

Indeed, those are not meant to be used directly and I'm reasonably sure no one touches them directly. So probably that'd be the easier approach and my vote goes to it.

[bbatsov]

I actually like option number 1 better. Since CIDER always used these specialized nrepl-dict-* accessors, it was kinda implied to treat the data values underneath as a black box.

Yeah, that's a fair point. In general I don't have any objections for both approaches, it just seems to me that the second will be a bit less work. I'm fine with either.

[yuhan0]

Ah, here's one such case which might break under option 1:

cider/nrepl-client.el

Line 1320 in 105da31

(nrepl-log--message-color (lax-plist-get (cdr msg) "id"))

(found by grepping for lax-plist-get, there may be other less obvious instances of this sort of thing)

[yuhan0]

I'll go with option 2 then, probably dogfooding it for a week or two before submitting a PR.