- Boost - lists.boost.org

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

21 Jun '11

> On 6/21/2011 12:21 AM, Alejandro Cabrera wrote: >> Hello all, >> >> 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) > I would suggest to you that you briefly explain what a Bloom filter > entails, and why it might be important, when sending your message to > this list. > Thank you for the suggestion. The data structure is introduced below. Briefly, a Bloom filter is a probabilistic data structure that represents a set of elements compactly. Two operations are supported in the most basic variant: insert, contains. An element is inserted by computing k hash values and setting the bits at the locations given by the hash values to 1. Checking whether an element is contained in the Bloom filter is achieved by hashing the element and checking that the bits at those locations are all 1. A Bloom filter may incorrectly tell you that an element is in the set (false positive). If false positives are acceptable, Bloom filters are a powerful data structure to avoid expensive look ups. There exist variants that also support element removal at the cost of an increase in storage requirements and the danger of false negatives - these are not covered by Boost.BloomFilter just yet. Bloom filters have seen use in file systems (avoiding duplicate writes, deduplication), network caches (determining whether to attempt to fetch from cache), databases (does a row/column exist on disk?) and hardware design. Where the primary interest is to compactly represent a potentially very large universe of elements to mitigate latency differences, Bloom filters are a great choice. Further details can be found in the project documentation files.

1 0

[type traits] Strange behaviour of comparison operators with pointers
by Frédéric Bron 21 Jun '11

21 Jun '11

The following code gives a compile time error (g++ and msvc): int const lhs=1; int* rhs=0; lhs == rhs; But the following code gives no error: int const lhs=0; int* rhs=0; lhs == rhs; because a const int with 0 value is a valid null pointer! Then there is no way to predict if it is possible to compare lhs and rhs based only on their types. The general rule is that it is not possible so that this is what I propose to use for the type trait extension detecting the possibility to call comparison operators on given types. Frédéric

4 7

Re: [boost] [gui] Help with a little experiment.
by Artyom Beilis 21 Jun '11

21 Jun '11

----- Original Message ---- > From: Mathias Gaunard <mathias.gaunard(a)ens-lyon.org> > To: boost(a)lists.boost.org > Sent: Mon, June 20, 2011 12:09:50 PM > Subject: Re: [boost] [gui] Help with a little experiment. > > On 18/06/2011 16:55, Artyom Beilis wrote: > > > Making a GUI library is not about providing > > nice syntactic sugar for building layout. > > > > Syntactic sugar is the last thing that should interest you. > > Having a short and concise declarative definition of your GUI has several >advantages. > It's easier to validate it, it allows to avoid bugs, and you can really >materialize > the intent of what you want instead of coding its logic directly. > > Moreover, writing GUIs is very tedious and uninteresting. It would be nice > if it were possible to automate more things. Few points. If you want an easy and fast declare GUI there are many RAD tools like QtCreator or Glade that do this job well. On the other hand. When I was programming some GUI tools the **easiest** part was to write a code that makes the layout and connects widgets... The hard part was to write the actions that should be done behind the widgets. Today when I write production code I think about users who are going to maintain it. And readability and clearness is very big concern. See: http://developer.qt.nokia.com/wiki/API_Design_Principles There are 6 primary points: * Be minimal * Be complete * Have clear and simple semantics * Be intuitive * Be easy to memorize * Lead to readable code Especially this one: An API is intuitive if a semi-experienced user gets away without reading the documentation, and if a programmer who doesn’t know the API can understand code written using it. IMHO The proposed API does not helps with all this and makes things very obscure for a programmer that is not fully familiar with the toolkit. If I show this code to average C++ programmer the vast majority of them would not know what happens there... The fact that you and 1 percentile of C++ programmers (that write Boost Libraries) understand the proposed code does not mean it is understandable to other. Consider: This > auto gui_definition = > Window(title="Hello, world!") << > VBox(expand=true) << > HBox(expand=true) << > Label(text="Name:") && Entry[SLOT(onEntryChanged)]) > << End(HBox); > << Button(text="hello")[SLOT(onButtonClick)]; > << End(VBox) > << End(Window); Or this? class MyWindow : public Window { MyWindow { setTitle(tr("Hello, World!")); base_layout = new VBoxLayout(); setLayout(base_layout); base_layout->sizePolicy(Expand); top_layout = new HBoxLayout(); base_layout->addItem(top_layout); top_layout->sizePolicy(Expand); top_layout->addWdiget(new Label(tr("Name:"))); text = new TextEdit(); top_layour->addWidget(text); button = new PushBotton(tr("Hello")); layout->addWidget(button); connect(text,SIGNAL(valueChanged()),this,SLOT(onEntryChanged()); connect(button,SIGNAL(pressed()),this,SLOT(onButtonClick()); } void onEntryChanged() { std::cout <<text->getText() << std::endl; } void onButtonClick() { std::cout << "Button Pressed" << std::endl; } } The second is more verbose but it is much readable, clear, intuitive code for an average C++ programmer. My $0.02 Artyom Beilis -------------- CppCMS - C++ Web Framework: http://cppcms.sf.net/ CppDB - C++ SQL Connectivity: http://cppcms.sf.net/sql/cppdb/

5 4

[yield_iterator] new iterator lib with C# yield return/yield break
by Oliver Kowalke 21 Jun '11

21 Jun '11

I've uploaded a new lib 'yield_iterator' (http://www.boostpro.com/vault/index.php?action=downloadfile&filename=boost.…) Documentation can be found also here: http://ok73.ok.funpic.de/boost/libs/yield_iterator/docu/html/ . The lib provides the same functionality as C# does with the 'yield return' and 'yield break' statements - this lib provides an easy way to iterate complex containers. The library uses boost.context internally. For instance iterating an tree would usally require to traverse the complete tree and store the nodes in a STL container - the begin/end iterators of this STL container are used to iterate the tree. With boost.yield_iterator you have only to derive a class from yield_adapter and overload the function 'void iterate()'. In 'void iterate()' you can iterate locally over the internal data and return appropriate elements via 'yield_return()'. class tree_adapter : public boost::yield_adapter< leaf >, public visitor { private: node::ptr_t root_; public: tree_adapter() : boost::yield_adapter< leaf >(), root_() {} tree_adapter( node::ptr_t root) : boost::yield_adapter< leaf >( true), root_( root) { BOOST_ASSERT( root_); } void visit( branch & b) { if ( b.left) b.left->accept( * this); if ( b.right) b.right->accept( * this); } void visit( leaf & l) { yield_return( l); } void iterate() { root_->accept( * this); } }; int main( int argc, char * argv[]) { { node::ptr_t root = create_tree(); boost::yield_iterator< tree_adapter > e; for ( boost::yield_iterator< tree_adapter > i( root); i != e; ++i) { std::cout << i->value << ""; } } std::cout << "\nDone" << std::endl; return EXIT_SUCCESS; } The library contains a example iterating over a tree via visitor pattern an yield_iterator. I hope I get some feedback. best regards, Oliver

3 6

[review] [heap] Summary
by Andrew Sutton 21 Jun '11

21 Jun '11

The formal review of Tim Blechmann's Heap library has concluded. Only four votes were cast, although more people commented on issues either on the mailing list or though the Code Collaborator tool. However, from the comments received, the review identified no fundamental problems in the design or implementation of the library that would entail rejection. A such, the Boost.Heap library is ACCEPTED into Boost Votes for the library were cast by: Phil Endecott Daniel Russel Votes against: Thomas Klimpel (provisionally) Andrew Sutton Other comments received during the course of the review were generally positive, with a number of technical issues identified that need to to be addressed. The final version of the library can be fully accepted once Tim has addressed the technical issues identified during the review. Below is a summary of technical concerns. - The pairing heap has a known issue, regarding stack overflows, making it potentially unusable for production code. If the recursion issue can't be adequately solved, then the data structure should carry a much stronger warning label (i.e., put it in an experimental directory). - The performance of b_heap vs. d_ary_heap vs. priority_queue needs to be better characterized. Under what circumstances does one outperform the other. If no convincing scenario can be found where b_heap outperforms the others, then it should also be placed in an experimental directory. - The heap concepts need to be revisited as per comments on the review tool. The concepts should also describe semantics of the operations, not just the interfaces. - There were several comments on the implementation of heap stability. Three alternatives were identified: “naturally stable” heaps (of which no examples were given), the current counter based approach, and a chaining approach. No consensus on the best implementation strategy. Although the counter-based approach is probably adequate for most applications, it is not universally desirable. A more thorough investigation of alternative strategies is encouraged. It would be acceptable to document the investigation in a “Future Work” section of the library documentations (with any experiments also housed in the library). - The notion of Mergeable heaps needs to be better addressed, at least to differentiate between heaps that merge in O(n) or slower time and those that can merge in O(lg n) time. The proposed solution is to write merge as a general heap algorithm and specialize it for Mergeable heaps by calling the member function merge. Also, merge should be destructive, so merge and clear should not be needed. - The documentation must be substantially improved with respect to the overall design of heap data structures (i.e., concepts), especially mutable heaps and best practices. It also needs to provide both theoretical and performance comparisons for the different heaps. - Include documentation of the benchmarking tool in the documentation. It could be instructive for users to evaluate different heap implementations on their host or target architectures. - Document the complexity of == and < for heaps. - Address the comments and issues in the Review Tool. There were other recommendations that should be considered in the long term for the library. - Thorsten Ottosen suggest making b_heap and d_ary_heap container adaptors along the lines of std::stack, std::queue, and std::priority_queue, allowing parameterization over (e.g., stack-based container). Subsequent discussion indicates that there are some impracticalities in doing so, namely that it could invalidate other policies (e.g., stability). - Phil Endecott suggested rewriting some heaps (b_heap and d_ary_heap) in terms of more general algorithms operating on a (Random Access) Range in order to support the formulation of heap structures on other memory structures. Doing this would also help support the definition of heaps that satisfied Thorsten's request. I strongly recommend investigating Phil's suggestion, but this is not a barrier to acceptance. This feature could be added in future revisions of the library. I'd like to thank the community members who took the time to review Tim's work and especially those that submitted formal reviews. I'd also like to thank Tim (again) for his contributions and patiently answering our questions and addressing our comments. Andrew

3 7

[gsoc]Boost.Ustr Unicode String Adapter First Preview
by Soares Chen Ruo Fei 20 Jun '11

20 Jun '11

Hi all, I would like to inform you all that the development repository for Boost Unicode String Adapter (now I call Boost.Ustr) is now available at GitHub: https://github.com/crf00/boost.ustr. I have been working closely with my mentor Chad Nelson on the design of the library, and now I'd like to show it to the community to gather some feedback before proceeding further on. Currently the main class, unicode_string_adapter, provides a uniform way for code point access from various string containers without having to concern about the underlying encoding and code units. unicode_string_adapter will not handle higher level Unicode processing tasks such as abstract characters, as I plan to leave the functionality to another class called unicode_abstract_character which I will build later. At the moment my library only works under GCC with C++0x enabled, as I was focusing on the design issues first. I also understand that I have not adopted the Boost way of building the project. While I am now going to spend more time on fixing these issues, I hope that this discussion can have more focus on the design issues instead. Feel free to let me know any potential issues on the class design so that I can fix it before it is too late. Thank you! cheers, Soares Chen

2 2

Boost.Xint is not thread-safe
by Bryce Lelbach 20 Jun '11

20 Jun '11

The proposed Boost.Xint does not fulfill the thread-safety promises that it makes. The library uses a custom allocator (allocator_t), which uses global variables and does not protect them with a synchronization primitive. There appears to be no way to override the use of this custom allocator (the library just passes the user-specified STL allocator to allocator_t, and allocator_t uses the STL allocator to get memory). Can the author of this library please make the custom allocation strategy optional? Merely making allocator_t threadsafe wouldn't be a solution for me unless I could change the synchronization primitive that this allocator uses. I am using this library within a parallel C++ runtime that implements (among other things) a user-threading layer, so I would want to use one of our synchronization primitives, as OS-level (e.g. Boost.Thread) based synchronization would interfere with our user threading subsystem. I think the better solution here is to not tie Boost.Xint to a particular memory allocation scheme. The allocator in question is in <boost/xint/detail/policies.hpp> -- Bryce Lelbach aka wash boost-spirit.com px.cct.lsu.edu github.com/lll-project

3 4

Boost memory debugging allocator?
by Beman Dawes 19 Jun '11

19 Jun '11

Does Boost have a memory debugging and measuring allocator? Something like Howard describes in http://tinyurl.com/67764p7: >What will it do for you? > > * It will detect whole program memory leaks. > * It will detect "delete on new[]" or "delete[] on new" mismatch. > * It will detect double deletes and non-heap based pointer deletes. > * You can query it for how much memory is used at any point. > * Because of the previous point, you can bracket a function call > with usage queries to find out "memory leaked" for that call. > * You can query a new-based pointer for how much memory it points to. > * Performance is quite respectible for a memory debugger (but it is > not intended for release code). Thanks, --Beman

2 1

[1.47.0] OK to build RC for beta?
by Beman Dawes 19 Jun '11

19 Jun '11

The beta is scheduled for tomorrow. Unless someone objects, I'll build the RC this afternoon (i.e. after 5 PM UTC). --Beman

3 3

[heap] A performance test and some questions
by Thomas Klimpel 19 Jun '11

19 Jun '11

Hi Tim, Attached is a performance test that tries to immitate the priority_queue usage a fast marching algorithm. I actually wrote this performance test in 2005 while tuning a heap implementation (TSequentialHeap, not attached) used by a "real" fast marching algorithm. I tried to adapt this test for Boost.Heap now, but it looks like I haven't yet found out how to use the mutable heap interface optimally for this task. The most obvious symptom of this are the performance numbers I get when executing the performance test: $ g++ heaptest.cpp -O2 -DNDEBUG -Iboost_heap-449f378 -I/cygdrive/c/nobackup/boost_release -DHAVE_SEQ_HEAP $ ./a.exe Sanity Check Small TStaticHeap Test : passed Linear TStaticHeap Test : passed March TStaticHeap Test : passed Small TUglyHeap Test : passed Linear TUglyHeap Test : passed Small TSequentialHeap Test : passed Linear TSequentialHeap Test : passed March TSequentialHeap Test : passed Small b_heap Test : passed Linear b_heap Test : passed March b_heap Test : passed Small binomial_heap Test : passed Linear binomial_heap Test : passed March binomial_heap Test : passed Small d_ary_heap Test : passed Linear d_ary_heap Test : passed March d_ary_heap Test : passed Small fibonacci_heap Test : passed Linear fibonacci_heap Test : passed March fibonacci_heap Test : passed Performance Check for Linear Forward 297 ticks and 15952569 compares for TStaticHeap 296 ticks and 15952569 compares for TStaticHeap 95 ticks and 5495826 compares for TSequentialHeap 78 ticks and 5495826 compares for TSequentialHeap 999 ticks and 20929621 compares for b_heap 1032 ticks and 20929621 compares for b_heap 875 ticks and 7012461 compares for binomial_heap 906 ticks and 7012461 compares for binomial_heap 797 ticks and 16164008 compares for d_ary_heap 812 ticks and 16164008 compares for d_ary_heap 688 ticks and 5637046 compares for fibonacci_heap 688 ticks and 5637046 compares for fibonacci_heap Performance Check for Linear Backward 297 ticks and 22976046 compares for TStaticHeap 328 ticks and 22976046 compares for TStaticHeap 94 ticks and 5225203 compares for TSequentialHeap 93 ticks and 5225203 compares for TSequentialHeap 1125 ticks and 31971032 compares for b_heap 1125 ticks and 31971032 compares for b_heap 688 ticks and 5636875 compares for binomial_heap 718 ticks and 5636875 compares for binomial_heap 813 ticks and 19465560 compares for d_ary_heap 828 ticks and 19465560 compares for d_ary_heap 703 ticks and 5866500 compares for fibonacci_heap 703 ticks and 5866500 compares for fibonacci_heap Performance Check for March 1672 ticks and 93489201 compares for TStaticHeap 1734 ticks and 93489201 compares for TStaticHeap 921 ticks and 53507489 compares for TSequentialHeap 907 ticks and 53507489 compares for TSequentialHeap 5625 ticks and 121120384 compares for b_heap 5563 ticks and 121120384 compares for b_heap 6312 ticks and 73639894 compares for binomial_heap 6265 ticks and 73639894 compares for binomial_heap 4391 ticks and 92667621 compares for d_ary_heap 4375 ticks and 92667621 compares for d_ary_heap 4000 ticks and 39902719 compares for fibonacci_heap 4078 ticks and 39902719 compares for fibonacci_heap $ We can see that "fibonacci_heap" has always more than a factor two fewer comparisons than TStaticHeap (a simple text book binary heap implementation used as reference), but is always more than a factor two slower than TStaticHeap. And "fibonacci_heap" seems to be the fastest heap from Boost.Heap in this performance test, while TStaticHeap is still a factor two slower than the tuned TSequentialHeap. I guess the problem here is that I found no way around using "std::pair<value_type, value_type*>" as value_type for the heap, because I need to know the position in the bulk of the point with the smallest arrival time. But Dijkstra algorithm should be no different, I have to know the vertex in the graph with the shortest path. Independent of this, I also have a totally different question. There is a FIXME in line 233 of the test program, and if the following line is commented out, fibonacci_heap shows undefined behavior, ranging from segmentation fault to failing the Sanity Check. Here is the code surrounding the FIXME: std::size_t Set_Size ( std::size_t lSize_p) { if (!m_tHeap.empty()) { exit(1); } // FIXME: I don't understand why the fibonacci_heap shows undefined behavior if clear() is not called. m_tHeap.clear(); m_tBackpointer.clear(); m_tBackpointer.resize(lSize_p); return lSize_p; } You can see that the heap is actually empty, so why is calling clear() on the empty heap important in case of a fibonacci_heap? Regards, Thomas

3 12