- Boost - lists.boost.org

[algorithm] any_of does not call std::find - bad performance
by Albert Yiamakis 15 Apr '14

15 Apr '14

Hello, Is there a particular reason why Boost.Algorithm's any_of does not call std::find? I have devised a simple benchmark that shows it to perform much worse (compiling with gcc): http://pastebin.com/nrgtTfPX boost::find is almost as fast as std::find - no surprises, as it calls it. any_of is considerably slower, whatever the optimization level. I have not dug in the implementation of std::find to determine why; perhaps the compiler recognizes this is a sorted range, perhaps it's even capable of doing the calculation at compile time. Whatever the case however, surely any_of should also call std::find to reap the same benefits? Albert

1 2

Re: [boost] [serialization] proposed improvements: forward-compatibility of serialization
by Andrzej Horoszczak 15 Apr '14

15 Apr '14

-------- Original Message -------- > From: Sohail Somani <sohail(a)taggedtype.net> > > This was a problem that interested me a few years ago so I made a > solution that worked with any archive and I presented it at BoostCon > (now CppNow). It was inefficient, hacky and required no modifications to > existing archives but forward compatibility did work so I know it is > completely possible. Do you have a specific link handy ? or do you perhaps remember project name so I could google it? > >My immediate question would be whether you already have released code >for the products in question which complicates things a bit. Fortunately we still have about 4-6 weeks before general release (-; > The proposal itself doesn't seem impossible, at a > glance. Thanks - that's promising (-; I believe that this approach should be more efficient and more elegant that Google's Protocol Buffers. And for us minimizing network traffic is of paramount importance. Andrew _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

2 1

[serialization] proposed improvements: forward-compatibility of serialization
by Andrzej Horoszczak 15 Apr '14

15 Apr '14

Hello Everybody, (it seems that my previous post had contained only title - so I repeat the full posting below) We've started (again) using boost::serialization in our multi-platform distributed application about one year ago. However, we have arrived at a road block with forward-compatibility of serialization - which of major importance to us since we cannot force users to upgrade to the same/newer version of application all at the same time. Firstly, question is: perhaps you or someone that you know of - would be interested in such improvement work? We are small company rushed against some die-or-prosper deadlines - and simply do not have enough resources to do it on our own in time avialable - but we could sponsor such work. Secondly, the problem is: To avoid ambiguity I have put together the following description and our own suggestion for solution: The project requirement is centred on improving multi-version class compatibility in binary archives e.g. more flexibility in a situation when we are reading or transferring modified class in C++ code. We need to go beyond what current version of object versioning in boost offers: http://www.boost.org/doc/libs/1_55_0/libs/serialization/doc/tutorial.html#v… Specifically we need to add ability to skip reading unknown or unexpected fields in a non-XML archives we are parsing. Specific example: Version of the application (newer one) that saved the archive has the following code: struct extensionClass { std::string moreInfo; time_t date; template<class Archive> void serialize(Archive & ar, const unsigned int version) { ar & moreInfo; ar & date; } } class gps_position { public: template<class Archive> void serialize(Archive & ar, const unsigned int version) { ar & degrees; ar & minutes; ar & seconds; ar & new_field } int degrees; int minutes; float seconds; extensionClass new_field; gps_position(){}; }; And now the version of the software that needs to read the archive is an older application that has the code that implements the gps_position class in the following way: class gps_position { public: template<class Archive> void serialize(Archive & ar, const unsigned int version) { ar & degrees; ar & minutes; ar & seconds; } int degrees; int minutes; float seconds; gps_position(){}; }; The purpose of the project is to gracefully allow for serialization in older version of application to continue reading the archive, by simply omitting information related to extensionClass new_field; e.g. to properly advance the read position to the beginning of next class in the archive. It is desirable to add to programming interface information that there was incompatibility detected, for further escalation to either to user interface, or higher level code logic that might decide, for instance, to change communication protocol. It is critically important for us to optimize archive size while adding this capability. We prefer to use eos::portable_iarchive which provides varinteger support for multi-OS compatibility (size of int, little vs big endian), therefore we prefer solution which would accept any archive, however, we will be ok with standard boost binary archive solution. Thirdly, the proposal is: The most promising solution that we envisage is to add recursive size information associated with the number identifying class (already placed in front of every data object). By recursive size information I mean size not in terms of bytes for raw data, but in terms of number of fields/objects in the class. The size information would than be expanded until it can be expressed in terms of C++11 standard predefined POD sizes. For instance for simple class example: class SimplePODs { uint32_t firstField, uint64_t int secondField; float thirdField; } The associated (leading) size information for the SimplePODs class is 3. Than within the class itself we already have identifiers of each field types. Since they are POD we can maintain global (and for the archive) dictionary of sizes for each identifier in this case: 4 than 8 and 4 And than it follows: class AggregateClass { SimplePODs first_field; char second_field; } In this case the size information (in the global dictionary) for identifier associated with AggregateClass is 2. Than within the class itself sizes for first_field would be 3 and for second_field it is of course 1. I believe this can be done as part of the version and object tracking process so the performance would still be high and most importantly, the incremental size overhead both in memory and in the archive will be relatively small (only one size information per each type of object contained in the archive - and no size overhead for POD fields). By the way this approach would also increase multi-OS compatibility for instance class on the source computer might be 32-bit compilation of : class CrossPlatform { int idont_care_about_size; } And during saving that field: idont_care_about_size would actually be saved and identified as uint32_t The same CrossPlatform class on destination machine would be compiled as 64-bit application - but since target int would be larger that source we can do silent promotion. Of course the other way around, we can throw exception if the actual value contained within idont_care_about_size exceeds the targets' compilation POD size. OK - I hope that my explanation is clear and I would appreciate any feedback that you might have. And finally let me state that we do greatly appreciate (and use) a lot of boost work and in particular, we consider boost.serialization approach to be probably the best possible under the current constrains of the language. Best regards, Andrew Horoszczak

6 5

[algorithm] LSD radix sort
by Jeremy Murphy 15 Apr '14

15 Apr '14

Dear community, I humbly offer you for perusal and review, LSD radix sort (and counting sort): https://github.com/jeremy-murphy/algorithm/tree/radix_sort The tests and docs are unfinished but the library code is as complete as I can manage without comment from others. The new files of interest are in include/boost/algorithm/integer_sort. I have more code with a speed test and CMake files in a separate repository: https://github.com/jeremy-murphy/integer-sort But perhaps I should move all those files into a branch off my Boost.Algorithm fork? Probably. Anyway, thanks in advance for any feedback and comments. Cheers. Jeremy

2 6

Amusing git pseudo-documentation
by Nat Goodspeed 15 Apr '14

15 Apr '14

Warning: this is not real. It just tickles me. http://git-man-page-generator.lokaltog.net/#72a7d7ff89dc3b268c857e3b2ddabff6 Apologies for the noise...

3 2

Application 0.4.6 with global_context.
by Renato Forti 15 Apr '14

15 Apr '14

Hi, thanks for your comments. >> If the main usage is likely to be 'daemonic', then Boost.Daemon would still be a good name. About the name 'application'. I chose this name because the library can support many kinds of application, see: http://www.dokfile.com/appbeta4/docs/libs/application/doc/html/boost_applic… >> From the current name, one would be unlikely to guess that it could do daemon work? The name 'Daemon' is usual in POSIX world. In Windows world the usual is 'Service'. I could call it as 'server', but it would also be wrong due to support for common application. In future the library can support other kinds of application (e.g. apache httpd modules) Thus I think that the name 'application' is more suitable. Let me know your thoughts. Thanks for help ReTF

1 0

[git] github cheat sheet
by Philippe Vaucher 15 Apr '14

15 Apr '14

Hello, I think this might be useful for many people: a list of overall tips n' tricks about github and git. https://github.com/tiimgreen/github-cheat-sheet Hope it helps, Philippe

1 0

[algorithm] Review Request: edit_distance
by Erik Erlandson 15 Apr '14

15 Apr '14

I would like to request a formal review for inclusion of the edit_distance() function. Description: The edit distance is the length of the shortest (or least-cost) edit script from one sequence to another, where an edit script is defined as a sequence of insertion, deletion and (optionally) substitution operations. The function implementing the edit distance is named edit_distance. This function will return the edit distance between two sequences, where sequences may be any valid range object supporting forward iteration. The edit_distance function will also, if requested, return the edit script. http://en.wikipedia.org/wiki/Edit_distance Documentation: http://erikerlandson.github.io/algorithm/libs/algorithm/doc/html/algorithm/… Code resides on a branch of my fork of Boost.Algorithm: https://github.com/erikerlandson/algorithm/tree/edit_distance The feature branch above includes the doc, unit tests and examples that are integrated via Jamfiles. The new dev resides specifically in this subdir: https://github.com/erikerlandson/algorithm/tree/edit_distance/sequence I have built the tests and examples on gcc and clang, with and without c++11 mode. I don't have access to a windows/MSVC build env, so I am definitely curious if it compiles properly in that env. My concept is that boost::algorithm::sequence can eventually serve as a home to additional related algorithms, for example other sequence comparison algorithms or perhaps other categories of sequence-related algorithms.

9 31

[graph] Are you interested in the Route Inspection Problems and Vehicle Routing Problems?
by Ciro Santilli 14 Apr '14

14 Apr '14

Are you interested in implementations for the following problems: - Route Inspection Problems: http://en.wikipedia.org/wiki/Route_inspection_problem - classic: find shortest path for undirected graph possibly repeating edges. O(n^3). If Eulerian path exists, it is the min. - mixed graphs. NP-complete. AKA Chinese postman problem. - k-Chinese postman problem. N postmen. - Vehicle routing problem: http://en.wikipedia.org/wiki/Vehicle_routing_problem Generalization of Route Inspection. NP-complete. Many variants: edges have one ore more weights, and multiple constraints are possible: - carrying capacity of each truck - time to travel an edge and delivery windows for each edge All of those problems have extensive literature, and obvious practical applications. Why don't you use GitHub's Issue tracker instead of the mailing list? It integrates better with the code tracking and merge requests, and is much easier to search. That would greatly reduce contribution barriers to new devs.

3 2

[variant] Why no move emulation with Boost.Move for C++03?
by Andrzej Krzemienski 14 Apr '14

14 Apr '14

Hi, I am trying to figure out what the best way to enable move semantics in Boost.Optional. I tried to pick at how Boost.Variant does it. If I understand correctly, move operations are only defined if compiler supports rvalue references. I wonder why it doesn't use Boost.Move, which would enable move semantics even for compilers w/o rvalue references. Is there any reason for this (that I should also take into account for Boost.Optional)? Regards, &rzej

7 7