Re: [Libreoffice] [PATCH] Replaced tools/list with std::vector in funcdesc.hxx / funcdesc.cxx

On Fri, 2011-01-28 at 22:14 +0100, Soeren Moeller wrote:
> Yet another patch, removing use of tools/list from ScFunctionList,
> too. In this class there should be a clear performance gain, by using
> a vector instead of a list, as our tests revealed that the random
> access Get() function is called 2-3000 times for each use of a
> spreadsheet function. Note that we use a std::list for constructing
> the object, as the number of elements is unknown while constructing,
> but then convert the list to a vector at the end of the construction,
> to make efficient random access possible.

Yup, a very nice approach indeed.  This is exactly the approach that I
would have taken (i.e. use list when the number of elements is not known
beforehand).  However, I'd like to point you to the little experiment I
did awhile ago

http://kohei.us/2010/03/31/stl-container-performance-on-data-insertion/

where it is shown that the performance of appending data into list and
vector was not exactly what I would have expected.  So, you could've
just used vector to populate the function list in the constructor and
the performance would have been okay (or in fact would have been
better).

It turns out that std::list allocates memory on the heap when inserting
new elements, which may cause its performance to be worse than
non-reserved vector.  As some of the commenters point out, however, that
this may be overcome if you use a custom allocator, but I just wanted to
point out that the performance of non-reserved vector is not as bad as
you may think.

Anyway, it doesn't really matter one way or the other in this case, so
I'm happy with the way you guys did it.

The only change I made after your commit was due to STLport not liking
assigning list's elements into vector via assign() call.  The code is
correct & it should work, but STLPort didn't like that for some reason.
So I had to replace it with constructor assignment & swap trick.

> With this patch (together with our last patch)
> funcdesc.hxx/funcdesc.cxx shouldn't use tools/list anymore, so we have
> removed the includes.

Excellent.  I want all uses of List to go away. :-)

Kohei

-- 
Kohei Yoshida, LibreOffice hacker, Calc
<kyoshida@novell.com>