April 2013 - Boost - lists.preview.boost.org

Voronoi benchmark update
by Sebastien Loriot 03 May '13

03 May '13

Hello, I'm involved in the CGAL Project, and saw the Voronoi benchmark. It would be nice if you could change the CGAL code slightly, as it is not as bad as it currently seems. Attached is the diff to the trunk of boost. Concerning the Voronoi diagram of points, a CGAL user, would use the Delaunay_triangulation_2 class. Concerning the Voronoi diagram of segments (that do not intersect) one would make a better choice for number types and traits classes. Also one better first inserts the endpoints and then the segments (I agree, this should definitely go into a member function). Admittedly our examples could be better. Cheers, Sebastien

3 4

[GSOC 2013]Boost.Math Proposal
by Nikhar Agrawal 03 May '13

03 May '13

Hi everyone, I have been in touch with mentors for the project "Boost.Math Bernoulli Numbers and Applications to Special Functions" for the past three weeks. And after regular interactions and assignments and suggestions from them, I have finally posted my proposal. I was a little late because in submitting the proposal because of my end semester examinations. But that now they are over, I have all the free time to completely concentrate on the project. Here's the link to the proposal. http://www.google-melange.com/gsoc/proposal/review/google/gsoc2013/nikhar/1 I'd be really grateful if you guys could review it and suggest improvements. Thanks a lot. :) Nikhar P.S.:- If anyone wants I could also forward the conversations I've had with the mentors until now and I could upload the assignments I've done if anyone's interested.

1 1

[gsoc-2013] proposal for approximate string matching
by Yu Jiang 03 May '13

03 May '13

Hi, I'm a student from Tsinghua University in china and interested in the idea about "approximate string matching". Below is my proposal for this. Could you please view it and give me any kinds of suggestions on it? Thanks! (1) Personal Details * Name: Yu Jiang * College/University: Tsinghua University, China * Course/Major: Computer Science and Technology * Degree Program: M.Sc. * Email: sunlightt07(a)gmail.com * Homepage: do not have one * Availability: - How much time do you plan to spend on your GSoC? Since I have a long summer holiday, I can spend 30 hours a week. - What are you intended start and end dates? I will follow the calendar of GSoC. I have plenty of time from June to September. - What other factors affect your availability (exams, courses, moving, work, etc.)? I have some courses this term which will end before June. 15th. However, these courses don't have heavy workload, I still have enough time to work on GSoC. (2) Background Information * Please summarize your educational background (degrees earned, courses taken, etc.). I majored in Computer Science and got my bachelor degree in Tsinghua University from 2008 to 2012. I learned some basic courses such as algorithm, data structure, algebra and logic. I also learned many advanced courses such as database, operating system, network, formal language, compiler, computer architecture. Currently I'm working for my master degree. My research interest is database. * Please summarize your programming background (OSS projects, internships, jobs, etc.). This is the first time I plan to take part in an OSS projects. I have worked as an intern in Hulu, an online video website, for one year, mainly focus on frontend webpages. I have used C++ to finish many course projects, such as a simple ftp server and client, completing a tiny os and so on. Recently I am learning the new features in C++11 and get to know much more about the C++ language. * Please tell us a little about your programming interests. I really love to optimize on the implantation of an algorithm by making full use of the compiler and the architecture(e.g. cache, SIMD). Besides, I like to write webpages using different kinds of excellent frameworks. * Please tell us why you are interested in contributing to the Boost C++ libraries. Boost is the most famous C++ libraries. It is powerful and can be used in many different kinds of programs. It's my honor to add some new features into it. * What is your interest in the project you are proposing? It's related to my research interest. Nowadays data are produced rapidly. To clean or integrate them so that we can get a better view, "Approximate string matching" is rather a powerful tool. I'd like to see such functions in boost library. * Have you done any previous work in this area before or on similar projects? Yes. My lab has focused on researching on such algorithms for 3-5 years. The "best" algorithm for general string similarity search and join is called "passjoin", which is invented by our lab. I have implemented it and done a lot of optimizations. Early this year we attended a string similarity search & join competition[1] and achieved champion. The code is mainly written by me. [1] http://www2.informatik.hu-berlin.de/~wandelt/searchjoincompetition2013/Resu… * What are your plans beyond this Summer of Code time frame for your proposed work? I will make efforts to make it accepted by the boost library. If it can be released someday, I will maintain it. * Please rate, from 0 to 5(0 being no experience, 5 being expert), your knowledge of the following languages, technologies, or tools: -C++: 3 -C++ Standard Library: 3.5 -Boost C++ Libraries: 2 -Subversion: 3 * What software development environments are you most familiar with? Eclipse. I use it in both windows and linux. * What software documentation tool are you most familiar with? Doxygen. (3) Project Proposal Approximate string matching is a "hotspot" in recent years. It's widely used in big data processing such as search engine, DNA matching. It also can be used in simple tasks like spell checking. However, there isn't a high performance and well-designed library in such area. I wish to see such algorithms in boost so that many people can benefit from this! My proposal contains two parts: A. To implement basic similarity metrics. Edit distance and Jaccard may be the most popular ones. Well, I'll implement more similarity metrics, such as Hamming distance, dice and cosine. B. To implement the fastest algorithm for string similarity search and join. Similarity metrics will be edit distance only since it is most commonly used. Similarity search is to find out all the strings in a given set S, which are "similar" to a query string. Similarity join is to find out all the string pairs<r,s>, where r is in set R and s is in set S and r is similar to s. They are the most useful operators in large data processing. However, the brute-force method for such problem is too slow. And it's not easy to write a correct and high performance algorithm without reading the details in many research papers and debugging them for a long time. To avoid reinventing the wheel, I strongly propose to implement it in boost library. Here is a prototype for the interface: Part A. basic similarity metrics (use edit distance as an example) (1) int edit_distance(const Range1T&, const Range2T&); // return edit distance. (2) int edit_distance(const Range1T&, const Range2T&, int threshold); // return edit distance if it is no larger than threshold, else return -1 or threshold + 1. (3) int edit_distance(const Range1T&, const Range2T&, equal_func); // use uqual_func to determine whether two elements are equal or not. (4) int edit_distance(const Range1T&, const Range2T&, insert_cost_func, delete_cost_func, substitute_cost_func); // use three cost functions to calculate the cost for one insert/delete/substitute operation. (5) some functions to return the sequence of operations? Version (1) may be the most common case. Version (2) can use the given threshold to do optimization for the speed (O(m*n) -> O(threshold * min(m, n))). It's useful since sometimes we only care about the exact edit distance if it is small. Version (3) and (4) extend the flexibility of this utility algorithm. I'm not sure whether to support (5) or not. Part B. string similarity search and join algorithms, focus on edit distance class searcher { void insert(IDType id, const string &word); // insert a word to the index, id is used as an identifier of this word. void erase(IDType id); // erase a word from the index, id should be the same one used in insertion process. vector<Result> search(const string &query, int threshold); // performing similarity search, which will return all the strings which are similar to the query string. Result may be a pair of the id and real edit distance. }; class joiner { vector<PairResult> join(const string_and_id_container &R, const string_and_id_container &S, int threshold); // performing similarity join. Usually we are doing on-line join, which means we cannot pre-build the index. So we only need this one function. It will return all the <r,s> pair where r is in R and s is in S and r is similar to s. PairResult may be a tuple of r's id, s's id and real edit distance. }; (4) Proposed Milestones and Schedule Now – June 15 To be more familiar with the Boost library. Discuss the details and interfaces with my mentor and on the develop mail list. June 15 – July 15 Develop a beta version of the approximate matching library. Most functions will be done at this time. July 15 – August 1 Review my code and improve its performance and quality. Discuss with my mentor for mid-term evaluation and future works. August 1 – September Write documentation, test code for my library. Make it "boost" like.

4 12

[gsoc-2013] Boost.Expected
by Pierre T. 02 May '13

02 May '13

Hello, My name is Pierre Talbot, I participated to GSoC 2011 and began the implementation of the Boost.Check library (for checking the validity of any number having a check digit — credit card number, ISBN, …). It was two years ago and the design is still evolving due to many variation points in the code. One of the function looks like : template <typename check_algo, typename range> boost::optional<typename check_algo::checkdigit_type> compute_checkdigit(const range &x); Using boost::optional tell us that: "A check digit should be computed if 'x' is a valid sequence". Since 'x' has many reasons to be incorrect, many errors could be raised. Based on a policy template class, it launches exception or returns with an empty optional . Then I though a lot about a better way to do it, allowing the user to get an exception or an error code. But it was quite complex for a so little part of my library… I decided that the policy "throw exception or nothing" should be enough. Yesterday, I watched the video of Mr. Alexandrescu on Boost.Expected and I think it would be a very useful library. It could mainly be useful in system programming (where many error codes can arise from a single call), but in any code where many exception errors can be thrown (like in Boost.Check). As you suspected, I'm interested in coding Boost.Expected during the summer as a GSoC student. Firstly, it could be very useful to list the resources on the subject (aside the talk), I have several articles that I will talk about later. Secondly, and hoping you'll debate, I would like to ask your opinion about several ideas and facts: 1) In the Boost project description, we can read: "adding a class expected-or-error_code". Obviously, the main design decision made by Alexandrescu is to consider that error code are exception. Do we need an abstraction of exception/error code ? Why do you think a "expected-or-error_code" class is interesting ? 2) Consider this code (from Alexandrescu slides) : // Caller string s = readline(); auto x = parseInt(s).get(); // throw on error auto y = parseInt(s); // won’t throw if (!y.valid()) { // handle locally if (y.hasException<std::invalid_argument>()) { // ------------------ < The flagged line. // no digits ... } y.get(); // just "re"throw } The flagged line has some tastes of "return to the past" flavor. Back to the C procedural language, the basic error code handling system was a lot criticized because: * Readability of the code decrease ; * Error handling occurs in the middle of the execution flow ; * <Add your favourite reason here>. Several links on the subjects (if you have others, I'm interested) http://www.joelonsoftware.com/articles/Wrong.html http://www.joelonsoftware.com/items/2003/10/13.html http://blogs.msdn.com/b/oldnewthing/archive/2005/01/14/352949.aspx http://nedbatchelder.com/text/exceptions-vs-status.html Basically, only the last one is clearly for exception. The main argument against the procedural approach is the readability. I would say that the Expected approach just differ by allowing to rethrow exception. But if you want to handle it, you must code multiple if-than-else statements. So I considered a complementary approach working with Expected to handle multiple error cases: string visa_number = readline(); expected<char> expected_checkdigit = compute_checkdigit<visa>(visa_number); if(expected_checkdigit.valid(visa_error_resolver)) { visa_number += expected_checkdigit.get(); std::cout << visa_number << std::endl; } With this code, there is only a if statement, and no more multiple error cases handles. But what is this error_resolver ? It may be declared as : // Somewhere in visa.hpp. A type list. typedef error_list<size_error_exception, unknown_character_exception, checkdigit_encoding_exception, …> visa_errors; // Somewhere in the user code. error_resolver<visa_errors, expected_type> visa_error_resolver; // in this case, expected_type is a char. // Initialize error handler on specific exception/errors. visa_error_resolver.on<size_error_exception>(size_error_handler) .on<unknown_character_exception>(unknown_character_exception) ... Now we are agree that visa_error_resolver can be reused everywhere we want to resolve an error on a visa number. What are the handlers ? There are [Function|Functor|Lambda] (pick up your favourite) with this form : expected<ExpectedType> size_error_handler(const size_error_exception&) expected<ExpectedType> unknown_character_exception(const unknown_character_exception&) Now you can understand for what the type list "error_list" stands for, we can store these handlers into the error_resolver and call them without any virtual cost. Why the return type of error handler is expected<ExpectedType> ? Consider this size_error_handler code : expected<ReturnType> size_error_handler(const size_error_exception& e) { std::cout << "The number you gave has a bad size." << std::endl; std::cout << "Enter it again : " << std::endl; return read_visa_checkdigit(); } read_visa_checkdigit can call recursively valid() until it's valid. Though there are some ways to make this treatment iterative. A basic treatment could be to print an warning message and just returns (in this case, valid returns false): expected<ReturnType> size_error_handler(const size_error_exception& e) { std::cout << "Warning: the VISA field is incorrect." << std::endl; return expected<ReturnType>::fromException(e); } Results: * The error code handling is delegated to specific functions ; * The readability is still excellent ; * You can easily re-use your error handler function ; * If you don't like it, you can still throw exception on failure with "get()". I can code a "proof of concept" if you think this is a good idea. Do not hesitate to comment it, point out programming pitfalls, request further clarification, or anything you judge useful. Thank you for reading it ! Pierre Talbot

10 63

[reference_wrapper] Overloading operator() in reference_wrapper
by Nathan Crookston 02 May '13

02 May '13

Hi all, std::reference_wrapper includes an overload of operator()[1] which allows a wrapped function object to be called without needing to first unwrap: #include <boost/ref.hpp> #include <functional> #include <iostream> int main() { auto f = [](int i) { std::cout << i * 2 << std::endl; }; std::ref(f)(5);//change this to boost::ref and it will not compile. } I think it would be valuable to update boost::ref to match the standard version. On compilers which support variadic templates and rvalue references the code is obvious. Those which support one or neither could still have overloads for some number of arguments. This would be handy in a few places, notably boost::gil::for_each_pixel[2]. I know that boost::bind + reference wrapper could be used instead (boost::bind(boost::ref(f), 5)). Given that implementing operator() is relatively simple, and that the standard object based on boost::reference_wrapper has it (rather than requiring std::bind), I'd argue that this change is desirable. Thanks, Nate [1] http://en.cppreference.com/w/cpp/utility/functional/reference_wrapper/opera… [2]http://comments.gmane.org/gmane.comp.lang.c%2B%2B.isocpp.general/513

6 9

[gsoc2013] Proposal for Boost.Math Bernoulli numbers and special functions project
by Artemy Margaritov 02 May '13

02 May '13

Hi folks! I want to provide my proposal for Boost.Math Bernoulli numbers and special functions poject to the Boost community. Please, lets discuss it! I will be grateful for your advices. -- Best regards, Artemy Margaritov

2 6

[gsoc 2013] draft proposal for chrono::date
by Anurag Kalia 02 May '13

02 May '13

I have prepared a draft proposal for Boost.chrono/date implementation. Could you kindly go through it and tell me of any errors and suggestions? Regards, Anurag Kalia.

3 9

[Log] Plans to use std::thread?
by Rich E 01 May '13

01 May '13

Hi all, As I've been testing out the newly added Boost.Log library, I noticed it is relying on Boost.Thread even when the C++11 <thread> library is present. Are there any plans to allow the native <thread> library to be used when it is available? I think this can be done with Boost.Config's BOOST_NO_CXX11_HDR_THREAD macro. Thanks, Rich

2 2

[gsoc-13][proposal] Boost.uBLAS
by Aditya Avinash 01 May '13

01 May '13

Hi, I have a proposal for boost in gsoc-13 under boost.ublas *Proposal: SIMD abstraction for uBlas.* - I want to develop SIMD abstraction for uBlas. Goal 1: Develop the Intel SSE & AVX backend for SIMD abstraction in uBLAS. Goal 2: Develop AMD SSE backend for SIMD abstraction in uBLAS. Goal 3: Develop frontend for SIMD abstraction in C++. Goal 4: Joining of frontend and backend, so the the code is flexible to implement on both AMD and INTEL. Goal 5: Develop the ARM-NEON backend for SIMD abstraction in uBLAS. (if time permits). -- ---------------- Atluri Aditya Avinash, India.

2 3

Re: [boost] [gsoc-2013] Boost.Thread/ThreadPool project
by Niall Douglas 01 May '13

01 May '13

> Le 29/04/13 21:35, Niall Douglas a ?crit : > > No major changes to the C++11 futures API is needed. Rather that a > > different, but compatible, optimized implementation of future<> gets > > returned when used from a central asynchronous dispatcher. So the C++ > > standard remains in force, only the underlying implementation is more > > optimal. > > Could you explain me what a central asynchronous dispatcher is? An asynchronous procedure call implementation. Here's Microsoft's: http://msdn.microsoft.com/en-us/library/windows/desktop/ms681951(v=vs.85).as px. Here's QNX's: http://www.qnx.com/developers/articles/article_870_1.html. Boost.ASIO is the same thing for Boost and C++ but implemented by application code. It is *not* like asynchronous POSIX signals which are a nearly useless subset of APCs. > If not, please could you elaborate what kind of optimizations can be > obtained? If you have transactional memory in particular, you gain multi-CAS and the ability to (un)lock large ranges of CAS locks atomically, and a central dispatcher design can create batch lists of threading primitive operations and execute the batch at once as a transaction. Without TM, you really need the kernel to provide a batch syscall for threading primitives to see large performance gains. > > Futures come in because you'd naturally use std::packaged_task<> with > > Boost.ASIO. It returns a future. > Could you point me to the Networking paper proposal that has > packaged_task<> on its user interface. I would expect this to be an > implementation detail. You misunderstand me. *If* you want Boost.ASIO to dispatch unknown std::function<>, *then* std::packaged_task<> is the most obvious route forwards. And the correct way to pass a value from one execution context to another is std::future<>. This includes the single threaded case e.g. when going through a C++ -> C -> C++ transition as a stack unwinds. > > For reference, the AFSIO/AFIO project is *not* a threadpool. It's a batch > > asynchronous execution engine based on Boost.ASIO that lets you chain, in > > vast numbers, huge arrays of std::function<> whose returns are fetched using > > std::future<> to be executed asynchronously according to specified > > dependencies e.g. if A and B and C, then D, then E-G. That sort of thing. > So the thread pool you need is an internal one that is adapted to you > particular needs, isn't it? I think you don't understand what Boost.ASIO is or how it works. Boost.ASIO's core is boost::asio::io_service. That is its dispatcher implementation which each dispatch execution context being executed via boost::asio::io_service::run() which is effectively an event loop. Third parties then enqueue items to be dispatched using boost::asio::io_service::post(). You don't have to run Boost.ASIO using multiple threads: it can be single threaded. So is my thread pool an internal one adapted to my particular needs? In the sense I need not use threads at all, yes. In the sense that boost::asio::io_service's use scenario is inviolate, no. Boost.ASIO has its API, and you have to use it. And Boost.ASIO's API will be similar to the TR2 networking API. There is nothing stopping a person merging a Boost.ASIO managed thread pool with a traditional thread pool. I would struggle to see the use case though - this would an excellent thought project actually which would benefit any Boost.ThreadPool. > > One thing presently implemented on that engine is asynchronous file i/o, but > > in the next month or two you'll hopefully see batch parallel SHA256 using > > 4-SHA256 SSE2 and NEON implementations also added to the asynchronous > > engine. The idea is that the engine is fairly generic for anywhere where you > > do need to chain lots of coroutine type items together (not that it supports > > Boost.Coroutine yet). v1 isn't particularly generic nor optimal, but I'm > > hoping with feedback from Boost that v2 in a few years' time would be much > > improved. > > > As Oliver noted you could take a look at Boost.Fiber and Boost.Task. Right now anything Boost.Context based can't have multiple contexts simultaneously entering the kernel apart from on QNX and possibly Hurd. Therefore, for the time being, full fat threads are the only thing being considered. If kernel support ever includes coroutines or fibres, that will be eagerly added (I like coroutines, I use them a lot on Python). Note that on async i/o capable platforms multiple threads are solely used for non-async APIs like batch directory creation and batch chmod. Normal i/o gets multiplexed using completion handlers. Currently on Windows for example, threads are barely used at all. Niall --- Opinions expressed here are my own and do not necessarily represent those of BlackBerry Inc.

3 2