Re: KFileItem (Re: Jenkins build became unstable: kdelibs_frameworks_qt5 #982)
Hi, 2013/8/22 David Faure: > On Thursday 08 August 2013 13:17:18 Frank Reininghaus wrote: >> 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. > > Yeah, conversions would not be great. But I don't see where you think > conversions would happen. The KFileItemList emitted by "itemsAdded" is created > item by item anyway, in addNewItem(). It's not like we can take the list that > is used as storage in KDirLister and emit that, since we only want to emit the > *new* items, not all of them (everything is async and incremental). OK, you're probably right. I had thought that copying the items from one KFileItemList to another KFileItemList is cheaper than iterating through a linked list, but that's probably wrong if the KFileItemList only keeps pointers to the actual items. I'll try to find some time to check that at some point. >> >> 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. > > Seems right. > >> If that is not >> the case, QList only stores T* pointers next to each other in one >> block of memory. > > Yes, which means taking the size of one pointer more, i.e. 8 bytes per item. > Not 32. But the memory allocator needs a considerable amount of memory for internal use, see below. >> I guess the reason for this design decision is that >> this permits QList to share the same core code (which uses memcpy >> to move around items in memory), no matter what T is. > > It's mainly an optimization: as you saw, when items are small enough, > replacing pointers with the item itself is a saving, not only in memory usage, > but also in speed since the data is much closer together (=less memory pages > to load). But if the data is bigger than a pointer, then it doesn't fit in > what was originally sized to contain a pointer. > > For putting large items in contiguous memory, there's QVector. > >> 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
Re: KFileItem (Re: Jenkins build became unstable: kdelibs_frameworks_qt5 #982)
On Thursday 08 August 2013 13:17:18 Frank Reininghaus wrote: > 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. Yeah, conversions would not be great. But I don't see where you think conversions would happen. The KFileItemList emitted by "itemsAdded" is created item by item anyway, in addNewItem(). It's not like we can take the list that is used as storage in KDirLister and emit that, since we only want to emit the *new* items, not all of them (everything is async and incremental). > >> 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. Seems right. > If that is not > the case, QList only stores T* pointers next to each other in one > block of memory. Yes, which means taking the size of one pointer more, i.e. 8 bytes per item. Not 32. > I guess the reason for this design decision is that > this permits QList to share the same core code (which uses memcpy > to move around items in memory), no matter what T is. It's mainly an optimization: as you saw, when items are small enough, replacing pointers with the item itself is a saving, not only in memory usage, but also in speed since the data is much closer together (=less memory pages to load). But if the data is bigger than a pointer, then it doesn't fit in what was originally sized to contain a pointer. For putting large items in contiguous memory, there's QVector. > 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 ;-) It's not that I don't trust you or these tools, but I would like to see an explanation of the "32 bytes" from the code rather than from high-level measurements. I can understand "losing" 8 bytes per item, but not 32. -- David Faure, fa...@kde.org, http://www.davidfaure.fr Working on KDE, in particular KDE Frameworks 5 ___ Kde-frameworks-devel mailing list Kde-frameworks-devel@kde.org https://mail.kde.org/mailman/listinfo/kde-framework
Re: KFileItem (Re: Jenkins build became unstable: kdelibs_frameworks_qt5 #982)
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 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 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 ___ Kde-frameworks-devel mailing list Kde-frameworks-devel@kde.org https://mail.kde.org/mailman/listinfo/kde-frameworks-devel
KFileItem (Re: Jenkins build became unstable: kdelibs_frameworks_qt5 #982)
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. > 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? 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) ? -- David Faure, fa...@kde.org, http://www.davidfaure.fr Working on KDE, in particular KDE Frameworks 5 ___ Kde-frameworks-devel mailing list Kde-frameworks-devel@kde.org https://mail.kde.org/mailman/listinfo/kde-frameworks-devel
