June 2020 - Boost - lists.preview.boost.org

Adding my sorting algorithm, ska_sort, to boost, attempt 2
by Malte Skarupke 24 Nov '21

24 Nov '21

Hi everyone, I started a discussion about this in October, but at the time the maintainer of the sort library was busy, then I was busy, so now it's January... I wrote a generalized version of radix sort a couple years ago and gave a talk about it here: https://www.youtube.com/watch?v=zqs87a_7zxw I would like to get a new version of that sorting algorithm into boost. It's faster than what I showed several years ago. It's also even more general and has a new interface that should be easier to extend. I uploaded the code here: https://github.com/skarupke/sort/tree/master The documentation is also already updated with new benchmark results. Let me know what's required to get this into boost. Would you like this in the form of a pull request? One of the big things that probably needs review is the interface, since radix sorting works differently than comparison based sorting. For most normal uses you just need to provide a sort key, but more complicated cases can get more complicated. I tried very hard to make everything easy, but I'd also be curious if others can come up with better ways of doing the interface. Thanks, Malte -- Malte Skarupke malteskarupke(a)fastmail.fm

8 10

Boost, not LEWG
by Glen Fernandes 01 Jul '20

01 Jul '20

(A new subject, since the thread has evolved past the Text review result). I spend part of my time in the C++ standards committee. I spend part of my time in Boost. I would prefer that my time spent in Boost, and that Boost itself, be focused on its goals of serving the C++ community and Boost users (existing ones, and growing to new ones). If there is benefit of Boost to any other entity, be it the LEWG of the committee, or some organization, that's great. i.e. When Boost is adopted by some organization, or when Boost components go into the standard, that's just a bonus. But Boost itself shouldn't compromise on quality - in its review process or what it ships in a Boost distribution, to serve any of those other interests. Putting a bunch of experimental libraries into a Boost release just because people have proposed them for standardization is not something we should do. If someone wants to, they can should just start their own project full of libraries that have not undergone any kind of formal review, and convince OS distributions to start including that as part of their packages based on its own merits. In case there was any misunderstanding on this point: Zach's goals of standardization are his own, and in Boost we don't have to be concerned with them. Because we're not changing the review process because of them, and he's not asking us to. Glen

16 40

[containers] Addition of a dense map implementation
by Jeremy Junac 29 Jun '20

29 Jun '20

Hi, While working on different projects in which performance is key, I came to realize that the efficiency of the associative containers that are available in the STL can be improved. For instance, it is well know that neither std::unordered_map nor std::map are cache-friendly. It isn't that hard to find implementations that are faster, for instance flat_map, already in Boost.Containers. However, I would be interested in another implementation, a "Dense Map", similar to the one we can find in SparseHash (https://github.com/sparsehash/sparsehash) or in LLVM's ADT (https://llvm.org/doxygen/DenseMap_8h.html) For sure I am not the only one attracted to such implementation, as we can find several ones in the internet, although, it really lacks of "one true generic implementation". SparseHash doesn't seem that maintained anymore and, well, LLVM is LLVM. Hence, instead of having yet another implementation of my own, I would rather have one in Boost, to ensure long-term maintainability. I know that this particular subject was kind of already discussed in this thread from 2016 (https://lists.boost.org/Archives/boost//2016/01/227076.php) and some very good points were made. But in the end, years have passed, and we still don't have an alternative, so in my opinion an implementation in Boost would actually be something to consider. Please let me know what you think about that. I am open to any other ideas, and in case we agree on the addition of a new implementation, I would actually be pleased to contribute. Best regards, Jeremy Junac

2 1

Re: [boost] Boost, not LEWG
by pbristow＠hetp.u-net.com 29 Jun '20

29 Jun '20

> -----Original Message----- > From: Boost <boost-bounces(a)lists.boost.org> On Behalf Of Vinnie Falco via Boost > Sent: 29 June 2020 06:40 > To: boost(a)lists.boost.org List <boost(a)lists.boost.org> > Cc: Vinnie Falco <vinnie.falco(a)gmail.com> > Subject: Re: [boost] [OT] Re: Boost, not LEWG > > On Sun, Jun 28, 2020 at 10:22 PM Schrom, Brian T via Boost <boost(a)lists.boost.org> wrote: > > My suggestion is.... > > Yeah mailing lists are nice for the monotonically decreasing set of older engineers used to the > anachronism but they are not in any way shape or form attractive for bringing in new, young blood. As one no longer in the first flush of youth (and I suspect a target of this barb 😉 ), I'm not sure that this is the most important issue. We seem to have shifted to CVS, SVN and now GIT and GitHub a little ahead of the curve (and I note that GitHub gives you an email interface as well as a web one). I suspect that 'If it ain't broke, don't fix it." applies to the mailing list/forum issue. I think that the key problem with reviews in finding people who are knowledgeable enough to make useful comments. Often users are best-informed we can get. Too many reviews are theoretical analyses, not based on any 'real-life' use that would expose strengths and weaknesses. There has long been a chicken and egg issue, you don't get many users until a library is in Boost, and so you don't get much informed feedback. I still favor some sort of 'Candidate' status, formalizing the current 'Acceptance subject to changes' status, but giving wider visibility on the Boost GitHub site. Boost has spawned several standards, but also provided many libraries that are entirely unsuitable for standardization. I hope this will continue. Paul Bristow PS I have always been impressed by the overwhelmingly politeness of interchanges on Boost and WG21 etc, in contrast to the internet in general. I believe that Boost is also entirely gender and color-blind.

6 6

[text] [review] Text formal review result
by Glen Fernandes 29 Jun '20

29 Jun '20

Many thanks to Zach for submitting his third library, Text, for Boost formal review. And thank you to the Boost community for participating. You can jump to result at the end of this email. The review period ran from June 11 to June 20 and we received a total of four reviews (three within the period). I won't summarise individual points, all reviews are accessible in the Boost list archives. 1. Emil Dotchevski submitted an early review, on June 3. He voted to accept the entire library with no conditions. 2. Rainer Deyke submitted a review on June 12. He voted to accept only the Unicode algorithms. 3. Phil Endecott submitted a review on June 18. He voted to accept only the UTF transcoding algorithms, and accept the Unicode layer providing the license issue is resolved. 4. JeanHeyd Meneide submitted a review after the review period ended, on June 21. He voted to accept the Unicode layer, and require that the text layer (if accepted) use std::string instead. I received no private reviews, but one email expressing concern about the copyright issue and eligibility for review. My thanks to Emil, Rainer, Phil, and JeanHeyd for your reviews. Thanks also to Gavin Lambert, Vinnie Falco, Alexander Grund, Villie Voutilainen, and everyone who participated in the discussion. The following points had the most weight in the review result that follows: 1. No desire for the string layer The bar for a custom string type is high. On a minor note presents incompatibilities with interfaces using std::string. On a major note a string replacement should give users things they currently depend on in std::basic_string. One of these is the ability to control dynamic allocations. Another is working with strings larger than 2GB. Allocators are not only about performance; i.e. the argument that supporting custom allocators would compromise the performance of the implementation is not enough to justify their absence. Users have the need to choose which area of dynamic memory their objects live in. In some cases users have a requirement that all dynamic allocations go through a custom (and stateful) allocator. JeanHeyd mentioned the now-deprecated wstring_convert functions which, despite their shortcomings, were usable. I filed LWG 2226 (http://wg21.link/lwg2226) years ago while at Microsoft because we had to reject its use in such a project where every dynamic allocation had to support stateful allocators, and wstring_convert did not. The end result was the developer reimplementing the functionality with proper support for stateful allocators. Supporting customizing allocation doesn't necessarily have to involve the current allocator model that containers or other standard library allocator-aware facilities support. As long as it provides the user with a similar level of control. 2. No strong acceptance for the text layer I won't repeat the points here. There was no strong desire expressed to have the text layer in Boost. The compromise to have it backed by std::string was still expressed in light of several shortcomings. 3. Portions of the library under a non-BSL license Phil identified three cases where the library did not have appropriate licensing. One was a simple omission, another has been resolved by the relevant code being relicensed under the BSL, but the other is still pending. We have a strict requirement for Boost licensing of code and data in our libraries that ship in the Boost distribution, and we cannot compromise on this. Zach understands this (he's authored two successful Boost libraries) and I'm confident he will address this. 4. A strong desire to have the Unicode layer in Boost Especially the encoding transcoding, the Unicode algorithms part of the library was well received. The reviews - though small in number - have convinced me of the value of accepting this layer of the library, provided the submission in question (all code and data) is licensed entirely under the BSL. A minor issue: 1. For a library of this size (all three layers are of non-trivial implementation size), I hoped for more reviews and participation. Rather than extend the review period by an additional week, the feedback received above lead me to believe that for Boost's and Zach's benefit, the result below and the prescribed course of action would be better: The result of this review is to reject the Text library in its current form, but to ask Zach to submit a subset of the library containing only the Unicode layer for mini-review, incorporating the feedback pertaining to it in this review. Where all of the code and data is licensed only under the BSL. The review wizard has the ability to grant a 5-day mini-review instead of a full 10-day review, and I've petitioned Mateusz to grant that Zach have this opportunity if he chooses for a second review of a library with just the Unicode layer. The text layer (backed by std::string, but ideally designed one that does not inhibit use of custom allocators ) could be reviewed as a separate library, to improve the chances of getting the Unicode algorithms in the hands of Boost users. My thanks once again to Zach for submitting his Text library for a review, and I hope that the second time's the charm. Glen

15 39

Re: [boost] [text] [review] Text formal review result
by Nikita Kniazev 28 Jun '20

28 Jun '20

> Mailing list sucks. I agree with this. I almost never reply to the mail list because I really have no idea how to do it without top-posting (I subscribed to daily digests). Simply, mail lists have only a single advantage -- everyone has an email. No code highlighting, quotes in digest are a bunch of '>' symbols and no threading. > We absolutely should move to a forum on boost.org for all things, > import as much as we can from the mailing list (as far back as > possible) into the forum, and then cease the use of the mailing list > forever. Anyone who emails the list should get an automated reply that > says "Please register for the wonderful forums at boost.org" etc With something like Discourse you can still use the old and good email to reply to posts (like on GitHub) and even to create threads ( https://meta.discourse.org/t/can-i-start-a-new-topic-by-sending-an-email-me… ).

1 0

[release] 1.74.0 deadline for new libraries is almost here!
by Marshall Clow 26 Jun '20

26 Jun '20

Tomorrow the master branch will be closed for new libraries and breaking changes. See the calendar here for more dates: https://www.boost.org/development/ <https://www.boost.org/development/> The next deadline is 1-July, when the master branch will be closed for major changes Thanks, — The Boost Release Team

2 3

Boost.Text review
by Phil Endecott 25 Jun '20

25 Jun '20

This is my review of Zach Laine's proposed Boost.Text. Zach is offering several things here: Unicode, a "better string", a trie, and more. I'm pleased that these components are all individually exposed to users and are independent of each other, rather than some being hidden as implementation details. I've spent a couple of days looking at a few parts of the library. I'll discuss at the Unicode stuff first. Boost gained support for Unicode functionality when Boost.Locale was accepted almost a decade ago, but I was not particularly impressed by that library and have not used it in my own work. Does the current proposal do better? I think it does, and though it's not perfect I think it would be worth accepting but subject to a concern about copyright. See another thread for the copyright discussion. Basically, if I understand correctly, Zach's code includes tables that are derived from Unicode data and the licence for that data requires a copyright attribution. The Boost licence does not require attribution and I support that. So if I've understood the situation correctly - and I am not a lawyer! - this means that sadly Boost must REJECT the affected code. I'll say some more about the other aspects of the Unicode code, just in case the copyright issue turns out to be surmountable. I've tried just a couple of things. Firstly, I tried the UTF-8 to UTF-32 conversion. This seems to work, and the API is reasonable. Performance is not bad, but it could be better (see another thread); that could be fixed later. I think it would be worth having just a UTF library in Boost! Secondly I looked at the line-splitting algorithm, i.e. template<typename CPIter, typename Sentinel, typename Extent, typename CPExtentFunc> unspecified lines(CPIter first, Sentinel last, Extent max_extent, CPExtentFunc cp_extent, bool break_overlong_lines = true); Again this seems to work, and the API is reasonable. Reference documentation is somewhat lacking though; in the description of lines(), the requirements for CPExtentFunc need to be described, and the "unspecified" return type needs to document that it includes members including iter and hard_line_break. I think there are probably similar omissions in much of the reference documentation. I'm unconvinced by the use of the word "sentinel" here. A sentinel is a value with a special meaning, e.g. a terminating null; what you have here is an end-iterator. It's good that you're allowing the begin and end iterators to have different types, but I think you should name that type something like CPEndIter. The implementation of line splitting seems to call its word length callback more often than necessary, i.e. when a word overflows a line, that word is subsequently measured a second time. That should be easily fixable. Moving on to other parts of the proposal, I'm less happy with text::string. The first thing I noticed was the very strange decision to use int, rather than (signed?) size_t, for indexing; yes I do work with chunks of text larger than 2 GB! I would REJECT text::string for this alone. I also dislike the use of operator() to extract substrings; the meaning just isn't obvious: auto x = y(4); Is that the 4th character of y? Or the substring from 4 to the end? No, it's the substring from the start to 3. I'd need to add a comment to explain what it's doing. But actually there's another problem with that line: x is a non-owning view of that substring. I think that methods that return a view (or span, etc.) should have a name that makes that clear, e.g. "subview". (This wouldn't have been a problem before auto.) This came up in the static_string review, where the substr() method was originally proposed to return a view; that was renamed subview() with substr() returning a copied string. I don't mind that the string isn't templated on the char type, but I do miss the allocator support; I've used strings with arena allocators (for performance) and with shared memory allocators. I know allocator support is a lot of work but it is necessary, IMO. text::text seems to be the obvious combination of text::string with unicode functionality, and I've not looked at that. I have had a look at the trie; I have sometimes wondered to what extent a trie can be implemented in C++ that works as much as possible like a standard container so this is interesting. The docs should mention briefly why trie is here, i.e. where it is used, just in anticipation of that obvious question from users. trie::operator[] returns an "optional ref". But it's not like a std::optional; as well as operator* it has conversion operators to access the value. Zach notes that this is "wonky" when the value type is bool, but it also seems to break for me when it's int: boost::trie::trie_map<std::string, std::string> counts; auto x = counts["Hello"]; if (x) std::cout << "present\n"; else std::cout << "absent\n"; // Prints absent, OK. boost::trie::trie_map<std::string, int> int_counts; // Now int. auto y = int_counts["Hello"]; if (y) std::cout << "present\n"; else std::cout << "absent\n"; // ../text/include/boost/text/trie.hpp:78: // boost::trie::optional_ref<T, Const>::operator T&() & // [with T = int; bool Const = false]: Assertion `t_' failed. operator T&() is being called by if(y), rather than operator bool(). There aren't has_value() and value() methods that I can use to work around this. Like a few other things in this proposal, Zach has implemented trie::operator[] how he wishes the standard library worked. As another example, dereferencing a trie_map iterator doesn't return a pair<KEY,VALUE> as a normal associative container would, but rather a struct with members called key and value. At worst, this will hit problems that the standard solutions avoid (as above). At best, it will make the library more difficult to learn for users who are familiar with the standard library (including its problems), and make generic code less likely to work with it. As a test I wrote a simple program to count word frequencies: using counts_t = std::map<std::string,int>; counts_t counts; while (std::cin.good()) { std::string s; std::cin >> s; counts[s]++; } for (auto i: counts) { std::cout << i.first << " = " << i.second << "\n"; } It would be great if I could just change it to: using counts_t = boost::trie_map<std::string,int>; but I can't do that; I need to change things: struct count { int value = 0; }; // Wrap the int. boost::trie::trie_map<std::string, count> counts; while (std::cin.good()) { std::string s; std::cin >> s; // operator[] doesn't insert, so: auto r = counts[s]; if (r) r->value++; else counts.insert(s,count{1}); } for (auto i: counts) { std::cout << i.key << " = " << i.value.value << "\n"; } That works; how about performance? Trie should perform well when the stored strings frequently share common prefixes, so I've tested with a large web server log file; this has timestamps and URLs which share common prefixes. The results: std::map: run time 1.2 seconds, memory 1007 pages trie_map: run time 1.8 seconds, memory 4868 pages So that's rather disappointing. Some general comments: Some people care about whether libraries are header-only or not, and the docs should mention this, and possibly say which functionality can be expected to work header-only. I got quite a few missing field initializer and unused parameter warnings; please fix these if at all possible. (gcc 6.3, -W -Wall). I think you should re-order the docs so that the "Hello World" example is much earlier. Some functions clearly need to embed large Unicode tables; it would be useful if the docs mentioned roughly how much the executable size is increased by. Some source files are executable. Conclusions: I fear that the only part of this that Boost should accept is the UTF transcoding. The implementation is not perfect but we could work on that. The other Unicode stuff would be good to have but the copyright issue is a blocker. Regards, Phil.

10 14

Re: [boost] Boost.Random
by degski 25 Jun '20

25 Jun '20

On Thu, 25 Jun 2020 at 03:24, <pbristow(a)hetp.u-net.com> wrote: > > > > > *From:* degski <degski(a)gmail.com> > *Sent:* 24 June 2020 15:25 > *To:* boost <boost(a)lists.boost.org> > *Cc:* Paul A. Bristow <pbristow(a)hetp.u-net.com> > *Subject:* Re: [boost] Boost.Random > > > > > > On Mon, 22 Jun 2020 at 06:59, Paul A Bristow via Boost < > boost(a)lists.boost.org> wrote: > > Using > > > std::mt19937::result_type(std::chrono::system_clock::now().time_since_epoch().count()); > > as seed looks nice and 'portable', assuming C++11. > > No need to build Boost.Chrono library - the disadvantage that I was trying > to avoid. > > But using random_device looks even simpler, again assuming Standard C++11. > > using std::random_device; > random_device seeder; > static std::mt19937 generator(seeder()); > > > > This can be better, you should seed the generator with a std::seed_seq, > which you would seed with the std::random_device. > > > > If you use sax::aes_random_device non of the above is needed, the seeder > (can) serve as a CPRNG, with a speed comparable (but faster) than > std::mt19937_64 (on Windows). > > > > > Random zealots seem to have reservations about random_device - and pretty > much anything? > > > > As I said before about random zealots! > > > > I am only testing round tripping of iostream, so true randomness is > entirely unimportant. > > And since the tests take many hours, any time for a randomish seed is also > of zero concern > > > > > > ps: > > > > All seem to work at C++11 with latest MSVC, Clang and GCC. > > > > We almost 2021, C++11 is almost complete on all compilers. > > > > But not necessarily standard libraries – GCC and Clang fail > roundtrip/loopback binary > decimal > binary using std::hexfloat ☹ > C++17 has introduced <charconv>, this does what the old stuff does, but much better (faster, better (C-) API). Here your caveat applies, I'm not sure this is in every standard library. STL has done most of the heavy lifting, as IIRC the MSVC implementation will be ported to GCC/Clang, when deemed 'finished'. I have not seen any announcement anywhere, so I guess it's on-going. I think you'll get std::hexfloat when the respective C++17-STL's have <charconv>. > > But Thanks > > Paul > > > > -----Original Message----- > > From: Boost <boost-bounces(a)lists.boost.org> On Behalf Of Christopher > Kormanyos via Boost > > Sent: 20 June 2020 11:41 > > To: Paul A Bristow via Boost <boost(a)lists.boost.org> > > Cc: Christopher Kormanyos <e_float(a)yahoo.com> > > Subject: Re: [boost] Boost.Random > > > > > > > So would following the crowd and using time(0)> be simplest? > > I never liked time(0) for that particular use casebecause in the old > days it had multiple > > millisecondresolution and lacked the seed resolution sometimes. > > I do not know it the code below is best practice,but I usually use some > kind of variation of below.You > > can switch system_clock for high_resolution_clock. > > All this is straight off-the-rack C++11. > > > > > > #include <chrono> > > #include <iostream> > > #include <random> > > > > // Use time point now seed to get a different set of values each time. > > const std::mt19937::result_type seed = > > > std::mt19937::result_type(std::chrono::system_clock::now().time_since_epoch().count()); > > > > // uint32_t > > static std::mt19937 gen(seed); > > > > int main() > > { > > std::cout << gen() << std::endl; > > } > > > > > > > > On Thursday, June 18, 2020, 10:27:27 AM GMT+2, Paul A Bristow via > Boost <boost(a)lists.boost.org> > > wrote: > > > > > > > > > -----Original Message----- > > > From: Boost <boost-bounces(a)lists.boost.org> On Behalf Of John Maddock > > > via Boost > > > Sent: 17 June 2020 18:48 > > > To: Paul A Bristow via Boost <boost(a)lists.boost.org> > > > Cc: John Maddock <jz.maddock(a)googlemail.com> > > > Subject: Re: [boost] Boost.Random > > > > > > > > > On 17/06/2020 15:53, Paul A Bristow via Boost wrote: > > > > I have wanted to use boost::random::random_device; as a seeder for > my generator. > > > > > > > > #include <boost/random/random_device.hpp> // For > > > > boost::random::random_device; seeder > > > > > > > > But using this requires that I link to a library file // LINK : > > > > fatal error LNK1104: cannot open file > 'libboost_random-vc142-mt-gd-x64-1_73.lib' > > > > > > > > So I have instead used C++ std random device successfully > > > > > > > > using std::random_device; > > > > random_device seeder; > > > > // Use seeder to get a different set of values each time. > > > > static boost::random::mt19937 gen(seeder()); // uint32_t > > > > > > > > But is there any way I can stick to the Boost version (I imagine > > > > that it might prove more > > portable? > > > > Or is this a delusion?) > > > > > > What do you mean by portable? random_device is inherently > > > non-portable because it's.... random ;) > > > > By portable I mean 'works on as many platforms and C++ standard versions > as possible'. > > > > > In many ways this is something that the std:: version does best as the > > > system implementer knows > > best > > > how to implement on their OS. Or you could just link to Boost.Random > > > of course which would work nearly everywhere too I'm sure. > > > > I was just puzzled why Boost.Random needed to *link* when > std:random_device doesn't appear to. Is > > it quietly linking to a standard library? > > > > Paul > > > > PS Thanks for the even-more-random suggestions but I really, really > don't care how randomly random it > > is for my application. > > > > So would following the crowd and using time(0) be simplest? > > > > > > > > > > _______________________________________________ > > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost > > > > _______________________________________________ > > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost > > > _______________________________________________ > Unsubscribe & other changes: > http://lists.boost.org/mailman/listinfo.cgi/boost > >

1 0

Boost.Random
by pbristow＠hetp.u-net.com 24 Jun '20

24 Jun '20

I have wanted to use boost::random::random_device; as a seeder for my generator. #include <boost/random/random_device.hpp> // For boost::random::random_device; seeder But using this requires that I link to a library file // LINK : fatal error LNK1104: cannot open file 'libboost_random-vc142-mt-gd-x64-1_73.lib' So I have instead used C++ std random device successfully using std::random_device; random_device seeder; // Use seeder to get a different set of values each time. static boost::random::mt19937 gen(seeder()); // uint32_t But is there any way I can stick to the Boost version (I imagine that it might prove more portable? Or is this a delusion?) Suggestions welcome. Paul

5 8