This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2020-01-01
Channels
- # adventofcode (1)
- # announcements (10)
- # babashka (13)
- # beginners (104)
- # braveandtrue (2)
- # calva (5)
- # clj-kondo (23)
- # cljdoc (8)
- # clojure (10)
- # clojure-finland (1)
- # clojure-greece (1)
- # clojure-norway (2)
- # clojure-sweden (7)
- # clojure-uk (29)
- # clojurescript (20)
- # community-development (12)
- # cursive (4)
- # datomic (1)
- # duct (2)
- # emacs (24)
- # fulcro (48)
- # off-topic (5)
- # pathom (2)
- # planck (2)
- # quil (3)
- # reagent (17)
- # reitit (7)
Can anyone help me understand why my Clojure solution is ~100 times slower than someone else's C++ solution? How can I optimize? Code and link to the reference implementation here: https://gist.github.com/Hindol/f918b382b94dd1f5d98306195f231128
If I had to take a wild guess, I'd say it's using +'
instead of +
that's costing you the most time. (Not sure if you run into overflow issues with +
). But if you want to optimize, you should profile your code using a java profiler and work on the bottlenecks.
An easy, but probably insignificant, win would be removing the pre and post conditions.
Also, are you sure yours is slower? Because once memoize, yours also runs under 100ms
I've used VisualVM in the past ☝️
Thanks for the profiler suggestions. I have to do some digging. @U0K064KQV Mine is definitely slower because the C++ one runs the whole program within 0.1 second, including filling the lookup table.
So, got curious and spent some time today trying to port the C++ solution to Clojure so it runs just as fast. Got pretty close, added a comment to your gist
That is pretty fast! Thanks for taking the time. I was hoping to achieve reasonable performance without resorting to Java arrays and aget. I am curious to know how far can I get with idiomatic Clojure.
Although, I do agree the source is also not idiomatic C++. It is hand optimized for the problem at hand. So this is not exactly apples to apples.
The truth is most high performance math algorithms with hot loops will always take a hit from the overhead of Clojure's idioms. And in a way, the idiomatic way to speed those up is to use loop/recur with primitives and possibly even arrays. So depending on your lens, you could call it idiomatic as well
Yeah, I read through the long discussion in #clojure and survived, 😅. Many great points came up, so thanks.
Ya, I learned a lot through it as well. I knew the basics of primitive math and all, but had never really needed to put it in practice so thanks for that
Reminder to myself (and possibly others), (set! *unchecked-math* :warn-on-boxed)
is super helpful in identifying math bottlenecks. Explanation here: http://clojure-goes-fast.com/blog/java-arrays-and-unchecked-math/
I could be wrong, but don't you need to use (partial map f) instead of (map f) when you're trying to use (map f) as an argument for comp?
Thanks for going through it. I am actually using [transducers](https://clojure.org/reference/transducers) here, so it might look a little different. Transducers have the additional benefit of not generating intermediate sequences. P.S. I can confirm that the program outputs the correct answer. My question is only around optimization.
Also, you could try using pmap or mapv and see if that doesn't cut down on your times
I do not want to introduce parallel processing for comparison's sake as the linked C++ code also does not use it.
(s/coll-of :count 2 :distinct true ::foo) might be better for that
Say I had a collection of collections and I want to eval to nil if any of those collections is nill, i.e., (seq [])
evals to nil, but works with only one thing, if I had (seq [["foo"] ["bar" "baz"] "wibble"])
, would I have to construct a macro to do something like this, or is there a combination of apply/reduce/juxt/? that would be already available to use?
Yes, only a handful of functions and a few higher order functions like apply, map, every? etc. can do wonders. Plus not having static typing makes these functions (and combinations) even more useful.
@UJRDALZA5 How so (regarding not being static typing)?
I contrived an example. Hard to do the same in a typed language, if at all possible. Of course you can make a list of Object
s, but then you are erasing types anyways.
(map (partial apply min) [[2 4 3 5 1] [2.0 4.0 3.0 5.0 1.0]]) ; => (1 1.0)
Well, you could create a function that detects the type of the list extending Number, then implements the comparator as needed. But it's not simple at all! Thanks for your example. I'm new to Clojure and your example has been quite an eye-opener.
That's a very silly and contrived example. There definitely are better example without using heterogeneous data structures. I can think of one more, the +' and *' operations in Clojure checks for overflow and expands the type as needed, because, noone is really counting on the return type.
So, you can sum a bunch of longs and have a long back if the sum fits, else you get the arbitrary precision BigNum type.
One downside to that is though, you might not be aware that you are getting a different type behind the scenes. But it might not matter much anyway, because the whole system is dynamic
in general, the lifetime of transients should be visible in a single scope. Ie, you know where they are created and where they are persisted. You are in for hurt if they escape and are passed around
I'm not sure. I'm building Collector implementation, which require to work with something mutable. So I'm collecting into transient and finisher makes that persistent. Am I really at a bad spot?
this is already a problem - if you don't use the return value of ops on transients you will eventually get garbage results
yes. I've followed advice to use atom and actual persistent data structures, it's safe now and without transients. I guess I'm not the first one ever to hit the wall with transients 🙂
yeah, sorry, when I wrote this I forgot I was in deep scrollback haha
I want to make sure with some assertion that proper collection is passed to initializer.
The only way I know to check whether something is a transient in Clojure/JVM is to check whether it is an instance of one of the several classes that are transients, about 4 or 5 of them, maybe, if you want to cover all kinds of transient collections in core: sets, maps, vectors, etc.
I think I can use ITransientCollection
interface that all of those implement. Is it a good idea?
If they all implement that interface, sounds reasonable to me. I have not checked whether they all do myself.
if you treat it like a reduce, then you don't need to check if a transient is passed and you can also use immutable collections
I do use reduce. Not sure about the nature of Collector though, I'm afraid it mutates internally by using methods like List::add
you have to pass around the result of operations, just like with the immutable collections
But I have to admit that I should also try to just use traditional persistent data structures. It should work as well as you said.
you might not notice for small collections (< 32)
as the return value will be the same instance, but at some point it will stop working
the main point is, transients are designed to return the modified collection and you should not continue using the source collection
that is, exactly the same calling style as persistent colls
(.collect (.stream [1 2 3 4])
(java.util.stream.Collector/of
(reify
java.util.function.Supplier
(get [_]
(atom 0)))
(reify
java.util.function.BiConsumer
(accept [_ a b]
(swap! a + b)))
(reify
java.util.function.BinaryOperator
(apply [_ a b]
(swap! a + @b)))
(reify
java.util.function.Function
(apply [_ a]
@a))
(into-array java.util.stream.Collector$Characteristics [])))
from https://clojure.org/reference/transients: "Note in particular that transients are not designed to be bashed in-place. You must capture and use the return value in the next call."
(defn- merge!
[x y]
(reduce (fn [acc [k v]] (assoc! acc k v))
(transient x)
y))
(deftype TransientCollector [t-coll]
java.util.stream.Collector
(supplier [_] (->Supplier (fn [] t-coll)))
(accumulator [_] (->BiConsumer (fn [c item] (conj! c item))))
(combiner [_] (->BinaryOperator (fn [x y] (merge! x y))))
(finisher [_] (->Function (fn [c] (persistent! c))))
(characteristics [_] #{Collector$Characteristics/UNORDERED}))
The problem is the accumulator doesn't return a new accumulated value, it expects to mutate the inputs
They are not "mutable collections" you will not get correct results using them that way
You tests are just not broad and large enough to hit the cases where they return a new object
You will almost always get a mutated object back, but there are known cases where you are guaranteed not to get one back. I will add an explicit example to http://ClojureDocs.org and link to it in a couple of minutes and put the link here, since I can't seem to find such an example there right now.
I have to agree. Now it does not even make sense to me to use transients... I can use java collections instead and it's very likely to be more idiomatic.
You can do it, you just need a mutable cell (like an atom) to adapt between the expectations of the two models
so I made my thing work like I want (i'll just make funcs and spec them as well after), can I do something to make it better ? https://0bin.net/paste/DXy6FMkqNVkRkVjA#WW-S2MDN0JgHLsJArW5lEc85ImEef11oPvfXRAYztDK
There is s/int-in
https://clojuredocs.org/clojure.spec.alpha/int-in
also; not super familiar with game boy assembly, but you seem to have two formats for instructions; either a keyword ‘the instruction’, or a map with a key as its instruction and some sort of tuple with arguments. I’d say that you would have an easier time dispatching if there was only one form
(just random observations, hope they help!)
didn't know about int-in it's perfect ! and about the data form I just thought that it would be nice to have something like that {:ld [:A :F]}
for example which conforms to the ::instruction
spec
I am not sure what you are going to use it for & know too little about (what presumably is a) gameboy intepreted to know what is ‘nice’ to have in data structures
ah the other way
Assembling from plain text asm files to a binary?
or clojure data structures
interesting!
@ales.najmann I have just added an example to the http://ClojureDocs.org page documenting the conj! function that demonstrates how in some cases, not using the return value of transient operations can give incorrect results: http://clojuredocs.org/clojure.core/conj!#example-5e0d14f7e4b0ca44402ef804 (even though in many cases it does work as you hope)