- Boost - lists.preview.boost.org

Re: [boost] GSOC 2013
by Boris Schaeling 21 Mar '13

21 Mar '13

On Wed, 27 Feb 2013 11:59:31 +0100, David Bellot <david.bellot(a)gmail.com> wrote: > Only 2 projects have been proposed so far for GSOC 2013: wake up Boost ! > > https://svn.boost.org/trac/boost/wiki/SoC2013 Google has started to accept applications from mentoring organizations. I'll have to submit our application in the coming days. If you want Boost to become a mentoring organization for GSoC 2013, please add projects to https://svn.boost.org/trac/boost/wiki/SoC2013 now! Boris

5 5

[container][intrusive] Treap for Boost.Container?
by Phil Endecott 20 Mar '13

20 Mar '13

Dear All, I have been playing with boost::intrusive::treap, and it seems like a useful thing. I think it would be helpful to create a boost::container::treap, i.e. a non-intrusive treap container, implemented using the intrusive version. That could make this useful data structure available to users who wouldn't otherwise need to learn how to use Boost.Intrusive. (While I'm here.... does anyone know about a list-like container that has lower memory overhead when the data type is small, i.e. ints or chars? I was considering something using chunks like a std::list< std::vector<T> >, but insertion would invalidate other iterators in the same chunk, which is unacceptable. Any ideas?) Regards, Phil.

4 3

[units] c++11 features to speed up compilation times
by Oliver Esser 20 Mar '13

20 Mar '13

Hi, I was wondering if there was a policy for boost including C++11 features into the libraries. Obviously there might be many projects out there that do not (yet) have access to a compiler implementing the new standard or choosing not to use such a compiler. Anyways I was looking for a dimensional analysis library for compile time units checking and found Boost.Units to be quite slow at compile time even for the relatively small example code in the quickstart documentation. So I've written a bit of code that follows the approach of Boost.Units but uses C++11 features (constexpr, variadic templates, suffix operator, auto). It is not a complete library that I would use in a production environment, but it looks promising, since compilation times are about a factor 2-3 faster on my machine. It would be great if some of you could take a look. https://github.com/legento/units Maybe one could add an implementation like that to Boost.Units as a C++11 compiler detected feature to speed things up. Maybe I am totally wrong and it is some coincidence that this compiles faster on my platform. I did just minimalistic 'ok it seems to work' testing and was about as thorough with measurements. So see this as an implementation sketch. Regards Oliver

3 2

C++Now 2013 is full [ 53 days before the conference ]
by Marshall Clow 19 Mar '13

19 Mar '13

Whoa. In the immortal words of W.C. Fields, "I expected this, but not so soon" We've set up a wait list in case we get any cancellations. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki

1 0

Re: [boost] [range][iterator] contiguous iterators
by Stefan Strasser 19 Mar '13

19 Mar '13

From [boost-users]: Am 18.03.2013 16:06, schrieb Jeffrey Lee Hellrung, Jr.: > On Sat, Mar 16, 2013 at 7:42 AM, Stefan Strasser <strasser(a)uni-bremen.de > is there any way to generically determine at compiletime whether an > iterator or a boost range refers to contiguous memory? > > is_contiguous<T *>::value == true > is_contiguous<vector<T>::iterator>::value == true > is_contiguous<std::list<T>::iterator>::value == false > AFAIK, not presently, but this has been discussed quite a bit in several > past threads on the Boost developers list. Then I'd like to suggest this again to the maintainers of Boost.Iterator and Boost.Range. I'd also like to suggest another addition to Boost.Range: a RangeOutputIterator, i.e. an OutputIterator that doesn't only accept single values, but assignment of ranges: template<class RangeOutputIterator> ... (...RangeOutputIterator out){ *out=range; where range can be any Boost.Range. You can find an implementation of this concept here, in the form of an back insert iterator that can insert entire ranges into a vector: http://pastebin.com/9M5rPDh9 Using these two things together can make generic algorithms as efficient as is possible, e.g. if the container that is being written to is a vector and the value type is a POD, there's one call to std::memcpy. think e.g. about file or database operations like database.get(1024*1024,out); This is in my "namespace detail" right now and I'd be willing to help make it public and document it. Stefan

2 8

Idea for O(1) hash-table
by Rani Sharoni 19 Mar '13

19 Mar '13

Hi All, I hope that you will find the following idea interesting. I have been using hash-table with, AFAICT, unique implementation and I thought that it might be handy for boost. The hash table is O(1) *non-amortized* lookup via extremely balanced buckets (for example, max 6 entries per bucket). The implementation itself is absurdly simple ;-) The hash-table is basically variation of linear addressing using double-hashing hash-table with special re-insert strategy. Algorithm for linear addressing (easy to adjust for chained hashing): Consider a two dimensional N*K array – N buckets with up to K elements per bucket. Assume that the zero-key is marking an empty entry. Lookup(key): for (hash = key, I = 0 ; I < K ;++i) { hash = HASH(hash); // double-hashing if (A[hash % N][i] == key) return found; } return not-found; Insert(key): for (hash = key, I = 0 ; I < K ;++i) { hash = HASH(hash); // double-hashing if (A[hash % N][i] == 0) { A[hash % N][i] = key; return true; } } return false; The above insert is basically a bounded double-hashing and as-is it has a low utilization (a bit similar to bloom filter). For example, for 100K buckets and K=6 - insert will fail when the table has less than 50% utilization (i.e. fail to insert though most entries are empty). The trick is to perform “re-insert”: Pick some random element, key1, from failed insert phase, replace it with the new key, and (re) Insert(key1). Retrying up to, say, 12 rounds of re-insert improves the utilization, of N=100K/K=6, to ~97%! Table resize is done (if needed) when such repetitive re-insert fails. Altogether this implementation trade-off insert for fast lookup which is very appealing to caches (i.e. insert done in the expensive path - only after a cache miss). Just for comparison, hash-table using naïve liner probing (A[HASH(key)%N][i]) has only ~80% utilization even when using K=128 (i.e. deep buckets)! Such unbalanced behavior is also typical classical hash-tables with link-lists (chained-hashing) since statistically some buckets will outgrow the average. The performance of the classic double-hashing algorithm itself is quite poor when the table is highly utilize since many steps are required to find empty entries. Though this hash-table is general purposed it has some interesting properties: 1) O(1) non-amortized with very low chance for collisions (each key has its own unique “virtual” bucket). 2) Can be implemented on continuous memory without pointers and with excellent utilization 3) Allow wait free implementation of caches (i.e. no lock or even interlocked needed). 4) Allow caches on shared memory – corruption safe/hazard algorithm (assuming at least 64 bit keys). 5) Allow persistent using direct memory to file mapping (i.e. disk representation is same as in-memory one). 6) Average 50% LRU eviction for caches (i.e. on average entry half from the oldest is evicted) BTW – there is little chance for patenting this algorithm since I already published similar idea in the public domain ;-) Thanks, Rani

4 4

[math] Extended float in C++ : Was : Support for libquadmath/ __float128
by Christopher Kormanyos 19 Mar '13

19 Mar '13

There has been some recent discussion on extended floating-point types in C++. >>> So the only way to add Q or q suffixes would be to find a way to query >>> the environment if it is supported. I wonder if GCC with >>> --enable-libquadmath has a kind of query for this. >> I haven't found one - gcc-4.7.2 has all sorts of __SIZEOF_XXX__ >> defines for every last type *except* >> __float128 and __float80 :-( > It won't help now, but is 'more precise types' an issue to > raise with WG21 for the next C++ standard? > Or is Multiprecision the way to go? Is there any definitive interest in adding more precise floating-point types to C++ in the next draft? Here, I am talking about floating-point types with fixed precision such as 24, 54, 113 or more binary digits, and possibly even extending beyond these to potential multiprecision types. See also Boost.Multiprecision. Consider the C language in ISO/IEC 9899:2011 (in other words C11). Extended precision is not specified, but there is a remark in Section 6.11.1: "Future standardization may include additional floating-point types, including those with greater range, precision, or both than long double." Recent specification of fixed-size integer types in C99, C11 and C++11 has drastically improved integer algorithm portability and range. Similar specification of fixed-size floating-point types could potentially improve the C++ language significantly, especially in the scientific and engineering communities. One could envision two ways to go: * Types such as float24_t, float53_t, float113_t, ... * Types such as float32_t, float64_t, float128_t, ...The first set above is intuitively coined from IEE754:2008. It is also consistent with the gist of std::uint32_t, et al --- in so far as the number of binary digits of precision is contained within the name of the data type. Is there any interest in committing to this project? Specification takes a long time and requires a coalition of collaborators. I could potentially contribute to this project as a subordinate author. But I don't feel confident enough to champion such a cause. Best regards, Chris.

2 1

Libaries accepted by not in Boost release yet - suitable for GSoC?
by Paul A. Bristow 19 Mar '13

19 Mar '13

I note there are some libraries that have been accepted but are not yet in a Boost release - and development seems to be stalled. This seems unfortunate - much effect from many people has gone into the whole process but we are not quite there yet - so a lot of work may be wasted? No doubt authors have other more pressing priorities J I spotted "Constrained value" and "endian" for example. Are any accepted but unfinished libraries suitable for Google Summer of Code students - with the task being to knock them into final shape? Is anyone willing to mentor these? Paul --- Paul A. Bristow, Prizet Farmhouse, Kendal LA8 8AB UK +44 1539 561830 07714330204 pbristow(a)hetp.u-net.com

5 5

[local_function] End scope function name declaration makes code hard to read.
by Mostafa 18 Mar '13

18 Mar '13

(This is a feature request/inquiry.) I'm just now seriously starting to use local_function, and I'm finding that having to "visually parse" until the end of scope to determine the local function name makes the code much harder to read. Is it possible to declare the function name at the beginning of the scope? (I don't mind having to also register the function name at the end of the scope.) Something like: BLF2(add, (int), (int lhs, int rhs)) { return lhs + rhs; } BLF2_REGISTER(add); Having said, I don't see why needing an "ending macro" for the local function scope is a requirement (albeit my understanding of the library internals is limited to implementation annex of the documentation). Can't the start macro just expand to something like: //----------------------------- //Macro Generated Output Start. //----------------------------- //Local class definition. //Local class instance registration. //Out of class method definition starts here: inline void local_add::body(int& sum, const int& factor, const int& num) //----------------------------- //Macro Generated Output End. //----------------------------- //User generated content starts here: { return lhs + rhs; } Thanks, Mostafa

4 8

[docs] How to install boost documentation?
by Mostafa 18 Mar '13

18 Mar '13

I'm having a real hard time trying to figure out how to install boost documentation. Can't find any instructions on boost.org nor any on google. Am I missing something really obvious?

2 3