This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2021-08-09
Channels
- # announcements (5)
- # aws (5)
- # babashka (7)
- # beginners (152)
- # cider (10)
- # clj-kondo (30)
- # clj-on-windows (1)
- # cljs-dev (14)
- # cljsrn (19)
- # clojure (94)
- # clojure-australia (4)
- # clojure-europe (43)
- # clojure-nl (2)
- # clojure-uk (11)
- # clojurescript (16)
- # clojureverse-ops (5)
- # code-reviews (7)
- # community-development (6)
- # core-async (29)
- # cursive (50)
- # datomic (22)
- # docker (10)
- # figwheel-main (3)
- # fulcro (4)
- # graalvm (1)
- # introduce-yourself (2)
- # kaocha (9)
- # lambdaisland (2)
- # lsp (19)
- # malli (37)
- # off-topic (50)
- # polylith (8)
- # portal (1)
- # reagent (10)
- # rum (1)
- # shadow-cljs (24)
- # spacemacs (14)
- # yada (2)
question about performance. I've starting a bit of a performance analysis of a program and the first thing I see is that the following function seems to be a bottleneck.
(letfn [(cr [td operands]
(cond (empty? operands)
(unit td)
(empty? (rest operands))
(first operands)
:else
(cons (first td) operands)))]
(defmethod create 'or
[td operands]
(cr td operands))
(defmethod create 'and
[td operands]
(cr td operands)))
the cond
is unfortunate because the sequence is rarely empty, yet the empty?
check appears first. It is basically asking which of the three cases are occurring, 2-or-more elements (most likely), singleton, or empty.
Is there any clever way to do this check more efficiently. I thought about a case and some soft of bounded count. but bounded count is not guaranteed to return the <= bound, as I understand.
Perhaps something like the following,
(case (min 2 (bounded-count 2 operands))
0 (unit td)
1 (first operands)
2 (cons (first td) operands))
does case
compile to a goto-like structure, or does it compile to a sequence of if-then-else like structures?
case ultimately complies to a single JVM tableswitch bytecode which is like an optimized goto
I could define a vector of three elements, and do something very cryptic like ((my-fun-arr (min 2 (bounded-count 2 operands))))
, note the double open paren to both get the nth element and then immediately funcall it.
I'm not sure how to interpret that. I think it means that sometimes case compiles to a table lookup and sometimes it doesn't. right? How can I force it to be a table lookup?
I’m not a java expert. The link is here only because I remember looking at it when I read through the source code
(case (bounded-count 2 operands)
0 (unit td)
1 (first operands)
(cons (first td) operands))
This avoids an extra call for min
and should generate a table lookup since all the keys are integers.And if you know for sure that operands
is counted?
, just use (count operands)
. Although given that cons
, I suspect that's not the case.
hmm. interesting because that was the opposite of my intuition. if I give a default as the final operand of case, my intuition was that it would have to do the check twice, once for the table out-of-bounds, and a second time for the table lookup.
Roughly
21: iload G__15905
23: tableswitch {
2: 52
3: 73
4: 94
5: 115
default: 136
}
This loads the case value, the table switches on value and goes to lineAt the end of each case you have
70: goto 137
Which is the "end" of the switch statementin all normal situations (excluding machine generated test cases) operands is going to be a list which a human being has typed in, thus is 2,3,4,5 but rarely more. So perhaps simply count
is better than (min 2 (bounded-count ...))
More to your case:
(defn foo
[x]
(case (count x)
0 100
1 200
300))
decompiles to
public static Object invokeStatic(final Object x) {
final int G__15943 = RT.count(x);
Object o = null;
switch (G__15943) {
case 0: {
o = fast$foo.const__2;
break;
}
case 1: {
o = fast$foo.const__4;
break;
}
default: {
o = fast$foo.const__5;
break;
}
}
return o;
}
And in bytecode:
public static java.lang.Object invokeStatic(java.lang.Object x);
Flags: PUBLIC, STATIC
Code:
linenumber 1
0: aload_0 /* x */
linenumber 3
1: invokestatic clojure/lang/RT.count:(Ljava/lang/Object;)I
4: istore_1 /* G__15951 */
linenumber 3
5: iload_1 /* G__15951 */
6: tableswitch {
0: 28
1: 34
default: 40
}
28: getstatic clj_fast/fast$foo.const__2:Ljava/lang/Object;
31: goto 43
34: getstatic clj_fast/fast$foo.const__4:Ljava/lang/Object;
37: goto 43
40: getstatic clj_fast/fast$foo.const__5:Ljava/lang/Object;
43: areturn
BTW, wrt clojure syntax, I always forget that the default of case
takes no :else
but they default of cond
takes an :else
.
well anything that is not false 🙂
In the end, I don't think the optimized code is too cryptic.
(letfn [(cr [td operands]
(case (count operands)
0 (unit td)
1 (first operands)
(cons (first td) operands)))]
(defn create-or [operands]
(cr '(or) operands))
(defn create-and [operands]
(cr '(and) operands)))
since this is bottle-neck code, it might even be better to inline the case
twice, and just put a comment that the code is repeated because it is critical path
good point
It seems like a small, well behaved function, it shouldn't be a bottle neck.
It can lie, though, because of laziness. If operands
are lazy, count
will realize them and you'll see the call stack of the lazy sequence realization in the stack of cr
and not the function which returned the lazy sequence
you might be right that it's not really a bottleneck. I was supposing this from my first unexperienced reading of the flamegraph
I don't feel bad because the optimized version isn't very ugly.
hmmm. good point about laziness. counting just one more element might have unexpected side effects. indeed. there may be cases in my code where counting one more element means realizing a lazy value by doing a tree traversal to compute it 😞
maybe I should change it back to bounded count???
no, I know that either the first element is nil, or it has 0 length. I'd still need to distinguish those cases
right?
aren't we going in circles. calling seq is back to my idea of calling empty?
IIRC seq
will still realize the first chunk. so there's no O(...)
difference between seq
and bounded-count
.
empty?
is just a small wrapper around seq
bounded-count realizes a chunk. right?
who decides the chunk size?
(defn bounded-count
"If coll is counted? returns its count, else will count at most the first n
elements of coll using its seq"
{:added "1.9"}
[n coll]
(if (counted? coll)
(count coll)
(loop [i 0 s (seq coll)]
(if (and s (< i n))
(recur (inc i) (next s))
i))))
If it's counted it will count allwell most of my sequences (rule-of-thumb) 5 or less.
only in machine generated test cases are the sequences really long.
> If it's counted it will count all Just to be clear - that will be O(1) because that's what "counted" means.
/* A class that implements Counted promises that it is a collection
* that implement a constant-time count() */
O(1) is a bit of a deception. It is O(1) times the complexity of generating an element, which in some cases might be exponential if it involves a tree traversal. right?
Unless you need to check for more than 2 elements, the code using seq
and next
above is probably the simplest one.
But before we run to deep into the weeds, @U010VP3UY9X I think you should rerun your profiling, see more https://clojurians.slack.com/archives/C03S1KBA2/p1628502511085100?thread_ts=1628260780.412300&cid=C03S1KBA2
@U010VP3UY9X No. counted?
means that there will be no generation of any sort. Basically, the number is already baked into the structure.
isn't seq
and next
equivalent to empty?
and (empty? (rest ...))
? which is what my original code was.
No, seq
is the exact opposite of empty?
Check the docstring of the functions, especially empty?
.
(defn empty?
"Returns true if coll has no items - same as (not (seq coll)).
Please use the idiom (seq x) rather than (not (empty? x))"
{:added "1.0"
:static true}
[coll] (not (seq coll)))
same in the sense of complexity.
I cheat a little. (rest [])
= ()
, (next [])
= nil
, which allows me to avoid one more check
of course opposite logically/semantically
All solutions so far are the same in the sense of complexity, except for the count
one.
hmmm. so my original code was perhaps better. To repeat. my original complaint was that I am always checking emptiness first even though I know that the sequence is rarely empty.
perhaps an emptiness check must always be done, even internally by count
?
This is slightly a case of looking for evidence under the flashlight. As long as we don't know where the real performance impact is, just go with what you find most readable. I can show you gloriously mangled code which makes the JVM happy
Anyone used Clojure and Kafka to spin up additional services on AWS (or similar cloud service) based on new partitions in Kafka? Elaborated here https://clojurians.slack.com/archives/C09N0H1RB/p1628505238008500
I was fooling around with protocols and this puzzles me:
user=> (defprotocol Quux)
Quux
user=> Quux
{:on user.Quux, :on-interface user.Quux, :sigs nil, :var #'user/Quux, :method-map {}, :method-builders {}}
Unable to resolve symbol: typeof in this context
user=> (type Quux)
clojure.lang.PersistentArrayMap
user=> user.Quux
user.Quux
user=> (type user.Quux)
java.lang.Class
user=>
why is Quux
a map?A protocol is a named set of named methods and their signatures
That's what you see when you evaluate Quux
.
defprotocol will automatically generate a corresponding interface,
with the same name as the protocol, i.e. given a protocol:
my.ns/Protocol, an interface: my.ns.Protocol
That's what you see when you evaluate user.Quux
.is there anything else in the language that does this? AFAIK this is different from how deftype
and definterface
operate
Can someone help me with laziness. Does this code guarantee that the predicate, pred
is NOT called after it returns true the first time? Do I need to control the call more precisely if that is important to me?
(defn conversion-C10
"(and A B C) --> (and A C) if A is subtype of B
(or A B C) --> (or B C) if A is subtype of B"
[self]
(letfn [(pred [u]
(exists [v (operands self)]
(and (not= u v)
(= (annihilator self u v) true))))]
(let [subs (filter pred (operands self))]
(if (empty? subs)
self
(let [sub (first subs)
keep (setof [sup (operands self)]
(or (= sup sub)
(not= (annihilator self sub sup) true)))]
(create self keep))))))
I think it is not important for the question, but here is the code for exists
(defmacro exists
"Test whether there exists an element of a sequence which matches a condition."
[[var seq] & body]
`(some (fn [~var]
~@body) ~seq))
Filter makes no such guarantees and will quite possibly do more “work” here than you intend. You do not have control over the amount of laziness like you are hoping
Would (first (split-with pred ...))
be better? Or (take-while (complement pred) ...)
?
there are no guarantees about how many elements of a lazy sequence are evaluated
yes, that is what I was hoping to avoid because the filter option is so elegant. 😞
unfortunately with loop/reduce I have to make an assumption about the type of sequence. i.e., whether it is list-like [`first`/`rest`] or whether it is index based. In these types of cases I try to use reduce
/`reduced` if possible.
you can use loop/recur with exit on a condition or reduce with reduced to early exit as other options
Does that hold if we only care about how many times pred
is called, and not how many elements of the lazy seq are realized?
you can use loop or reduce to call pred, but if the function calling pred is lazy you no longer control how many times it is called
@UJY23QLS1 to be more specific, in the example above pred
is passed to filter, and called by filter, since filter is lazy you can't have true control of when and how many times it uses its arg
(also editorial comment using a side effecting function as a filter seems very odd...)
Ok. After using Reveal for like 5 min, I recant all previous reservations re: tap>
. It’s super nice to have real values from the middle of a process show up in the repl on demand.
cc: @seancorfield @vlaaad
I wasn’t too excited about the idea of making tap>
a middleman for an atom when def
works almost as well. But having dev tool integration is a real improvement.
The nice thing about tap>
is that you can leave it in your code and let it go to production if you want and it's "harmless". Which means you can also attach a viewer to in via a Socket REPL in production if you need to debug something complex there.