Josh Cherry wrote:
> 1. The slowness depends (in part, at least) on the fact that there is a
> cont.end() call for every iteration. If the code is changed to look like
> this:
>
> cont_end = cont.end()
> while it != cont.end():
> it.next()
>
> it is much faster. Of course, calling end() *should* be constant time.
>
In C++, maybe, where the compiler may be able to inline the call
completely. When you bind it to a scripting language, end() is always a
function call. This slowdown is unavoidable.
Even in C++, the recommendation is NOT to call end() repeatedly if you
can avoid it, as inlining is just a hint and the compiler could fail to
do it (for whatever reason).
> Ondrej Marsalek wrote:
>
> n pyvector pylist pydeque pyset
> 1024 1.87 25.19 2.40 19.79
Those numbers don't look that right, but they don't look wrong either to
me.
I should also point out that this:
> cont = pystl.pylist(xrange(n))
will indeed do a dummy check on each element of the range when *FILLING*
the container, not when iterating thru it. Again, this check cannot be
avoided.
Take this out of the timing and you'll see the numbers perform much better.
Here's for example the test fixed (for ruby):
--
%module li_std_speed
%include <std_list.i>
%include <std_vector.i>
%include <std_deque.i>
%include <std_set.i>
%template(RbList) std::list<swig::GC_VALUE>;
%template(RbVector) std::vector<swig::GC_VALUE>;
%template(RbDeque) std::deque<swig::GC_VALUE>;
%template(RbSet) std::set<swig::GC_VALUE>;
--
require 'li_std_speed'
include Li_std_speed
require 'benchmark'
def iterate(c)
i = c.begin
e = c.end
while i != e
i.next
end
end
n = 16384
elems = (0..n).to_a
puts '--- build containers (takes long)'
all = {}
[RbVector, RbList, RbDeque, RbSet].each do |klass|
puts "build #{klass}"
all[klass] = klass.new( elems )
end
puts '--- iterate'
GC.disable # to avoid measuring any GC slowdown
all.each do |klass, c|
Benchmark.benchmark('') do |x|
name = klass.to_s.sub(/.*::/,'') + ' '*5
name = name[0,10]
x.report("#{name} #{n}") { iterate(c) }
end
end
Iteration speed is linear on all containers:
--- build containers (takes long)
build Li_std_speed::RbVector
build Li_std_speed::RbList
build Li_std_speed::RbDeque
build Li_std_speed::RbSet
--- iterate
RbList 16384 0.083333 0.000000 0.083333 ( 0.052038)
RbDeque 16384 0.116667 0.000000 0.116667 ( 0.061717)
RbVector 16384 0.100000 0.000000 0.100000 ( 0.061583)
RbSet 16384 0.100000 0.000000 0.100000 ( 0.063578)
If, however, assignment is taking into account (this is done with the
container's assign if available), each container behaves quite
differently.
require 'li_std_speed'
include Li_std_speed
require 'benchmark'
n = 16384
@elems = (0..n).to_a
def create_and_iterate(klass)
c = klass.new( @elems )
i = c.begin
e = c.end
while i != e
i.next
end
end
GC.disable # to avoid measuring any GC slowdown
[RbVector, RbList, RbDeque, RbSet].each do |klass|
Benchmark.benchmark('') do |x|
name = klass.to_s.sub(/.*::/,'') + ' '*5
name = name[0,10]
x.report("#{name} #{n}") { create_and_iterate(klass) }
end
end
---
RbVector 16384 4.183333 0.033333 4.216667 ( 2.550497)
RbList 16384 17.566667 0.016667 17.583333 ( 10.562868)
RbDeque 16384 3.533333 0.000000 3.533333 ( 2.118050)
RbSet 16384 17.066667 0.016667 17.083333 ( 10.272435)
*NOTE: std::set is slow as expected. std::deque and std::vector are
expected to be relatively fast.
The performance of std::list is weird, as you expect insertions on a
list to be constant time. Problem is, the list copy constructor is
*not* constant, while a std::vector/deque is (usually just a memcpy).
Currently swig is kind of dumb in how copy constructors are handled in
the STL, as the container is actually copied twice when the element
passed in is not another STL container, but the language's native
list/array container.
Summary: no bug.
--
Gonzalo Garramuño
[EMAIL PROTECTED]
AMD4400 - ASUS48N-E
GeForce7300GT
Kubuntu Edgy
_______________________________________________
CMake mailing list
CMake@cmake.org
http://www.cmake.org/mailman/listinfo/cmake
