[libcxx-dev] Memory usage for chrono time zones

[Marshall Clow via libcxx-dev]

When I posted a bit of chrono code for review (
https://reviews.llvm.org/D56692), Eric kvetched about the use of `string`
in std::chrono::link, and how this would lead to a bunch of allocations.

So I decided to so some measurements.
I used Howard's date library, and loaded up two different time zone
databases; one from Ubuntu 18.04 (supplied by the OS), and the other by
downloading it from IANA.

there are two data types worth noting here.
A timezone, which contains a name.
A link, which contains a name, and the name of a time zone. (It's basically
an alias).
If you load the data from the OS's file system (Linux/Mac OS), you get lots
of zones, but no links. (~600). If you get the data from IANA, and parse it
yourself (thanks Howard), you get ~400 zones and ~200 links.

[ tl;dr: Managing a string pool manually reduced the number of allocations,
but increased the memory usage. ]

I investigated four different approaches.

#0: Strings everywhere.  A string in the zone, two strings in the link.
#1: A string in the zone, a string + string_view in the link (since it
refers to a zone)
#2: A pool of text, and string_views everywhere.
#3: A series of fixed-size pools (4K), and string_views everywhere.

Note that #2 is not very realistic, because it relies on knowing how big to
make the pool.

Other assumptions:
* 64 bit machines
* strings are 24 bytes, string_views are 16
* Allocations are multiples of 16 bytes.


== Using the OS TZ info ===
607 time zones, no links.
583 zones fit into the SSO.
24 zones required 32 byte allocations
1 zone required 48 byte allocation
Total bytes needed to hold the names = 8620 bytes (rounded up to 8624).

Option #0: Strings everywhere (1 in the zone, 2 in the links)
583 names fit in SSO
24 allocations of 32 bytes
1 allocation of 48 bytes.
Total memory use:
607 * 24 + 24 * 32 + 48 = 14568 + 720 + 48 = 15536
25 total allocations.

Option #1: Keep a string in the zone, and a string + string_view in the
links.
583 names fit in SSO
24 allocations of 32 bytes
1 allocation of 48 bytes.
Total memory use:
607 * 24 + 24 * 32 + 48 = 14568 + 720 + 48 = 15536
25 total allocations

Option #2: Manage a separate pool and use string views everywhere
1 allocation of 8624 bytes
Total memory use:
607 * 16 + 8624 = 9712 + 8624 = 18336
1 total allocation

Option #3: Manage a series of 4K pools and use string views everywhere
3 allocations of 4K bytes
Total memory use:
607 * 16 + 12288 = 9712 + 12288 = 22000
3 total allocations

== Using the IANA TZ info ===
387 zones, 206 links
0 zones required 31 byte allocations
24 zones required 48 byte allocations
5733 + 2703 = 8436 total bytes needed to hold all the strings. (rounded up
to 8448)
[ Additional 3054 total bytes for link targets ]
1 link name required 48 byte allocations
11 link targets required 48 byte allocations

Option #0: Strings everywhere (1 in the zone, 2 in the links)
363 zone names fit in SSO
24 allocations of 48 bytes
205 link names fit in SSO.
1 allocation of 48 bytes
195 link targets fit in SSO.
11 allocations of 48 bytes
36 total allocations

Total memory use:
387 * 24 + 24 * 48 + 206 * 48 + 12 * 48 = 9288 + 1152 + 9888 + 576 = 20904


Option #1: Keep a string in the zone, and a string + string_view in the
links.
363 zone names fit in SSO
24 allocations of 48 bytes
205 link names fit in SSO.
1 allocation of 48 bytes
25 total allocations

Total memory use:
387 * 24 + 24 * 48 + 206 * 40 + 48 = 9288 + 1152 + 8240 + 48 = 18728


Option #2: Manage a separate pool and use string views everywhere
1 allocation of 8448 bytes
Total memory use:
387 * 16 + 206 * 32 + 8624 = 6192 + 6592 + 8624 = 21024
1 total allocations


Option #3: Manage a series of 4K pools and use string views everywhere
3 allocations of 4K bytes
Total memory use:
387 * 16 + 206 * 32 + 3 * 4096 = 6192 + 6592 + 12288 = 25072
3 total allocations

-- Marshall
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/libcxx-dev/attachments/20190826/1c3549c9/attachment.html>