Fork me on GitHub
#beginners
<
2021-02-24
>
grazfather02:02:36

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))
fwiw don’t tell me what’s wrong with it lol

grazfather02:02:14

So i figured out the bug just by throwing in printlns, but more interested in best practices

alexmiller02:02:50

test smaller pieces

seancorfield02:02:32

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

seancorfield02:02:10

(can anyone remember the talk I'm thinking of with the generic error handler and the REPL exploration of the code?)

grazfather02:02:10

I’ve seen his scientific method talk actually

grazfather02:02:23

it’s more a problem that’s mechanical

grazfather02:02:41

how do I non-annoyingly extract parts to test and extract information

seancorfield02:02:40

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.

seancorfield02:02:58

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

grazfather02:02:10

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

seancorfield02:02:28

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)
  .)
so I could evaluate pieces of this code via the REPL
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))]

seancorfield02:02:17

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.

grazfather02:02:12

yeah, cqq works well in fireplace

grazfather02:02:15

no sweat I will figure it out

seancorfield02:02:30

I would expect spc m e e to eval the form if your cursor is on or just after the )

grazfather02:02:37

I am definitely more accustomed to printf debugging or step by step

grazfather03:02:10

Yeah, you’d think so, right?

seancorfield03:02:15

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

robertfw03:02:03

@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

robertfw03:02:13

Actually I use , e v, I believe spacemacs comes with , already set by default as the major mode leader key

seancorfield03:02:00

(it certainly has a lot of "send and eval" variants though!)

robertfw03:02:28

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

seancorfield03:02:29

Oh joy 🙂 Calva did a similar reshuffle and folks are still "recovering" from that 🙂

pez07:02:20

And the reshuffle was about three of the bindings. 😃 You simply don’t mess with people’s muscle memory.

robertfw03:02:52

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

robertfw03:02:52

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/

grazfather03:02:23

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

grazfather03:02:32

yeah practically brought me here

grazfather03:02:41

and clojure force me into emacs 😅

robertfw03:02:52

yeah I'm finding those two get me 99% of what I need

grazfather03:02:24

Now I just need to figure out all the slurping stuff

robertfw03:02:44

slurp and barf, don't leave home without em

grazfather03:02:15

Yep! I have those well enough that I wish I could use them in my golang work

grazfather03:02:20

thanks for the help, guys, good night

West07:02:38

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?

West22:02:45

Awesomesauce!

Yang Xu09:02:17

How to do some initialize things when the first load in a namespace?

dharrigan09:02:07

Can you elaborate on what you mean by "initialize things" please?

Yang Xu09:02:50

Some myself logic need to do before execute code of namespace.

Yang Xu09:02:02

In other words, I just need a way to execute when first load namespace.

noisesmith17:02:39

any code at the top level of the namespace (usually this is just "outside a defn") will execute when the namespace is loaded

noisesmith17:02:11

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)

noisesmith17:02:47

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

Yang Xu10:02:50

Wow, Thank you for your help and give me some library for that.

dharrigan09:02:44

I don't think there is a "pre-load" eval that would eval functions and do something before the namespace is loaded.

dharrigan09:02:49

Someone else might know better

Adrian Imanuel10:02:32

@xu20151211 do you mean load the dependencies from project.clj? when you load lein repl with dependencies it load all the library

Adrian Imanuel11:02:43

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?

andy.fingerhut14:02:10

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.

andy.fingerhut14:02:09

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.

Adrian Imanuel14:02:10

ohhh okay... i don't really get the Rich Hickey part?

andy.fingerhut14:02:53

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.

Adrian Imanuel14:02:10

does he said, that by using atom, it'll make things/apps much more simpler?

andy.fingerhut14:02:13

i.e. You can create many atoms if you want, but there is often no need to do so.

andy.fingerhut14:02:14

You can write complex intertwined code even with atoms, refs, agents, etc. These mechanisms don't force simpler code. They can enable simpler code.

Adrian Imanuel14:02:56

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

andy.fingerhut14:02:26

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.

Adrian Imanuel14:02:52

yes, and by storing in memory, what memory? is it in the cache?

Adrian Imanuel14:02:19

sorry this is just out of curiosity

andy.fingerhut14:02:25

What cache are you referring to? The CPU's L1/L2/etc. caches?

Adrian Imanuel15:02:02

that i don't know. just curious where the atom stored? and if we stop/restart the repl is it still storing?

andy.fingerhut15:02:44

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.

andy.fingerhut15:02:18

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)

Adrian Imanuel15:02:25

ahh okay, thanks a lot for the explanation

Adrian Imanuel15:02:36

now i know better

andy.fingerhut15:02:14

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.

andy.fingerhut15:02:34

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.

aratare11:02:29

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 (): Failed to transfer file  with status code 401
I've configured deploy tokens and GPG accordingly. Any insight is appreciated. Thanks.

grazfather15:02:59

that’s an authentication issue. either your GPG isn’t set up correctly or they don’t have your public key

aratare16:02:00

So I've created a GPG key pair, signed credentials.clj and then do lein deploy clojars as instructed by clojars itself.

aratare16:02:15

but it seems that clojars keeps refusing my file transfer.

Yang Xu14:02:25

@adrianimanuel No, Isn't relate about dependencies.

Pravin16:02:16

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

vanelsas16:02:52

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

👍 3
grazfather16:02:51

you need to use a date/datetime type to be able to compare dates

👍 3
afry19:02:58

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

clojure-spin 9
mbjarland20:02:45

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))))))
where doall is there to eliminate stack overflow

pez21:02:36

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

afry22:02:49

Welp ... you both made it a lot farther than I did 😛

afry22:02:07

Didn't finish it this time around, but I'll be continuing the challenge next afternoon EST.

pez22:02:41

I’ll wait with posting some of my other solutions then. 😃

pez22:02:32

I spent A LOT of time with it. Just say’n. Turned out it had some performance lessons for me to take. Haha.

West22:02:18

Just followed!

Stuart23:02:20

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

Stuart23:02:59

(time (sieve-primes 1000000))
"Elapsed time: 1765.2869 msecs" 
slow 😞

pez07:02:17

Been there! 😃

pez07:02:36

Also, 1 is not a prime. 😃

em07:02:18

@U013YN3T4DA Your solution seems to be the fastest by far out of all the ones posted so far though!

em07:02:00

just for fun, a (relatively) faster version with transients

(defn sieve-mask [n]
  (let [upper (inc n)
        mask (transient (vec (repeat upper true)))]
    (loop [p 2
           mask mask]
      (if (< n (* p p))
        (persistent! mask)
        (if (get mask p)
          (recur (inc p) (reduce #(assoc! %1 %2 false) mask (range (* 2 p) upper p)))
          (recur (inc p) mask))))))

(defn sieve [n]
  (let [mask (map vector (range (inc n)) (sieve-mask n))]
    (->> (filter second mask)
         (mapv first)
         (drop 2))))

(time (sieve 1000000))
;; => "Elapsed time: 485.8439 msecs"
Probably poorly optimized, would be interested to see how fast we could push this

pez07:02:28

I don’t know how fast it can be pushed, but know it can be pushed quite a bit beyond that nice piece, @UNRDXKBNY

pez07:02:48

You can probably win some millisecs by starting with 3 and adding the 2 at the end.

mbjarland14:02:02

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))))))))
and timing:
(time 
 (count 
  (sieve 1000000)))
"Elapsed time: 26.078883 msecs"
=> 78500
(includes 0 and 1 which could be argued is incorrect)

mbjarland14:02:58

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

Stuart14:02:13

my laptop must be slow. It's 4x slower on my machine 😮

Stuart14:02:06

more than 10x actually when doing count.

(time
  (count
    (sieve 1000000)))
"Elapsed time: 375.747701 msecs"
=> 78500
What spec is your machine?

mbjarland14:02:57

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

Stuart14:02:34

I need to have a talk with HR, I need a new laptop!

mbjarland14:02:24

CPU: Intel Core i7-7700 @ 8x 4.2GHz
OS:  Ubuntu 20.10
JVM: 11.0.10.9.1-amzn

mbjarland14:02:49

not exactly new, but it was fast a few years back and these days not that much happens year to year so still pretty fast

mbjarland14:02:05

interesting, this is the same machine running your sieve-primes above:

(time 
 (count 
  (sieve-primes 1000000)))
"Elapsed time: 1115.377674 msecs"
=> 78499

Stuart14:02:44

yeah, my avg time for that over 5 runs was 1466.8

mbjarland14:02:52

so not that big a difference there

mbjarland14:02:38

anyway, would love to see some more solutions, I learn a lot from reading different peoples solutions to the same problem

mbjarland14:02:59

oh, there seems to be a #code-golf channel...

mbjarland14:02:03

I reposted the above solutions there, hope that was ok @pez @U013YN3T4DA and @UNRDXKBNY

mbjarland14:02:51

@pez by the way, (pos? (rem x)) does divisibility

mbjarland14:02:37

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

Stuart14:02:17

Upgraded my java version, from 8 to 15, now your sieve does:

(time
  (count
    (sieve 1000000)))
"Elapsed time: 39.0181 msecs"
=> 78500
Much better.

pez15:02:44

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

mbjarland15:02:39

and short-circuiting for n < 2 etc : )

mbjarland15:02:37

that is fast...:

(time 
 (count 
  (sieve 1000000)))
"Elapsed time: 13.828079 msecs"
=> 78498

mbjarland15:02:52

I think the count adds something like 1ms or 2...

pez15:02:40

Maybe doall adds less?

mbjarland15:02:20

it's interesting, now it's stuck around 35-40 ms and I can't make it run in ~13 again

mbjarland15:02:19

and then it does this:

(time
 (do (doall (sieve 1000000))
     nil))
"Elapsed time: 10.447096 msecs"
yeah, not sure what the deal is with the fluctuating timings

mbjarland15:02:29

some jvm hotspot optimization thing perhaps

pez15:02:38

I use criterium for keeping sanity when timing these things. 😃

mbjarland15:02:06

yeah, agreed, the only sane way to do this

pez15:02:40

Your machine is fast, btw!

mbjarland15:02:48

(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
this is for your latest @pez, and my bitset version gives:
(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 ns

pez15:02:10

A difference could be that I start with an array with only odd numbers.

mbjarland15:02:23

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

mbjarland15:02:14

yeah I suspect there are quite a few things I could improve performance vise with the bitset version. Perhaps tomorrow : )

😄 3
mbjarland15:02:02

@U013YN3T4DA hmm...java 15. Will have to try that

mbjarland15:02:01

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
=> nil

afry16:02:28

Damn, there is some serious talent in this thread!

pez19:02:15

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)))))))))
A cool thing with that experiment was that it sort of landed me the job I have today. Long story, but it boils down to that I had use for my fiddlings with java bitsets during the job interview and tests. 😃

em00:02:24

@pez

"Elapsed time: 4.2257 msecs"
holy smokes your version is fast, skipping evens in both candidate sequence and filter sequence shaves off ~2ms for me which is pretty good, it's a neat optimization Tried the same exact algorithm with transients to see what a more clojure-ish solution would be but ends up at around "Elapsed time: 62.2843 msecs" on the same spec

pez07:02:35

I only learnt about transients quite recently. Can you share the solution, @UNRDXKBNY?

mbjarland14:02:53

@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

❤️ 3
pez17:02:10

Your bitset solution croaks Eric’s test script, btw, @U4VDXB2TU. I haven’t figured out why, the test never finishes, afaikt.

mbjarland18:02:09

Could be because it returns 0 and 1? I can check once I'm by a repl again : )

em21:02:25

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

em21:02:16

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

pez22:02:24

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.

em22:02:33

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!

mbjarland16:02:43

Ok @pez, @UNRDXKBNY , @U013YN3T4DA 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
and the latest code, replaced a range with a loop and a few other tweaks:
(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))))))))

mbjarland17:02:43

running this on a different machine though so times probably not comparable to before

pez17:02:37

Way to go!

pez17:02:32

Eric’s test still can’t cope with it, though. 😃

pez17:02:00

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 ns

mbjarland18:02:21

that is strange…what java version are you on?

mbjarland18:02:00

me: Clojure 1.10.0 and java 15.0.1-amzn

pez20:02:15

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)
Same Clojure version as you.

pez20:02:24

I get the same results if I try with 15.0.2.7.1-amzn

mbjarland06:03:38

Interesting discrepancy.

mbjarland06:03:46

I run these within an intellij cursive repl. Should not matter though, a java process is a java process

pez07:03:12

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

pez08:03:27

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

mbjarland14:03:16

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 ns

Stuart14:03:55

what is quick-bench from ?

mbjarland14:03:41

@pez nice with the bit flip by setting the high bit! That was bothering me

mbjarland15:03:21

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.

pez16:03:49

I think it could be argued to be part of the algo 😃 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Pseudocode

pez17:03:28

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))))))))
Now, I am thinking that on your machine, @U4VDXB2TU, the gain from reducers might be a bigger win than it is on mine. Can you test it for me? 😃

pez23:03:13

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

pez11:03:58

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))))))))
It shaves 3ms from the reducers attempt. Will try to parallellize this one as well.

pez18:03:14

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
Contrast to the version I had when this thread started and I said I would not open up this box again. 😃
(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 ns

em08:03:44

I 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

pez14:03:04

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?

pez23:03:06

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))))))))
Doesn’t gain me the slightest speed on my machine, though. I don’t quite understand why, because in a more syntetic test I had a 40% speed gain. Maybe on some other machine it makes more difference. In any case, now I sieve through 10M numbers in 70ms on my laptop. Chasing this particular local maxima might not be the way to make real progress.

pez10:03:12

I now understand why I couldn’t see a gain in the sieve. 😃 Update coming. Haha.

mbjarland10:03:07

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 ns

mbjarland10:03:11

that 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
=> nil
and same here, very stable across a number of runs. So on this machine the parallel code seems to make a difference, about 22% faster.

pez11:03:58

Thanks! 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.