GC Issue 36: Add Counted marker interface


  • Type: Defect Defect
  • Status: Closed Closed
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:


Reported by richhickey, Jan 07, 2009
Marker interface with no methods. Would indicate O(1) count for
collections. Could be used to optimize vectr creation and some sequence ops

Comment 1 by chouser, Feb 10, 2009
Besides Java built-in classes, RT.count() works on
IPersistentCollection objects, so these are the ones that need to be
examined to see if they should implement Counted.

(defn getClassesInDir [basedir subdir]
  (let [regex (re-pattern (str basedir #"(.*)\.class"))]
    (map #(Class/forName (.replace (second (re-find regex (str %))) "/" "."))
         (.listFiles ( (str basedir subdir))))))

(def clj-classes (getClassesInDir "/home/chouser/build/clojure/classes/" "clojure/lang"))

(defn has-count? [c]
  (try (.getMethod c "count" (into-array Class []))
    (catch NoSuchMethodException e)))

(count (filter has-count? clj-classes))  ==> 62 -- hopefully there are some useful
base classes.

(defn has-own-count? [c]
  (try (.getDeclaredMethod c "count" (into-array Class []))
    (catch NoSuchMethodException e)))

(count (filter has-own-count? clj-classes))  ==> 26 -- better

user=> (dorun (map println (sort (map str (filter has-own-count? clj-classes)))))
class clojure.lang.AMapEntry
class clojure.lang.APersistentSet
class clojure.lang.APersistentVector$RSeq
class clojure.lang.APersistentVector$Seq
class clojure.lang.APersistentVector$SubVector
class clojure.lang.ASeq
class clojure.lang.ArraySeq
class clojure.lang.ArraySeq$ArraySeq_double
class clojure.lang.ArraySeq$ArraySeq_float
class clojure.lang.ArraySeq$ArraySeq_int
class clojure.lang.ArraySeq$ArraySeq_long
class clojure.lang.Cons
class clojure.lang.LazilyPersistentVector
class clojure.lang.PersistentArrayMap
class clojure.lang.PersistentArrayMap$Seq
class clojure.lang.PersistentHashMap
class clojure.lang.PersistentList
class clojure.lang.PersistentList$EmptyList
class clojure.lang.PersistentQueue
class clojure.lang.PersistentQueue$Seq
class clojure.lang.PersistentStructMap
class clojure.lang.PersistentTreeMap
class clojure.lang.PersistentTreeMap$Seq
class clojure.lang.PersistentVector
class clojure.lang.Range
interface clojure.lang.IPersistentCollection

The promise of Counted is non-obvious for some of these.  For example,
APersistentSet and PersistentStructMap both have count() methods that
rely on IPersistentMap, which does not itself promise Counted.
However everything in clojure.lang that currently provides
IPersistentMap also promises Counted, so it seems appropriate for
APersistentSet and PersistentStructMap to promise Counted as well.

Similarly, APersistentVector$Seq uses count() from IPersistentVector
which does not itself promise Counted.  But since PersistentVector and
LazilyPersistentVector are both Counted, APersistentVector$Seq can
promise Counted.

Finally, PersistentQueue and PersistentQueue$Seq use ISeq.count(), but
the only ISeqs they use are PersistentList or seqs on vectors, so both
can also promise Counted.

If any of those conclusions are incorrect, or if the Counted marker
should be moved up to a parent interface in any of those cases, please
let me know.

The first patch attached marks almost all of the 'has-own-count?'
classes listed earlier as Counted.  The four non-Counted classes from
that list are:

(dorun (map println (filter #(and (has-own-count? %)
                                  (not (isa? % clojure.lang.Counted)))

There are total of 36 Counted classes, and 27 non-Counted
IPersistentCollection classes.

10.2 KB Download
Comment 2 by richhickey, Feb 10, 2009
Thanks for doing the legwork on this, fixed in 1268
Status: Fixed


  • Assignee:
Vote (0)
Watch (0)


  • Created: