Saturday, June 29, 2013

Clojure vectors vs. PersistentQueue

Clojure has several pre-built data structures that can be used to implement our ideas. Here you have a comparison of the well-known vector and the poorly-documented clojure.lang.PersistentQueue. Edit: I changed the code in quotes to a Github Gist since I like it much better the way it looks. Sorry for the horrible contrast of the gists and the blogger template, I believe nothing will save me from modifiying the colors.

There was a fatal flaw in the implementation. It is now corrected. Thanks to the commentators.

6 comments:

  1. Hello,
    I am not sure both loops are comparable and fair to PersistentQueue. Please let me explain.

    First you can try to add some debugging. For example add (prn e) into inner loop. Did it print the same amount of information in the same format. Did it print 1000 lines or 1 line with 1000 numbers? Why is there a difference?

    Let's dive into first example, time-queue.clj. I guess `q' is a synonym for clojure.lang.PersistentQueue/EMPTY. A little bit better way to construct queue would be (into q (range 1000)).

    In second example, check the documentation of vector function. It takes N parameters and construct a vector of N items. This second line of code creates a vector of size 1. The vector has only 1 item, it is list of 1000 numbers. Try to replace it with (into [] (range 1000)).

    Did elapsed time changed?

    Best regards,
    Dan

    ReplyDelete
  2. You are comparing apples and oranges. 'first' converts collection to seq, 'peek' does not. 'vector' uses transients, 'apply conj' does not. 'pop' does not hold onto original collection, 'subvec' does.

    ReplyDelete
  3. Thank you both for the heads up, I made a very quick draft and posted it carelessly. Obviously vec is what I wanted, thank you Daniel for the wartning. Now it can be compared.

    ReplyDelete
  4. I'd be wary about using time - have you considered using criterium? Microbenchmarks

    ReplyDelete
  5. Hi pete23, thanks for the suggestion, I was aware of criterium but this test was a quick one. I tried to use criterium but it fails every time, semms to leave the JVM on some sort of loop. Have you heard of this problem? I installed it with lein, from the instructions on Criterium's Github.

    ReplyDelete
  6. PArticularly, this is what I get:
    => (benchmark (java.lang.Thread/sleep 1000) {:verbose false})
    WARNING: Final GC required 4.70377337288366 % of runtime

    ReplyDelete