[libcxx-dev] Memory usage for chrono time zones

[Zoe Carver via libcxx-dev]

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

On Mon, Aug 26, 2019 at 1:40 PM Marshall Clow via libcxx-dev <
libcxx-dev at lists.llvm.org> wrote:

> 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
> _______________________________________________
> libcxx-dev mailing list
> libcxx-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/libcxx-dev/attachments/20190826/721dda89/attachment.html>