- Boost - lists.boost.org

[1.47.0] Merge requests for iostreams + quickbook
by Daniel James 27 Jun '11

27 Jun '11

Hi, Is it okay to merge a couple of changes to release? This change activates an existing workaround for Visual C++ 8 in iostreams. https://svn.boost.org/trac/boost/changeset/72726/ This change reverts the support for escaped characters in 'simple markup' in quickbook because it breaks the regex documentation. It isn't used anywhere else, and the documentation still builds, so it's safe. Will be reintroduced for quickbook 1.6. https://svn.boost.org/trac/boost/changeset/72695/

2 1

[review][assign] Formal review of Assign v2 ends today
by John Bytheway 27 Jun '11

27 Jun '11

The formal review of the Assign v2 library upgrade by Erwann Rogard is scheduled to end today. Although there have been no actual reviews with formal votes, there has been useful discussion of the library, and we have chosen not to request an extension of the review. Despite the end of the review, please feel free to discuss the library further, make any final comments, or even submit a late review. I will certainly not declare the review request before next Monday, and will incorporate any comments made before then. I would like to thank all those who participated in the discussions, and Erwann for developing the library, and being so prompt in his responses during the review. A quick reminder of where to find more about the library: The documentation is online at: <http://svn.boost.org/svn/boost/sandbox/assign_v2/libs/assign/v2/doc/html/in…> With the change log at: <http://svn.boost.org/svn/boost/sandbox/assign_v2/libs/assign/v2/doc/html/bo…> The Assign v2 source can be found in the Boost sandbox at: <http://svn.boost.org/svn/boost/sandbox/assign_v2/> or downloaded from: <http://www.boostpro.com/vault/index.php?action=downloadfile&filename=assign…> John Bytheway Review Manager

4 3

Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project
by Pierre Morcello 26 Jun '11

26 Jun '11

Hello Alejandro, In your first example, you wrote : for (int i = INSERT_MAX; i < CONTAINS_MAX; ++i) { if (bloom.probably_contains(i)) cout << "collision" << endl; } I suppose that you meant ++collision instead. Best regards, Pierre Morcello

2 1

Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project
by Phil Endecott 26 Jun '11

26 Jun '11

Arash Partow wrote: > Phil Endecott wrote: > > Sorry Arash but I don't understand your reply; what exactly > > is correct? > > My point was that you are correct, the "and" does not provide anything of > value. Only "or" and "xor" are practical for non-counting bloom filters. Well no, that's not what I said. For clarity, I believe that: 1. Bitwise OR of two bloom filters achieves the set union without any side effects. 2. Bitwise AND of two bloom filters achieves the set intersection, but it will introduce additional false positives, which may or may not be acceptable since they are already inherent in bloom filters. 3. Bitwise XOR of two bloom filters achieves something like the set symetric difference, but will introduce false negatives, which probably are not acceptable because bloom filters do not otherwise suffer from them. > I'm not sure what you mean by overlapping hashes I simply mean the case where two distinct values have the same hash for some of the hash functions. Regards, Phil.

1 0

[1.48.0] Schedule discussion
by Beman Dawes 26 Jun '11

26 Jun '11

In the "[boost] [1.47.0] Release branch now closed" thread, Daniel James and I discussed possible schedules for 1.48: Beman>>> While the release managers haven't talked about the 1.48.0 schedule Beman>>> yet, I personally would like to get back to our traditional quarterly Beman>>> schedule. That would mean 1.48.0 would be scheduled for the first Beman>>> Monday in August. Daniel>> We haven't got enough time for that. If we release 1.47 after a 2 week Daniel>> beta (i.e. pretty quickly), it will be released on 4th July, leaving Daniel>> just under a month before the first Monday in August. Beman> Agreed, but we could aim for as short a 1.48 schedule as is reasonable Beman> so that the 1.49 schedule is then back on the quarterly cycle. A 1.48 beta 5 weeks after 1.47 ships seems doable. That would be about August 8th, and then the release 3 weeks later, or about August 29. The 1.49 release then would be back on schedule for the first Monday in November. To make the above happen, we would need to open branches/release for merges immediately after 1.47 ships. Or maybe create a branch now for 1.48. Thoughts? --Beman

9 11

Re: [boost] Is there interest in an alternative to the Singleton anti-pattern?
by Ben Robinson 26 Jun '11

26 Jun '11

> > > If you choose the default policy of single_threaded, there is no > > thread safety, but there is also no overhead in using a mutex and using a > > volatile pointer. > > > > Volatile in C++ doesn't really help with threading... Check out < > > http://software.intel.com/en-us/blogs/2007/11/30/volatile-almost-useless-fo… > > > for one of many articles on the subject. > -- > Nevin ":-)" Liber <mailto:nevin@eviloverlord.com> (847) 691-1404 > > Thank you for the feedback. That article and the accompanying discussion is very interesting and informative. However, given the design of Singularity, I feel I still must make "instance_ptr" volatile for thread safety. If I do not, the compiler can store the pointer in a register, and other threads of execution will not see changes to its value. The linked article seems mostly concerned with fencing access to the variable, which I am achieving by using a mutex object. I only need volatile to prevent effectively reading a "cached" value for the pointer. I found the following article by Andrei Alexandrescu especially interesting: http://drdobbs.com/cpp/184403766 Also note, that the ThreadingModel for Singularity is policy based, so users of the class are free to develop alternative thread-safe policies, using whatever techniques are appropriate for their environment. Thank you, Ben Robinson, Ph.D.

2 1

[1.47.0] Regression in type_traits, is it too late to revert?
by John Maddock 26 Jun '11

26 Jun '11

There's a regression in type_traits caused by the addition of compiler-intrinsic support for Clang - this got reverted on Trunk after a flurry of discussion a while back: http://lists.boost.org/Archives/boost/2011/06/182844.php. Unfortunately it appears it never got reverted on the release branch. Can we please revert this? Thanks, John.

3 3

Interest in multi-dimensional array class templates.
by Brian Smith 25 Jun '11

25 Jun '11

The file maps.zip in the containers directory in Boost's vault contains a library with classes for the development of multi-dimensional array applications. Also included are scalar and fixed-size vector and matrix class templates with an expression template implementation of operators. The multi-dimensional array's can be fixed-size statically or dynamically allocated, or dynamically allocated and resizeable. Vectors and matrices can be statically or dynamically allocated and written in block form. The notation follows that provided by the STL and other Boost libraries. The classes lack tests using Boost's test framework and the documentation is rather sparse. The intention would be to remedy both issues if interest is sufficient to warrant it. Regards Brian

8 36

Re: [boost] [GSoC] Request for Feedback on Boost.Bloom Filter Project
by Alejandro Cabrera 25 Jun '11

25 Jun '11

Hello Phil, > Hi Alejandro, > > Alejandro Cabrera wrote: >> I'm writing to request feedback, suggestions, and advice from the Boost >> community. I've been working on a Bloom filter data structure for about >> a month and a half now. At this point, the following is complete and >> available in the Boost Sandbox: >> - working, basic prototype (insert& query operations, union& intersect) >> - a test suite covering the public interface >> - five examples >> - documentation covering many aspects of the project (tested on Chrome >> 12 and 13, Firefox 4 and 6) > At first glance, this looks very good. Well done. > > Bloom filters are essentially a quite simple concept, and I suggest > that you should stick to that i.e. resist any temptation to add lots of > extra features. Having said that, I think you should look at e.g. > std::set<> and std::unordered_set and see what you can do to make your > class closer to them. I can think of: > > - empty() > - clear() (Ah, you do have this, but not documented?) I accidentally skipped documenting this. Thank you for pointing this out. > - a constructor that takes a range, e.g. > int a[] = { 1,2,3,4,5 }; > bloom_filter<int> b(a,a+5); > std::list<int> l; > bloom_filter<int> c(l.begin(),l.end()); > - insert(begin,end) similarly I hadn't considered various ways to construct the Bloom filter. I assumed users would always want to start with an empty Bloom filter, but this would make using the Bloom filter more flexible. > - swap() I overlooked swap. I'll add this. > - You have a size() which is (confusingly?) different from those > containers' size(); it's more like capacity() I guess. (Similarly I > think I would rename count() to maybe bit_count().) I agree that using size() as I do is confusing, versus what size() has come to mean for standard containers. This would better be named something like bit_count(). I'll reconsider the name. > There is a trade-off between the size of the filter, the number of > values stored, the number of hash functions and the false positive > rate. You might consider adding some sort of compile-time > metafunctions to help the user determine the right size and number of > hash functions, based on their expected number of values stored and > acceptable false positive rate. Similarly, you could add a static > expected_false_positive_rate() method that takes the number of stored > values as a parameter. Given a desired false positive rate, an expected number of elements and an upper-limit on the storage requirement, it is possible to determine both a good Size value and a good number of hash functions. I see now how meta-functions can help alleviate the burden on the user for picking good values. This might take a bit of work to provide as a feature. It would involve ratios to represent the false positive rate as a template parameter to the meta-function. I'll put this feature off 'til version 1.1 or 1.2. Until that time, users will have to determine the best parameters for their application using the documentation guidelines. On that note, I think I should add a section to the tutorial detailing how to choose good parameters. > Sometimes it would be better for size to be a run-time parameter. I have a dynamic Bloom filter in the queue for variants. It's definitely required if I were to develop a scalable Bloom filter that guarantees a certain false positive rate, as detailed in a recent research paper titled "Scalable Bloom Filters". > Sometimes it would be useful to access the underlying data. For > example, say I have a spell check dictionary or a URL block-list; I > might want to compile that list into a bloom filter and ship that as a > binary file. For that I'd want to be able to use it as an adaptor on > top of an underlying container that I supply: > > // compile: > std::vector<uint32_t> data(100000); > bloom_filter b(data); // acts as a container adaptor > b.insert(...); > file f; > f.write(data.begin(),data.end()); > > // use: > memory_mapped_file f("dictionary.bloom"); > bloom_filter b(f); > if (b.contains(url)) .... I'm not sure how this would work. Could you elaborate further in this regard? Currently, as I understand, there's two components of interest. The first is to be able to access the underlying Bloom filter data for serialization/deserialization purposes. This should be easy enough to do given a function that exposes the Bloom filter data. The other component that I'm picking up on is to be able to construct a Bloom filter using various sources. Range construction will be added that semantically behaves as an insertion for each element in the range. However, I'm not sure how to support construction from a memory_mapped_file. > I think it would be sufficient for false_positive_rate() to return a > float. No-one cares about its 19th digit. I preferred greater precision to anticipate user needs. Unless false_positive_rate() were called frequently, I wouldn't expect that the added precision would incur a significant performance penalty. > For some reason I have a mental block about how intersection works. > Union is OK; I can see that > > set a; > set b; > bloom_filter(a) union bloom_filter(b) == bloom_filter( a union b ); > > but it's not clear to me if > > bloom_filter(a) intersect bloom_filter(b) == bloom_filter( a intersect > b ); > > Can you convince me? Intersect intends to leave only the bits shared between two bloom filters on. This also corresponds to the elements that both Bloom filters have inserted. The reason for this is because intersection is only allowed between Bloom filters that use the same hash function set and the same storage size. Assume that both Bloom filters are instantiated with hash functions that return the integer value of the element hashed. Then the following occurs: bloom_filter<int, 4> a; bloom_filter<int, 4> b; bloom_filter<int, 4> c; a.insert(1); a.insert(2); // 0110 b.insert(2); b.insert(3); // 0011 c = a & b; // 0010 At this point, only c.contains(2) will return true. > During the XInt review there was some discussion about whether > is_prime() should be called is_probably_prime(). The same argument > could be made here about whether your contains() should be > probably_contains(). If there were some six-letter word meaning > "probably contains" then I would support using it, but > "probably_contains" is a lot of typing. The wording for contains() is another tricky issue. probably_contains() has the benefit that it points out the probabilistic nature of the data structure. This is very helpful to warn users. I don't think the addition of 9 more characters to type (probably_) should be a problem, since it isn't the type of function that can nest on itself (x.contains(t).contains...). I will tentatively rename the function probably_contains(), and if further comments indicate that this adds some level of confusion, I'll reconsider the name again. > Regarding hash functions: I believe I have read that some care is > needed when you use essentially the same hash function but with > different seeds i.e. are the results really independent? It would be > be more obviously correct to have a set of hash functions that use > entirely different algorithms. Unfortunately this is hard. I've left the hashing component open to extension exactly because of this reasoning. The Bloom filter data structure does rely greatly on the use of good hash functions. However, the definition of "good" depends on the context. It might be that a CRC32 is perfect for some applications, but a murmurhash3 is better for others, and some applications might even require a cryptographically secure hash. Since the intent of the project is not to develop great hash functions, I'm inclined to leave the option of boost::hash_value as the default, though it might be best to default to an mpl::vector containing a single hash function instead of two, since as you stated, the results aren't independent. > Performance: it would be great to see some benchmarks for different > types against std::set and std::unordered_set. In particular it would > interesting to look at string keys of different lengths: both the bloom > filter and the unordered_set always have to look at every byte of the > string to compute the hash, while a std::set need only look at the > string's unique prefix. You mention things like web caches, and so I > guess getting some real-world benchmark data would be simple enough. > One hashing option for strings is to hash substrings. > I suspect that a benchmark on at least strings would be useful to demonstrate how the bloom_filter compares against std::set and std::unordered_set, assuming that most users will be hashing data (file names, URLs, etc.). I'll add benchmarks to my queue of things todo, but I want to make sure the interface is close to stable before I do commit to writing benchmarks. > Anyway, good work so far. > > > Regards, Phil. > Thank you for taking the time to comment so thoroughly on the Bloom filter project!

2 1

SVN Ignore for Bin dirs
by Joshua Boyce 25 Jun '11

25 Jun '11

Is it possible for somebody to add an svn:ignore for dirs like Bin, Stage, Dist, etc on the Boost trunk? Not a big deal, but I pull down Boost using svn:externals for one of my projects, then build it as part of my build script, and it's a little annoying having all the built files pop up in the commit list with no way to set them to ignore without having to do it manually on every checkout. Unless someone knows an SVN trick I can use in my project to work around this? (Though I can't see a reason using svn:ignore in Boost would be a problem...)

3 4