Review Request 118452: Reduce the memory usage of UDSEntry by using QVector, rather than QHash, for the internal data storage

Thu Dec 11 22:08:33 UTC 2014

> On Dez. 10, 2014, 11:03 nachm., Milian Wolff wrote:
> > src/core/udsentry.cpp, line 155
> > <https://git.reviewboard.kde.org/r/118452/diff/2/?file=332446#file332446line155>
> >
> >     is this called often? if so, prefer to use a QList for the udsIndexes, to prevent the costly conversion here.
> >     
> >     QList and QVector of uint are "nearly" the same. QVector just has a much nicer API, and stuff like resize, which QList is lacking. For this use-case, I think it should be OK though.
> >     
> >     Maybe add a TODO kf6 to change this to QVector?

If QList and QVector of uint are nearly the same depends on the definition of "nearly", I guess ;-)

AFAIK, since QList treats all data types as pointers internally, it will add padding to the 4-byte uints on a 64 bit system, which will waste some memory, and probably also affect the performance since more data needs to be loaded into the CPU caches.

I think the listFields() function is not used much. KIO itself uses it only in unit tests, and most other libraries and applications probably don't use UDSEntry directly, but only indirectly via KDirLister and KFileItem.

Therefore, I'm not sure if changing the return type in KF6 is desirable. It would improve the performance in some cases, but these cases are probably rather exotic (?), and it seems that the API of both Qt and Frameworks consider QList as the default container for everything (even if this is debatable from a memory usage and performance point of view).

- Frank

-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/118452/#review71763
-----------------------------------------------------------

On Dez. 9, 2014, 10:44 nachm., Frank Reininghaus wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/118452/
> -----------------------------------------------------------
> 
> (Updated Dez. 9, 2014, 10:44 nachm.)
> 
> 
> Review request for KDE Frameworks and David Faure.
> 
> 
> Repository: kio
> 
> 
> Description
> -------
> 
> I am continuing to split up https://git.reviewboard.kde.org/r/113355/ , which attempts to make UDSEntry more efficient memory and CPU-wise, into independent parts. This is the third step after 
> https://git.reviewboard.kde.org/r/113591/ and https://git.reviewboard.kde.org/r/115739/ .
> 
> The present patch modifies the internal data storage of UDSEntry. UDSEntry contains a mapping from unsigned int keys to "Field" values, where Field is a struct that contains a QString and a long long (some keys correspond to numeric values, like size, date, etc, whereas others, like user and group, correspond to a QString).
> 
> Currently, UDSEntry stores all data in a QHash<uint, Field> internally. This ensures that everything can be accessed in O(1) time, but is not very efficient memory-wise because a separate memory allocation is done for each hash node.
> 
> I propose to change this and store both the uint keys and the Field values in a QVector each. This means that accessing a value becomes a O(n) operation, since the entire QVector of keys may need to be scanned in order to find a value, but because the number n of values in a UDSEntry is usually quite small and can currently not exceed a number ~100, this should not matter in practice.
> 
> Some parts of https://git.reviewboard.kde.org/r/113355/ are still missing:
> 
> (a) The QVectors which store the keys (which are usually the same for all items in a directory) are not shared yet. Changing this would reduce the memory usage further, but I decided to keep this change separate in order to keep the current patch small and easy to understand. Moreover, this makes it easier to benchmark other similar approaches (e.g., replace QVector by std::vector, or store keys and values together in a std::vector<std::pair<uint,Field>>).
> 
> (b) No space is reserved in the vectors when key/value pairs are inserted one by one. Implementing this would make UDSEntry faster on the slave side (since repeated re-allocations would not be necessary any more), but this can be done in a later patch. Moreover, it might not be needed any more if UDSEntry is not used directly any more on the slave side, as suggested on the frameworks mailing list by Aaron (good idea BTW!). 
> 
> 
> Diffs
> -----
> 
>   autotests/udsentry_benchmark.cpp b5fa8d6 
>   src/core/udsentry.h 98a7035 
>   src/core/udsentry.cpp b806e0e 
>   src/ioslaves/file/file.cpp 1a2a767 
>   tests/udsentrybenchmark.cpp d9a118c 
> 
> Diff: https://git.reviewboard.kde.org/r/118452/diff/
> 
> 
> Testing
> -------
> 
> Unit tests still pass.
> 
> The memory usage of listjobtest with a directory with 100,000 files is reduced from 71344 K to 35392 K according to KSysGuard. I see similar savings when opening the directory in Dolphin.
> 
> I still haven't set up a Qt5/KF5 build in release mode (shame on me!), so I cannot present any benchmark results.
> 
> 
> File Attachments
> ----------------
> 
> Benchmark results
>   https://git.reviewboard.kde.org/media/uploaded/files/2014/12/09/038e443c-78eb-443b-b33a-b451b28d10ea__UDSEntry-benchmarks.png
> 
> 
> Thanks,
> 
> Frank Reininghaus
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20141211/27dedf0f/attachment.html>