The reasons why Enlive templates return seqs of strings

unsorted — cgrand, 10 February 2010 @ 12 h 03 min

The main reasons behind Enlive templates returning seqs of strings are:

  • Ring does not expose the output stream (and I think it is a good thing)
  • I don’t want to allocate the whole response as a single string

Hence it seemed to me the simplest thing to do. (Simpler than implementing InputStream or making templates and Ring to communicate through a kind of reduce-based IO.)

Nodes serializations are cached when the source of the template is read:

user=> (deftemplate hello (-> "<h1>This is a static title<h2>This is a dynamic title" java.io.StringReader. html-resource) [name] [:h2] (content name))
#'user/hello
user=> (hello "Replaced dynamic title")
("<html>" "<body>" "<h1>This is a static title</h1>" "<h2>" "Replaced dynamic title" "</h2>" "</body>" "</html>")
user=> (hello "Replaced dynamic title II")
("<html>" "<body>" "<h1>This is a static title</h1>" "<h2>" "Replaced dynamic title II" "</h2>" "</body>" "</html>")
user=> (map identical? *1 *2)
(true true true true false true true true)

Thus no string allocation except for the dynamic parts but the real raison d’être of the static nodes serializations cache is to reduce the time spent traversing the tree and the number of allocated Cons (since the strings are longer).

Even without this cache there’s no String allocation when serializing a tree (but many Cons instances are allocated):

user=> (let [x {:tag :html :content [{:tag :body :content [{:tag :h1 :content ["This is a static title"]} {:tag :h2 :content ["This is a dynamic title"]}]}]}]
         (every? (partial apply identical?) (map vector (emit* x) (emit* x))))
true

Are pipe dreams made of promises?

unsorted — cgrand, 18 November 2009 @ 19 h 32 min

follow-up: pipe dreams aren’t necessarily made of promises

(defn pipe
 "Returns a pair: a seq (the read end) and a function (the write end).
  The function can takes either no arguments to close the pipe 
  or one argument which is appended to the seq. Read is blocking."
 []
  (let [promises (atom (repeatedly promise))
        p (second @promises)]
    [(lazy-seq @p)
     (fn 
       ([] ;close the pipe
         (let [[a] (swap! promises #(vector (second %)))]
           (if a
             (deliver a nil)
             (throw (Exception. "Pipe already closed")))))
       ([x] ;enqueue x
         (let [[a b] (swap! promises next)]
           (if (and a b)
             (do
               (deliver a (cons x (lazy-seq @b)))
               x)
             (throw (Exception. "Pipe already closed"))))))]))

Beware of not printing the seq while the pipe is still open!

(let [[q f] (pipe)]
  (future (doseq [x q] (println x)) (println "that's all folks!"))
  (doseq [x (range 10)]
    (f x))
  (f)) ;close the pipe

Enlive Google group

unsorted — cgrand, 15 October 2009 @ 21 h 36 min

I created a google group dedicated to Enlive — my HTML/XML CSS-based transformation and extraction library.

Clojure and Me has moved

unsorted — cgrand, 26 September 2009 @ 16 h 04 min

I’m sorry if my previous posts reappeared in your RSS reader. I just moved Clojure and me from blogger to cgrand.net.

About the subtitle

unsorted — cgrand, 13 August 2009 @ 10 h 54 min

The subtitle for this blog may be misleading. Actually it reads “When the pupil is ready to learn, a teacher will appear.”
I picked this Zen proverb because in early 2008 I was looking for a language with the following requirements: strong metaprogrammability, strong concurrency support, strong functional bias and bonus points for running on the JVM. I had prepared myself to not find the rare bird when I met Clojure (and it was nearly love at first sight).
So in that perspective I am the pupil and Clojure (the language, Rich Hickey and the whole community) the teacher.

Clojure as fast as Java!

unsorted — cgrand, 6 August 2009 @ 17 h 08 min

I wrote a prototypal implementation of IPersistentSet in Clojure written with new new and, surprisingly, on its first benchmark it’s already on par with Java-based implementations.

(dotimes [i 10]
  (let [n (int (Math/pow 2 (+ 10 i)))
        _ (println "n=" n)
        a (do
            (print "clojure\t")
            (time (doall (let [s (reduce conj empty-set (range 0 n 2))] (map #(get s %) (range n))))))
        b (do
            (print "java\t")
            (time (doall (let [s (reduce conj #{} (range 0 n 2))] (map #(get s %) (range n))))))]
    (println (= a b))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

n= 1024
clojure "Elapsed time: 1.006064 msecs"
java "Elapsed time: 0.736197 msecs"
true
n= 2048
clojure "Elapsed time: 1.813009 msecs"
java "Elapsed time: 1.328102 msecs"
true
n= 4096
clojure "Elapsed time: 3.590191 msecs"
java "Elapsed time: 2.608153 msecs"
true
n= 8192
clojure "Elapsed time: 7.046566 msecs"
java "Elapsed time: 5.807302 msecs"
true
n= 16384
clojure "Elapsed time: 16.015862 msecs"
java "Elapsed time: 10.284897 msecs"
true
n= 32768
clojure "Elapsed time: 29.803928 msecs"
java "Elapsed time: 23.850378 msecs"
true
n= 65536
clojure "Elapsed time: 68.79778 msecs"
java "Elapsed time: 63.947582 msecs"
true
n= 131072
clojure "Elapsed time: 132.082499 msecs"
java "Elapsed time: 113.433411 msecs"
true
n= 262144
clojure "Elapsed time: 292.149631 msecs"
java "Elapsed time: 265.39197 msecs"
true
n= 524288
clojure "Elapsed time: 595.265321 msecs"
java "Elapsed time: 698.711009 msecs"
true

To tell the truth, this benchmark is a bit unfair for Java: no dummy map and slightly different algorithms (half-full bitmap nodes become array-nodes, no leaf-node etc.).
Follow me on Twitter, here

Everybody loves the Sieve of Eratosthenes

unsorted — cgrand, 30 July 2009 @ 11 h 27 min

If I judge by traffic logs for this blog, many newcomers want to compute prime numbers in Clojure.

A recent thread on the mailing list prompted me to test an idea I had for a while: to use a map to implement the Sieve of Eratosthenes.

The first implementation was this one:

(defn primes [max]
  (let [enqueue (fn [sieve n factor]
                  (let [m (+ n factor)]
                    (assoc sieve m
                      (conj (sieve m) factor))))
        next-sieve (fn [sieve candidate]
                     (if-let [factors (sieve candidate)]
                       (reduce #(enqueue %1 candidate %2)
                         (dissoc sieve candidate)
                         factors)
                       (enqueue sieve candidate candidate)))]
    (apply concat (vals (reduce next-sieve {} (range 2 max))))))

where the sieve is a map from the next non-prime numbers to their factors. It’s so naive that even numbers are tested for primality but it doesn’t perform that bad: on my box, it takes 3s to compute all primes below 1,000,000 (it’s roughly as fast as clojure.contrib.lazy-seqs/primes when the seq isn’t yet memoized).

I wasn’t happy with the way I handled the case where a non-prime was already checked off (ie was a key of the map): I was conjing onto the list of prime factors for this number. If instead I tried to check off n+p (where n is the already known non-prime and p the current prime) or n+2p or n+3p… until I found a yet unknown non-prime I wouldn’t need to maintain a list of factors, nor to conj or reduce over it. And I was hoping that less allocations would yield better perfs.

Here is the second iteration:

(defn primes2 [max]
  (let [enqueue (fn [sieve n factor]
                  (let [m (+ n factor)]
                    (if (sieve m)
                      (recur sieve m factor)
                      (assoc sieve m factor))))
        next-sieve (fn [sieve candidate]
                     (if-let [factor (sieve candidate)]
                       (-> sieve
                         (dissoc candidate)
                         (enqueue candidate factor))
                       (enqueue sieve candidate candidate)))]
    (vals (reduce next-sieve {} (range 2 max)))))

and it computes all the primes below 1,000,000 in 1.8s instead of 3s but it still tests even numbers for primality.

primes3 is primes2 modified to only test odd numbers:

(defn primes3 [max]
  (let [enqueue (fn [sieve n factor]
                  (let [m (+ n (+ factor factor))]
                    (if (sieve m)
                      (recur sieve m factor)
                      (assoc sieve m factor))))
        next-sieve (fn [sieve candidate]
                     (if-let [factor (sieve candidate)]
                       (-> sieve
                         (dissoc candidate)
                         (enqueue candidate factor))
                       (enqueue sieve candidate candidate)))]
    (cons 2 (vals (reduce next-sieve {} (range 3 max 2))))))

and it computes the same list of primes in 1.5s.

Out of curiosity, I wrote a lazy version of primes3:

(defn lazy-primes3 []
  (letfn [(enqueue [sieve n step]
            (let [m (+ n step)]
              (if (sieve m)
                (recur sieve m step)
                (assoc sieve m step))))
          (next-sieve [sieve candidate]
            (if-let [step (sieve candidate)]
              (-> sieve
                (dissoc candidate)
                (enqueue candidate step))
              (enqueue sieve candidate (+ candidate candidate))))
          (next-primes [sieve candidate]
            (if (sieve candidate)
              (recur (next-sieve sieve candidate) (+ candidate 2))
              (cons candidate
                (lazy-seq (next-primes (next-sieve sieve candidate)
                            (+ candidate 2))))))]
    (cons 2 (lazy-seq (next-primes {} 3)))))

and, surprisingly (better locality?), it computes the primes below 1,000,000 in 1s.

Counting without numbers

unsorted — cgrand, 4 May 2009 @ 20 h 09 min

I was writing something along these lines:

(loop [state init, n (count some-seq)]
  (if (pos? n)
    (recur value (dec n))
    (ends here)))

when it struck me that seqs are numerals too!

(loop [state init, n some-seq]
  (if (seq n)
    (recur value (rest n))
    (ends here)))

or:

(loop [state init, n (seq some-seq)]
  (if n
    (recur value (next n))
    (ends here)))

Counting occurences (solution to the exercise)

unsorted — cgrand, 28 April 2009 @ 18 h 00 min
What does (merge-with + {:a 12} {:b 4} {:a 3 :b 7}) return?
{:b 11, :a 15} when there are several values for a key, these values are merged (two at a time) using the specified function — here they are summed.
Can you count occurrences of each value in a collection using merge-with?
(apply merge-with + (map (fn [x] {x 1}) coll)) or, using for: (apply merge-with + (for [x coll] {x 1})).

Counting occurences

unsorted — cgrand, 27 April 2009 @ 17 h 44 min

One asked me how to count occurrences of each value in a collection. I answered (reduce #(assoc %1 %2 (inc (%1 %2 0))) {} coll). Since it can take some time to get accustomed to the functional way of thought, here is how one can work such an expression out:

How to count all occurrences of 42?
(count (filter #{42} coll))
How to express count using reduce?
(defn my-count [coll] (reduce (fn [n _] (inc n)) 0 coll))
How to count all occurrences of 42 using reduce?
(reduce (fn [n _] (inc n)) 0 (filter #{42} coll))
Can you get rid of the filter?
(reduce (fn [n x] (if (= 42 x) (inc n) n)) 0 coll)
I’d like the result to be {42 occurences-count}.
(reduce (fn [m x] (if (= 42 x) (assoc m 42 (inc (m 42))) m)) {42 0} coll)
42 is hardcoded in four places, it’s bad!
(reduce (fn [m x] (if (= 42 x) (assoc m x (inc (m x))) m)) {42 0} coll)
Can’t you replace {42 0} with {}?
No (inc (m x)) would fail because (m x) would return nil.
How does one provide a default value when the key is not found ?
(a-map a-key default-value)
Can’t you replace {42 0} with {}?
(reduce (fn [m x] (if (= 42 x) (assoc m x (inc (m x 0))) m)) {} coll)
I changed my mind I’d like you to count occurrences of each value.
Easy! (reduce (fn [m x] (assoc m x (inc (m x 0)))) {} coll) or, terser, (reduce #(assoc %1 %2 (inc (%1 %2 0))) {} coll)

Exercise:

What does (merge-with + {:a 12} {:b 4} {:a 3 :b 7}) return?
Can you count occurrences of each value in a collection using merge-with?
« Previous PageNext Page »
(c) 2012 Clojure and me | powered by WordPress with Barecity