[Kde-pim] KDE/kdepimlibs/akonadi

[Volker Krause]

On Friday 11 April 2008 12:42:30 Marc Mutz wrote:
> On Friday April 11 2008 09:46, Volker Krause wrote:
> > On Friday 11 April 2008 08:55:45 Marc Mutz wrote:
> > > On Thursday April 10 2008 17:35, Tobias Koenig wrote:
> > > > SVN commit 795521 by tokoe:
> > > >
> > > > Change all QList<QByteArray> to QSet<QByteArray> for itemParts
> > >
> > > This is a bad idea. A set doesn't pay it's weight for small numbers of
> > > items. In the vast majority of cases, it's faster to use a sorted
> > > vector/qlist instread of a set. A set is node-based, while a (q)list is
> > > simply an array. Locality of reference and malloc-free appends ruin
> > > set's day.
> >
> > Right, performance-wise it's probably not the best choice, but it
> > provides exactly the semantics we want here: no duplicates, order doesn't
> > matter. That's why we decided to use it instead of a list. The
> > performance impact should be limited since these sets are not created
> > very frequently (which is the expensive part AFAIU), but mostly passed
> > around and checked to contain a specific value. So, I would rather
> > enforce correctness here and keep the set, especially since this is not
> > an implementation detail but public API.
>
> <snip>
>
> Right, the passing around is not a problem. Neither is the creation, if
> it's done infrequently. It's the checking that counts here. Checking is
> much slower in sets than in sorted vectors. Locality of reference. It might
> be a good idea to not use a naked container here, but wrap it in a class:

Tobias actually meassured it, running contains() 10^5 times on a list and a 
set containing 5 elements each (which are typical numbers for our use case). 
The result was 7-9ms vs 9-11ms. So, the list is indeed faster, but the 
absolute times are so small that it's not worth the effort to optimize 
anything here.

regards
Volker
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 194 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kde-pim/attachments/20080411/051a78c8/attachment.sig>
-------------- next part --------------
_______________________________________________
KDE PIM mailing list kde-pim at kde.org
https://mail.kde.org/mailman/listinfo/kde-pim
KDE PIM home page at http://pim.kde.org/