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

List:       kmail-devel
Subject:    Re: KMMsgDict slowness
From:       Ronen Tzur <rtzur () shani ! net>
Date:       2001-12-31 21:03:01
[Download RAW message or body]

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 [**].

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().


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 
KMMsgBase::getMsgSerNum() that reach all the way to
KMMsgDict::getMsgSerNum(), spending many cycles.

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;
	(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.

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().


Well, that turned out to be quite longer than I anticipated.   :-)
_______________________________________________
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]