- Boost - lists.boost.org

Re: [boost] Algebraic abstractions related to (big) integers in C++
by Brent Spillner 29 Mar '11

29 Mar '11

On 3/27/11 00:21 Thomas Klimpel wrote: >The goal of this message is to reflect on the two's complement representation of negative integers, from a relatively abstract algebraic perspective. I suspect that practical arguments may resonate more deeply with this list than theoretical ones. Indeed, from a theoretical point of view it's trivial to convert operations on a sign bit + N-1 magnitude bit representation to/from operations on the N-bit 2's complement representation, and in fact there is one value representable in the two's complement representation that is not in the sign/magnitude representation of the same length, which seems like a (very minor) theoretical win for 2's complement. If the operands are the same size (even if that spans multiple machine words), I think 2's complement is clearly preferable to take advantage of the hardware instruction set. With the exception of the overflow flag, addition, subtraction, and the low-order result of a multiplication yield the same bitstring whether the operands (and result) are taken to be 2's complement or unsigned, which means that you can perform arithmetic on lower-order word-size chunks of a large integer without caring whether the highest-order chunk is positive or negative. Might as well take advantage of the instruction-level building blocks for 2's complement representation (with appropriate overflow, carry-in, etc. options) in this case. If you might be adding or subtracting large integers of different length, the sign-magnitude representation is arguably simpler than sign-extending the smaller operand (and potentially propagating carry-outs up to the highest-order chunk of the result.) This then lets you choose to represent negative numbers in the smallest possible number of words without worrying about an arithmetic performance tradeoff. On the other hand, multiword sign-magnitude arithmetic requires two code paths for every operation, with an initial test-and-branch to determine whether all your ADDs should be replaced by SUBs. And given that 2's complement seems preferable for fixed-width arithmetic, I think I'd want a library supporting both fixed- and variable-width representations to adopt the same convention for both. >"What I consider especially strange from an algebraic point of view, is to automatically promote a signed integer type to its corresponding unsigned integer type, when >an arithmetic expression contains both signed and unsigned integer types. Shouldn't it be the other way round? Or wouldn't it be even better, if there would be no >automatic conversion at all? At least from an algebraic point of view, any natural number is also an integer, not vice versa like in C." To be precise, this happens only when the rank of the unsigned type is greater than or equal to that of the signed type. In the case where both operands have non-negative values, this minimizes the risk of overflow during addition or multiplication. When performing an operation on a unsigned value and a signed value (or subtracting a unsigned value from a signed positive value of lesser magnitude), it is incumbent upon the programmer to have some notion of what he or she is doing. I believe the rationale may be that signed values are the default, so if you went out of your way to declare something as unsigned then you're accepting some responsibility for using it appropriately. Note also that (at least in ANSI C) when performing arithmetic between an unsigned value and a signed value of higher rank, the promotion is to the signed type--- so the "promote to the 'larger' type" principle is consistently applied across the board, particularly if you consider unsigned types "larger" than the signed equivalent (seems reasonable to me given how uncommon negative values are in most integer code.)

4 3

[context review] Updated vote
by Giovanni Piero Deretta 29 Mar '11

29 Mar '11

Hi all, There is a lack of reviews so far and the review deadline is getting close; as I really, really would like to see a context switching library into boost in one way or another, I would like to change my vote from a negative to conditional acceptance. These are the conditions: - A C (or low level), light weight API is publicly exposed and documented - Context is made movable, without additional memory allocation for non legacy (i.e. ucontext) implementations. - The documentation is polished and expanded with a discussion on context switching and use cases. I do not think these points are particularly contentious as Oliver has already stated that at least the first two is in his TODO list and that he will make context movable. Of course I would like Oliver to address the other points raised by me and others reviewers. I also encourage Oliver to engage more in discussions with the reviewers; the mail threads just died off after a few replies and not all issues raised were discussed. -- gpd

3 4

[context review] Review ends tomorrow Mars 30st 2011
by Vicente BOTET 29 Mar '11

29 Mar '11

Hi all, The review of Oliver Kowalke Context library ends tomorrow Mars 30th. If you have taken already a look at the library, please make a review even if you can do only a short one. Let me know if you think you need more time to do a deeper review, so I can see with Oliver and the review wizards if we can extend the library. Best regards, Vicente Review Manager Boost.Context is a basic building block library that is used for more higher abstractions. It is used by Boost.Fiber, Boost.Tasklet and Boost.Task from the same author. I really hope to see your vote and your participation in the discussions on the Boost DEVELOPMENT mailing lists! WARNING !!!!!!!!!!!!! Only on the Boost DEVELOPMENT mailing lists Please use [context review] as prefix of your post to make easier the review follow up. You can download a frozen version for the review from the Vault, TinyURL: http://tinyurl.com/5r77rel or The documentation is available directly here: http://ok73.ok.funpic.de/boost/libs/context/doc/html/ --------------------------------------------------- About the library: Boost.Context provides a possibility to switch between different user-level context and is intended to be the basis for a higher abstraction like coroutine and fiber. A user-level context represents the current execution state, including all registers and CPU flags, the instruction pointer, the stack pointer. boost::context encapsulates such a user-level context and is able to store/restore its associated user-level context. This allows multiple execution paths running on a single thread using a sort of cooperative scheduling (in contrast a thread is preemptively scheduled) - the running boost::context decides explicitly when its yields to allow another boost::context to run (user-level context switching). A context can only run on a single thread at any point in time but may be migrated between thread. A context switch between threads costs usually thousands of CPU cycles on x86 compared to a user-level context switch with few hundreds of cycles. Boost.Context differes to setjmp()/longjmp() in the fact that the C99 standard does not require that longjmp() preserves the current stack frame, e. g. jumping into a function which was exited via a call to longjmp() is undefined. Boost.Context allows to select the mechanism provided by the operating system (ucontext on UNIX, Windows Fibers on Windows) or a faster implementation provided by this library (fcontext using assembler). --------------------------------------------------- Please always state in your review, whether you think the library should be accepted as a Boost library! Additionally please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain?

1 0

[GSOC] Thoughts about a metaheuristic library
by Murilo Adriano Vasconcelos 29 Mar '11

29 Mar '11

Hi, I'm thinking about proposing a library of genetic algorithms for this GSOC and wondered what the community thinks about it. The main idea is to provide a in extensible set of classes that a user can easily implement a GA without difficulty. /* Individual with double as fitness fuction type * An individual is a possible solution for the problem * In this case, bit_individual can be a class with boost::array<bool> * and some more information like the fitness function type * and an interface for basic things like sorting the population */ typedef bit_individual<double> individual_d; // Fitness function: evaluates a solution double fitness_func(const individual_d& ind) { double value = 0.0; // calc the fitness of ind return value; } // Fitness evaluator fitness_function fitness(fitness_func); // A population is a set of solutions population<individual_d> pop; // We can for example initialize the poulation with // some size passing a random number generator (rng) initialize_random_population(pop, SIZE, rng); // The tournament selector: chooses T_SIZE elements from population // and selects the one with greater fitness tournament_selector<individual_d> selector(T_SIZE); // roullete_selector<individual_d> ... // This specifies the mutation rate of each bit of each individual bit_mutation<individual_d> mutator(RATE); // Crossover in bit_crossover<individual_d> cross; // 1-point crossover // bit_crossover<individual_d> cross(n) : n-point crossover // When the algorithm will stop: in this case, number of generations generation_continuator<individual_d> continuator(MAX_GEN); // can be fitness_continuator<individual_d> cont(val) : continues until the best fitness is less than val // Genetic Algorithm functor ga<individual_d> algo(selector, cross, CROSS_RATE, mutator, fitness, continuator); // Run the GA taking pop as initial population algo(pop); // Gets the best element from the population individual_d best_element = pop.best_element(); // Prints the fitness of the best element std::cout << best_element.fitness() << std::endl; For this basic example, the user only have to choose the parameters (like selector, crossover, continuator, ...) and provide a fitness function with the problem specific rating for an individual. This library can be extended to cover more metaheuristics and be parallelized with Boost.MPI. Ideas about the design and other thinks are also welcome. Regards, -- Murilo Adriano Vasconcelos http://murilo.wordpress.com

3 3

lexical_cast crashing on solaris
by boostman 29 Mar '11

29 Mar '11

Hi Boost Experts Below is the code that is causing crash on solaris: entity::VecObj getData(const message::Message & msg) { entity::VecObj odfs; util::MyString keyStr; keyStr = _T("Test msg"); for(size_t i=2; msg.hasKey(keyStr) ; ++i) { util::MyString mdfAlias = msg.value(keyStr); entity::VecObj ret = storage::byAlias(mdfAlias); if(ret.size()) odfs.push_back(ret[0]); keyStr = _T("Test msg") + util::convert(util::getString(i)) + _T("]"); } if(!odfs.size()) throw util::Exception(util::ERROR_MDFNOTFOUND, util::ERROR_MDFNOTFOUND_STR); return odfs; } template std::string getString(const T & val) { std::string res(""); try { res = boost::lexical_cast(val); } catch(bad_lexical_cast &) { } return res; } Below is the stack trace corresponding to it. ----------------- lwp# 248 / thread# 248 -------------------- fd5c6d10 waitid (0, 4b5d, fa2faf40, 3) fd5b9a34 waitpid (4b5d, 0, 0, 0, 1c800, fd5f3580) + 60 000c76e4 void handleSignal(int) (b, 35d4, fa2fb208, fd5f4604, fd5f3580, 4b5d) + 114 fd5c5924 __sighndlr (b, 0, fa2fb208, c75d0, 0, 0) + c fd5ba868 call_user_handler (b, 0, 12, 0, fc395000, fa2fb208) + 3b8 fd3df5d4 void std::ios::init(std::streambuf *) (fa2fb738, 0, 45, fab18, 3, fd4e30a8) + a8 fd3dfce0 std::ios::basic_ios #Nvariant 1() (fa2fb738, fd4e52b8, 103408, 0, fd4e30a8, 348) + 44 fd467648 std::stringstream::basic_stringstream(int) (fa2fb6c8, c, 1e4, fa2fb738, fd4e800c, fd4e30a8) + 48 fc929ec8 boost::detail::lexical_stream<std::string,unsigned>::lexical_stream #Nvariant 1() (fa2fb6c8, fcb1d710, 0, fdbfff58, fd0ee26c, fd0ee830) + 10 fc929bd0 __type_0 boost::lexical_cast<std::string,unsigned>(__type_1) (fa2fb7f4, 2, fa2fb7fb, fcbcbd88, 57b5040, 0) + 28 fc925844 std::string util::getString(const __type_0&) (fa2fb89c, fa2fb8b8, 3, 4, 4bac880, fd0ee8f8) + 64 fca9cf00 std::vector<boost::shared_ptr<entity::Entity> >operation::getData(const message::Message&) (fa2fb964, 8195784, 1a86c, 4288d10, 4288d10, 4288d10) + 168 I am wondering how can this crash can happen for a very simple case of converting from unsigned to string using lexical cast. Any help would be highly appreciated. Regards Boostman -- View this message in context: http://boost.2283326.n4.nabble.com/lexical-cast-crashing-on-solaris-tp34137… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 1

[Parallel Graph] MPI installation procedure
by Cosimo Calabrese 29 Mar '11

29 Mar '11

Hi to all, I'm searching for a detailed procedure to install MPI (such OpenMPI) under Win32 (WinXP in my case) with Boost, and some sample code to use the parallel graph algorithm. Can someone help me? Thanks, Cosimo Calabrese.

3 8

Help needed for shared_ptr issue on iPad2 (dual core ARM)
by Peter Dimov 28 Mar '11

28 Mar '11

Hi everyone, Ticket #5372: https://svn.boost.org/trac/boost/ticket/5372 says that shared_ptr's ARM spinlock implementation (which uses the swp instruction) doesn't work properly on iPad2 (which has a dual core ARM processor). The sample program in the ticket compares it to a loop using __sync_fetch_and_add, which means that the __sync intrinsics are implemented by the compiler the submitter is using. These didn't work on gcc for ARM when we tested them, but may have been added meanwhile. (I can see some code samples that test for 4.4, but the official docs state that ARM intrinsics are only supported on Linux before 4.6, which was released yesterday.) So, we have two questions; first, why does the swp-based spinlock fail, and second, how can we detect support for __sync intrinsics and use them. Anybody with ARM knowledge and iPad2 development access?

4 10

GSOC LP library for Boost
by Chad Seibert 28 Mar '11

28 Mar '11

Hello, Previously, I mentioned implementing an LP library for Boost. However, there didn't seem to be a consensus on how I should go about it. If we can't agree on a method of attack, then there is no hope for me to get a proposal through the selection committee. So now, I solicit the communities advice on writing a wrapper for lp_solve, an LGPL library that purported to be one of the most stable free LP solvers. Do we care that a dependency is LGPL? I've done my due diligence and there doesn't seem to be a comparable MIT/Boost licensed library. Thanks for your consideration, Chad

4 7

[website] New build script
by Daniel James 28 Mar '11

28 Mar '11

Hi, I've been writing a new script for generating the release notes, the feeds and some other things. I'd like to put it in place on the live site soon, so that I can use it to update the site for the boost build release. It should now be easier for you to regenerate the release notes. You'll need python and quickbook on your path. Then run: python build/build.py update from the root of the beta site (you can actually run the script from anywhere, you just need to get the path to 'build.py' correct). There are some other commands, but they're probably not very interesting. You'll need to commit all the changes this makes. If something goes wrong, just commit the quickbook files, and let me know so that I can investigate. I'll still handle all of this if you wish, but it should be easier for you if you want to. I'll update the instructions on the site soon. Daniel

2 3

Call for Mentors
by Andrew Sutton 28 Mar '11

28 Mar '11

All, If you are planning to or would like to mentor a student project for GSoC this year, please login here http://www.google-melange.com/gsoc/homepage/google/gsoc2011 and a) sign up, update your info from last year etc. b) request to be a mentor for Boost c) or contact me with your linkid and I can invite you. I would have done this sooner, but Google was rolling out a new UI for the web app. It looks a lot nicer, but the timing is not especially good. Andrew

1 0