diff options
author | Andreas Buhr <andreas.buhr@qt.io> | 2020-11-16 17:58:39 +0100 |
---|---|---|
committer | Andreas Buhr <andreas.buhr@qt.io> | 2020-11-24 18:54:45 +0100 |
commit | 115955069f050d2549d0a341460b1473fd383db7 (patch) | |
tree | 259d7f4f6535748c0671e7661c2c6ec2dedb9b35 /src/corelib/doc/src/containers.qdoc | |
parent | 764fbb1c014c2adf61b53d0f3b3d7affaf4f22de (diff) |
Update container overview documentation - section on growth strategies
The Qt container overview documentation contained outdated information
on container growth strategies. This patch updates the documentation
to reflect the current implementation.
Task-number: QTBUG-86584
Pick-to: 6.0
Change-Id: I8fd014138f9a2e73925dafaa270d4c98ab672d96
Reviewed-by: Lars Knoll <lars.knoll@qt.io>
Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
Diffstat (limited to 'src/corelib/doc/src/containers.qdoc')
-rw-r--r-- | src/corelib/doc/src/containers.qdoc | 44 |
1 files changed, 14 insertions, 30 deletions
diff --git a/src/corelib/doc/src/containers.qdoc b/src/corelib/doc/src/containers.qdoc index 70c22b1407..9cda3f91d8 100644 --- a/src/corelib/doc/src/containers.qdoc +++ b/src/corelib/doc/src/containers.qdoc @@ -543,39 +543,23 @@ We build the string \c out dynamically by appending one character to it at a time. Let's assume that we append 15000 characters to - the QString string. Then the following 18 reallocations (out of a - possible 15000) occur when QString runs out of space: 4, 8, 12, - 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, - 12276, 14324, 16372. At the end, the QString has 16372 Unicode + the QString string. Then the following 11 reallocations (out of a + possible 15000) occur when QString runs out of space: 8, 24, 56, + 120, 248, 504, 1016, 2040, 4088, 8184, 16376. + At the end, the QString has 16376 Unicode characters allocated, 15000 of which are occupied. - The values above may seem a bit strange, but here are the guiding - principles: - \list - \li QString allocates 4 characters at a time until it reaches size 20. - \li From 20 to 4084, it advances by doubling the size each time. - More precisely, it advances to the next power of two, minus - 12. (Some memory allocators perform worst when requested exact - powers of two, because they use a few bytes per block for - book-keeping.) - \li From 4084 on, it advances by blocks of 2048 characters (4096 - bytes). This makes sense because modern operating systems - don't copy the entire data when reallocating a buffer; the - physical memory pages are simply reordered, and only the data - on the first and last pages actually needs to be copied. - \endlist + The values above may seem a bit strange, but there is a guiding + principle. It advances by doubling the size each time. + More precisely, it advances to the next power of two, minus + 16 bytes. 16 bytes corresponds to eight characters, as QString + uses UTF-16 internally. + + QByteArray uses the same algorithm as + QString, but 16 bytes correspond to 16 characters. - QByteArray uses more or less the same algorithm as - QString. - - QList<T> also uses that algorithm for data types that can be - moved around in memory using \c memcpy() (including the basic C++ - types, the pointer types, and Qt's \l{shared classes}) but uses a - different algorithm for data types that can only be moved by - calling the copy constructor and a destructor. Since the cost of - reallocating is higher in that case, QList<T> reduces the - number of reallocations by always doubling the memory when - running out of space. + QList<T> also uses that algorithm, but 16 bytes correspond to + 16/sizeof(T) elements. QHash<Key, T> is a totally different case. QHash's internal hash table grows by powers of two, and each time it grows, the items |