<< Back to previous view

[CLJ-1804] take transducer optimization Created: 25/Aug/15  Updated: 26/Aug/15

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.8
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Karsten Schmidt Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance, transducers

Attachments: Text File clj-1804-1.patch     Text File clj-1804-2.patch    
Patch: Code
Approval: Triaged

 Description   

A basic refactoring to remove the let form and only requires a single counter check for each iteration, yields an 25% performance increase. With the patch, 2 checks are only required for the last iteration (in case counter arg was <= 0)...

;; master
(quick-bench (into [] (take 1000) (range 2000)))
WARNING: Final GC required 34.82584189073624 % of runtime
Evaluation count : 13050 in 6 samples of 2175 calls.
             Execution time mean : 46.921254 µs
    Execution time std-deviation : 1.904733 µs
   Execution time lower quantile : 45.124921 µs ( 2.5%)
   Execution time upper quantile : 49.427201 µs (97.5%)
                   Overhead used : 2.367243 ns

;; w/ patch
(quick-bench (into [] (take 1000) (range 2000)))
WARNING: Final GC required 34.74448252054369 % of runtime
Evaluation count : 18102 in 6 samples of 3017 calls.
             Execution time mean : 34.301193 µs
    Execution time std-deviation : 1.714105 µs
   Execution time lower quantile : 32.341349 µs ( 2.5%)
   Execution time upper quantile : 37.046851 µs (97.5%)
                   Overhead used : 2.367243 ns


 Comments   
Comment by Karsten Schmidt [ 25/Aug/15 10:35 AM ]

Proposed patch, passes all existing tests

Comment by Alex Miller [ 25/Aug/15 11:28 AM ]

From a superficial skim, I see checks for pos? and then neg? which both exclude 0 and that gives me doubts about that branch. That may actually be ok but I will have to read it more closely.

Comment by Karsten Schmidt [ 25/Aug/15 11:58 AM ]

Hi Alex, try running the tests... AFAICT it's all still working as advertised: For (take 0) or (take -1) then the pos? check fails, but we must ensure to not call rf for that iteration. For all other (take n) cases only the pos? check is executed apart from the last iteration (which causes a single superfluous neg? call) The current path/impl always does 2 checks for all iterations and hence is (much) slower.

Comment by Alex Miller [ 25/Aug/15 7:22 PM ]

The only time that neg? case will be hit is if take is passed n <= 0, so I think this is correct. However, you might consider some different way to handle that particular case - for example, it could be pulled out of the transducer function entirely and be created as a separate transducer function entirely. I'm not sure that's worth doing, but it's an idea.

Comment by Karsten Schmidt [ 26/Aug/15 6:01 AM ]

Good idea, Alex! This 2nd patch removes the neg? check and adds a quick bail transducer for cases where n <= 0. It also made it slightly faster still:

(quick-bench (into [] (take 1000) (range 2000)))
Evaluation count : 20370 in 6 samples of 3395 calls.
             Execution time mean : 30.302673 µs

(now ~35% faster than original)





[CLJ-1803] Enable destructuring of sequency maps Created: 22/Aug/15  Updated: 26/Aug/15

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Reid McKenzie Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: destructuring

Attachments: Text File 0001-Enable-destructuring-of-seq-map-types.patch    
Patch: Code
Approval: Triaged

 Description   

At present, Clojure's destructuring implementation will create a hash-map from any encountered value satisfying clojure.core/seq? This has the I argue undesirable side effect of making it impossible to employ destructuring on a custom Associative type which is also a Seq. This came up when trying to destructure instances of a tagged value class which for the purpose of pattern matching behave as [k v] seqs, but since the v is known to be a map, are also associative on the map part so as to avoid the syntactic overhead of updates preserving the tag.

;; A sketch of such a type
(deftype ATaggedVal [t v]
  clojure.lang.Indexed
  (nth [self i]    (nth self i nil))
  (nth [self i o] (case i (0) t (1) v o))

  clojure.lang.Sequential
  clojure.lang.ISeq
  (next  [this]     (seq this))
  (first [this]     t)
  (more  [this]     (.more (seq this)))
  (count [this]     2)
  (equiv [this obj] (= (seq this) obj))
  (seq   [self]     (cons t (cons v nil)))

  clojure.lang.Associative
  (entryAt [self key] (.entryAt v key))
  (assoc [_ sk sv]    (ATaggedVal. t (.assoc v sk sv)))

  clojure.lang.ILookup
  (valAt [self k]   (.valAt v k))
  (valAt [self k o] (.valAt v k o))

  clojure.lang.IPersistentMap
  (assocEx [_ sk sv] (ATaggedVal. t (.assocEx v sk sv)))
  (without [_ sk]    (ATaggedVal. t (.without v sk))))

So using such a thing,

(let [{:keys [x]} (ATaggedVal. :foo {:x 3 :y 4})] x)
;; expect 3
=> nil

Since for any type T such that clojure.core/get will behave, T should satisfy clojure.core/map? it should be correct simply to change the behavior of destructure to only build a hash-map if map? isn't already satisfied.

The attached patch makes this change.



 Comments   
Comment by Alex Miller [ 22/Aug/15 1:21 PM ]

Probably worth watching CLJ-1778 too which might cause this not to apply anymore.

Could you add an example of what doesn't work to the description?

Comment by Ragnar Dahlen [ 24/Aug/15 1:20 AM ]

The current patch for CLJ-1778 does not address this issue.

The idea seems sound to me, if we're map destructuring a value that's
already a map (as determined by map?), we don't need to create a
new one by calling seq and HashMap/create, unless there's a
really good reason it should be exactly that map implementation (I
don't see one).

I don't think the current patch is OK though as it makes an
(unneccessary) breaking change to the behaviour of map destructuring.
Previously, destructuring a non-seqable value returned nil, but with
patch, seq is always called on value and for non-seqble types this
will instead throw an exception. It should be trivial to change the
patch to retain the original behaviour.

1.8.0-master:

user=> (let [{:keys [x]} (java.util.Date.)] x)
nil

with 0001-Enable-destructuring-of-seq-map-types.patch:

user=> (let [{:keys [x]} (java.util.Date.)] x)
IllegalArgumentException Don't know how to create ISeq from: java.util.Date  clojure.lang.RT.seqFrom (RT.java:528)
Comment by Reid McKenzie [ 26/Aug/15 1:15 PM ]

I contend that the behavior broken is, at best, undefined behavior consequent from the implementation and that the failure to cast exception is at least clearer than the silent nil behavior of the original implementation.

I would personally prefer to extend the destructuring checks logically to (cond map? x seq? (hash-map (seq x)) :else (throw "Failed to destructure non-map type") but I think that change is sufficiently large that it would meaningfully decrease the chances of this patch being accepted.





Generated at Fri Aug 28 12:10:37 CDT 2015 using JIRA 4.4#649-r158309.