Performance of seq on empty collections
Eric Kobrin
I was working on some code recently found that my biggest performance
bottleneck was calling `seq` to check for emptiness. The calls to
`seq` were causing lots of object allocation and taking noticeable CPU
time. I switched to using `identical?` to explicitly compare against
the empty vector and was rewarded with a drastic reduction in
execution time.
Here are some hasty tests showing just how big the difference can be:
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(identical? [] []))) (time (dotimes [_ iterations] (seq []))))
"Elapsed time: 3.512 msecs"
"Elapsed time: 2512.366 msecs"
nil
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(identical? "" ""))) (time (dotimes [_ iterations] (seq ""))))
"Elapsed time: 3.898 msecs"
"Elapsed time: 5607.865 msecs"
nil
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(identical? () ()))) (time (dotimes [_ iterations] (seq ()))))
"Elapsed time: 3.768 msecs"
"Elapsed time: 2258.095 msecs"
nil
Has any thought been given to providing a faster `empty?` that is not
based on seq?
Thanks,
Eric Kobrin
Ken Wesson
> In the API it is suggested to use `seq` to check if coll is empty.
>
> I was working on some code recently found that my biggest performance
> bottleneck was calling `seq` to check for emptiness. The calls to
> `seq` were causing lots of object allocation and taking noticeable CPU
> time. I switched to using `identical?` to explicitly compare against
> the empty vector and was rewarded with a drastic reduction in
> execution time.
Only there's a wee problem:
user=> (identical? [] (pop [3]))
false
Not all empty vectors are considered identical. = works:
user=> (= [] (pop [3]))
true
= is also ten times SLOWER than seq if the empty vectors are not
identical, though it's as fast as identical? when they are:
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(= [] (pop [3])))) (time (dotimes [_ iterations] (seq []))))
"Elapsed time: 29994.93852 msecs"
"Elapsed time: 2745.21924 msecs"
This is troubling. The seq function should be faster than this, and =
on nonidentical empty colls should be WAY faster than this.
On the other hand, the identical? test taking <4ms for 100,000,000
iterations suggests it was optimized away to nothing by the JIT
compiler. Unless of course both of us have 100GHz CPUs that can
execute a fresh instruction every 10 picoseconds. :)
David Sletten
On Nov 14, 2010, at 2:16 PM, Eric Kobrin wrote:
> In the API it is suggested to use `seq` to check if coll is empty.
Your timing results raise some interesting questions, however, the API doesn't suggest using 'seq' to check if a collection is empty. That's what 'empty?' is for. The documentation note suggests (for style purposes apparently) that you use 'seq' to test that the collection is not empty. So to be precise you are testing two different things below. For instance, (identical? coll []) is true when coll is an empty vector. (seq coll) is true when coll is not empty. The correct equivalent would be to test (empty? coll).
Of course, this doesn't change the results. I get similar timings with empty?:
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(identical? [] []))) (time (dotimes [_ iterations] (empty? []))))
"Elapsed time: 2.294 msecs"
"Elapsed time: 2191.256 msecs"
nil
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(identical? "" ""))) (time (dotimes [_ iterations] (empty? ""))))
"Elapsed time: 2.657 msecs"
"Elapsed time: 4654.622 msecs"
nil
user=> (let [iterations 100000000] (time (dotimes [_ iterations]
(identical? () ()))) (time (dotimes [_ iterations] (empty? ()))))
"Elapsed time: 2.608 msecs"
"Elapsed time: 2144.142 msecs"
nil
This isn't so surprising though, considering that 'identical?' is the simplest possible test you could try--do two references point to the same object in memory? It can't get any more efficient than that.
Have all good days,
David Sletten
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
Ken Wesson
> user=> (let [iterations 100000000] (time (dotimes [_ iterations]
> (= [] (pop [3])))) (time (dotimes [_ iterations] (seq []))))
> "Elapsed time: 29994.93852 msecs"
> "Elapsed time: 2745.21924 msecs"
It occurred to me that the JIT might not be hoisting the constant (pop
[3]) out of the loop so I retested with this:
user=> (let [iterations 100000000 ev (pop [3])] (time (dotimes [_ iterations]
(= [] ev))) (time (dotimes [_ iterations] (seq []))))
"Elapsed time: 16477.68672 msecs"
"Elapsed time: 2105.01128 msecs"
Still nearly 10x slower. The JIT did something (optimized the function
call overhead away, most likely) but it didn't hoist the entire thing,
and most of the time is indeed spent in the = test.
= is damned slow.
Eric Kobrin
vectors. The last one is always [] and no others are empty. Using
`identical?` instead of `seq` to detect that last vector shaved quite
a bit of time in my loop.
This brought to mind the general case of detecting emptiness. The
current practice of using `seq` to check for non-emptiness wastes
resources. This limits the use of nice abstractions like `reduce` in
performance critical environments where a sentinel could be used. Not
everyone will be able to use a sentinel value to solve their
particular problem. What can be done to make `empty` faster?
David Nolen
In the particular bit of code I'm working on, I have a collection of
vectors. The last one is always [] and no others are empty. Using
`identical?` instead of `seq` to detect that last vector shaved quite
a bit of time in my loop.
Ken Wesson
Interestingly, (= (count v) 0) is relatively fast (900 msec); (seq v)
is slower (2s); (empty? v) is even slower (3s); and (= v []) is
slowest (16s).
As for a real sentinel, nothing beats the old (Object.) -- it's
guaranteed not equal to any existing object at time of creation, so no
preexisting piece of data in your input will look like a
freshly-created one, unlike the case with such traditional sentinels
as nil and zero. (The zero sentinel in C strings has caused no end of
trouble whenever the input string could have an ASCII NUL in it, and
we're all sick to death of Java collections that choke on null
elements, keys, or values. ConcurrentHashMap is a notorious culprit
there.)
(let [sentinel (Object.) v (conj some-vector sentinel)]
(loop [...]
(if (= sentinel something) ...
Another nice thing about (Object.) is that the Object .equals method
boils down to the Java == operator, and JIT-optimizes away to same, so
the above is just as fast as, and more readable than, (if (identical?
sentinel something) ...). Just be sure to put the sentinel first so
the object whose method is being called is an unspecialized Object. If
it's the other way around something else's .equals gets called, and if
it's well designed it will start with if (other == this) return true;,
and branch prediction on the JITted code will eventually eliminate the
cost of the rest of the method not just being return false;, but you
never know.
Michael Gardner
> Interestingly, (= (count v) 0) is relatively fast (900 msec); (seq v)
> is slower (2s); (empty? v) is even slower (3s); and (= v []) is
> slowest (16s).
Strange. Here are the timings I get for 1e8 iterations:
(zero? (count v)): ~3600 msecs
(seq v): ~2300 msecs
(empty? v): ~3100 msecs
(= v []): ~460 msecs
(= 0 (count v)) is even slower than (zero? (count v)). I'm running Clojure 1.2 on a MacBook (Core 2 Duo, 2GHz).
Eric Kobrin
differences between alternatives:
(let [iterations 1e8] (time (dotimes [_ iterations] (= 0 (.length
(.substring "x" 1))))) (time (dotimes [_ iterations] (seq (.substring
"x" 1)))))
"Elapsed time: 3125.125 msecs"
"Elapsed time: 8198.331 msecs"
(let [iterations 1e8] (time (dotimes [_ iterations] (= 0 (count
(.substring "x" 1))))) (time (dotimes [_ iterations] (seq (.substring
"x" 1)))))
"Elapsed time: 9586.196 msecs"
"Elapsed time: 8006.184 msecs"
I also tried using String.intern() so that `identical?` could be used,
that took longer than any of the other options.
Note: I run each of these several times and only include the results
once they are consistent between runs. This avoids results tainted by
compilation and jit overhead.
Christophe Grand
This brought to mind the general case of detecting emptiness. The
current practice of using `seq` to check for non-emptiness wastes
resources.
It depends: in many cases you need to call seq anyway in the non-empty branch so seq+if-let is both expressive and efficient.
However from time to time you really need to check for emptiness quickly.
(zero? (count x)) is one way, (.isEmpty ^java.util.Collection x) is another.
This limits the use of nice abstractions like `reduce` in
performance critical environments where a sentinel could be used. Not
everyone will be able to use a sentinel value to solve their
particular problem. What can be done to make `empty` faster?
However if your [] is really a sentinel, what about creating a real sentinel with (Object.) or (gensym) and checking it with identical?
hth,
Christophe
--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.cgrand.net/ (en)
Alan
x) is implemented as (not (seq x)). You certainly won't ever get
improved performance by using empty? - at best you break even, most of
the time you lose. For example:
(if (empty? x)
; empty branch
; not-empty branch
Can be replaced with
(if (seq x)
; not-empty branch
; empty branch
This is usually more readable, since the empty case tends to be less
interesting. Further, you usually have to seq the object anyway if
it's not empty, so the seq call becomes free except in the case where
the collection is in fact empty:
(if-let [x (seq x)]
; do stuff with x
; give up
compared to:
(if (not (seq x)) ; this is what empty? does
; give up
(let [useful-var (seq x)]
; do stuff with useful, seq'd version of x
Of course performance isn't usually the main driver, so if you feel
empty? really is more expressive in your case, go for it. But the OP
seems to care about performance, and suggesting empty? is off the
mark.
David Sletten
Yes, the API *does* suggest using seq to check for emptiness. (empty?
x) is implemented as (not (seq x)). You certainly won't ever get
improved performance by using empty? - at best you break even, most of
the time you lose. For example:
Of course performance isn't usually the main driver, so if you feel
empty? really is more expressive in your case, go for it. But the OP
seems to care about performance, and suggesting empty? is off the
mark.
Ken Wesson
> Yes, the API *does* suggest using seq to check for emptiness. (empty?
> x) is implemented as (not (seq x)). You certainly won't ever get
> improved performance by using empty? - at best you break even, most of
> the time you lose. For example:
>
> (if (empty? x)
> ; empty branch
> ; not-empty branch
> Can be replaced with
> (if (seq x)
> ; not-empty branch
> ; empty branch
>
> This is usually more readable, since the empty case tends to be less
> interesting.
I disagree. I tend to prefer to front-load the empty case, because
it's usually the base case of a (recur)sion. Getting it out of the way
quickly and early establishes both how the result is generated and the
semantics of many of the loop variables.
More generally, I like to test for, handle, and discard the
corner/special cases and quickie cases and then have the meat of the
function last. It gets the distractions out of the way to focus on the
main, common case (in loops, the iteration rather than the
termination).
> Further, you usually have to seq the object anyway if
> it's not empty, so the seq call becomes free except in the case where
> the collection is in fact empty:
> (if-let [x (seq x)]
> ; do stuff with x
> ; give up
>
> compared to:
> (if (not (seq x)) ; this is what empty? does
> ; give up
> (let [useful-var (seq x)]
> ; do stuff with useful, seq'd version of x
Funny. My own use cases tend not to use seq explicitly at all. I'm
likely to have e.g.
(loop [s some-coll o nil]
(if (empty? s)
o
(let [f (first s)]
(blah blah blah s blah blah blah f blah blah blah)
(recur (rest s) (conj o foobar)))))
or some similar control flow structure, where s gets first and rest
used on it, but not (directly) seq. If some-coll is not already a seq,
using these implicitly generates a seq view of it with seq; on every
iteration but the first, s is bound to a seq implementation already.
Meikel Brandmeyer
Am 15.11.2010 um 23:07 schrieb Ken Wesson:
> (loop [s some-coll o nil]
> (if (empty? s)
> o
> (let [f (first s)]
> (blah blah blah s blah blah blah f blah blah blah)
> (recur (rest s) (conj o foobar)))))
>
> or some similar control flow structure, where s gets first and rest
> used on it, but not (directly) seq. If some-coll is not already a seq,
> using these implicitly generates a seq view of it with seq; on every
> iteration but the first, s is bound to a seq implementation already.
Changing the above code to the following (which is similarly readable) should give an immediate speed bump. Rich once stated something around 20%, although I have not verified the numbers and this was quite a while ago...
(loop [s (seq some-coll)
o nil]
(if s
(let [f (first s)]
(bla bla bla f bla bla bla)
(recur (next s) (conj o foobar)))
o))
Sincerely
Meikel
Ken Wesson
> Changing the above code to the following (which is similarly readable) should give an immediate speed bump. Rich once stated something around 20%, although I have not verified the numbers and this was quite a while ago...
>
> (loop [s (seq some-coll)
> o nil]
> (if s
> (let [f (first s)]
> (bla bla bla f bla bla bla)
> (recur (next s) (conj o foobar)))
> o))
Eh. I'd heard first and rest had replaced next. No?
Sean Corfield
> Eh. I'd heard first and rest had replaced next. No?
rest and next do different things:
rest - Returns a possibly empty seq of the items after the first.
Calls seq on its argument.
next - Returns a seq of the items after the first. Calls seq on its
argument. If there are no more items, returns nil.
--
Sean A Corfield -- (904) 302-SEAN
Railo Technologies, Inc. -- http://getrailo.com/
An Architect's View -- http://corfield.org/
"If you're not annoying somebody, you're not really alive."
-- Margaret Atwood
Meikel Brandmeyer
On 16 Nov., 02:31, Ken Wesson <kwess...@gmail.com> wrote:
> Eh. I'd heard first and rest had replaced next. No?
differences pointed out by Sean:
next returns nil if there are no more items in the sequence, which is
nice to use in if and when statements to test for emptiness. However
in order to be able to return nil the sequence has to be realised.
Otherwise you can't know whether to return nil or not. So next is "non-
lazy of order 1" so to say. To allow full laziness lazy-seq was
introduced. It returns an object which doesn't know directly whether
it's empty, but it knows how to find out, when you ask for it. When
you know call empty? on the lazy-seq you realise the sequence and the
seq call hidden in empty will return most likely a Cons, where first
and rest are just field references, or nil of there are no elements in
the sequence. But you throw this away. Then you call first on the lazy-
seq. first itself calls seq and gets again the now cached Cons. Then
you call rest, which calls seq, which returns the cached Cons. A lot
of indirection going on. If you handle non-seqs like vectors or maps,
you have to replace that with multiple creations of very short-lived
objects. This is even more expensive.
So you can see, that by capturing the return value of the seq call you
can save quite a bit of indirection. Plus seq becomes the identity,
which should be fast.
I did some quick'n'dirty benchmarking and the improvement seems to be
12% for me. Not thaaaat much, but quite a bit for such trivial
changes.
user=> (bench (loop [s (take 10000 (range)) i 0]
(if (empty? s)
i
(recur (rest s) (+ i (first s))))))
Evaluation count : 8100
Execution time mean : 7,393586 ms 95,0% CI: (7,391431 ms,
7,394906 ms)
Execution time std-deviation : 3,062580 ms 95,0% CI: (3,043205 ms,
3,086849 ms)
Found 2 outliers in 60 samples (3,3333 %)
low-severe 2 (3,3333 %)
Variance from outliers : 22,2178 % Variance is moderately inflated by
outliers
nil
user=> (bench (loop [s (seq (take 10000 (range))) i 0]
(if s
(recur (next s) (+ i (first s)))
i)))
Evaluation count : 9840
Execution time mean : 6,502692 ms 95,0% CI: (6,499507 ms,
6,505352 ms)
Execution time std-deviation : 3,708928 ms 95,0% CI: (3,687700 ms,
3,731890 ms)
nil
Hope that helps.
Sincerely
Meikel
Laurent PETIT
Meikel Brandmeyer
On 16 Nov., 09:51, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> Agreed with the explanation, but ... 12% of what, exactly ?
But maybe this whole microbenchmarking story is paper waste. As I
said: quick'n'dirty.
Will now drop out of perfomance discussions...
Meikel
Laurent PETIT
Salut Laurent,
6,502692ms / 7,393586ms ~ 0,88 => 12% improvement, no?
On 16 Nov., 09:51, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> Agreed with the explanation, but ... 12% of what, exactly ?
But maybe this whole microbenchmarking story is paper waste. As I
said: quick'n'dirty.
I don't know.
But my thougts were just that if you want to measure the time for a particular way "W" of coding things (and a variant "Wv"), and you test this with other computations "OC",
then
(not=
(/ (time Wv)
(time W))
(/ (+ (time Wv) (time OC))
(+ (time W) (time OC))))
?
Especially if (time OC) is non neglictible ... ?
Will now drop out of perfomance discussions...
Meikel
Meikel Brandmeyer
On 17 Nov., 09:44, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> I don't know.
>
> But my thougts were just that if you want to measure the time for a
> particular way "W" of coding things (and a variant "Wv"), and you test this
> with other computations "OC",
>
> then
> (not=
> (/ (time Wv)
> (time W))
> (/ (+ (time Wv) (time OC))
> (+ (time W) (time OC))))
>
> ?
>
> Especially if (time OC) is non neglictible ... ?
traversal and the access is done in the benchmark. But to be honest:
my gut feeling sound the alarm bells about "do you test what you claim
you test or does HotSpot do its magic and optimises things away?"
user=> (let [s (doall (take 10000 (range)))]
(bench
(loop [s s i 0]
(if (empty? s)
i
(recur (rest s) (first s))))))
Evaluation count : 42060
Execution time mean : 1,423636 ms 95,0% CI: (1,423576 ms,
1,423708 ms)
Execution time std-deviation : 236,456463 us 95,0% CI: (235,124875
us, 238,050869 us)
Found 4 outliers in 60 samples (6,6667 %)
low-severe 4 (6,6667 %)
Variance from outliers : 1,6389 % Variance is slightly inflated by
outliers
nil
user=> (let [s (doall (take 10000 (range)))]
(bench
(loop [s (seq s) i 0]
(if s
(recur (next s) (first s))
i))))
Evaluation count : 77100
Execution time mean : 801,433279 us 95,0% CI: (801,390707
us, 801,464994 us)
Execution time std-deviation : 156,316400 us 95,0% CI: (154,780303
us, 158,550059 us)
Found 2 outliers in 60 samples (3,3333 %)
low-mild 1 (1,6667 %)
Variance from outliers : 1,6389 % Variance is slightly inflated by
outliers
nil
That means:
0.801433279ms / 1.423636ms ~ 0.56 => 44% improvement?
Meikel