- Boost - lists.preview.boost.org

[GSoC 2013] Boost.Math Bernoulli Numbers and Applications to Special Functions
by Łukasz Marecik 30 Apr '13

30 Apr '13

Hi, My name is Lukasz Marecik, I am fifth year student of Mathematics and fourth year student of Computer Science at Warsaw University. I would like to apply to Google Summer of Code 2013 project. I am interested in Bernoulli Numbers and their applications. While thinking about this project and doing some research, I collected some questions and issues, which I would like to discuss with my (potential) mentors. The answers can have strong influence at my official proposal. 1. Is (one of) the goal of this project to implement FROM SCRATCH completely new boost library, which will calculate Bernoulli Numbers ? I have already found two great C++ open-source programs: - http://www.bernoulli.org/ - http://web.maths.unsw.edu.au/~davidharvey/papers/bernmm/ They are already extremely efficient and fast (the funny thing is that they use completely different approach). Can boost project include and adapt one of them ? Why not ? 2. Are we going to implement only precise calculation of Bernoulli numbers or also Bernoulli numbers modulo p (where p is prime) ? 3. How the implementation of method of computing Bernoulli numbers will look like? Will it be a big template which works with all (reasonable) types (built-in, multiprecision) in the same way ? I was thinking for a while about this and I think it would be better to implement separately computing rational Bernoulli numbers (e.g. gmp_rational type) in a modern way: compute B_n modulo a lot of small primes and then reconstruct B_n via Chinese Remainder Theorem. This algorithm is one of the faster for this concrete type: precise rational numbers, but (in my opinion) it will be inefficient, when we want the output be built-in types. I do not know if I express precise what I want. For example: naive Akiyama–Tanigawa algorithm does not assume the type of output: the calculation can be performed at any type. Will our library work with all types in the same manner, or will our library run different algorithms and choose which one is better in this concrete case ? 4. Do I need to make my own research, reads papers about Bernoulli numbers, find the best practical algorithm and then propose it to my mentor or my mentor will help me to find and choose algorithm ? (so: Can I rely on myself only ?). Until now I have found three interesting approach: - use Chinese Remainder Theorem (described above) - use Euler's formula and the zeta-function algorithm - use completely new subquadratic algorithm (the paper was "submitted to publication", but it was not published in magazine until now ; it is online) The first two of them all already implemented and work (I think) in O(n^(2+eps)) time (it is good to mention that we need \theta(n log n) bits to represent precise number). The third one had (asymptotically) better complexity, but it goes throw a lot of complicated Maths, p-adic numbers etc and it has been not implemented yet - so it can turn out that the constant hidden in Big O notation is so big, that it is unpractical. But who knows. Do I need to discuss in my proposal different approach ? 5. Do I need to include in my proposal some words about applications to boost function: - theoretical view: where bernoulli numbers appear - practical view: how those functions are implemented now and how there will be implemented - and why they will be better ? I am sorry, that I am writing so late, but I was not sure for a long time if I want to apply ; I hope I finish my proposal in time. Kind regards, Lukasz Marecik

2 1

[type_traits] boost::decay vs std::decay
by Agustín K-ballo Bergé 30 Apr '13

30 Apr '13

Hello, It has been pointed out before that `boost::decay` and `std::decay` are not exactly the same. The standard does remove CV qualifiers while boost doesn't. See https://svn.boost.org/trac/boost/ticket/7760 I would like to know if there is a resolution on this issue. If the difference is intentional, then I suggest a note be added to the documentation. I could prepare a patch either way. Regards, -- Agustín K-ballo Bergé.- http://talesofcpp.fusionfenix.com

1 0

GAL (Generic Audio Library) based on GIL
by Brendon Costa 30 Apr '13

30 Apr '13

I am looking into the possibility of developing a library based on the same concepts and a similar interface to Boost.GIL call Boost.GAL. The idea is simply to define something very similar to GIL but for audio processing instead of image processing. Most of the concepts in GIL map almost 1 to 1 to audio processing as well. What are peoples thoughts on such a project? Is there anything in Boost.GIL that we have learn't from that should be done differently? --- Basic Premise --- The base concepts for GAL are described below and shown are the direct equivalents in the GIL library: * GAL.Sample ~= GIL.Channel Represents the amplitude of a single audio sample (float32, int16, ...) * GAL.SampleTime ~= GIL.Point Identifies the "time" a sample was taken (in units of the SampleRate) * GAL.Channel ~= GIL.Colour Identifies an audio channel location (FRONT_LEFT, or FRONT_RIGHT might be a channel for example) * GAL.ChannelMapping ~= GIL.Colour-space Maps channels to specific layout in memory (offset 0 is FRONT_LEFT, ...) * GAL.Frame ~= GIL.Pixel Identifies a single time slice (multiple channels for single sample point in time) * GAL.Block ~= GIL.Image Identifies a 1D sequence of Frame's * GAL.SampleRate ~= GIL.PPI I don't think GIL has this concept at the moment, but would be similar to Pixels Per Inch in the image world * GAL.Layout ~= GIL.?? This is the same in GIL and GAL the memory layout can be interleaved or not (planar for GIL) * GAL.Format ~= GIL.?? I don't think GIL has this concept at the moment but it represents the format of data without actually storing any data. It contains: - Sample type - ChannelMapping (implicitly identifies count of channels) - SampleRate - Layout

4 6

[Boost.FixedPoint] Choose notation
by Dmitriy Gorbel 30 Apr '13

30 Apr '13

Hello, community! I propose extending the Boost Libraries to provide binary fixed-point arithmetic, within GSOC project. Fixed-point library will provide nonnegative and negatable class templates for fractional arithmetic, and cardinal and integral for integer arithmetic. In total, four class templates. Fixed-point arithmetic use more than one notation, and I want to provide several notation to make happy all. Now I plan to implement two notations - Q notation and notation from C++1y proposal. Examples: C++1y proposal notation: cardinal<16> 0 <= n < 65536 integral<4> -16 < n < 16 nonnegative<8,-4> 0 <= n < 256 in increments of 2^-4 = 1/16 negatable<16,-8> -65536 < n < 65536 in increments of 2^-8 = 1/256 Q notation: cardinal<16> 0 <= n < 65536 integral<4> -16 < n < 16 nonnegative<8, 4> 0 <= n < 256 has 4 bit for fractional part negatable<16, 8> -65536 < n < 65536 has 8 bit for fractional part Please, help me to choose default notation, propose other notation, or just make any feedback. Sincerely, Dmitriy. -- View this message in context: http://boost.2283326.n4.nabble.com/Boost-FixedPoint-Choose-notation-tp46462… Sent from the Boost - Dev mailing list archive at Nabble.com.

8 16

[GSoC 2013] Moving to Boost to Boost.Move
by Vicente J. Botet Escriba 30 Apr '13

30 Apr '13

Hi, In case there are some students that are looking for a last idea. There a re a lot of Boost libraries that don't support move semantics. It would be nice if one student propose to adapt the some of the existing libraries. The idea is to use Boost.Move so that an emulation is provided for compilers not supporting rvalue references. Some of the libraries (let me know if I'm wrong are). My priority is given between [], lower numbers means higher priority. Of course others would have others priorities: C++11 * [0] Tuple or * Fusion/tuple (it seems that it support or will support c++11 move semantics but don't use Boost.Move) * [0] Bind * [1] Function * [2] SmartPtr * [8] Array ? Accepted for C++14 * [5] optional Having an active proposal for C++1y * [3] Heaps * [6] Any * [7] Variant Other * [4] LockFree * [9] Parameters * [10] Signals? Please help me to complete this list. Adding constexpre and noexcept would be welcome also. Best, Vicente

3 4

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

30 Apr '13

> > There are many ways systemically of implementing futures. The way you > > and Anthony have taken to date is a non-intrusive approach such that > > futures stand alone. This is great for not forcing design onto third > > parties and is a decentralised POSIX-y approach, but it comes with > > significant performance and memory costs because it's hard to get > > standalone, non-intrusive futures to batch themselves without > > sacrificing performance. > > I have no merit here. This is the approach the standard has defined futures. 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. > > An alternative approach is to assume a central dispatcher/event loop > > which can optimize then() chaining because it knows of all futures and > > their relationships currently in flight (this is a much more > > centralized statist NT-y approach, and it you can see that philosophy > > clearly in Microsoft's N3428). You can see an example of this approach > > to implementing future chaining with multiple dependencies which > > extends Boost.ASIO in > > https://github.com/ned14/TripleGit/blob/master/triplegit/include/async > > _file_ io.hpp#L785. I also went ahead and implemented N3428's > > when_all() which returns a future chained to multiple input futures, > > not that I claim the implementation mature yet. > > I don't know ASIO enough to understand the advantages or liabilities. > While a central dispatcher/event loop could be useful for some applications > other need more concurrency. > I'll need to take a deep look at ASIO when I would have enough time. I know you'll have studied Microsoft's N3428 in depth. Their proposal is quite trivial to implement when you have an NT kernel to hand where the kernel directly manages all multithreading primitives and there is a top quality APC implementation. Implementing N3428 without a NT kernel to hand is very considerably harder, indeed there are many, many gotchas as I know you know. Even then() is tricky, because code called from then() needs two main call forms, asynchronous and synchronous (i.e. the original object completes only after type B then() completes, whereas type A then() lets the original complete first). Not introducing race conditions is quite hard (for me at least). > > My concern with Boost.ThreadPool right now is that it could get in the > > way of the latter approach. I have zero objection to a formulation > > which embraces both approaches, but when you ask why a thread pool > > isn't in the standard, I think it's because until we've fixed futures > > implementation and all the composibility and chaining we're sure we > > need, and made sure that interops smoothly with the forthcoming TR2 > > networking proposal, then and only then is it wise to proceed with > > threadpool design. > > I'm not aware of the TR2 networking proposal needs respect to futures or > thread pool. Again I'll take a look to the current proposals. Futures come in because you'd naturally use std::packaged_task<> with Boost.ASIO. It returns a future. > > All that said, this is purely a cautious opinion of mine. You're one > > of the Boost.Thread maintainers, so I happily defer to your judgment > > on this. If you think we need a threadpool now, you'll find no > > opposition from me. > > If IIUC you are not suggesting that the student uses the ASIO approach, but that > it is not time to solve the thread_pool now. Could you confirm? > If yes, could you tell me what is blocking that we can not try to solve? We ought to finish N3428 for pure POSIX first. During implementation, you will find many areas where significant optimization using a central dispatcher become possible. Specialisations of N3428 for some arbitrary central dispatcher might be worth prototyping as a thought exercise. After that I see no reason to hesitate on thread_pool as it now has the type inferences available to it to have an optimal design. > I was not aware that there was a AFSIO GSoC project as described here > https://svn.boost.org/trac/boost/wiki/SoC2013#Boost.ASIO and that this > project propose also thread pool. I understand better now your concerns. I hadn't announced it to this list for various reasons. Hopefully I'll have news there soon. 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. 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. Niall --- Opinions expressed here are my own and do not necessarily represent those of BlackBerry Inc.

3 2

[iterator] Is there general const_iterator adaptor?
by TONGARI 30 Apr '13

30 Apr '13

Hi folks, I wonder if there's a general const_iterator adaptor that transforms any iterator to a const one: template<class Iterator> struct const_iterator : iterator_adaptor < const_iterator<Iterator>, Iterator , typename iterator_value<Iterator>::type const > { const_iterator() {} const_iterator(Iterator const& base) : const_iterator::iterator_adaptor_(base) {} }; Which is simple but handy for use in that we don't have to make 2 versions for both const & non-const iterators each time we make a container. Does Boost offer this which I missed somewhere, or would you think it's a good idea to add? Thanks

3 5

GSOC 2013
by Razvan Florea 29 Apr '13

29 Apr '13

Hello, I'm a student interested in working on odeint project this summer in GSOC. In the last weeks I spoke with Mario Mulansky about my ideas. After he gave me a task in order to accustom with odeint project, I started building my proposal. He suggested me to put my first version of proposal on the mailing list to get feedback or some advice about what should I change. Is this the right mailing list to share my proposal? If yes, how should I share my proposal with you? Should I put on melange or can I put it on a google doc and give you a link to it? Have a nice day, Razvan

3 3

Re: [boost] hi
by dominic ibeme 29 Apr '13

29 Apr '13

http://expecthead.com/wp-content/plugins/wp-plugin-repo-stats/china.php?ygf… \\\\\\ The improver of knowledge absolutely refuses to acknowledge authority, as such. For him, skepticism is the highest of duties, blind faith the one unpardonable sin. -- Thomas Huxley (1866)

1 0

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

29 Apr '13

> > I'm not ruling out the merit of a Boost.Thread threadpool. For me > > personally though, the hurdle is very significantly raised: you need > > to strongly prove to me why your proposed thread pool is much superior > > to a Boost.ASIO based threadpool. Otherwise I will zero score the GSoC > > proposal, because in the end we need other proposed projects more. > This is your right, but I don't know how the fact you can write easily the thread > pool you need to diminish a generic thread pool working well with futures. > [snip] > Hopping this helps you to understand the project I'm looking for. There are many ways systemically of implementing futures. The way you and Anthony have taken to date is a non-intrusive approach such that futures stand alone. This is great for not forcing design onto third parties and is a decentralised POSIX-y approach, but it comes with significant performance and memory costs because it's hard to get standalone, non-intrusive futures to batch themselves without sacrificing performance. An alternative approach is to assume a central dispatcher/event loop which can optimize then() chaining because it knows of all futures and their relationships currently in flight (this is a much more centralized statist NT-y approach, and it you can see that philosophy clearly in Microsoft's N3428). You can see an example of this approach to implementing future chaining with multiple dependencies which extends Boost.ASIO in https://github.com/ned14/TripleGit/blob/master/triplegit/include/async_file_ io.hpp#L785. I also went ahead and implemented N3428's when_all() which returns a future chained to multiple input futures, not that I claim the implementation mature yet. My concern with Boost.ThreadPool right now is that it could get in the way of the latter approach. I have zero objection to a formulation which embraces both approaches, but when you ask why a thread pool isn't in the standard, I think it's because until we've fixed futures implementation and all the composibility and chaining we're sure we need, and made sure that interops smoothly with the forthcoming TR2 networking proposal, then and only then is it wise to proceed with threadpool design. All that said, this is purely a cautious opinion of mine. You're one of the Boost.Thread maintainers, so I happily defer to your judgment on this. If you think we need a threadpool now, you'll find no opposition from me. Niall --- Opinions expressed here are my own and do not necessarily represent those of BlackBerry Inc.

3 2