- Boost - lists.boost.org

Google SoC 2007 Big Integer project
by Marco 26 Mar '07

26 Mar '07

Ok, problably this is the N-th proposal that you read for the big integer project, with N large as you like :), and this isn't an upside for my application, anyway these are my ideas: (1) evaluate the need for a specific allocator because std::allocator doesn't provide a reallocate method, and growing allocated space could be a better policy than a create/destroy policy; (2) minimize useless object copy: where it's possible we'd have to adopt a move semantic technique as described in "http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1690.html#Library-… Move Solution" ; (3) use different algorithms according to the size of the numbers involved, the GMP library can be taken as an example and Knuth's TCP Vol 2 as a reference for the algorithms' implementation; (4) decide if we have to use exception handling C++ constructs for arithmetic exceptions ( divide by zero, etc) or simply abort the program; this is essentially a matter of performance; (5) implement ctors in order to inizialize a big integer from standard arithmetic type and obviously from a number represented by a string; implement conversion functions to arithmetic types and string types; (6) implement common arithmetic, shift, bitwise and comparison operators; using the boost::operator library would be usefull where this doesn't lead to a performance loss; (7) implement io stream operator; (8) basic functions: sign(), odd(), abs(), etc; numeric functions pow, sqrt, etc; algebric and combinatorial functions: factorial, gcd, etc.; there are a lot of functions we could implement : all depend on the avaible time; (9) decide if it's worth creating a specific class unsigned big integer; (10) about fixed size big integer I had tought to something like this: template< unsigned int N > class big_int; where N are the number of bits which have to be used; (11) make all that working on the larger number of architectures; write down library documentation, implement correctness and performance tests; (12) it would be nice to support infinity and indefinite forms, but it could mean performance problems because we'd have to evaluate all possible cases, maybe it will be better realize a specific wrapper/adaptor class for such a goal, moreover this class adaptor could be used also for standard integral type; Question : is it possible to get good performance without implement the basic algorithms in assembler ? Comments and critiques to my ideas are welcome. Thanks Marco -- Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

8 19

Re: [boost] [SoC 2007] the Web Crawler Library
by Yang Lang 26 Mar '07

26 Mar '07

Mathias Gaunard wrote: >How is it required? >I think asynchronous I/O with a pool of threads should be the most >efficient solution. I think pool of threads is a way of multithreading. I have mentioned above are only rough ideas. Thanks for you advise, I think pool of threads is a good idea ^^

1 0

[Report] 79 regressions on RC_1_34_0 (2007-03-22)
by Douglas Gregor 26 Mar '07

26 Mar '07

Boost Regression test failures Report time: 2007-03-22T00:20:02Z This report lists all regression test failures on release platforms. Detailed report: http://engineering.meta-comm.com/boost-regression/CVS-RC_1_34_0/developer/i… 79 failures in 4 libraries iostreams (6) optional (6) parameter (1) python (66) |iostreams| bzip2_test: msvc-7.1 msvc-8.0 gzip_test: msvc-7.1 msvc-8.0 zlib_test: msvc-7.1 msvc-8.0 |optional| optional_test: msvc-6.5 msvc-6.5 msvc-6.5_stlport4 msvc-7.0 optional_test_ref_fail2: msvc-7.1 msvc-8.0 |parameter| python_test: gcc-cygwin-3.4.4 |python| bases: gcc-4.1.1_sunos_i86pc builtin_converters: gcc-3.4.5_linux gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 crossmod_exception: gcc-3.2.3_linux gcc-3.3.6_linux gcc-3.4.5_linux gcc-3.4.5_linux_x86_64 gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 intel-linux-9.0 crossmod_opaque: gcc-3.2.3_linux gcc-3.3.6_linux gcc-3.4.5_linux gcc-3.4.5_linux_x86_64 gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 intel-linux-9.0 exec: gcc-4.1.1_sunos_i86pc exec-dynamic: gcc-3.4.5_linux gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 gcc-4.1.1_sunos_i86pc import_: cw-9.4 gcc-4.1.0_linux_x86_64 gcc-mingw-3.4.2 gcc-mingw-3.4.5 intel-vc71-win-9.1 msvc-6.5 msvc-6.5 msvc-6.5_stlport4 msvc-7.0 msvc-7.1 msvc-7.1 msvc-7.1 msvc-7.1_stlport4 msvc-8.0 msvc-8.0 msvc-8.0 iterator: gcc-3.2.3_linux gcc-3.3.6_linux gcc-3.4.5_linux gcc-3.4.5_linux_x86_64 gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 intel-linux-9.0 map_indexing_suite: gcc-3.4.5_linux gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 pointee: gcc-4.1.1_sunos_i86pc pointer_type_id_test: gcc-4.1.1_sunos_i86pc try: gcc-3.2.3_linux gcc-3.3.6_linux gcc-3.4.5_linux gcc-3.4.5_linux_x86_64 gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 intel-linux-9.0 upcast: gcc-4.1.1_sunos_i86pc

13 24

Re: [boost] Boost.Threads, N2178, N2184, et al
by Emil Dotchevski 26 Mar '07

26 Mar '07

> Note that simply allowing pthread_cancel to throw an exception doesn't > make C and C++ cancellation portably interoperable. So we've still > got a problem there. Indeed maybe even a bigger one: fclose is > allowed to throw! :-\To me as a programmer, what fread is allowed to do when you cancel its thread is of little importance, provided that things don't collapse when a cancellation crosses the C/C++ language barrier.So let's assume for a moment that this is what we want to achieve. What is the solution, then?Emil Dotchevski _________________________________________________________________ It’s tax season, make sure to follow these few simple tips http://articles.moneycentral.msn.com/Taxes/PreparationTips/PreparationTips.…

1 0

[Soc 07] BigInt Alternate Projects -- SOC BigInt applicants please read!
by Jeff Garland 26 Mar '07

26 Mar '07

Hi All - We've had a ton of BigInt (I'd guess ~40) proposals for SoC. This is really unfortunate because some good students are going to get left out -- we're only going to accept one. We've already been warning folks, but to help just a bit more, I've come up with a couple of alternatives that are closely related to BigInt, but a bit different. This way we might improve things just a bit. So, everyone that's applied for BigInt that might be interested in doing one of these other 2 projects, please do the following: a) make a comment on your application that indicates you are interested in doing one of these others b) or, send an email to soc_mentors2007-at-crystalclearsoftware.com indicating this fact c) Write a new proposal before the deadline Obviously C is the best, but I realize time is short before the deadline -- and I know the Google server has been timing out, so I'm trying to make this as fair as possible. If your application is sketchier, we'll understand because it's short notice and we will work with the leading candidates after the deadline to refine the application. If you really prefer to do one of the new projects feel free to withdraw your BigInt application. However, if you leave it we will continue to consider that your first choice unless you indicate otherwise. Below is the text I've added to the Wiki. Thx, Jeff --------------------------- Safe Integer Introduction: Implement 'safe int' class template which supports all C++ arithmetic and boolean operators and will ensure client notification on all failures such as arithmetic overflow and underflow. Goal: Platform independent code, docs and tests to Boost need to be delivered -- review within SoC? period would be a plus (only if you think it's doable). Requirements: Basic knowledge of C++ templates and a good understanding of limits of computer computation systems. Extreme ability to focus on details. Notes: The target here is to applications that are highlh David LeBlanc? at Microsoft created something similar a couple years back. See http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dncode/htm… SafeInt and suggest might be combined with existing Boost code from date_time call constrained_value. this would allow you to define constrained range safe integers like this: typedef SafeInt?<int, 0, 255> BufRange?; char buf[BufRange?::max()+1]; BufRange? i = 254; i++; //ok i++; //out of range exception //now it's impossible for this to be out of range: if (buf[i] == ... --------------------------- Fixed Decimal Introduction: Fixed Decimal types provide an alternative to floating point types that are superior in their calculation properties. Robert Klarer of IBM has proposed adding these types to C++ [in n2198 (pdf)] and prior papers. This work is now on track to be included in C++0x. Robert has an implementation of these types with a restrained license. This project involves implementing the n2198 interfaces in a Boost library. Goal: Platform independent code, docs and tests to Boost need to be delivered with as much of 2198 as possible. Requirements: Basic knowledge of C++ templates and a good understanding of limits of computer computation systems. Extreme ability to focus on details. Notes: This project clearly involves much less 'interface design' since the interface is already defined. However there is still tricky design work to implement these types correctly. Some research on the best approaches might be required.

2 1

[futures] future producer/consumer streams and prior art
by Braddock Gaskill 25 Mar '07

25 Mar '07

I don't really know where the 'future' concept came from (maybe someone does?), but I've been looking at some old parallel programming papers, and was surprised to find the concept of a "single-assignment variable" in a 1996 paper by Ian Foster entitled "Compositional Parallel Programming Languages", which in turn credited the concept to a 1982 "Data flow languages" paper by W. Ackerman. Single assignment variables are essentially the futures concept. Most interesting was a description of a very neat producer/consumer idiom using these "single-assignment variables" in an academic parallel language. I have implemented and tested this idiom in C++ using futures and shared_ptrs below (uses my futures implementation, which is pretty generic). It is essentially a "future stream" concept, where a linked list of futures is constructed and then eaten by the producer and consumer respectively. Is this new, or old hat? Either way, I'll be adding "future_stream" templates to my implementation! Braddock Gaskill Dockside Vision Inc // define my "future stream" int types...make pretty templates someday struct stream_item; typedef shared_ptr<stream_item> stream_item_p; typedef future<stream_item_p> future_stream; typedef promise<stream_item_p> promised_stream; struct stream_item { stream_item(int v, promised_stream p) : value(v), next(p) {} int value; future_stream next; }; // produces 24 int values, 0 - 23 void producer(promised_stream cur) { promised_stream next; for (int i=0; i<24; ++i) { next = promised_stream(); cur.set(stream_item_p(new stream_item(i, next))); cur = next; } cur.set(stream_item_p()); //set a null next to terminate } // consumes values and sums them until the stream ends int consumer(future_stream stream) { int accum=0; while (stream.get()) { accum += stream.get()->value; stream = stream.get()->next; } return accum; } void TestCase13() { //producer/consumer list of futures promised_stream stream; // launch producer boost::thread t(boost::bind(producer, stream)); int accum = consumer(stream); BOOST_CHECK_EQUAL(accum, 276); t.join(); }

1 0

Re: [boost] Boost.Threads, N2178, N2184, et al
by Sohail Somani 25 Mar '07

25 Mar '07

RAII? If the response is "API on top of pthreads" then why discuss pthreads at all? -----Original Message----- From: boost-bounces(a)lists.boost.org on behalf of Emil Dotchevski Sent: Sat 3/24/2007 12:07 PM To: boost(a)lists.boost.org Subject: Re: [boost] Boost.Threads, N2178, N2184, et al But let's turn things over: why not use pthread instead of creating another API? I think it is clear that using pthreads has a few advantages. What is the drawback?

5 15

[Boost-bugs] [ boost-Patches-1688009 ] boost::graph::graph_utility.hpp is_connected() bad call
by SourceForge.net 25 Mar '07

25 Mar '07

Patches item #1688009, was opened at 2007-03-25 14:20 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1688009&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: None Group: None Status: Open Resolution: None Priority: 5 Private: No Submitted By: Nobody/Anonymous (nobody) Assigned to: Nobody/Anonymous (nobody) Summary: boost::graph::graph_utility.hpp is_connected() bad call Initial Comment: The function is_connected() makes an incomplete call to is_reachable(). It simply doesn't pass the graph object. Patch file attached. btstadle(a)uncg.edu ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=307586&aid=1688009&group_… ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys-and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

Re: [boost] Boost.Threads, N2178, N2184, et al
by Emil Dotchevski 25 Mar '07

25 Mar '07

> > If all of your code is in C++, you'd know not to call pthead_cancel because> > it won't work. That would be no problem because you can work at the C++> > <thread> level where everything is nice and cool -- but what if a 3rd party> > library built on <pthread> calls pthread_cancel?> > Then it would be a very bad library. A library should either create its > own threads and then it is the responsible to join/detach/cancel it, or > it works with thread created by the application and then shouldn't do > any of those things. Just as Howard's example with > malloc/free/new/delete - what happens if I pass a pointer created with > new to a library which tries to deallocate it using free? Bad things > happen. I shouldn't do it, and more than that, such a library, that > tries to free a pointer not allocated by it, is not a good friend of mine. The malloc/free/new/delete reference is not appropriate: I wasn't saying that someone would pthread_cancel a thread created using the C++ <thread> interface. The C library creates threads, the C library cancels them; the question is, what happens when the C library cancels a thread it created, which happens to be running C++ code at the time? Emil Dotchevski _________________________________________________________________ It’s tax season, make sure to follow these few simple tips http://articles.moneycentral.msn.com/Taxes/PreparationTips/PreparationTips.…

1 0

Re: [boost] Boost.Threads, N2178, N2184, et al
by Emil Dotchevski 25 Mar '07

25 Mar '07

> >> <snip> > >> The fact that pthreads exist is completely irrelevant. We setup a C++> >> standard, and it should be as good as it gets. The POSIX model is good,> >> so we take it. The POSIX syntax is not so good (for C++, obviously) so> >> we don't take it.> > > > What follows then, is that you would like existing pthread C libraries to > > continue to be non-portable. I don't see why. I might be blind, but I don't > > see why would that be desirable.> > I never said that. If the C standard committee decides to fully adopt > pthreads, I'd be fine with it. And if the C++ standard committee decides > to be backwards compatible with C, and also adopt pthreads, I'd be fine > with that too. I just don't think it should come instead of "the best" > C++ interface, which is what I care about most. If pthreads becomes part of C or C++ in its current form, what you'll get is that I can write C++ code on pthreads, or C code on pthreads, and it'll work. You will not be able to respond in C++ to a pthread_cancel, because pthread is a C standard and therefore doesn't specify that pthread_cancel throws. If all of your code is in C++, you'd know not to call pthead_cancel because it won't work. That would be no problem because you can work at the C++ <thread> level where everything is nice and cool -- but what if a 3rd party library built on <pthread> calls pthread_cancel? Even today, on non-windows platforms where pthread is standard, we have this problem. So this discussion is not about adopting pthreads. It's about adopting an extended pthread interface, which specifically deals with C/C++ interoperability. It is because this issue affects both the C and the C++ community that we can not simply say "we'll leave it up to the others to figure out." > > <snip> > > While strictly speaking I do not *need* to use existing C libraries in my > > C++ code, I *want* to be able to. And I mean this in general, not just for > > threading libraries.> > Ok, so we come again to what seems to be the true heart of the debate. > Do we want interoperability between the C library and the C++ library, > and how much are we willing to pay for it. And it seems we give > different answers to this question. I'm sure you're familiar with the zlib library. It's free, and if it does what you need, would you rather use it as-is, or would you "port" it to C++? _________________________________________________________________ Your friends are close to you. Keep them that way. http://spaces.live.com/signup.aspx

3 2