October 2019 - Boost - lists.preview.boost.org

istream_iterator_limited
by Frederick Gotham 21 Nov '19

21 Nov '19

[MODERATOR: I tried to post this a week ago, but for some reason the word SPAM was prefixed to the subject line and so it didn't show up on the GMane server. I don't think many people actually saw it.] - - - - WHY I NEEDED THIS: I wanted to open a file using "ifstream", and then I wanted to read 32 bytes from the file and feed them directly into boost::algorithm::hex. Unfortunately I couldn't do this because 'hex' takes two iterators [begin,end), and there's no alternative function "hex_n". So I had to read the file into a string first, and then pass the string to 'hex'. - - - - THE IDEA I CAME UP WITH: Open the file using "ifstream", and then use a special iterator that will stop reading from the file after 32 bytes, with syntax like this: ifstream logfile("log.txt"); hex( istream_iterator_limited<char>(logfile,32), istream_iterator_limited<char>(), g_some_global_container.begin() ); - - - - SAMPLE CODE: #include <cstddef> /* size_t */ #include <iterator> /* istream_iterator */ template <typename T> class istream_iterator_limited : public std::istream_iterator<T> { protected: std::size_t const m_limit; std::size_t m_current_count; public: /* Shorter names */ typedef std::istream_iterator<T> Base; typedef istream_iterator_limited<T> This; istream_iterator_limited(typename Base::istream_type &obj_stream, size_t const arg_limit) : Base(obj_stream), m_limit(arg_limit), m_current_count (1) { /* The initialiser list above does all the construction work */ } istream_iterator_limited(void) /* This gives the End-Of-Stream iterator */ : Base() , m_limit(0), m_current_count(1) { /* The initialiser list above does all the construction work */ } This &operator++(void) { if ( m_limit <= m_current_count ) { Base::operator=( Base() ); /* Becomes End-Of- Stream iterator */ } else { ++m_current_count; Base::operator++(); } return *this; } }; #include <algorithm> /* copy */ #include <string> /* string */ #include <sstream> /* istringstream */ #include <iostream> /* cout, endl */ #include <iterator> /* back_inserter */ auto main(void) -> int { std::istringstream iss("123456789"); std::string str; /* Let's use copy to read 5 char's into our string */ std::copy( istream_iterator_limited<char>(iss,5), istream_iterator_limited<char>(), std::back_inserter(str) ); std::cout << str << std::endl; str.clear(); /* Get another 3 */ std::copy( istream_iterator_limited<char>(iss,3), istream_iterator_limited<char>(), std::back_inserter(str) ); std::cout << str << std::endl; }

1 1

[container] static_string ?
by Vinnie Falco 09 Nov '19

09 Nov '19

Beast has static_string which someone has asked to be move, is there any interest in moving this to Boost.Container? See: <https://github.com/boostorg/beast/issues/1691> <https://github.com/boostorg/beast/blob/b7230f12f16fe7a9f7a1ece5be1f607c8552…> -- Regards, Vinnie Follow me on GitHub: https://github.com/vinniefalco

19 50

Interest in a Unicode library for Boost?
by Zach Laine 02 Nov '19

02 Nov '19

About 14 months ago I posted the same thing. There was significant work that needed to be done to Boost.Text (the proposed library), and I was a bit burned out. Now I've managed to make the necessary changes, and I feel the library is ready for review, if there is interest. This library, in part, is something I want to standardize. It started as a better string library for namespace "std2", with minimal Unicode support. Though "std2" will almost certainly never happen now, those string types are still in there, and the library has grown to also include all the Unicode features most users will ever need. Github: https://github.com/tzlaine/text Online docs: https://tzlaine.github.io/text If you care about portable Unicode support, or even addressing the embarrassment of being the only major production language with next to no Unicode support, please have a look and provide feedback. I gave a talk about this at C++Now in May 2018, and now it's a bit out of date, as the library was not then finished. It's three hours, so, y'know, maybe skip it. For completeness' sake: https://www.youtube.com/watch?v=944GjKxwMBo&index=7&list=PL_AKIMJc4roVSbTTf… https://www.youtube.com/watch?v=GJ2xMAqCZL8&list=PL_AKIMJc4roVSbTTfHReQTl1d… Zach

8 10

Change TCP_USER_TIMEOUT
by JH 01 Nov '19

01 Nov '19

Hi, I am using boost asio TCP socket in my device application for network connection in Linux platform. I am troubled currently by long TCP tmeout issues in a device to switch application between WiFi and 4G LTE. If my application TCP was connected via 4G LTE initially, when WiFi is available, the network is switched to WiFi, but the application TCP connection would have 30 minutes timeout before it terminated the 4G LTE and reconnects to WiFi. That 30 minutes is too long. I checked TCP document for TCP_USER_TIMEOUT: TCP_USER_TIMEOUT Decreasing user timeouts allows applications to "fail fast", if so desired. Otherwise, failure may take up to 20 minutes with the current system defaults in a normal WAN environment. My question is, in boost asio socket, is there an API to change TCP_USER_TIMEOUT? Appreciate if showing an example or point me to a document how to do it. Thank you. Kind regards, - jh

2 3

Re: [boost] [Boost-users] Interest in a Unicode library for Boost?
by Zach Laine 30 Oct '19

30 Oct '19

On Wed, Oct 30, 2019 at 4:51 AM Leon Mlakar <leon(a)digiverse.si> wrote: > On 29.10.2019 17:11, Zach Laine wrote: > > > > >> - for the sake of completeness the normalization type used at the text >> level ought to be a policy parameter; although I do understand your >> arguments against it I think it should be there even at the cost of >> different text types being inoperable without conversions >> > > I disagree. Policy parameters are bad for reasoning. If I see a > text::text, as things currently stand, I know that it is stored as a > contiguous array of UTF-8, and that it is normalized FCC. If I add a > template parameter to control the normalization, I change the invariants of > the type. Types with different invariants should have different names. To > do otherwise is a violation of the single responsibility principle. > > Okay, the policy or not the policy was not my point ... it was to allow > for different underlying normalizations. Granted, it may only be important > to (a few) corner cases where input and/or output normalizations are given, > and your assessment that it may not be worth the effort is reasonable ... > unless you are aiming towards adding to the standard. Then the completeness > imho becomes more important. > > Frankly, I'm not proficient enough in the meta-programming to make a > strong case either for policy parameter or for explicit types/templates. I > just happen to prefer the policy based approach. > Understood. FWIW, the algorithms provided by Boost.Text make it possible to use any normalization representation, though at times conversions may be necessary. Some of those conversions are mandated by the Unicode standard itself -- you cannot feed NFC, NFKC, or NFKC to the collation algorithm, for instance (though implementations are possible for NFD and FCC). > > > - at the text level I'm not sure I'm willing to cope with different >> fundamental text types; I just want to use boost::text::text, pretty >> much the same as I use std::string as an alias to much more complex >> class template; heck, even at the string layer I'd probably prefer >> rope/contiguous concept to be a policy parameter to the same type >> template. >> > > That would be like adding a template parameter to std::vector that makes > it act like a std::deque for certain values of that parameter. Changing > the space and time complexity of a type by changing a template parameter is > the wrong answer. > > No, that is not making the std::vector to act as std::deque - the text > would still remain the text and act as a text, with the same interface. > It's more like FIFO implementation using either std::vector or std::dequeu > for its store - since in both cases the FIFO has the same interface and > functionally behaves the same, I really don't want two distinct types. The > type template with the parameter that makes the choice between the > underlying storage seems much more natural to me. > You example highlights my point. For N inputs to your FIFO queue, a deque underlying implementation is worst-case O(N). A vector implementation is worst-case O(N*N). The invariants of the type matter, and they matter a lot. Saying a foo may be like a bar or like a baz only work when bar and baz are so similar that you cannot observe a difference in the behavior of foo. Zach

1 0

[SPAM] istream_iterator_limited
by Frederick Gotham 28 Oct '19

28 Oct '19

- - - - WHY I NEEDED THIS: I wanted to open a file using "ifstream", and then I wanted to read 32 bytes from the file and feed them directly into boost::algorithm::hex. Unfortunately I couldn't do this because 'hex' takes two iterators [begin,end), and there's no alternative function "hex_n". So I had to read the file into a string first, and then pass the string to 'hex'. - - - - THE IDEA I CAME UP WITH: Open the file using "ifstream", and then use a special iterator that will stop reading from the file after 32 bytes, with syntax like this: ifstream logfile("log.txt"); hex( istream_iterator_limited<char>(logfile,32), istream_iterator_limited<char>(), g_some_global_container.begin() ); - - - - SAMPLE CODE: #include <cstddef> /* size_t */ #include <iterator> /* istream_iterator */ template <typename T> class istream_iterator_limited : public std::istream_iterator<T> { protected: std::size_t const m_limit; std::size_t m_current_count; public: /* Shorter names */ typedef std::istream_iterator<T> Base; typedef istream_iterator_limited<T> This; istream_iterator_limited(typename Base::istream_type &obj_stream, size_t const arg_limit) : Base(obj_stream), m_limit(arg_limit), m_current_count (1) { /* The initialiser list above does all the construction work */ } istream_iterator_limited(void) /* This gives the End-Of-Stream iterator */ : Base() , m_limit(0), m_current_count(1) { /* The initialiser list above does all the construction work */ } This &operator++(void) { if ( m_limit <= m_current_count ) { Base::operator=( Base() ); /* Becomes End-Of- Stream iterator */ } else { ++m_current_count; Base::operator++(); } return *this; } }; #include <algorithm> /* copy */ #include <string> /* string */ #include <sstream> /* istringstream */ #include <iostream> /* cout, endl */ #include <iterator> /* back_inserter */ auto main(void) -> int { std::istringstream iss("123456789"); std::string str; /* Let's use copy to read 5 char's into our string */ std::copy( istream_iterator_limited<char>(iss,5), istream_iterator_limited<char>(), std::back_inserter(str) ); std::cout << str << std::endl; str.clear(); /* Get another 3 */ std::copy( istream_iterator_limited<char>(iss,3), istream_iterator_limited<char>(), std::back_inserter(str) ); std::cout << str << std::endl; }

1 0

Re: [boost] disjoint_sets?
by Glen Fernandes 27 Oct '19

27 Oct '19

Peter wrote: > At some point we removed the disjoint_sets module from the develop branch, > but it's still on master. When are we going to remove it from master as > well? The relevant changes need to be merged from Graph develop to master, before we can retire the disjoint_sets repository entirely. John, any concerns about doing this now, before the 1.72 release progresses? Glen

1 0

disjoint_sets?
by Peter Dimov 25 Oct '19

25 Oct '19

At some point we removed the disjoint_sets module from the develop branch, but it's still on master. When are we going to remove it from master as well?

1 0

question re BOOST_NO_EXCEPTION
by Robert Ramey 25 Oct '19

25 Oct '19

I want to detect whether or not the -no_exception compile time flag has been used on gcc/clang. Will BOOST_NO_EXCEPTIONS do this? If not is there something I can use? Robert Ramey

5 10

Multi-Dimensional Dynamic Array Boost Library Proposal
by Richard Hogaboom 24 Oct '19

24 Oct '19

I've written a library at GitHub/rahogaboom/daa that does dynamic array allocation in ptr to ptr ... style that is very simple to use(only two routines), header file only, can allocate an unlimited number of dimensions with subscripts for each dimension starting at an arbitrary number e.g. 0, 1, -5 etc, can allocate anything you can take sizeof() and allocates all in one contiguous block(stack, heap) for easy freeing. I'm aware of the Boost.MultiArray library, however, I think daa has some advantages. Specifically, a. each dimension has it's own starting subscript b. it's relative simplicity(2 routines) c. it's longevity - 30 years and two articles d. also can be used in a C only environment. Following is the points noted in the GitHub README.md: |Library: daa.hpp Dynamic Array Allocator - C++ header file only library - ptr to ptr to ... style arbitrary N dimensional array allocator of anything you can take sizeof() - arbitrary starting subscript(0, 1, -10, ...) for each separate dimension - Note: for each array dimension the starting subscript and dimension size determine the valid subscripts for that dimension - any index outside that range is invalid and will give unpredictable results - allocates anything of any type(double, int, long, struct, ...) - one contiguous block allocation of memory for all ptr's and data(locality of reference and easy free()) - array or slices of array can be passed to subroutines to any depth, modified there, and be seen at all levels - simple library, two routines(das()(calculate space needed) and daa()(allocate ptr to ptr ... array)) - no library dependencies(except standard header files) - initialization pointer argument set to instance of initialized type or NULL for no initialization - implemented by a recursive routine(ptr_init()) which calls two other different recursive routines(off() and doff()) - see article in Embedded Systems Programming, Dec. 2000, "Flexible Dynamic Array Allocation"(included) - see article in The C Users Journal, Nov. 1990. "A Flexible Dynamic Array Allocator"(included) - 18 verification tests that show code usage examples, see daa_test.cpp - see cut/paste Examples section and API(das(), daa()) section below - a daa-compile.tar file is provided with a non-header compiled(clang, clang++, gcc, g++) version - for an excellent reference on this type of array(ptr to ptr to ...) access see Numerical Recipes in C, Press, Flannery, Teukolsky, and Vettering, Cambridge University Press, 1992, pg. 20-23. Ch. 1 Preliminaries -> 1.2 Some C Conventions for Scientific Computing -> Matrices and Two-Dimensional Arrays. From the above reference read: 'Here is our bottom line: We avoid the fixed-size two-dimensional arrays of C as being unsuitable data structures for representing matrices in scientific computing. We adopt instead the convention “pointer to array of pointers,” with the array elements pointing to the first element in the rows of each matrix.' - this file is the entire documentation needed to use the library - Author: Richard Hogaboom, richard.hogaboom(a)gmail.com| | Usage: - das() - find size necessary malloc()(or whatever memory allocation routine) - allocate memory daa() - populate allocated memory - allocate auto stack or static area storage e.g. unsigned char mem[SIZE] das() - determine if array will fit in mem[] daa() - populate allocated memory | |Example:| | int err_code = 0; int asize = 0; char *mem_ptr; unsigned int d[4] = {3, 5, 4, 2}; /* dimensions */ int st[4] = {-1, -5, 10, 0}; /* starting subscripts */ double ****array = NULL; /* array pointer */ asize = das(sizeof(double), 4, d, &err_code); mem_ptr = (char *)malloc(asize); array = (double ****) daa(sizeof(double), 4, d, st, &err_code, mem_ptr, NULL);| | double d = array[-1][-5][10][0];| -- Richard A Hogaboom 16 Alprilla Farm Road Hopkinton, MA 01748-1922 richard.hogaboom(a)gmail.com www.linkedin.com/in/richardhogaboom/ www.github.com/rahogaboom M508-330-3775

2 1

Boost logo font?
by Hans Dembinski 23 Oct '19

23 Oct '19

Dear all, does someone remember which font was used for the Boost logo on boost.org? Is it possible to get this font to make another logo? I want to make a logo for Boost.Histogram. Best regards, Hans

4 11

New JSON library from the maker of Beast!
by Vinnie Falco 23 Oct '19

23 Oct '19

I've been working on a massively-multiplayer online blackjack casino server, called Beast Lounge [1]. The server and client communicate using JSON-RPC over WebSocket. I have developed a brand-new JSON library for this project, in accordance with the following design goals: * Robust support for custom allocators throughout. * Array and object interfaces closely track their corresponding C++20 container equivalents. * Use `std::basic_string` for strings. * Minimize use of templates for reduced compilation times. * Parsers and serializers work incrementally (['online algorithms]). * Elements in objects may also be iterated in insertion order. You can see the JSON library in development here: https://github.com/vinniefalco/json Is there any interest in proposing this for Boost? I'm happy to hear feedback or answer questions about this library. Feel free to open an issue on the repository, or reply here. Thanks [1] <https://github.com/vinniefalco/BeastLounge>

21 68

[lockfree][Interprocess] - SPSC queue in shared memory cause SEG fault
by Saravanan A 23 Oct '19

23 Oct '19

Hi Team, We Currently trying to develop a prototype with boost libraries, where we are facing an issue in it with boost library. It would be great if someone help out here . we are having two process where one process create “*managed xsi shared memory”* and other get attached to it. Here we trying to have a spsc queue in a shared memory structure which will be accessed by both process . Where SPSC queue data is a user defined class object. when we have a integer in ” *Mydata”* (Class name) mentioned below and try to do a Push /pop operation in the spsc queue on respective process it was working fine without any issues. But the same framework when we have an array of greater size(more than 28 byte around. Example: a[7] ) .We are facing a crash in consumer side . (It seems spsc queue write somewhere in process heap memory after first pop leading to memory corrupt ) please let us know if there any open issue in this ? or if we have used boost library incorrectly ? Thanks for reading. I would be thankful for any information you may have to offer. *Backtrace:* /data/users/kapparao/example_boost/anony-SHM-managed> $./processB Consumer-TX - Read data from Q - [1,b] notify_one@93 - I am here! notify_one@159 - I am here! Segmentation fault (core dumped) /data/users/kapparao/example_boost/anony-SHM-managed> $gdb ./processB GNU gdb (GDB) Red Hat Enterprise Linux 7.6.1-115.el7 Copyright (C) 2013 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html > This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Type "show copying" and "show warranty" for details. This GDB was configured as "x86_64-redhat-linux-gnu". For bug reporting instructions, please see: <http://www.gnu.org/software/gdb/bugs/>... Reading symbols from /data/users/kapparao/example_boost/anony-SHM-managed/processB...done. (gdb) r Starting program: /data/users/kapparao/example_boost/anony-SHM-managed/./processB [Thread debugging using libthread_db enabled] Using host libthread_db library "/lib64/libthread_db.so.1". Consumer-TX - Read data from Q - [1,b] Program received signal SIGSEGV, Segmentation fault. 0x00007ffff7bcb09b in pthread_cond_signal@@GLIBC_2.3.2 () from /lib64/libpthread.so.0 Missing separate debuginfos, use: debuginfo-install glibc-2.17-292.0.1.el7.x86_64 libgcc-4.8.5-39.0.1.el7.x86_64 libstdc++-4.8.5-39.0.1.el7.x86_64 (gdb) bt #0 0x00007ffff7bcb09b in pthread_cond_signal@@GLIBC_2.3.2 () from /lib64/libpthread.so.0 #1 0x00000000004063de in boost::interprocess::ipcdetail::posix_condition::notify_one (this=0x28) at ../../boost/include/boost/interprocess/sync/posix/condition.hpp:160 #2 0x00000000004066e1 in boost::interprocess::interprocess_condition::notify_one (this=0x28) at ../../boost/include/boost/interprocess/sync/interprocess_condition.hpp:94 #3 0x0000000000402941 in main () at processB.cpp:42 Attached the complete code in tar for your reference. *Compilation and Execution* : *Process A : * Compilation syntax : c++ my_data.cc processA.cpp -I < boost_header_file_path> <boost_lib_path> -lpthread -g -o processA -std=c++11 Execution syntax : ./processA *Process B :* Compilation syntax : c++ my_data.cc processB.cpp -I < boost_header_file_path> <boost_lib_path> -lpthread -g -o processB -std=c++11 Execution syntax : ./processB *Thanks in advance !!!!!* Regards, saravanan =====================================================

2 1

Re: [boost] New JSON library from the maker of Beast!
by Daniel Frey 22 Oct '19

22 Oct '19

> On 23. Oct 2019, at 00:33, Vinnie Falco <vinnie.falco(a)gmail.com> wrote: > > On Tue, Oct 22, 2019 at 3:13 PM Daniel Frey via Boost > <boost(a)lists.boost.org> wrote: >> That sounds like you should stop using the STL altogether. What if std::string is suddenly 2x slower? So... no, I don't buy that argument. >> >> I just switched our JSON library <https://github.com/taocpp/json> from >> our own classic enum+union implementation (back from the C++11 days) >> over to std::variant (as we are now C++17 anyways). > > Any idea why taocpp compiled with optimizations is 5 to 10 times > slower than the other libraries at parsing the same inputs? Yeah... I'd actually *try* to blame MSVC here :) We haven't benchmarked our libraries on Window as we are not Windows users ourselves. The numbers on Linux/MacOS should look different. Have you tested there as well? So Emil's argument has some truth to it, but still I'd rather like to see the STL to improve rather than rolling back. But I haven't even verified it, so take that with a grain of salt. > It seems like there's this thing called PEGTL which has some large > number of functions showing up as taking up time in the profile? What > is PEGTL? The PEGTL is the Parsing Expression Grammar Template Library <https://github.com/taocpp/PEGTL>, our general-purpose parser library. the JSON library actually started out as a benchmark for the PEGTL. Obviously, the parser spends most time in some methods from the PEGTL. And older version that are in the nativejson-benchmark were doing quite well for a general-purpose parser framework <https://github.com/miloyip/nativejson-benchmark#parsing-time>. Not as fast as RapidJSON, but that also largely depends on the design choices for the value type to hold the result.

2 1

Re: [boost] New JSON library from the maker of Beast!
by Vinnie Falco 22 Oct '19

22 Oct '19

On Tue, Sep 24, 2019 at 7:32 AM Dominique Devienne <ddevienne(a)gmail.com> wrote: > ...why conflate the array and object APIs in the value > type, rather than just having as_object() and > as_array() as you already? I agree, and these additional APIs have been pruned. I have also pruned other unnecessary APIs (thanks to advice from Peter Dimov) such as the local iterator and bucket interfaces in `json::object` (which needlessly constrain the implementation). > So I'm curious why it should be different here. Does the doc goes into that already? `json::value` is not `variant<...>` for the same reason that `string_view` is not `std::pair<char const*, std::size_t>`. > On the "compact" side, how compact is your json::value? > What are the different sizeof on 32 and 64-bit arch? I've done some work on this. I gave up on using std::string to represent strings for a few reasons related to performance and API. I have reimplemented string to have a small buffer optimization and to work natively with the `json::storage_ptr` type which gives some space efficiencies (and eliminates some unnecessary atomic operations caused by std::string's Allocator interface). The new sizes look like this: 32-bit sizeof(value) == 40 sizeof(object) == 8 sizeof(array) == 8 sizeof(string) == 32 sizeof(number) == 24 64-bit sizeof(value) == 48 sizeof(object) == 16 sizeof(array) == 16 sizeof(string) == 40 sizeof(number) == 24 The string type has a 20-byte small buffer which is pretty generous Thanks

4 5

[release] Is everyone ready for the 1.72.0 release (cycle)?
by Marshall Clow 21 Oct '19

21 Oct '19

We're getting ready to start the release cycle. People should be familiar with the milestones. They're on the calendar at https://www.boost.org/development/ The first two milestones are: 23-Oct: Boost 1.72.0 closed for new libraries and breaking changes 30-Oct: Boost 1.72.0 closed for major changes -- Marshall

1 0

[Exception] PR #24 passes CI tests
by dariomt＠gmail.com 21 Oct '19

21 Oct '19

Hi, PR #24 [1] at last passes all CI tests. It should solve Issue #10 [2]. I'd like to ask for it to be reviewed and merged. I'm hopeful we can get it into the 1.72 release. Regards, Dario PS: thanks to pdimov for suggesting how to fix the Travis configuration [1] https://github.com/boostorg/exception/pull/24 [2] https://github.com/boostorg/exception/issues/10

1 0

Re: [boost] Adding my sorting algorithm, ska_sort to boost
by Malte Skarupke 20 Oct '19

20 Oct '19

Thanks for the replies. I finished a first pass of the documentation, tests, and other work of including my algorithm in boost and uploaded it here: https://github.com/skarupke/sort/tree/master I also re-ran all the single threaded benchmarks and updated the documentation. For the big O complexity: I am actually still not quite sure what it is. I used similar notation to what spreadsort uses. I think O(n*key_length) is correct for the worst case, but for long keys (like when sorting long strings) the algorithm may fall back to comparison based sorting, so I used the same thing as spreadsort: min(O(n log n), O(n key_length)). For speed: ska_sort should be the fastest sorting algorithm even for small numbers of items. I included three graphs of benchmarks, for sorting ints, floats and strings: https://github.com/skarupke/sort/blob/master/doc/images/sorting_ints.png https://github.com/skarupke/sort/blob/master/doc/images/sorting_strings.png https://github.com/skarupke/sort/blob/master/doc/images/sorting_floats.png For ints and strings ska_sort is always fastest, for floats pdqsort is briefly faster, but starting at N >= 128 ska_sort is faster. Part of the work of this new version of ska_sort was to make radix sort really fast even for small N. Before I would use std::sort for any small array of less than 128 items. Now that cutoff is at 32 items, so I skip straight to insertion sort and never do std::sort. The biggest effect of this change is that it removes the "waves" from the benchmark graph, like we still see for spreadsort in the above picture. I used to also have those when I gave a talk about this algorithm. Now the graph is much more smooth. (this also confuses my answer to the question "what is the big O complexity of this algorithm?" Because the O(n*b) answer that I gave in my talk was justified by the presence of the waves) The biggest questions I have at this point are around the interface. I reworked that completely so that even relatively advanced use cases are now pretty straightforward. I don't think that anyone else will ever need to use those advanced features, so I kept the documentation of them small, choosing instead to focus on the common use cases. And I made sure to give lots of examples of converting existing comparison-based sorting examples to my interface. Oh and for the big point of a parallel version of this algorithm: At this point I have no idea how to do that. I haven't even begun to look into parallel algorithms. The current version was a lot of work already. I think that'll have to be a project for another time. (it's definitely appealing though since currently the sorted algorithms are only 2.4 times as fast as ska_sort on a machine with 8 cores/16 hyper threads in benchmark_numbers.cpp, so even a little bit of parallelism would beat the existing algorithms...) Francisco, since you'll be busy in the near term it sounds like I can't expect too much response for another month, but I would really appreciate it if you could look at it a little just to see if anything obvious stands out to you that I can work on while I wait. (otherwise no biggie, I understand how hard it can be to find time for maintaining projects, since that is exactly one of the reasons why I want to get this into boost...) Thanks, Malte -- Malte Skarupke malteskarupke(a)fastmail.fm > Date: Sun, 20 Oct 2019 13:24:06 +0200 > From: Francisco Jos? Tapia <fjtapia(a)gmail.com> > To: boost(a)lists.boost.org > Subject: Re: [boost] Adding my sorting algorithm, ska_sort to boost > Message-ID: > <CADBNGqQJpHux3AdRJON-nh76BaouRn1FRO4_LrMR76TywmCH+g(a)mail.gmail.com> > Content-Type: text/plain; charset="UTF-8" > > Hi Malte, > I am Francisco Tapia, one of the co-authors of the Sort library. > We will examine your algorithm. But we must examine the internal parts of > the algorithm, and evaluate the correctness of the algorithm, how is > implemented the worst case and a couple of details. After, we check the > speed with the benchmarks used in the library, with several sets of data. > Since the near sorted to the fully unsorted, and from the single numbers to > structs with heavy comparison functions. > > Now, I am overburdened by work, and I can't revise until December. But we > will do and provide to you a reasoned response, and according to it, decide > the inclusion or not in the library. > As commented by Phil Endecott, the most interesting now is the parallel > algorithms. Today, we don't have any parallel algorithm based on radix sort > or any other hybrid algorithm. > Because with small sets of data the differences are insignificant. But when > you have big sets of data, use parallel algorithms, and then, the new > single thread algorithms are in the middle, in the no man's land. > > If you have any doubt or question, contact me, and I will try to answer you. > > El mar., 15 oct. 2019 a las 23:06, Kostas Savvidis via Boost (< > boost(a)lists.boost.org>) escribi?: > > > > > > On Oct 13, 2019, at 03:06, Malte Skarupke via Boost < > > boost(a)lists.boost.org> wrote: > > > > > > Hi, > > > a couple of years ago I wrote a generalized version of radix sort, > > called ska_sort. I gave a talk about it at CppNow, available here: > > > https://www.youtube.com/watch?v=zqs87a_7zxw > > > > > > I have a new version of that algorithm that is both faster and more > > general. I can now sort almost anything. For example when I gave the talk I > > couldn't sort a std::vector<std::list<int>> because std::list doesn't have > > a random access interface, but now that works. (and it's faster than > > sorting the same thing with std::sort) > > > > > > > This seems like a product of a large investment of effort. > > The big advantage over any previously available radix_sort > > is the ability to sort almost any datatype if a key maps to an integer > > somehow. > > Plus, an advantage in measured practical speed, and apparently no claims > > about Big O improvement. > > > > The average performance is O(n*b) where b is unknown and/or dependent on n > > ? > > > > Is the theoretical worst-case O(n^2) ? Why? Is it because of working > > in-place? > > (yes, I understand you fall back to std::sort if you hit this case) > > > > Is this software/algorithm fully documented? - I mean by another way than > > reading the source code. > > > > Maybe too many questions at once, but it was not clear after watching your > > talk at cppcon and the blog posts. > > > > Cheers, > > Kostas > > > > <https://www.youtube.com/watch?v=Nz1KZXbghj8> > > > > _______________________________________________ > > Unsubscribe & other changes: > > http://lists.boost.org/mailman/listinfo.cgi/boost > > > > > ------------------------------ > > Subject: Digest Footer >

1 0

constexpr for boost::endian
by Gero Peterhoff 20 Oct '19

20 Oct '19

Hello developer, can you implement constexpr support for boost::endian? And i'm missing support for (compiler-dependent) int128 (boost::u/int128_type). thx Gero

2 2

Adding my sorting algorithm, ska_sort to boost
by Malte Skarupke 20 Oct '19

20 Oct '19

Hi, a couple of years ago I wrote a generalized version of radix sort, called ska_sort. I gave a talk about it at CppNow, available here: https://www.youtube.com/watch?v=zqs87a_7zxw I have a new version of that algorithm that is both faster and more general. I can now sort almost anything. For example when I gave the talk I couldn't sort a std::vector<std::list<int>> because std::list doesn't have a random access interface, but now that works. (and it's faster than sorting the same thing with std::sort) I've also made it much easier to extend the algorithm with your own types. It was always easy if your type isn't too complicated, but now even weird types like std::variant are pretty easy to add. In my old version I had to go deep into the guts to add support for std::variant, now it's easy enough to do that that I'll add it to the documentation. I'm thinking of releasing the new version in boost, mainly so that it will be used more widely and so that it can be kept working in the long term. Since this is a long weekend in the US, I will try to as much of the work as possible this weekend. I'm currently trying to figure out how the boost documentation works (I saw that there are quickbook files in Boost.Sort, but how do I run the build for it?) and I've already made good progress on cleaning up my code and making it use the boost::sort namespace. Before I go any further I wanted to ask though: Does boost want my sorting algorithm? This would essentially deprecate spreadsort since this one is faster and more general and easier to use. To convince you that this is worth adding, I ran the benchmark that is included in the Boost.Sort source code. On random numbers here is how long all the algorithms took: std::sort: 9.04 pdqsort: 4.65 std::stable_sort: 11.57 spinsort: 5.42 flat_stable_sort: 7.26 spreadsort: 4.41 ska_sort: 2.00 There are a lot more bencmarks in the Boost.Sort code, and in general the results are this: If the data is already sorted or mostly sorted, other algorithms are faster, but if there are no easy patterns, ska_sort is always fastest. (I was going to include the entire table in this email, but the formatting breaks. I can attach all the results separately if anyone is interested) The Boost.Sort code also has benchmarks for sorting "objects" and "strings" and the results are similar there: On random data ska_sort is always fastest. I think this new version would be great in boost. It's not every day that a new sorting algorithm comes along that's literally twice as fast as what we had before. If we want this in boost, what would the next steps be? From the "submission process" document it sounds like there will be several stages of "Refinement" for the code. (or should this go through the Boost Library Incubator?) After I figure out how the documentation works I can upload a first version of this to github. (I want to get the documentation working so that we can talk about the interface) Let me know what you think, Malte -- Malte Skarupke malteskarupke(a)fastmail.fm

5 4

[SPAM] [preprocessor][vmd] Updates to the preprocessor and vmd libraries
by Edward Diener 19 Oct '19

19 Oct '19

The C++20 preprocessor construct __VA_OPT__ has the additional affect of providing the ability to write a general purpose macro for testing emptiness, ie. no preprocessor tokens, in C++ macro programming that is 100% reliable for any preprocessor data passed to it. Previously such a macro testing for emptiness always had some corner cases where the test might fail with a preprocessor error, but in C++20 mode at least the test can now be completely reliable in all cases. So I have added two macros along with documentation, as well as a topic discussing emptiness, to the Boost PP library. The first macro is called BOOST_PP_VARIADIC_OPT, invoked with no parameters as BOOST_PP_VARIADIC_OPT(), which expands to 1 if the compiler is in C++20 mode, supports variadic macros, and supports the C++ 20 __VA_OPT__ construct, and otherwise expands to 0. The second macro, which only exists if BOOST_PP_VARIADIC_OPT() expands to 1, is called BOOST_PP_CHECK_EMPTY. This second macro is a variadic macro which takes a single parameter of variadic data, and expands to 1 if the data is empty or expands to being empty, while otherwise expanding to 0 if the data is not empty. Furthermore in the Boost VMD library I have updated the BOOST_VMD_IS_EMPTY macro to essentially invoke the BOOST_PP_CHECK_EMPTY macro when BOOST_PP_VARIADIC_OPT() expands to 1, while retaining the current processing when that is not the case. As well I have updated the VMD discussion of emptiness in the documentation of Boost VMD to include information about the ability to provide a 100% reliable test for emptiness in C++20. Neither change in Boost PP or Boost VMD should affect any end-user or Boost library in any way. There are tests for all these changes and all tests have passed. I will update the release notes for Boost PP and Boost VMD for the next release of Boost with this information. As always any comments, questions, or criticism of these changes are always welcome.

1 1

Warning from Boost.Exception
by pbristow＠hetp.u-net.com 17 Oct '19

17 Oct '19

Using Clang 9 on Windows b2 toolset-clang-linux cxxstd=2a . I am seeing lots of these warnings In file included from ..\..\..\boost/test/included/unit_test.hpp:23: In file included from ..\..\..\boost/test/impl/execution_monitor.ipp:37: In file included from ..\..\..\boost/exception/diagnostic_information.hpp:11: ..\..\..\boost/exception/info.hpp:134:21: warning: delete called on non-final 'boost::exception_detail::error_info_container_impl' that has virtual functions but non-virtual destructor [-Wdelete-non-abstract-non-virtual-dtor] delete this; ^ It seems that trying to supress is ineffective with -Wno-delete-non-abstract-non-virtual-dtor Perhaps by design? https://releases.llvm.org/9.0.0/tools/clang/docs/DiagnosticsReference.html#… te-non-abstract-non-virtual-dtor -Wdelete-non-abstract-non-virtual-dtor <https://releases.llvm.org/9.0.0/tools/clang/docs/DiagnosticsReference.html> Diagnostic text: warning: delete destructor called on non-final B that has virtual functions but non-virtual destructor -Wdelete-non-virtual-dtor <https://releases.llvm.org/9.0.0/tools/clang/docs/DiagnosticsReference.html> Some of the diagnostics controlled by this flag are enabled by default. Controls -Wdelete-abstract-non-virtual-dtor <https://releases.llvm.org/9.0.0/tools/clang/docs/DiagnosticsReference.html> , -Wdelete-non-abstract-non-virtual-dtor <https://releases.llvm.org/9.0.0/tools/clang/docs/DiagnosticsReference.html> . Should I be concerned about this? Paul Paul A. Bristow Prizet Farmhouse Kendal, Cumbria LA8 8AB UK

4 13

[Math] float16 on ARM
by Phil Endecott 16 Oct '19

16 Oct '19

Hi, There seems to be support for 16-bit floats on iOS, when using Apple's XCode clang. This seems to be a storage-only format with the only instruction set support being conversions to and from 32- and 64-bit floats. Quick test: #if __ARM_FP & 2 #warning "Have 16-bit FP" #endif void test() { __fp16 a = 1.234; static_assert(sizeof(a)==2); __fp16 b = 2.345; auto sum = a+b; static_assert(sizeof(sum)==4); } There doesn't seem to be a std::numeric_limits specialisation. I suspect that other platforms have something similar. It would be good to have a boost::float16_t typedef and a portable feature-test macro (and maybe a software fallback). As far as I can see, boost/math/cstdfloat/cstdfloat_types.hpp checks the sizes of float, double and long double, and checks for 128-bit floats provided by the compiler. Can this be extended to check for __fp16 ? (P.S. it seems that gcc also has support, see https://gcc.gnu.org/onlinedocs/gcc/Half-Precision.html ) Cheers, Phil.

5 10

Does boost asio ssl support sslv3?
by JH 15 Oct '19

15 Oct '19

Hi, I've been running boost asio socket and sslv2 for many months, it works very well: server.cpp ontext_(boost::asio::ssl::context::sslv23) context_.set_options(boost::asio::ssl::context::default_workarounds | boost::asio::ssl::context::no_sslv2 | boost::asio::ssl::context::single_dh_use); context_.set_password_callback(boost::bind(&Server::get_password, this)); context_.use_certificate_chain_file("ssl/server.pem"); context_.use_private_key_file("ssl/server.pem", boost::asio::ssl::context::pem); context_.use_tmp_dh_file("ssl/dh2048.pem"); on client.cpp boost::asio::ssl::context context(boost::asio::ssl::context::sslv23); Recently we changed a nodejs server nodejs which using sslv3, the client failed to connect to server sslv3: Failed handshake: sslv3 alert handshake failure Any tips how to fix sslv3 handshake failure? Thank you. Kind regards, - jh

4 6

Cryptic Boost.Build error (help required!)
by John Maddock 14 Oct '19

14 Oct '19

Can anyone see what's wrong here: https://github.com/boostorg/regex/issues/89 ? The reduced test case is: |./b2 -sICU_PATH="/opt/some/path" -sICU_LINK="-L/opt/some/path/lib/x86_64-linux-gnu -licuuc -licudata -licui18n" toolset=gcc-8 -n --with-filesystem --with-log Many thanks, John. | -- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

2 1