From kde-core-devel  Thu Mar 07 10:13:16 2002
From: Michael Brade <brade () kde ! org>
Date: Thu, 07 Mar 2002 10:13:16 +0000
To: kde-core-devel
Subject: Re: [patch] Zone allocator and kcompletion using it
X-MARC-Message: https://marc.info/?l=kde-core-devel&m=101549614131514

Hi,

On Thursday 07 March 2002 08:58, Michael Matz wrote:
> while looking for the cause of so many malloc() that we now even have a
> whole malloc() replacement, one thing (among others) we found was
> KCompletion.  The attached patch reworks it to not use QValueList<>
> anymore for the children per node, which quarters the amount of malloc(=
).
> I.e.  QValueList<> is not the optimal thing for holding many small thin=
gs.
Ah, now that's the reason for kio/kdirlister/konqueror being slow! ;)=20
Seriously, the jobs emit a QValueList inside a QValueList (one QValueList=
 per=20
file) which is thrown away immediately after finishing the signal's execu=
tion=20
so changing this to something better could improve speed greatly.=20

Yes, damn, we're short before a release but still I think a speed improvm=
ent=20
would be important. It's even more "now-or-never" as this would be BIC.

> The second thing which this patch does is to rework KZoneAllocator to m=
ake
> it more usefull.  It now can be used as a real obstack (i.e. clearing a=
ll
> objects allocated since a certain one) or as a general purpose allocato=
r
> with a normal deallocate (or as a mixture of both).  Because it does no
> compaction it's still much faster than malloc()/free()  (some simple te=
sts
> just allocating heaps of small objects and deallocating them again show
> that it's 5 times faster than malloc()/free()).  It's still targeted at
> allocating many small objects.  Also to not hold memory longer than
> necessary nearby objects (as defined by allocation time) should be
> deallocated also nearly together.  I.e.  something like allocating 100
> things, and then only freeing every second one will not free any memory=
=2E
> It also potentially uses less memory, because we have no per-object
> overhead item as in malloc, which for small objects (say 4 bytes) might
> double the amount actually needed.
>
> And the final thing is to make use of that KZoneAllocator in KCompletio=
n
> by defining operators new and delete for KCompTreeNode which gets rid o=
f
> the last malloc() in the code.
>
> A changed kcompletiontest which just add a big number of strings in
> different ways, and clears the completion object in between showed more
> than a double speedup (from 4950 to 2100 msec).  I'm using various
> versions of this patch since last sunday (or saturday?).
>
> Binary compatibility is not really an issue here, because KZoneAllocato=
r
> wasn't used anywhere in kdecvs.  I think it could be used very well in
> khtml and similar things dealing with a large number of rather small
> objects.  If used correctly it can also greatly simplify code because
> there's no need to remember pointer just for freeing them (this only wo=
rks
> for objects without destructors of course), but if not it makes it fast=
er
> because of no needed free() calls.  Kind of like a poor mans garbage
> collection ;-)
This all sounds really really like it would fit for the kio case. However=
, I'm=20
quite sure we won't change it :-( but I'd like to ask anyways, so... Step=
han?=20
Waldo?

(hmm, I have the strange feeling this post expected a different kind of=20
answer... well, that's life)

--=20
Michael Brade;                 KDE Developer, Student of Computer Science
  |-mail: echo brade !#|tr -d "c oh"|s\e\d 's/e/\@/2;s/$/.org/;s/bra/k/2'
  =B0--web: http://www.kde.org/people/michaelb.html

KDE 3.0: Konquering the Desktops