[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kmail-devel
Subject:    Re: KMMsgDict slowness
From:       Michael =?iso-8859-1?q?H=E4ckel?= <haeckel () kde ! org>
Date:       2002-01-01 9:01:42
[Download RAW message or body]

On Tuesday 01 January 2002 05:01, Ronen Tzur wrote:
> Hi
>
> On Monday 31 December 2001 04:21, Michael Häckel wrote:
> > If you have a better idea how to solve this, then it can of course also
> > be done that way.
>
> I have a different idea, which is an optimization to the existing
> clockwork.
>
>
> When a message moves between folders it is a real KMMessage, and as
> such has the potential for knowing its serial number "by heart", so
> invoking KMMsgBase::getMsgSerNum() on it would not be costly [**].

KMMsgBase::getMsgSerNum is not expensive, because it does a hash table lookup, 
but because it does a KMFolder::find(KMMsgBase*) which scans through the 
whole folder.
But this is no longer a problem when moving messages, since I changed that two 
days ago to no longer use that function.

> Thus the basic cost for moving a message is the dict->remove() called from
> KMMsgList::remove() of the original folder, followed by dict->insert() in
> KMMsgList::insert().
>
> (More precisely, the cost of removing an element from the dictionary list,
> plus the cost for inserting it again.)
>
> [**] - a small fix has to be done for that, to make KMMsgList::remove()
> store the serial number returned by dict->remove(), into the KMMessage
> that it has just removed, using KMMessage::setMsgSerNum().

Now it is stored simply in an int within KMMsgList::remove which does the same 
trick.

> Let's assume for now that this basic cost is not too expensive.
>
>
> Side-effects of removal are the numerous dict->remove() and dict->insert()
> performed by KMMsgList::remove() in the original folder, to update
> indexes in the dictionary.  This also involves a lot of costly

This is the real problem.

> KMMsgBase::getMsgSerNum() that reach all the way to

This is no longer true.

diff -u kdenetwork/kmail/kmmsglist.cpp:1.20 
kdenetwork/kmail/kmmsglist.cpp:1.21
--- kdenetwork/kmail/kmmsglist.cpp:1.20 Fri Dec  7 19:44:06 2001
+++ kdenetwork/kmail/kmmsglist.cpp      Sun Dec 30 19:37:36 2001
@@ -175,7 +175,10 @@
   mHigh--;
   for (i=idx; i<mHigh; i++) {
     if (dict)
-      msn = dict->remove(at(i + 1));
+    {
+      msn = dict->getMsgSerNum(at(i + 1)->parent(), i + 1);
+      dict->remove(msn);
+    }
     KMMsgListInherited::at(i) = KMMsgListInherited::at(i+1);
     if (dict)
       dict->insert(msn, at(i), i);

> KMMsgDict::getMsgSerNum(), spending many cycles.

This operation is not that expensive, since it is just a hash table lookup.

> My idea would be to change that process to use a new dict->update() which
> would be considerably faster than dict->remove() followed by
> dict->insert(). This dict->update can work at O(1) if two things are done:
> 	(a) a new pointer is added to KMFolder which points at the
> 		reverse-dictionary for that specific folder;

I actually wonder, why the reverse dictionary is a QPtrDict at all. The 
QMemArray<ulong> could also be simply a member variable of the folder.

> 	(b) each element of the reverse-dictionary points to the
> 		element of the normal dictionary.   (This can be in addition to,
> 		or instead of, having that element contain the serial number,
> 		which currently it does.)
> And the method would have to be invoked with a specific folder and index.

The serial numbers are already there.

> With (a), the RDictEntry is immediately known to dict->update().  Then,
> with (b), the normal DictEntry is immediately known and can be updated.
> No hash-table lookups.
>
> Since dict->update() would be O(1) it should be less painful to have
> it invoked, even many times.  Much like that " at(i) = at(i+1) " in the
> loop in KMMsgList::remove().

It is already O(1), assuming, that a hash table lookup is O(1), but it is 
painful to call it that often.

If there are n messages in a folder and one message is deleted, this operation 
is O(n). If all n messages are deleted from the folder the operation is 
O(n^2) which is not good. It should be O(n).

Regards,
Michael Häckel
_______________________________________________
kmail Developers mailing list
kmail@mail.kde.org
http://mail.kde.org/mailman/listinfo/kmail
[prev in list] [next in list] [prev in thread] [next in thread]