<div dir="ltr">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. <br><div><br></div><div>Zoe</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Aug 26, 2019 at 1:40 PM Marshall Clow via libcxx-dev <<a href="mailto:libcxx-dev@lists.llvm.org">libcxx-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">When I posted a bit of chrono code for review (<a href="https://reviews.llvm.org/D56692" target="_blank">https://reviews.llvm.org/D56692</a>), Eric kvetched about the use of `string` in std::chrono::link, and how this would lead to a bunch of allocations.<div><br></div><div>So I decided to so some measurements.</div><div>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.</div><div><br></div><div>there are two data types worth noting here.</div><div>A timezone, which contains a name.</div><div>A link, which contains a name, and the name of a time zone. (It's basically an alias).</div><div>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.</div><div><br></div><div><div>[ tl;dr: Managing a string pool manually reduced the number of allocations, but increased the memory usage. ]</div><div><br></div></div><div>I investigated four different approaches.</div><div><br></div><div>#0: Strings everywhere. A string in the zone, two strings in the link.</div><div>#1: A string in the zone, a string + string_view in the link (since it refers to a zone)</div><div>#2: A pool of text, and string_views everywhere.</div><div>#3: A series of fixed-size pools (4K), and string_views everywhere.</div><div><br></div><div>Note that #2 is not very realistic, because it relies on knowing how big to make the pool.</div><div><br></div><div>Other assumptions:</div><div>* 64 bit machines<br>* strings are 24 bytes, string_views are 16<br>* Allocations are multiples of 16 bytes.<br></div><div><br></div><div><br></div><div>== Using the OS TZ info ===<br>607 time zones, no links.<br>583 zones fit into the SSO.<br>24 zones required 32 byte allocations<br>1 zone required 48 byte allocation<br>Total bytes needed to hold the names = 8620 bytes (rounded up to 8624).<br><br>Option #0: Strings everywhere (1 in the zone, 2 in the links)<br> 583 names fit in SSO<br> 24 allocations of 32 bytes<br> 1 allocation of 48 bytes.<br>Total memory use:<br> 607 * 24 + 24 * 32 + 48 = 14568 + 720 + 48 = 15536<br>25 total allocations.</div><div><br>Option #1: Keep a string in the zone, and a string + string_view in the links.<br> 583 names fit in SSO<br> 24 allocations of 32 bytes<br> 1 allocation of 48 bytes.<br>Total memory use:<br> 607 * 24 + 24 * 32 + 48 = 14568 + 720 + 48 = 15536<br> 25 total allocations</div><div><br>Option #2: Manage a separate pool and use string views everywhere<br> 1 allocation of 8624 bytes<br>Total memory use:<br> 607 * 16 + 8624 = 9712 + 8624 = 18336<br>1 total allocation</div><div><br>Option #3: Manage a series of 4K pools and use string views everywhere<br> 3 allocations of 4K bytes<br>Total memory use:<br> 607 * 16 + 12288 = 9712 + 12288 = 22000<br></div><div>3 total allocations</div><div><br></div><div>== Using the IANA TZ info ===<br>387 zones, 206 links<br>0 zones required 31 byte allocations<br>24 zones required 48 byte allocations<br>5733 + 2703 = 8436 total bytes needed to hold all the strings. (rounded up to 8448)<br>[ Additional 3054 total bytes for link targets ]<br>1 link name required 48 byte allocations<br>11 link targets required 48 byte allocations<br></div><div><br></div><div>Option #0: Strings everywhere (1 in the zone, 2 in the links)<br> 363 zone names fit in SSO<br> 24 allocations of 48 bytes<br> 205 link names fit in SSO.<br> 1 allocation of 48 bytes<br> 195 link targets fit in SSO.<br> 11 allocations of 48 bytes<br> <div>36 total allocations</div><br class="gmail-m_-3641886326434320286gmail-Apple-interchange-newline">Total memory use:<br> 387 * 24 + 24 * 48 + 206 * 48 + 12 * 48 = 9288 + 1152 + 9888 + 576 = 20904<br> <br> <br>Option #1: Keep a string in the zone, and a string + string_view in the links.<br> 363 zone names fit in SSO<br> 24 allocations of 48 bytes<br> 205 link names fit in SSO.<br> 1 allocation of 48 bytes<br><div>25 total allocations</div><br class="gmail-m_-3641886326434320286gmail-Apple-interchange-newline">Total memory use:<br> 387 * 24 + 24 * 48 + 206 * 40 + 48 = 9288 + 1152 + 8240 + 48 = 18728<br><br><br>Option #2: Manage a separate pool and use string views everywhere<br> 1 allocation of 8448 bytes<br>Total memory use:<br> 387 * 16 + 206 * 32 + 8624 = 6192 + 6592 + 8624 = 21024<br><div>1 total allocations</div><br class="gmail-m_-3641886326434320286gmail-Apple-interchange-newline"><br>Option #3: Manage a series of 4K pools and use string views everywhere<br> 3 allocations of 4K bytes<br>Total memory use:<br> 387 * 16 + 206 * 32 + 3 * 4096 = 6192 + 6592 + 12288 = 25072<br><div>3 total allocations</div><br class="gmail-m_-3641886326434320286gmail-Apple-interchange-newline">-- Marshall</div></div>
_______________________________________________<br>
libcxx-dev mailing list<br>
<a href="mailto:libcxx-dev@lists.llvm.org" target="_blank">libcxx-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/libcxx-dev</a><br>
</blockquote></div>