Memory usage for chrono time zones

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

It looks like the question is really only between #1 and #2. #3 has the highest memory footprint for (seemingly) no benefits, and #0 has the most allocations and second-highest memory footprint. It would probably be good to do some benchmarks (ideally on a variety of systems) to test the time it takes to allocate memory. The question comes down to “is the extra amount of memory used in #2 worth the performance of a single allocation”. My gut instinct is “yes,” but, I am not sure.

Zoe