Clojurians Log v2
beginners
I have a function that’s sort of hard to pull apart to debug. What’s a good way to basically print out each intermediate step without hacking it apart?
defn my-merge-with
[f & maps]
(reduce (fn [acc v]
(reduce (fn [iacc [key newval]]
(assoc iacc key (if-let [oldval (key iacc)]
(f oldval newval)
newval)))
acc (seq v)))
{} maps))So i figured out the bug just by throwing in printlns, but more interested in best practices
test smaller pieces
@grazfather Stu Halloway has a great talk online where he defined the REPL error handler to just report a very generic error (so there are no clues about the failure) and then he shows how to step through the code in the REPL, one expression at a time, so you can see what each piece does and where your code "breaks". I can't remember which talk that is, unfortunately. Then he has another talk called Debugging With The Scientific Method which is a really good overall look at how you should approach debugging in general: https://github.com/matthiasn/talk-transcripts/blob/master/Halloway_Stuart/DebuggingWithTheScientificMethod.md (transcript with slides, links to video if you prefer that format).
(can anyone remember the talk I'm thinking of with the generic error handler and the REPL exploration of the code?)
I’ve seen his scientific method talk actually
it’s more a problem that’s mechanical
how do I non-annoyingly extract parts to test and extract information
With the code above, my first suggestion would be to extra the two (fn [..] ..) forms as named private functions so you can explore those directly from the REPL.
Another trick is, in a comment form, to write def forms for the parameter names so you can eval subforms of the functions directly in the REPL. I just did this today in trying to debug some refactoring I was doing...
actually, yeah I have a question about that: How do I send just a subform to the repl in spacemacs? spc m e f sends the top level, and spc m e e just gives me the symbol name
For example, I added this RCF:
(comment
(countries "fr")
;; so that I could test subforms in the function above:
(def ^:private locale "fr_FR")
(def ^:private featured? #{"GB" "FR"})
(def ^:private as-clojure? true)
.)all-countries (map #(set/rename-keys % {:iso :value})
(countries (if (seq locale) (subs locale 0 2) "en")))
featured (into [] (filter (comp featured? :value) all-countries))
collated-query (cond-> featured
(seq featured)
(conj {:name "----" :value "__"})
:all
(into all-countries)
(not as-clojure?)
(cfml/to-clj-struct))]No idea about any variant of Emacs, sorry, but I know all Clojure-integrated editors do have a commend for sending just the "current" form at the cursor.
yeah, cqq works well in fireplace
no sweat I will figure it out
I would expect spc m e e to eval the form if your cursor is on or just after the )
I am definitely more accustomed to printf debugging or step by step
Yeah, you’d think so, right?
With VS Code/Clover, I can "eval block" whenever my cursor is on or just after the opening ( or on or just after the closing ) in general...
@grazfather it may not be exactly what you are looking for, I have been just finding my way around spacemacs eval as well and have been using spc m e v with my cursor on the opening bracket of the form
Actually I use , e v, I believe spacemacs comes with , already set by default as the major mode leader key
Hmm, I don't see that listed on https://www.spacemacs.org/layers/+lang/clojure/README.html#evaluation @robertfrederickwarner?
(it certainly has a lot of "send and eval" variants though!)
spacemacs recently went through a big keybinding shuffle, I'm guessing that hasn't landed on master yet. Most installs recommend using the develop version
https://develop.spacemacs.org/layers/+lang/clojure/README.html#evaluation is for the develop version
Oh joy 🙂 Calva did a similar reshuffle and folks are still "recovering" from that 🙂
I almost ditched it after they dropped that! Massive shock to the system. But I got tired of maintaining my own emacs config pretty quickly and decided to just go with the flow
@robertfrederickwarner thank you!
glad to help 🙂 I recently completely redid my setup using the practicalli guide and their provided configs, it got everything working nicely out of the box. https://practicalli.github.io/spacemacs/
Ah, and spc m e e works but you have to to be actually after it, so on the next line to eval a top level. I’ll stick with e f and now e v
yeah practically brought me here
and clojure force me into emacs 😅
yeah I'm finding those two get me 99% of what I need
Now I just need to figure out all the slurping stuff
slurp and barf, don't leave home without em
Yep! I have those well enough that I wish I could use them in my golang work
thanks for the help, guys, good night
And the reshuffle was about three of the bindings. 😃 You simply don’t mess with people’s muscle memory.
So I found this side-by-side comparison of Clojure and Clojurescript. https://www.freecodecamp.org/news/here-is-a-quick-overview-of-the-similarities-and-differences-between-clojurescript-and-javascript-c5bd51c5c007/ I'm sure this isn't an exhaustive list, but I'd be curious to know what other features there are. Has anyone else made a list like this? If not, how can I see JavaScript generated from ClojureScript, with variable and function names intact?
Here you go: http://app.klipse.tech/
Awesomesauce!
How to do some initialize things when the first load in a namespace?
Can you elaborate on what you mean by "initialize things" please?
Some myself logic need to do before execute code of namespace.
In other words, I just need a way to execute when first load namespace.
Wow, Thank you for your help and give me some library for that.
I don't think there is a "pre-load" eval that would eval functions and do something before the namespace is loaded.
Someone else might know better
@xu20151211 do you mean load the dependencies from project.clj? when you load lein repl with dependencies it load all the library
hi all, i've read atom description : Atoms provide a way to manage shared, synchronous, independent state. They are a reference type like refs and vars. question is : how many atom can i made? does each atom = 1 thread? is there any side effect to use a lot of atom?
Hi there. Not sure if this is the right channel to ask this but I can't seem to deploy to Clojars. I'm going through the steps as mentioned on Clojars but whenever lein is sending the package I always get this:
Could not transfer artifact epsilon:epsilon:jar:v1.0.0 from/to clojars (<https://repo.clojars.org/>): Failed to transfer file <https://repo.clojars.org/epsilon/epsilon/v1.0.0/epsilon-v1.0.0.jar> with status code 401
You can create as many atoms as you want. Each one only takes a relatively small amount of memory, perhaps around 32 bytes or so, depending upon the JVM version you are using. No threads are created when you create an atom. An atom can be accessed from any or all threads that are in your JVM process that have a reference to it.
Many Clojure developers find that if they store a collection inside of an atom, e.g. a Clojure map, that they have no need for a large number of atoms in a typical application. Rich Hickey mentions how many Clojure applications can easily get by with a few, or one, atom.
ohhh okay... i don't really get the Rich Hickey part?
I'm looking for one of his talks where he mentions the perhaps surprising fact that many Clojure applications, even complex ones, can often get by with very few atoms.
does he said, that by using atom, it'll make things/apps much more simpler?
i.e. You can create many atoms if you want, but there is often no need to do so.
You can write complex intertwined code even with atoms, refs, agents, etc. These mechanisms don't force simpler code. They can enable simpler code.
"An atom can be accessed from any or all threads that are in your JVM process that have a reference to it." This part is enlightening for me, we could update using atom and pass it to another thread then wow...
atoms, refs, and agents are intended to help simplify writing Clojure programs that access and update state in a multi-threaded program. atoms are sometimes used even in single-threaded programs, as a place to store some value that you want to be able to change over time.
yes, and by storing in memory, what memory? is it in the cache?
sorry this is just out of curiosity
What cache are you referring to? The CPU's L1/L2/etc. caches?
@adrianimanuel No, Isn't relate about dependencies.
that i don't know. just curious where the atom stored? and if we stop/restart the repl is it still storing?
All values in a Clojure program, whether they are contained within atoms, refs, agents, or not, are in the main memory of your system, which is usually DRAM hardware chips that loses its state if the power goes off, but CPUs make copies of parts of that memory in on-chip L1/L2/etc. caches temporarily near the time when they are accessing those values, just as they do when running programs written in any programming language.
CPU cache behavior is designed into the CPU hardware design, independent of programming language (although a few low-level programming languages, e.g. assembly language, give you mechanisms for having some effect on how those caches operate -- those are rarely explicitly used in high level languages like C, C++, Java, or Clojure)
ahh okay, thanks a lot for the explanation
now i know better
No values in Clojure are automatically stored to non-volatile storage like a hard disk or SSD, unless you make explicit calls that write the data there.
There are probably some third-party libraries, separate from Clojure, that provide such "automatically store updates to disk/SSD when you make changes", but those are separate libraries not built into Clojure.
okay noted
that’s an authentication issue. either your GPG isn’t set up correctly or they don’t have your public key
I have two functions, each gets me the minimum year and date respectively. What Iam seeing the function works good if i pass integer values and get me min value, but breaks when i pass date value, what will be the alternative of this function to make it work for date values ? (def data [{:date1 "2012-10-07", :emp "emp-1", :yrs 2} {:date1 "2014-10-06", :emp "emp-2", :yrs 3} {:date1 "2017-10-08", :emp "emp-3", :yrs 1}] (def dates (map :date1 data)) (def years (map :yrs data)) (def min-year-value (apply min years)) (println "Min years in employment is : " min-year-value) ;; returns 1 (def min-date-value (apply min dates)) (println "Min employment date is : " min-date-value) ;; throws exception: class java.lang.String cannot be cast to class java.lang.Number
you need to use a date/datetime type to be able to compare dates
It breaks because you are trying to find a minimum in a vector of strings instead of numbers. So (apply min dates) will fail. Take a look at a time library that helps to convert date strings to something that you can compare. Maybe this one? https://github.com/dm3/clojure.java-time
So I've created a GPG key pair, signed credentials.clj and then do lein deploy clojars as instructed by clojars itself.
but it seems that clojars keeps refusing my file transfer.
any code at the top level of the namespace (usually this is just "outside a defn") will execute when the namespace is loaded
usually needing one of these is a sign of a design problem (but it could be needed because of some dep like javafx that needs initialization)
for a more principled approach, there are libs like stuartsierra/component and integrant which are designed to manage "lifecycles" of code objects, which includes initializing all your namespaces, plus shut down / restart if needed https://github.com/stuartsierra/component https://github.com/weavejester/integrant
Hello fellow beginners! After taking a break from streaming my Clojure Startup in a Month project, I'm getting back into it this week. We start each stream with a warmup exercise. Today's comes from @pez of VS Code Calva renown, and it sounds really interesting! It will consist of implementing this 1800-year-old algorithm for finding prime numbers: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes If you'd like to watch me stumble through it (I've been programming in Clojure for all of two months), I'll be starting the stream in about 5-10 minutes: https://www.twitch.tv/a_fry_ We also have a channel if you'd like to join: #startup-in-a-month
I'll add another which is a bit more performant and using java BitSet:
(defn sieve [end]
(let [bs (BitSet. end)]
(loop [x 2]
(if (= x end)
(-> (doto bs (.flip 0 end)) .stream .toArray vec)
(do (doseq [y (range (* x 2) end x)]
(.set bs y))
(recur (.nextClearBit bs (inc x))))))))(time
(count
(sieve 1000000)))
"Elapsed time: 26.078883 msecs"
=> 78500guess I could add a (drop 2 ... to throw away the 0 and the 1. Anyway, this is fairly performant and could be argued cheating by walking into java land. Though I have to say, any time I've tried to push performance far enough, I end up using some java stuff in clojure.
my laptop must be slow. It's 4x slower on my machine 😮
more than 10x actually when doing count.
(time
(count
(sieve 1000000)))
"Elapsed time: 375.747701 msecs"
=> 78500: ) yeah, I'm running this on a workstation and I ran it a few times in the repl and picked one timing randomly. Not exactly scientific, the times tend to bounce between 25ish ms and 40ish
I need to have a talk with HR, I need a new laptop!
CPU: Intel Core i7-7700 @ 8x 4.2GHz
OS: Ubuntu 20.10
JVM: 11.0.10.9.1-amznnot exactly new, but it was fast a few years back and these days not that much happens year to year so still pretty fast
interesting, this is the same machine running your sieve-primes above:
(time
(count
(sieve-primes 1000000)))
"Elapsed time: 1115.377674 msecs"
=> 78499yeah, my avg time for that over 5 runs was 1466.8
so not that big a difference there
anyway, would love to see some more solutions, I learn a lot from reading different peoples solutions to the same problem
oh, there seems to be a #code-golf channel...
I reposted the above solutions there, hope that was ok @pez @qmstuart and @eagonmeng
@pez by the way, (pos? (rem x)) does divisibility
for correctness as it was pointed out above that 0 and 1 should not be there, a version excluding them with BitSet:
(defn sieve [end]
(let [bs (BitSet. end)]
(loop [x 2]
(if (= x end)
(drop 2 (-> (doto bs (.flip 0 end)) .stream .toArray vec))
(do (doseq [y (range (* x 2) end x)]
(.set bs y))
(recur (.nextClearBit bs (inc x))))))))Upgraded my java version, from 8 to 15, now your sieve does:
(time
(count
(sieve 1000000)))
"Elapsed time: 39.0181 msecs"
=> 78500I might as well post my fastest solution so far. (Not that I am super likely to jump down this rabbit hole again 😄 ) I also went for mutability.
(defn sieve [^long n]
(let [primes (boolean-array (inc n) true)
sqrt-n (int (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if (< sqrt-n p)
(concat '(2)
(filter #(aget primes %)
(range 3 (inc n) 2)))
(do
(when (aget primes p)
(loop [i (* p p)]
(when (<= i n)
(aset primes i false)
(recur (+ i p p)))))
(recur (+ p 2))))))))and short-circuiting for n < 2 etc : )
that is fast...:
(time
(count
(sieve 1000000)))
"Elapsed time: 13.828079 msecs"
=> 78498I think the count adds something like 1ms or 2...
Maybe doall adds less?
it's interesting, now it's stuck around 35-40 ms and I can't make it run in ~13 again
and then it does this:
(time
(do (doall (sieve 1000000))
nil))
"Elapsed time: 10.447096 msecs"some jvm hotspot optimization thing perhaps
I use criterium for keeping sanity when timing these things. 😃
yeah, agreed, the only sane way to do this
Your machine is fast, btw!
(crit/quick-bench
(doall (sieve 1000000)))
Evaluation count : 54 in 6 samples of 9 calls.
Execution time mean : 14.509525 ms
Execution time std-deviation : 3.175044 ms
Execution time lower quantile : 11.937822 ms ( 2.5%)
Execution time upper quantile : 18.133132 ms (97.5%)
Overhead used : 2.753197 ns(crit/quick-bench
(doall (sieve-bitset 1000000)))
Evaluation count : 30 in 6 samples of 5 calls.
Execution time mean : 30.563095 ms
Execution time std-deviation : 8.093254 ms
Execution time lower quantile : 24.216931 ms ( 2.5%)
Execution time upper quantile : 39.494854 ms (97.5%)
Overhead used : 6.554876 nsA difference could be that I start with an array with only odd numbers.
my machine by the way is an airtop2 from a few years back. Totally fanless, no moving parts, passive cooling and small form factor. The latest incarnation can be found here <https://fit-iot.com/web/products/airtop3/>
yeah I suspect there are quite a few things I could improve performance vise with the bitset version. Perhaps tomorrow : )
@qmstuart hmm...java 15. Will have to try that
fyi with java 15:
(crit/quick-bench
(doall (sieve-bitset 1000000)))
Evaluation count : 36 in 6 samples of 6 calls.
Execution time mean : 19.852500 ms
Execution time std-deviation : 3.493472 ms
Execution time lower quantile : 16.478030 ms ( 2.5%)
Execution time upper quantile : 23.753494 ms (97.5%)
Overhead used : 7.001575 ns
=> nil
(crit/quick-bench
(doall (sieve-pez 1000000)))
Evaluation count : 66 in 6 samples of 11 calls.
Execution time mean : 11.521028 ms
Execution time std-deviation : 2.464373 ms
Execution time lower quantile : 9.025629 ms ( 2.5%)
Execution time upper quantile : 14.383504 ms (97.5%)
Overhead used : 7.001575 ns
=> nilDamn, there is some serious talent in this thread!
Haha, in my case more like many hours invested in this silly problem: https://clojureverse.org/t/eratosthenes-party-time-a-k-a-feedback-wanted-on-this-implementation-of-eratosthenes-sieve/3801
btw, I also tried bitsets back then. Had a version of my boolean-array solution that used bitsets instead. Didn’t succeed in bringing it to the same speed, but came pretty close:
(defn bs-sieve [^long n]
(let [primes (java.util.BitSet. n)
sqrt-n (long (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if-not (< p sqrt-n)
(concat '(2)
(remove #(.get primes %)
(range 3 (inc n) 2)))
(do
(loop [i (* p p)]
(when (< i n)
(.set primes i)
(recur (+ i p))))
(recur (.nextClearBit primes (inc p)))))))))
"Elapsed time: 4.2257 msecs""Elapsed time: 62.2843 msecs" on the same specI only learnt about transients quite recently. Can you share the solution, @eagonmeng?
@pez, yea, bitsets are applicable surprisingly often and something not everybody knows about...or has the energy to care about. I think if you've taken the time to find it, understand it, and know when to use it it is an indicator that you know what you are doing. Not surprised if it tipped the scales during an interview
Your bitset solution croaks Eric’s test script, btw, @mbjarland. I haven’t figured out why, the test never finishes, afaikt.
Could be because it returns 0 and 1? I can check once I'm by a repl again : )
@pez Sure! Here's my (slightly) more idiomatic clojure implementation with transients:
(defn sieve [n]
(let [limit (inc n)
primes (transient (into [] (repeat limit true)))
sqrt-n (int (Math/ceil (Math/sqrt n)))
filter-multiple (fn [primes p]
(reduce #(assoc! %1 %2 false)
primes
(range (* p p) limit (* p 2))))
sieve-prime (fn [primes p]
(if (get primes p)
(filter-multiple primes p)
primes))]
(let [mask (reduce sieve-prime primes (range 3 sqrt-n 2))]
(cons 2 (filter #(get mask %) (range 3 limit 2))))))A neat thing with transients is that since the ergonomics are the same, the purely clojure implementation without mutability is literally 2 edits away: remove the call to transient for primes at the top, and then take away the bang in filter-multiple, i.e. assoc! -> assoc. Transients gives me a roughly 5x speedup, the pure clojure implementation is ~400ms for me
On my machine your transients solution costs 4x the performance from mutating a byte-array. A cost I think I would be willing to pay in many, even most, cases.
Yeah definitely, that's well within what I'm happy to pay for a more consistent approach and interfacing with other persistent code. But it's pretty cool that transients mesh so well with just the normal stuff we do, so often in thread-safe hot loops it's a super quick drop in for a performance boost!
Ok @pez, @eagonmeng , @qmstuart and gang, took another look at the performance of my solution, results now after tweaks:
(crit/quick-bench
(count (sieve-bitset 1000000)))
Evaluation count : 96 in 6 samples of 16 calls.
Execution time mean : 6.476842 ms
Execution time std-deviation : 79.562876 µs
Execution time lower quantile : 6.411202 ms ( 2.5%)
Execution time upper quantile : 6.574641 ms (97.5%)
Overhead used : 6.046188 ns
=> nil
(crit/quick-bench
(count (sieve-pez 1000000)))
Evaluation count : 72 in 6 samples of 12 calls.
Execution time mean : 10.665594 ms
Execution time std-deviation : 2.495503 ms
Execution time lower quantile : 8.844994 ms ( 2.5%)
Execution time upper quantile : 14.692171 ms (97.5%)
Overhead used : 6.046188 ns(defn sieve-bitset [end]
(let [bs (BitSet. end)]
(loop [x 2]
(if (= x end)
(drop 2 (-> (doto bs (.flip 0 end)) .stream .toArray))
(do (loop [y (+ x x)]
(when (< y end)
(.set bs y)
(recur (+ y x))))
(recur (.nextClearBit bs (inc x))))))))running this on a different machine though so times probably not comparable to before
Way to go!
Eric’s test still can’t cope with it, though. 😃
I get different results on my machine. Here your new version is faster than the previous one, but still takes 2X the time of mine.
(quick-bench (count (mbjarland-bs-sieve 1000000)))
Evaluation count : 12 in 6 samples of 2 calls.
Execution time mean : 97,098755 ms
Execution time std-deviation : 341,019335 µs
Execution time lower quantile : 96,681139 ms ( 2,5%)
Execution time upper quantile : 97,402338 ms (97,5%)
Overhead used : 14,531080 ns
(quick-bench (count (mbjarland-bs-sieve-2 1000000)))
Evaluation count : 12 in 6 samples of 2 calls.
Execution time mean : 78,531183 ms
Execution time std-deviation : 1,032172 ms
Execution time lower quantile : 77,299070 ms ( 2,5%)
Execution time upper quantile : 79,888896 ms (97,5%)
Overhead used : 14,531080 ns
(quick-bench (count (pez-bs-sieve 1000000)))
Evaluation count : 18 in 6 samples of 3 calls.
Execution time mean : 43,063580 ms
Execution time std-deviation : 564,826778 µs
Execution time lower quantile : 42,403500 ms ( 2,5%)
Execution time upper quantile : 43,831587 ms (97,5%)
Overhead used : 14,531080 ns
(quick-bench (count (pez-sieve 1000000)))
Evaluation count : 24 in 6 samples of 4 calls.
Execution time mean : 27,789680 ms
Execution time std-deviation : 344,536671 µs
Execution time lower quantile : 27,344088 ms ( 2,5%)
Execution time upper quantile : 28,228818 ms (97,5%)
Overhead used : 14,531080 nsthat is strange…what java version are you on?
me: Clojure 1.10.0 and java 15.0.1-amzn
java --version
openjdk 15.0.2 2021-01-19
OpenJDK Runtime Environment Zulu15.29+15-CA (build 15.0.2+7)
OpenJDK 64-Bit Server VM Zulu15.29+15-CA (build 15.0.2+7, mixed mode, sharing)I get the same results if I try with 15.0.2.7.1-amzn
Interesting discrepancy.
I run these within an intellij cursive repl. Should not matter though, a java process is a java process
How does my bitset sieve fare on your computer? Pasting again for convenience
(defn pez-bs-sieve [^long n]
(let [primes (java.util.BitSet. n)
sqrt-n (long (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if-not (< p sqrt-n)
(concat '(2)
(remove #(.get primes %)
(range 3 (inc n) 2)))
(do
(loop [i (* p p)]
(when (<= i n)
(.set primes i)
(recur (+ i p p))))
(recur (.nextClearBit primes (+ p 1)))))))))I made a faster version now. Shaves some 30% of my byte-array solution time, even:
(defn pez-bs-sieve-2 [^long n]
(let [primes (doto (java.util.BitSet. n) (.set 0 (inc n)))
sqrt-n (long (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 2]
(if-not (< p sqrt-n)
(drop 2 (-> primes .stream .toArray))
(do
(loop [i (* p p)]
(when (<= i n)
(.clear primes i)
(recur (+ i p))))
(recur (.nextSetBit primes (+ p 1)))))))))best out of a few runs:
(crit/quick-bench
(pez-bs-sieve-2 1000000))
Evaluation count : 102 in 6 samples of 17 calls.
Execution time mean : 6.035838 ms
Execution time std-deviation : 101.771435 µs
Execution time lower quantile : 5.921544 ms ( 2.5%)
Execution time upper quantile : 6.155316 ms (97.5%)
Overhead used : 7.118834 nswhat is quick-bench from ?
<https://github.com/hugoduncan/criterium>
thanks!
@pez nice with the bit flip by setting the high bit! That was bothering me
and also optimizing with sqrt as all the ones below have already been caught...could be argued that it is then a modified algorithm, but works for me. : ) Nice, definitely the fastest so far.
I think it could be argued to be part of the algo 😃 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode
After running some more tests I think I have concluded that:
• It is much faster to aset into a boolean-array than to .clear or .set bits in a BitSet
• It is much faster to .stream .toArray from a BitSet than to filter out the values of a boolean-array
So, I now tried to speed up my filtering by using reducers/filter and it does speed it up enough to make my boolean-array solution as fast as my BitSet one, on my machine. Here’s the latest incarnation:
(defn pez-ba-reducer-sieve [^long n]
(let [primes (boolean-array (inc n) true)
sqrt-n (int (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if (< sqrt-n p)
(concat '(2)
(into [] (r/filter #(aget primes %)
(range 3 (inc n) 2))))
(do
(when (aget primes p)
(loop [i (* p p)]
(when (<= i n)
(aset primes i false)
(recur (+ i p p)))))
(recur (+ p 2))))))))reducers might be a bigger win than it is on mine. Can you test it for me? 😃Someone has tested the writing to BitSet vs to boolean[] more scientifically than I did, but came to similar results. https://www.baeldung.com/java-boolean-array-bitset-performance
Since updating the byte-array is faster, I started to focus on how to get the results from it faster. The reducers solution was one such attempt. Also tried core.async/pipeline, but that was super slow, some 200X slower. It’s not a big enough problem for that tool. 😃 But then I got a tips to try with loop and that does make a difference. Not huge, but anyway:
(defn pez-ba-loop-sieve [^long n]
(let [primes (boolean-array (inc n) true)
sqrt-n (int (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if (< sqrt-n p)
(loop [res []
i 3]
(if (<= i n)
(recur (if (aget primes i)
(conj res i)
res)
(+ i 2))
(concat [2] res)))
(do
(when (aget primes p)
(loop [i (* p p)]
(when (<= i n)
(aset primes i false)
(recur (+ i p p)))))
(recur (+ p 2))))))))Enter transient. 😃
(defn pez-ba-loop-transient-sieve [^long n]
(let [primes (boolean-array (inc n) true)
sqrt-n (int (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if (< sqrt-n p)
(loop [res (transient [])
i 3]
(if (<= i n)
(recur (if (aget primes i)
(conj! res i)
res)
(+ i 2))
(concat [2] (persistent! res))))
(do
(when (aget primes p)
(loop [i (* p p)]
(when (<= i n)
(aset primes i false)
(recur (+ i p p)))))
(recur (+ p 2))))))))
Evaluation count : 60 in 6 samples of 10 calls.
Execution time mean : 10,599681 ms
Execution time std-deviation : 163,784470 µs
Execution time lower quantile : 10,417649 ms ( 2,5%)
Execution time upper quantile : 10,831060 ms (97,5%)
Overhead used : 14,507923 ns(defn pez-ba-sieve [^long n]
(let [primes (boolean-array (inc n) true)
sqrt-n (int (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if (< sqrt-n p)
(concat '(2)
(filter #(aget primes %)
(range 3 (inc n) 2)))
(do
(when (aget primes p)
(loop [i (* p p)]
(when (<= i n)
(aset primes i false)
(recur (+ i p p)))))
(recur (+ p 2))))))))
Evaluation count : 24 in 6 samples of 4 calls.
Execution time mean : 25,913184 ms
Execution time std-deviation : 569,484180 µs
Execution time lower quantile : 25,135620 ms ( 2,5%)
Execution time upper quantile : 26,538920 ms (97,5%)
Overhead used : 14,507923 nsI think at this point the can of worms has been fully opened lol Double byte-array + transient for filter output is a neat way to get around the bottlenecks of either approach Curious though, I wonder how close these implementations are getting to bare metal Java solutions
I think I have lessons gained in my optimizing of the Java-ish solution that I can bring over to my more Clojuresque solutions. Maybe there are at least two classes to this hunt?
Here’s a version of that last loop w/ transients solution, where I parallelize the collection of the sieved indexes.
(defn pez-ba-loop-transient-parallel-sieve [^long n]
(let [primes (boolean-array (inc n) true)
sqrt-n (int (Math/ceil (Math/sqrt n)))]
(if (< n 2)
'()
(loop [p 3]
(if (< sqrt-n p)
(let [num-slices (if (and (even? n)
(> n 1000))
50
1)
slice-size (quot n num-slices)
futures (mapv (fn [^long slice-num]
(future
(let [start (inc (* slice-num slice-size))
end (dec (+ start slice-size))]
(loop [res (transient [])
i start]
(if (<= i end)
(recur (if (aget primes i)
(conj! res i)
res)
(+ i 2))
(persistent! res))))))
(range num-slices))]
(concat [2]
(drop 1 (into []
(mapcat deref)
futures))))
(do
(when (aget primes p)
(loop [i (* p p)]
(when (<= i n)
(aset primes i false)
(recur (+ i p p)))))
(recur (+ p 2))))))))I now understand why I couldn’t see a gain in the sieve. 😃 Update coming. Haha.
for reference, I ran this on the same airtop workstation as the earlier benchmarks:
(crit/quick-bench
(do
(doall (pez-ba-loop-transient-parallel-sieve 1000000))
nil))
Evaluation count : 156 in 6 samples of 26 calls.
Execution time mean : 4.214238 ms
Execution time std-deviation : 548.921344 µs
Execution time lower quantile : 3.861080 ms ( 2.5%)
Execution time upper quantile : 4.931209 ms (97.5%)
Overhead used : 7.105910 nsthat is quite fast and also very stable across a number of quick-bench runs. The version without parallel:
(crit/quick-bench
(do
(doall (pez-ba-loop-transient-sieve 1000000))
nil))
Evaluation count : 132 in 6 samples of 22 calls.
Execution time mean : 5.424505 ms
Execution time std-deviation : 868.418473 µs
Execution time lower quantile : 4.685846 ms ( 2.5%)
Execution time upper quantile : 6.411823 ms (97.5%)
Overhead used : 7.105910 ns
=> nilThanks! I was super curious. Seems the airtop does not outperform my macbook with as much for these. Btw, try the parallel one without the doall. Since it’s an eager solution, that will add a pass over the collection that is not necessary for the test.
Would love to see some clojure solutions to the sieve here. I think it would be quite instructive. I’ll start with one:
(defn sieve [end]
(loop [ps [] [x & xs] (range 2 end)]
(if (not x)
ps
(recur (conj ps x) (doall (remove #(= 0 (rem % x)) xs))))))That’s quite awesome! I happen to have my first solution to this saved. Totally slow and verbose:
(defn not-divisible-by [n d]
(when-not (integer? (/ n d))
n))
(defn sieve [n]
(loop [found-primes [2]
candidates (range 3 (inc n))]
(let [highest-found-prime (last found-primes)
remaining (->> candidates
(map #(not-divisible-by % highest-found-prime))
(remove nil?))]
(if (= remaining candidates)
(concat found-primes candidates)
(recur (conj found-primes (first remaining)) (rest remaining))))))Welp ... you both made it a lot farther than I did 😛
Didn't finish it this time around, but I'll be continuing the challenge next afternoon EST.
I’ll wait with posting some of my other solutions then. 😃
I spent A LOT of time with it. Just say’n. Turned out it had some performance lessons for me to take. Haha.
Just followed!
This turned out pretty slow, but I wanted to use reduce. Thinking is create set of all the numbers. Then reduce that over the numbers 1..(sqrt n). Then to remove the values that are multiples of n is just set/difference with range with step of n.
(defn sieve-primes [upper]
(let [xs (->> (range 1 (inc upper))
(set))]
(sort (reduce #(if (or (= 1 %2) (not (%1 %2)))
%1
(let [multiples (range (* 2 %2) (inc upper) %2)]
(set/difference %1 multiples))) xs (range 1 (Math/sqrt (inc upper)))))))(time (sieve-primes 1000000))
"Elapsed time: 1765.2869 msecs"