- Boost - lists.boost.org

[multi_index] Extending multi_index_container hash tables
by Vladimir Voznesensky 16 May '11

16 May '11

Dear Joaquin, Dear all, Please, find the comments below. Joaquin M Lopez Munoz writes: > Vladimir Voznesensky<vvoznesensky<at> gmail.com> writes: > > >> > >> > Hello there. >> > >> > Current implementation of hashed index has, at least, two issues, preventing >> > me from re-using it in some places. >> > >> > First, the time for unlink operation in >> > multi_index/detail/hash_index_node.hpp is O(m) where m is a occupancy of the >> > given bucket. I'ts usually ok for unique index, but seems to hit performance >> > of removing item in a non-unique index. It's all because of using >> > single-linked list instead of double-linked one. >> > The question here is whether non-unique indices will be populated > with many equivalent elements or not: if the former, a singly-linked > list implementation such as that of Boost.MultiIndex certainly > degrades at erasure, but going to a doubly-linked list unncessarily > imposes a non-negligible penalty (one pointer per element) in the > latter case. Having to decide I chose to favor the former case. > I think it should be up to a user to choose: the usage pattern could be very specific (for instance, a LIFO pattern seems to work OK with the single linked machinery). > If you can contribute a Boost-quality modification of the implementation > that lets the user decide between singly-linked and doubly-linked > implementation (say with an extra template paramater in > the hashed<...> index specifier I can certainly add it to the > library. > I have some questions to discuss here. 1. The 1st obvious step is to realize a double- linked list near a single-linked one. I plan not to subclass any stuff from the current detail/hash_index_node.hpp, but use it as a near sample. Should I copy detail/hash_index_node.hpp to, say, detail/hash_index_dbl_node.hpp or use the same file for realization? It seems not to be a problem to add a concrete NodeImpl second template argument to a class bucket_array. 2. hashed_index.hpp arise some gentle problems. I could put another template argument into detail::hashed_index, hashed_unique and hashed_non_unique, but what kind should it be? It's seems possible to add NodeType template argument to class hashed_index without breaking up BOOST_MULTI_INDEX_ENABLE_SAFE_MODE stuff, but how should we pass such sophisticatedly formed type from the final API? detail::hashed_index_args looks like a template hell. So, maybe it would be wiser to just introduce struct hashed_dbl_unique and struct hashed_dbl_non_unique extra variants? > Hahsed indices have the following bucket-handling interface: > > // bucket interface: > > size_type bucket_count()const; > size_type max_bucket_count()const; > size_type bucket_size(size_type n)const; > size_type bucket(const key_type& k)const; > > local_iterator begin(size_type n); > const_local_iterator begin(size_type n)const; > local_iterator end(size_type n); > const_local_iterator end(size_type n)const; > const_local_iterator cbegin(size_type n)const; > const_local_iterator cend(size_type n)const; > > local_iterator local_iterator_to(const value_type& x); > const_local_iterator local_iterator_to(const value_type& x)const; > > (See > http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html#hash_…) > Is this not what you're looking for? > It's not clear from the docs and the sources, how to, say, insert a new element before or after a given one. Thank you.

1 0

Conversion/Enums/Opaque request for interest
by Vicente BOTET 16 May '11

16 May '11

Hi, Lastly I've been working on 3 Boost libraries proposals. * Boost.Conversion (https://svn.boost.org/svn/boost/sandbox/conversion/libs/conversion_ext/doc/…) * Boost.Enums (https://svn.boost.org/svn/boost/sandbox/enums/libs/enums/doc/html/index.html) * Boost.Opaque (https://svn.boost.org/svn/boost/sandbox/opaque/libs/opaque/doc/html/index.h…) Boost.Conversion manages with generic explicit conversion between unrelated types. The template function convert_to allows to convert a source type to a target type, using argument dependent lookup (ADL) to select a specialized convert_to function if available. If no specialized convert_to function is available, boost::conversion::convert_to is used. Boost.Enums intends to provide a partial solution to the scoped enums problem ensuring a portable solution compatible with compilers supporting natively scoped enums or not. In addition provides a framework to view enumerations as ordinal types so we can define some specific and efficient enum containers. Boost.Enums is composed of the following parts: * Scoped enums * Ordinal enums * Enum containers * MPL enums * String <-> Enum conversions Boost.Opaque intends to provide a library partial solution to "opaque typedefs". Boost.Opaque provides: * a generic mixin class hierarchy which can be specialized by the user to make new opaque classes. * a generic class hierarchy which can be instantiated by the user to make new opaque typedefs. * a meta-mixin concept that allows to compose in a easy way several aspects of a class in an orthogonal way. * a considerable number of meta-mixins that helps defining new types from an underlying type * Some helper macros that can reduce the declaration of a new opaque type to a single line, emulating the language-based approach. Boost.Opaque and Boost.Enums depend in some degree on Boost.Conversion. These are quite basic libraries that any of you could find useful (or not) and that are not associated to a complex domain, so any of you could have an opinion without spending too much time. Please follow the above links to have a better idea of the motivation of these libraries. Before continuing completing the design, docs and tests of these libraries I would like to know if there is an interest on these libraries and if you have any suggestion on how to improve them, you see something missing or that should be removed. This will help me a lot to concentrate my efforts on the library that reveals more interest. Any comment will really be appreciated. Thanks, Vicente

7 10

Status of make_shared_array
by Joe Dougherty 16 May '11

16 May '11

Hello; Roman Kecher started a thread<http://lists.boost.org/Archives/boost/2009/11/158170.php>in November 2009 regarding the creation of a boost::make_shared_array() function to complement the boost::make_shared()function. What is the status of this addition to the boost library? Thanks Joe

1 0

[Range] Support for array references, svn:executable on headers
by Bryce Lelbach 15 May '11

15 May '11

Boost.Range does not support array reference types. I'd like to add the specializations/overloads/code to Boost.Range to support array reference types (I have commit rights). Neil, is this alright? Does anyone see any see any problems with such changes? (some) of the places where changes are needed: 2011.05.13_18.45.33< VeXocide> it works perfectly fine with char const [5], but not with char const (&)[5] [snip] 2011.05.13_18.47.12< VeXocide> this probably means it's missing a whole bunch of specializations, because the other functions don't seem to support it either [snip] 2011.05.13_18.57.41< wash> VeXocide: where else do you believe changes would need to be made? 2011.05.13_18.58.43< VeXocide> wash, as far as I can tell (I've only checked a few) all functions at http://www.boost.org/doc/libs/1_46_1/libs/range/doc/html/range/reference/co… and http://www.boost.org/doc/libs/1_46_1/libs/range/doc/html/range/reference/co… need to have the specializations added 2011.05.13_18.59.49< VeXocide> an, range_end supports T (&a)[sz] 2011.05.13_18.59.51< VeXocide> ah * 2011.05.13_19.00.12< VeXocide> hmz 2011.05.13_19.01.42< VeXocide> range_difference doesn't 2011.05.13_19.01.53< wash> *nods* 2011.05.13_19.02.30< VeXocide> range_iterator and range_const_iterator don't either 2011.05.13_19.04.12< VeXocide> hmz One test case demonstrating the problem: #include <boost/range.hpp> #include <iostream> #include <typeinfo> int main(void) { std::cout << typeid(boost::range_size<char const (&)[5]>::type).name() << std::endl; return 0; } P.S. A number of the headers in Boost.Range have the svn:excecutable property. Can I remove this property from said headers? -- Bryce Lelbach aka wash boost-spirit.com px.cct.lsu.edu github.com/lll-project

4 4

Need second opions from some threading / object creation experts...
by John Maddock 15 May '11

15 May '11

Folks, I'm looking at the code for singleton_pool, and I can't *quite* convince myself that it's completely thread safe and guaranteed to do what it says, the code in question is in boost/pool/detail/singleton.hpp which is a deceptively clever/simple singleton implementation. I haven't been able to break it in practice, but would a sufficiently clever compiler be able to optimize away the call create_object.do_nothing(); and therefore not instantiate the object prior to main()? Thanks in advance, John.

3 5

[phoenix] Creating a download for boostcon
by Daniel James 15 May '11

15 May '11

I'm looking to create the download for boostcon either tonight or tomorrow. I'll probably do it myself rather than using the nightly downloads so that it will include the geometry documentation. Since there were changes to phoenix since the regression test were last run, we need to check that it has been manually tested on all the popular platforms first. I'll run the phoenix (and spirit?) tests on OS X if that will help.

5 12

[Block Pointer] single threaded
by Phil Bouchard 15 May '11

15 May '11

Hi, What if Block Pointer was single threaded for the moment? Would that prevent it from being part of Boost? A lot of applications are single threaded and could take advantage of it already. fast_pool_allocator is not multithread safe as well. The problem is the structure keeping track of each set, block_header, is dynamic (gets created and destroyed over and over) and to maintain a mutex in such conditions is not trivial. Thanks, -Phil

1 0

Mixing different versions of Boost libs in a single process
by Grund, Holger 15 May '11

15 May '11

Hi, I've been looking into how we can improve our own usage of Boost libraries and there's one thing that's been sticking out. We typically have often lots of components running in a single process. Many of these components are developed on different release schedules and while there's certainly demand to adopt later Boost versions, the logistics required to move all of these at the same time is a big headache. Now, while I haven't seen any official word on it, I've always assumed there's no binary compatibility guarantees whatsoever between Boost versions. It's been my impression that there may be a few or even a lot of folks who would be happy to see binary compatibility, but it's unlikely to happen anytime soon. So the next best thing would be the ability to mix different versions of Boost in a single process. Today, linkage names will be identical across versions, which is problematic for static libraries on Windows, and static libs and DSOs on Linux. I remember discussion about making use of GCC's visibility attribute. This would certainly be a step in the right direction. I can't find the page I'm thinking of right now (pointers anyone?). Anyhow, what's the status of this? Also there's BCP, which supports renaming namespaces. That's great, but I guess it could be even better -- e.g. on toolchains where we have inline namespaces or __attribute__((strong)). On Linux targets, symbol versioning via GNU LD version scripts might make things a bit better -- specifically, in that things gone wrong fail earlier and with better diagnostics. Lastly, there's the problem of interop. Say libfoo built with Boost Version 1.40 provides an API like: boost::some_class make_some_object(); If I want to use this in my component where I use Boost Version 1.50, how do I do it? I can think of a few of approaches, none of which really fully convinces me. Consider the same API as a virtual member function, where no linkage name is involved (assuming boost::some_class changed in some relevant way). What to do there? And how to detect this in the first place? There might be other problems like having two different instances of a singleton for two libs in process, or something completely different I haven't thought of. Is there any work going on in this area? Any interest? Thanks! -hg Holger Grund, Vice President Morgan Stanley | MS Strats and Modeling 25 Cabot Square | Canary Wharf | Floor 03 London, E14 4QA Phone: +44 20 7677-4095 Holger.Grund(a)morganstanley.com -------------------------------------------------------------------------- NOTICE: Morgan Stanley is not acting as a municipal advisor and the opinions or views contained herein are not intended to be, and do not constitute, advice within the meaning of Section 975 of the Dodd-Frank Wall Street Reform and Consumer Protection Act. If you have received this communication in error, please destroy all electronic and paper copies and notify the sender immediately. Mistransmission is not intended to waive confidentiality or privilege. Morgan Stanley reserves the right, to the extent permitted under applicable law, to monitor electronic communications. This message is subject to terms available at the following link: http://www.morganstanley.com/disclaimers. If you cannot access these links, please notify us by reply message and we will send the contents to you. By messaging with Morgan Stanley you consent to the foregoing.

1 0

[ICL] How to define infinite endpoint for the types without infinity?
by Joachim Faulhaber 15 May '11

15 May '11

Hi all, Denis raised a question concerning handling of infinities in icl::intervals in an off list email conversation. I thought this could be of greater interest so I am posting it here. > On Sat, May 14, 2011 at 4:23 PM, Joachim Faulhaber > <afojgo(a)googlemail.com> wrote: > >> 2011/5/14 Denis <denis(a)camfex.cz>: >>> Hello. >>> >>> Boost.Icl has four interval types: closed [a,b] for a<=x<=b, open >>> (a,b) for a<x<b, left-open (a,b] for a<x<=b, rigth-open [a,b) for >>> a<=x<b. >>> >>> That's enough for types which have explicit minimal and maximal >>> values: double, all integers, boost::time_interval, boost::ptime, ... >>> But there are types like string and vector, which have the minimal >>> value (i.e. empty string) but not the maximal one. It makes impossible >>> to define an interval with infinite right endpoint. Intervals (and >>> intervals with infinite right end) have sense for strings end vectors, >>> for sharding. >>> >>> Simplest solution looks like to use tuple<bool, string> in place of >>> string (true means infinity so such a pair will be bigger than any >>> string). But it will force me to use the pair instead of string >>> everywhere in the program (or to create pairs before any interval >>> operation, which implies string copying). >>> >>> Is there a better solution? Maybe to add a 5th and 6th interval types >>> into Icl: closed_to_infinity [a,+inf) and open_to_infinity (a,+inf) ? >>> >>> I asked also here: >>> http://stackoverflow.com/questions/6000655/boost-icl-how-to-define-infinite… >>> >> >> Hi Denis, >> >> thank you for using Boost.Icl. The point that you are addressing is an >> interesting one and I was thinking about the integration of infinities >> while developing the library a few times. Introducing infinity for >> icl::intervals has some problems. We would have to check for the >> infinity condition in almost every function, which makes the code more >> clumsy. >> >> I decided not to do this for pragmatic reasons: In most applications >> of intervals and interval containers infinity is not needed or can be >> replaced by a value that represents some sufficient maximum. So I >> thought that this situation does not justify to bloat the code of the >> interval concept by code related to infinities. >> >> I'd be nice if you could provide a small and compelling example using >> interval containers, where infinities are really needed and can not be >> replaced by some simple pragmatic means. I am always interested in >> those use cases to demonstrate the possibilities and check the limits >> of the usefulness of the ICL. In case you do and the example shows a >> new important use case I will add it to the library's docs and give >> credit to you as the author. >> >> This was the short answer. If this is o.k. for you, I will provide a >> longer answer later this weekend and send it to the boost developers >> and users list and also stack-overflow, because I think the topic is >> of interest to others as well. >> >> Thanks again, >> Joachim >> > > 2011/5/14 Denis <denis(a)camfex.cz>: > Hi Joachim > > Well. > That's all very depend on do we need to add both infinities or only +infinity. > I need intervals with open end for arbitrary byte vectors, but I > cannot imagine what negative infinity can be used for. > Seems like all the types with negative infinity already have an > explicit representation of the minimal value (maybe even signed > biginteger?). a limitless integer implementation can not have a fixed min and max, of course, and whether it has a special value for +/-infinity is up to the library author. To be able to express both infinities might be interesting even for types like built in integers that have their min and max values. > So, hereinafter I talk only about the possibilities of adding +inf as > endpoint of intervals. > And I assume that the domain type has its minimal value. > > I have just made a small patch (about 30 lines) marking +inf in a bit > in `interval_bounds` for dynamic bound intervals. > It has little overhead (the bit is checked only in `bounded_upper()` > `is_empty()` `exclusive_less()` `contains()` `upper_less()` and > `operator <<()`) and enabled only for intervals which are dynamic > bound and continuous. I see that you have tried to keep the impact of the intended infinity-extension of the code small... > As a future optimization, the continuous realm can be divided to > double-like and string-like ones in order to avoid checking this bit > for double-likes. ... and thought even further, which is nice. > Also it not easy to talk about performance when it comes to types like > strings or vectors. > Using something like "\xFF\xFF\xFF\xFF\xFF\xFF\xFF\xFF".... to > represent the maximal blob could be slower and buggy than just an +inf > bit . > > > About the static intervals. > > In the classes `right_open_interval` and `open_interval`, if `_upb` > contains domain's unit value it comes to an empty interval > irregardless what is in `_lwb`. nifty considerations ... > This is not the only way to represent empty interval, any `_lwb` <= > `_upb` would also work. > > So those extra invariants can be used to store infinity without adding > extra fields to the static intervals classes. ... nifty but tricky > Domain's unit in `_upb` can represent +inf, and be seen by comparison > functions as the biggest value, but still the smallest when it is in > `_lwb`. > The case of both `_lwb` and `_upb` having unit will represent the > whole interval so user's tries to construct a empty interval > specifying two units (`open_interval("", "")`) should be corrected in > the constructors (to "\1","\1") > > In order not to impact the performance of the existing > `right_open_interval` and `open_interval`, two new classes > `right_open_interval_with_inf` and `open_interval_with_inf` can be > created by copying with small patching of the comparators and the > constructors. hmm... your posting is interesting with respect to different aspects. You are obviously using icl::intervals (and I guess also icl::interval_containers) with domain types of some types like string and (byte)vector. It was my ambition to allow for such types as domain types in addition to numbers. Of course you have to watch efficiency, if your values get large (not to mention approaching infinity ;) Because you are using icl in this realm you might experience difficulties and even detect bugs that no one else has found. Also you might explore properties of the underlying concept, which is the concept of a sequence, I guess. As I wrote in my first answer, I'd be very much interested in a short compelling example for the tutorial that demonstrates the kind of use case that you cover. It might be kind of unique and open up a new horizon of icl usage. I think it is a good idea to implement infinity as a property of intervals instead of using special values. I had similar considerations, but as I mentioned earlier, I didn't do that for pragmatic considerations. I think a real need to work with infinities does not occur in most applications. And even if someone want's to use them, it is always only a phenomenom that applies to the very first or last interval of an interval container. It might be true that by good design and use of metaprogramming we might be able to limit the impact a infinity extension to just a few functions and I acknowledge you tried to demonstrate that. Still these are functions (e.g. exclusive_less) that are called extremely frequently. So there is performance penalty also on those majority of instances where infinities are not needed at all. I appreciate your ideas but I guess I need some more time to think about them. One possibility might be to create a concept for infinity bounded intervals on top of dynamic intervals. So only users who explicitly need to model infinity bounded intervals would choose those. Regards, Joachim -- Interval Container Library [Boost.Icl] http://www.joachim-faulhaber.de

1 0

Boost.Context review result
by Vicente BOTET 15 May '11

15 May '11

Hi, this was my first experience as review manager and it has been more difficult than I had expected. Apologies if I forget some important things or I misunderstood others. I hope that the major points have been taken in account. Here it is the result of the Boost.Context review. The library is accepted provisionally and will need to address some mandatory points before a mini review (4/5 days). There were not too much complete reviews (5) but globally all the reviewers voted for acceptation and two subject to some major redesign modifications. I hope I didn't miss somebody. YES Gordon Woodhull YES/Cnd Giovanni Piero Deretta YES Artyom YES Nat Linden YES Phil Endecott YES/Cnd, Jeffrey Lee Hellrung, Jr Thanks to all the review participants Gordon Woodhull, Giovanni Piero Deretta , Artyom, Nat Linden, Holger Grund, Phil Endecott, Jeffrey Lee Hellrung, Jr.. Special thanks to Giovanni Piero Deretta showing some major flaws in the global design and Holger Grund for showing a (possible) major bug on the Windows implementation. I know Oliver that you have already redesigned your library, but if there are points that you have not been addressed yet or have some difficulties addressing them, I will suggest you to work closely with Giovanni, he know well the domain and have a lot of good ideas, and exchange on this ML. You should follow up more closely the discussions during the mini review and even try to get feedback from the ML posting how you see your redesigned library. Point to be addressed before the mini review: Design 1. Separation of the context class in two interface: - A C-like interface that defines a POD struct that is memcpy-able and that can be implemented either using platform libraries, as ucontext, fibers or directly using assembler when a robust implementation is available. The context swap implementation don't need to save the signals as ucontext does. The following is just for illustrations purposes. struct boost_context; typedef void boost_context_fn_t(intptr_t); extern "C" void boost_context_make(boost_context* ctx, boost_context_fn_t * f, intptr_t p, ...); extern "C" void boost_context_swap(boost_context* from, boost_context const* to); extern "C" intptr_t boost_context_destroy( boost_context* fc); boost_context_make is a merge of get_context with make_context + some fields assignations. "A user will have lower expectations from such a low level API and at the same time will give more freedom for other people to implement on top of it higher abstractions as Boost.Corutines, Boost.Fibers ..." - A non-copiable but movable safe context class on top of the low level C-like interface, that will provide modern and efficient C++ interface, that is usable by a user in a safe way. The safe context class would just be one of the client of the C-like interface, other library authors could either use the underlying C-like API directly or the class context depending on wether they need the speed or safety. * The context class will not be templated any more, and the use of type erasure will ensure that. * The constructor will accept any C++ callable, function pointers, functors, ... * At this high level interface, the function provided by the user could throw exceptions, and the library must wrap the user function and needs to store the exception raised and provide an interface to retrieve them. 2. The stack implementation must ensure that the stack is unwound before it is destroyed. A stack should only be safely deallocated if either has been completely unwound or if it doesn't own any resources. A basic stack without protection seems mandatory. For debug purposes it has been required to provide some stack usage functions that allow to know the max size used for example. Implementation 3. The assembler implementation on Windows must be disallowed if the ABI bug reported by Holger is confirmed. As far as Windows provides a fiber implementation that is as efficient as the assembler one, the assembler implementation is not mandatory and the user of the provided Windows fiber is a preferable choice. 4. Most of the 'throw' statements in the context class should actually be asserts. 5. The provided stack should be used to store any context parameters as far as no major impediment is found during the implementation. This will avoid further allocations on the safe context class. Documentation 6. The documentation is very minimalist and should be expanded with a discussion on context switching and use cases. Take care of all the grammar/spelling improvements suggested by the reviewers (It will be great if Jeffrey could review the documentation before the mini-review). Some user land examples should be provided (why not the yield example). 7. The concept of (Movable) Stack must be clearly defined, as it is done in the standard, using expression requirements with semantic constraints. 8. The assembler implementation should be carefully documented, so others could maintain the code and add other implementations if needed. 9. Some performance measure should be added. Providing the number of cycles on each implemented platform would be nice. Build system 10. The default build on a platform must work (It must be ABI compatible with the underlying platform) and take care of the specific features. Of course, the build needs to support cross compiling, so the user should be able to override the default values. Others points that are not required but that can make the library more usable or efficient: 1. The assembler implementations could be simplified if the context itself was represented as a single pointer to the top of the stack. This would save some instructions to move the source address from the stack return address to the context struct and back. 2. Instead of supporting a 'fc_link' a-la ucontext, have the callback function return a new context (it is void now). 'fc_link' is useful only on some limited cases (usually when you have an external scheduler managing your contexts), while the having the callback return the 'next continuation' has more applications (note that fc_link can be implemented easily in term of the continuation returning variant, but the reverse is harder). This will be very useful, for example, to implement some kind of 'exit_to' functionality (unwind the stack and restore another context), a key piece for safe context destruction. 3. Give to boost_context_swap the ability to exchange a parameter with the other context: boost_context_parm_t boost_context_swap( boost_context * ofc, boost_context const* nfc, boost_context_parm_t parm) where boost_context_parm_t is either union boost_context_parm_t { void * ptr; int int_; }; or simply intptr_t; boost_context_swap saves the current context in ocf and restores the context ncf as usual; additionally, if ofc was 'captured' on a call to boost_context_swap, this call will return the value of parm on the original context. This extra parameter is equivalent to the second parameter of longjmp. If ofc was created with boost_context_swap, 'parm' will be an extra parameter to the function. Note that this can be potentially implemented with little or no overhead. 4. Add a variant of boost_context_swap that allows executing a function on the destination context (in this case 'parm' would be passed parameter to this function. This is mostly useful for injecting an exception on the destination context. This can be potentially implemented on top of the existing functionality, but would slow down every context switch; a possible efficient implementation would manipulate the destination stack to add a call to the function on top of it, so that the cost is paid only when required. 5. Add a current context function (thread local). Vicente Review Manager

5 8