Thought I'd share with the group. Clojure's sets are fast!

http://www.holygoat.co.uk/blog/entry/2009-09-13-1

Nice writeup!

...and I hate to be picky, but you can probably compare
strings sizes using a faster mechanism than the examples you
gave.

While 'count' can give the size of a string, it first checks
it's type against a couple other possibilities before
calling the string's .length method.

        (defn t [] (dotimes [i 2e7] (= 10 (count "123"))))
        (time (t)) ; run this a few times to let HotSpot work its magic
        --> "Elapsed time: 1000.960992 msecs"

If we know it's a string, we can call the .length method
directly.  If you also type-hint the string, this can make
the code rather uglier, and since this is hardly ever the
bottleneck in any application, it may not be worth it.  But
when you're benchmarking tiny opertions repeated a huge
number of times, this sort of detail starts to matter:

        (defn t [] (dotimes [i 2e7] (= 10 (.length "123"))))
        (time (t))
        --> "Elapsed time: 100.096957 msecs"

There's no need to type hint the string there because it's
a literal and the Clojure compiler already knows its type.

It's time to see if == will help us, since we are after all
dealing with numbers here:

        (defn t [] (dotimes [i 2e7] (== 10 (.length "123"))))
        (time (t))
        "Elapsed time: 96.791805 msecs"

So that's a bit better, but it's also worth looking at
where our numbers may be getting boxed or unboxed.

        (use '[clojure.contrib.repl-utils :only (expression-info)])
        (expression-info '10)
        --> {:class java.lang.Integer, :primitive? false}

        (expression-info '(.length "123"))
        --> {:class int, :primitive? true}

So now we're comparing a boxed Integer 10 with an unboxed
int returned by 'length'.  We can do better:

        (defn t [] (dotimes [i 2e7] (== (int 10) (.length "123"))))
        (time (t)) ; Watch HotSpot remove orders of magnitude, until:
        --> "Elapsed time: 0.044282 msecs"

That's really really fast.  That elapsed time is too small:
we'd have to increase the test size to get any useful
conclusion besides "really fast".  In fact, I almost wonder
if HotSpot is somehow memoizing the expression all by
itself.

Anyway, Clojure's sets by themselves appear to be fast
enough for you, or I assume you wouldn't have described them
as "crazy fast".  However, *if* you discover later that
they're are not fast enough you may be able to do length
tests faster than you were thinking.  This may yet be
a route to explore for improved overall speed.

--Chouser

Thanks!

Yeah, I figured I must have been doing something wrong, but I thought  
I'd leave it out there as a bit of ethnographic research :)

That's interesting... this is a case in which I thought HotSpot (or  
even Clojure's compiler) would automatically unbox: by the time it  
emits code for == it knows that it's comparing a primitive int to a  
constant non-primitive Integer (produced by the reader). Put another  
way: I would expect (== 10 10) to do no work at runtime, or at worst  
only primitive math, not boxed math.

Incidentally, this whole thing is a good example of a user expecting a  
sufficiently smart compiler: coming from Common Lisp one would expect  
the count implementation to be specialized for strings and other  
common types (essentially turning into a null check and a call  
to .length), and a similar optimization of ==. After all, the  
compiler(s) knows the input and output types of all the functions, and  
one of the arguments is constant. From that perspective, there's no  
reason why (== 10 (count some-string)) should not produce much the  
same bytecode as (== (int 10) (.length some-string)) -- both forms are  
equivalent, assuming no rebinding of count.

(While I'm very happy with Clojure, I can see the point of view of the  
people who come here and mouth off about Clojure not being as fast as  
Java. They're not strictly correct, but getting fast Clojure code does  
require some familiarity with which things its compiler will take care  
of, and which it leaves up to you.)

It might be! In this case I suspect that something is inlining the  
result of (.length "123"), which is after all a compile-time constant.  
It might even be optimizing the entire contents of the loop away,  
replacing them with `false`.

You're quite right, and thanks for taking the time to continue the  
exploration!

My main conclusion from all this is that the JVM is really quick, and  
HotSpot is (by and large) a thing of wonder. There's not too much  
point in optimizing away a few hundred microseconds!

I put an update in my original post, and I also (like you) timed
without the side effects I'd inserted (empty-string print statements).
Unlike your code, I'm using non-constant strings, which might explain
the difference.

I note:

The 1,000 string length comparisons take 0.184ms; the negative set
test takes 0.281ms; and the positive takes 0.77ms. The string length
check, then, is slightly faster, but if the length matches you still
have the set test to perform. Probably not worth the complexity.