KFileItem (Re: Jenkins build became unstable: kdelibs_frameworks_qt5 #982)

[Frank Reininghaus]

Hi David,

2013/8/7 David Faure:
> On Tuesday 06 August 2013 20:53:05 Frank Reininghaus wrote:
>> OK, I see now that it uses pointers to be able to modify the actual
>> KFileItems in KDirListerCache (if it would just keep KFileItems and
>> modify these, I guess that they would just detach from the ones inside
>> the cache, leaving those unchanged).
>
> Yes.
>
>
> I suppose a solution would be to use a QLinkedList in KDirListerCache. This
> would basically cancel the Q_MOVABLE_TYPE for that particular list (since it
> would need to allocate nodes), but every other KFileItemList out there would
> still benefit.

But it would also slow down things when KDirListerCache has to convert
its internal data to KFileItemLists when emitting signals. Hm, I'll
try to find some time to think about it and see if there is a good
solution. I was going to have a close look at KDirListerCache anyway
because I have the impression that the remaining sources of O(N^2)
behavior in Dolphin when adding/removing many items to a directory in
weird ways are in this class.

>> It looks like a solution for this problem is more complicated than I
>> thought, so maybe I'll just revert the commit to make Jenkins happy
>> again. However, I still think that making KFileItem a Q_MOVABLE_TYPE
>> might be a desirable long-term goal because it saves quite a bit of
>> memory (32 bytes per KFileItem on my system).
>
> 32 *bytes* ? Are you sure? I think you meant 32 bits?

Yes, I am sure, see below.

> In fact I'm surprised. sizeof(KFileItem) = sizeof(void*), right? So QList
> should already lay out the kfileitems next to each other in memory, the only
> issue is that insertion makes copies, but I don't see where a memory saving
> happens. I thought QList only wasted memory for types bigger than a pointer
> (in which case it had to allocate nodes) ?

AFAIK, QList only puts items of type T next to each other in memory if
sizeof(T) <= sizeof(void*) *and* T is a Q_MOVABLE_TYPE. If that is not
the case, QList<T> only stores T* pointers next to each other in one
block of memory. I guess the reason for this design decision is that
this permits QList<T> to share the same core code (which uses memcpy
to move around items in memory), no matter what T is.

Also my experimental findings in
https://git.reviewboard.kde.org/r/111789/ support that. According to
massif/massif-visualizer, a simple program that creates a
KFileItemList with 1 million Q_MOVABLE null KFileItems needs about 8
MB (is to be expected because that's what you need for 1 million
pointers on my 64-bit system). However, without Q_MOVABLE_TYPE, i.e.,
with the current master or frameworks branch, it needs 16 MB because
the list only stores KFileItem* pointers in the 8 MB block, and the
memory for the items themselves is allocated with 1 million calls of
"new KFileItem" -> 8 MB more.

However, this is only the net memory usage. In reality, the memory
allocator also needs some memory for its own bookkeeping, and it thus
adds a bit of overhead to any memory allocation with new or malloc.
With KSysGuard, I found that the difference in memory consumption for
my test program with/without Q_MOVABLE_TYPE is a bit more than 30.5
MiB, and if you take into account that 1 MiB = 1024*1024 bytes, and my
test used 1 million = 10^6 KFileItems, this looks pretty much like
every "new KFileItem" occupies 32 bytes. And this is a bit too much
for my taste ;-)

Best regards,
Frank