Fork me on GitHub
#beginners
<
2020-01-01
>
hindol07:01:47

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

codonnell13:01:48

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.

hindol17:01:17

Thanks. Which profiler do you recommend?

didibus02:01:55

VisualVM is free and included with the JVM

didibus02:01:33

clj-async-profiler is also free and nice because you can use it from inside the repl

didibus02:01:51

Also, are you sure yours is slower? Because once memoize, yours also runs under 100ms

codonnell12:01:48

I've used VisualVM in the past ☝️

hindol15:01:19

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.

didibus00:01:20

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

hindol06:01:42

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.

hindol06:01:20

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.

hindol06:01:16

Oops, just noticed you added a second comment as well with more details.

didibus06:01:33

Ya, I have 3 comments

didibus06:01:41

The last one is possibly the most idiomatic-ish

didibus06:01:07

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

hindol07:01:33

Yeah, I read through the long discussion in #clojure and survived, 😅. Many great points came up, so thanks.

didibus17:01:02

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

hindol07:01:35

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/

Akshay C. Gollapalli10:01:10

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?

hindol10:01:49

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.

Akshay C. Gollapalli10:01:39

Also, you could try using pmap or mapv and see if that doesn't cut down on your times

hindol10:01:07

I do not want to introduce parallel processing for comparison's sake as the linked C++ code also does not use it.

uknys13:01:49

how can I check with spec, that a tuple has 2 unique elements from the same spec ?

alexmiller15:01:46

(s/coll-of :count 2 :distinct true ::foo) might be better for that

👍 4
uknys16:01:56

Perfect thx a lot :)

dharrigan15:01:03

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?

dharrigan15:01:51

(every? seq [.......])

👍 4
dharrigan15:01:54

clojure ftw!

hindol16:01:29

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.

Gulli18:01:31

@UJRDALZA5 How so (regarding not being static typing)?

hindol18:01:53

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 Objects, 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)

Gulli19:01:38

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.

Gulli20:01:25

But also, heterogeneous data structures can be a minefield.

hindol15:01:08

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.

Gulli15:01:33

That's nifty

hindol15:01:41

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.

Gulli15:01:40

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

littleli19:01:22

Is there a way, some predicate for example, to check if collection is transient?

dpsutton19:01:55

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

dpsutton19:01:07

the answer being, if you need to check, you're in a bad spot

littleli19:01:54

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?

noisesmith17:01:00

this is already a problem - if you don't use the return value of ops on transients you will eventually get garbage results

littleli21:01:00

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 🙂

noisesmith21:01:12

yeah, sorry, when I wrote this I forgot I was in deep scrollback haha

littleli19:01:35

I want to make sure with some assertion that proper collection is passed to initializer.

andy.fingerhut19:01:21

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.

littleli19:01:33

I think I can use ITransientCollection interface that all of those implement. Is it a good idea?

andy.fingerhut19:01:44

If they all implement that interface, sounds reasonable to me. I have not checked whether they all do myself.

littleli19:01:07

I'll check of course. Thanks Andy 🙂

hiredman19:01:13

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

littleli19:01:52

I do use reduce. Not sure about the nature of Collector though, I'm afraid it mutates internally by using methods like List::add

hiredman20:01:00

and if you can't make it a reduce, transients won't work correctly

hiredman20:01:27

because transients are not mutable collections

hiredman20:01:01

you have to pass around the result of operations, just like with the immutable collections

hiredman20:01:52

which is not what Collector expects

hiredman20:01:16

so you need to wrap things in some mutable cell (like an atom)

littleli20:01:18

I only use conj! merge! (which uses reduce)

littleli20:01:24

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.

hiredman20:01:02

you can't use a transient data structure directly in a Collector like that

hiredman20:01:14

it amounts to what the docs call "bashing in place"

hiredman20:01:09

a transient is not the same as a mutable collection

littleli20:01:42

Well, I don't understand why not

littleli20:01:52

My tests are passing so far

alexmiller20:01:37

you might not notice for small collections (< 32)

alexmiller20:01:59

as the return value will be the same instance, but at some point it will stop working

alexmiller20:01:09

the main point is, transients are designed to return the modified collection and you should not continue using the source collection

alexmiller20:01:22

that is, exactly the same calling style as persistent colls

hiredman20:01:25

(.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 [])))

hiredman20:01:33

if you stick the transient in an atom similar to that you can use it

alexmiller20:01:47

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."

littleli20:01:23

@hiredman @alexmiller

(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}))

hiredman20:01:37

The problem is the accumulator doesn't return a new accumulated value, it expects to mutate the inputs

hiredman20:01:09

Which is not the correct behavior for transients

hiredman20:01:27

Transients operations will sometimes return a new object

hiredman20:01:55

They are not "mutable collections" you will not get correct results using them that way

littleli20:01:14

well, the problem is, I'm getting correct results so far...

hiredman20:01:33

They are more like immutable collections with shortcuts

littleli20:01:57

I believe you, but my observation is different from the expectation.

hiredman20:01:42

Transients do not always return a new collection

hiredman20:01:18

You tests are just not broad and large enough to hit the cases where they return a new object

andy.fingerhut20:01:22

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.

littleli20:01:33

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.

littleli20:01:22

Thank you for your help!

littleli20:01:32

I wanted to use nice clojure-like api, but it's just wrong in this case.

hiredman20:01:43

You can do it, you just need a mutable cell (like an atom) to adapt between the expectations of the two models

littleli20:01:28

Ok. I'll follow your example.

littleli22:01:16

Of course what you suggested worked really well. Thanks, I took a lesson 👍

uknys21:01:58

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

Lennart Buit21:01:21

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

Lennart Buit21:01:31

(just random observations, hope they help!)

uknys22:01:27

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

Lennart Buit22:01:04

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

uknys22:01:01

an assembler using clojure ^^'

Lennart Buit22:01:21

ah the other way

uknys22:01:43

yes, using clojure to make an assembler without being annoyed by the parsing phase

Lennart Buit22:01:22

Assembling from plain text asm files to a binary?

Lennart Buit22:01:43

or clojure data structures

uknys22:01:50

clojure data structures to binary

uknys23:01:15

a bit like magic / mage for the coreclr which gave me the idea ^^

andy.fingerhut21:01:00

@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)

👍 8