- Boost - lists.boost.org

[review] a mini-review of containers
by Thorsten Ottosen 12 Aug '11

12 Aug '11

Hi Ion & John, I apologize for not having time to do a full review. I base these comments mainly on the documentation. I have been using the flat_map/flat_set stuff for years, both in my own PhD work and in production code in my company. A. I find the motivation sufficient; I guess the new allocator concept in C++11 would allow one to use interprocess allocators, but as this won't work with older compiler, I can see the need. Also, since the standard does not e.g. guarantee nothrow of default constructors, this library provides an escape route if one wishes to have portable code. The recursive structure is also a nice feature. B. The new containers are very useful. I have not used stable vector before, but I note that boost::ptr_vector provides similar guarantees. C. slist should probably be called forward_list like in the new standard, and should probably be interface compatible with the standard design. D. I skimmed some of the unit-tests. I saw that some sections are commented out. Maybe a little more testing could be done. E. I didn't look at the map/set implementation; do you use the same optimization as Boost.MultiIndex that saves the color in the parent pointer (as a bit). F. I noticed that you use std::reverse_iterator. Why not use boost::reverse_iterator? IIRC, it has some minor benefits. G. flat_xxx. (a) We already discussed the issue of exposing the underlyng container. I think that would be most natural, and provides use with an escape hatch when they need it. (b) I think all these containers should allow one to decide the wrapped sequence. I have several types of sequences I would like to be able to use. Sure it takes some work to handle alocators and such, but it makes these much more useful IMO. (c) At some point, long time ago, I suggested that one should be able to construct a set/map with an already sorted sequence. This was based on actual use cases; one sometimes have access to an already sorted sequence. I think the most elegant way to support this would be to make a new constructor that forwards; that is, use the same approach as boost::optional such that we can say flat_xxx cont( boost::in_place(...) ); ------------------------------------- So, should this library be accepted into Boost? Yes. But I would like to see G.b and G.c addressed first. kind regards Thorsten

2 1

[iostreams] null_sink slower than array_sink
by Daniel Larimer 12 Aug '11

12 Aug '11

I was thinking about using boost::iostreams in place of my own 'array stream', but was surprised by the poor performance. When doing RPC calls, I often use the following pattern: a) calculate buffer space required to serialize arguments b) allocate buffer space c) serialize into buffer I use a stream type with an interface of write(),read(), putc(), getc() etc similar to iostreams. In doing some basic tests serializing a struct I get the following numbers: stringstream: 2.4e6 times/sec stream<array_sink>: 3.2e6 times/sec stream<null_sink>: 1.5e6 times/sec mystream<char*>: 8.7e6 times/sec (fixed size array) mystream<size_t>: 1.07e7 times/sec (similar to null_sink, but tracks bytes written) Perhaps this is the difference between polymorphic and static method calls? In any case, there is no reason for stream<null_sink> to take twice as long as array_sink as there are no memory copies, all write should be no-ops. It would probably be useful to add a size_sink that can be used to track the number of bytes written and thus avoid dynamically resizing buffers.

1 0

[iostreams] basic_buffer int usage
by Judson Weissert 12 Aug '11

12 Aug '11

Hello, I was working with some boost::iostreams code for compressing and uncompressing streams of data when I encountered an interesting type conversion warning. Within buffer.hpp in the iostreams library (boost/iostreams/detail folder), the constructors accept an int buffer_size and assign it to std::streamsize size_. Upon further investigation, I learned that this was intentional as of r27330 (Log msg: "made all buffer size params ints so that int literals can be used without interfering with overload resolution"). Here is some example code that triggers the same warnings I was receiving: // Tested with boost 1.46.1 // Compiler Microsoft VC2010 SP1. // Compiled with cl /EHsc /W3 repro.cpp #include <boost/iostreams/copy.hpp> #include <boost/iostreams/device/array.hpp> #include <boost/iostreams/filtering_streambuf.hpp> int main (int, char *[]) { static const char b[] = { 'A', 'B', 'C' }; boost::iostreams::array_source as (b, 3); boost::iostreams::filtering_streambuf <boost::iostreams::input> in; in.push (as); // This line generates a 'std::streamsize' to 'int' warning. // See also boost/iostreams/detail/buffer.hpp boost::iostreams::copy (in, std::cout); return 0; } I am not completely sure what overload resolution is taking place, I only see a default constructor and a constructor that takes a buffer size. What am I missing? I posted approximately a week ago on this topic, but I don't think it made it to the list. Forgive me if this is a repost, I modified the content of the message since I learned more about the subject in the meantime. Thanks, Judson Weissert

2 1

[numeric] Adding numeric_cast_traits.hpp on 08/11 (today) breaks trunk
by Edward Diener 12 Aug '11

12 Aug '11

The addition and integration of numeric_cast_traits.hpp to boost numeric is breaking compiles on the trunk which use numeric. I am attempting to compile quickbook, only to see: gcc.compile.c++ ..\..\bin.v2\tools\quickbook\src\gcc-mingw-4.6.0\release\link-st atic\quickbook.o gcc.compile.c++ ..\..\bin.v2\tools\quickbook\src\gcc-mingw-4.6.0\release\link-st atic\actions.o In file included from ..\../boost/numeric/conversion/numeric_cast_traits.hpp:28: 0, from ..\../boost/numeric/conversion/cast.hpp:34, from ..\../boost/lexical_cast.hpp:40, from src\actions.cpp:19: ..\../boost/numeric/conversion/detail/numeric_cast_traits.hpp:77:31: error: miss ing binary operator before token "(" ..\../boost/numeric/conversion/detail/numeric_cast_traits.hpp:82:31: error: miss ing binary operator before token "(" etc. The same errors occur with msvc-10.0. These changes need to be fixed or reverted. Too many things depend on numeric_cast for this to remain broken.

4 8

[fusion] pop_back doesn't work on fwd sequences
by Eric Niebler 12 Aug '11

12 Aug '11

The documented requirement of pop_back are wrong. The docs say that pop_back works on Forward Sequences, however the following does not compile: // ERROR fusion::list<int, int> l(1, 2); fusion::pop_back(l); The problem is that the implementation of pop_back uses prior, which only works on Bidirectional Sequences. That's merely a doc problem, but this is a more serious problem: // ERROR fusion::pop_back(fusion::pop_back( fusion::push_back(fusion::push_back(fusion::nil(), 1), 2))); A sequence created by push_back is a Forward Sequence, which means you can't call pop_back on it. I think that's a serious shortcoming. Fusion needs something like MPL's Back Extensible and Front Extensible concepts. http://www.boost.org/doc/libs/1_47_0/libs/mpl/doc/refmanual/back-extensible… Unfortunately, this would likely require a redesign of the whole (push|pop)_(front|back) mechanism. -- Eric Niebler BoostPro Computing http://www.boostpro.com

3 21

[Containers] Review
by Phil Endecott 12 Aug '11

12 Aug '11

Dear All, Following are some comments about Ion's proposed Boost.Containers. I have not really reviewed the code, but frankly that doesn't seem necessary: Ion knows what he's doing, much of this code has already been in Boost for a while as part of Interprocess, and much of it is designed to implement standard interfaces. I'll confine my comments to a few words about the documentation, and some observations about the "flat" containers. Regarding the documentation, I believe that it would benefit from: - The "Acknowledgements" page is currently empty. There are various (c) notices in the source referring to sources from which parts of the code may have come. This page should clarify these sources, including any cases where the original code has now all been replaced, and assert that the licenses are all in order. It should also point out the history of the code in Boost, i.e. that parts were previously in Boost.Interprocess, so that anyone with previous exposure to the Interprocess containers is not confused. - A few lines of rationale for stateful allocators would be useful, i.e. pointing out that although the std::allocator has a typedef for pointer the containers can assume it is T*, and the implications of that. (I dealt with all this back in about 2004, and it took me a long time to get up-to-speed with the issues.) - Similarly, some rationale for string (and pointing out how it differs from std::string in the common implementations) would be useful. (Now, I can't even find where it says that it is non-COW. I know that I've seen that written somewhere. A page specifically about string shown on the top-level table of contents would be appropriate.) - The Doxygen reference docs seem to jump to the header docs from the table of contents; I think it would be more useful to jump primarily to the classes. Is this the same issue that I saw in the last review? Regarding the "flat" containers, I've previously posted about this in a couple of threads on this list. I have used this sort of structure in two applications recently: - In the first case, I store read-only (key,value) data in a binary file. I have a utility that prepares this file offline by inserting into a vector<pair<>>. I then sort it, and save the contents of the vector in the file. In the program that uses the data, I memory-map the file. I then have an adaptor class that takes a pair of pointers to the begin and end of the mapped data and permits read-only access like Ion's flat_multimap<>. - In the second case, I have an insert-only key-value data structure. New data is inserted in batches. I have a vector<pair<>> and insert new data at the end; at the end of each batch, I sort the new values and merge them into the body of the vector using std::inplace_merge. Neither of these cases can be implemented efficiently using the current containers. Doing so would need: - Access to the underlying container, at least for reading. - An "adaptor" version that could wrap a pair of pointers to raw memory, or more generally a pair of iterators, at least for reading. - Some sort of efficient batched insert mode. Regarding the batched insert, we have previously discussed the complexity of inserting a range. Fundamentally, however, I don't think it is acceptable to have efficient insertion ONLY in the case of the insert(begin,end) method: it is too common to want to insert several values in a loop without creating a temporary container. I'm not aware of any established (i.e. std:: or boost::) pattern for doing this: class flat_container { void insert(val); // appends at the end of the vector void commit(); // merges new values into the body of the vector }; - Between calling insert() and calling sort(), what do lookups do? Undefined? Only look at old values? Sort-on-demand? - Is there also an "insert one" method? How are the variants named? - What about erase()? - How about a "batch" or "transaction" object?: flat_container c; { flat_container::insert_batch b(c); b.insert(data1); b.insert(data2); } // b's dtor merges new values. A further interesting case is when the new values are already sorted, because insertion can be more efficient in this case: void insert_sorted(iter first, iter last) { resize vector to make space for new items for each new item in reverse order { find the position where it should be inserted using binary chop move old items after that point forward move the new item in behind them } } I could imagine a general insert_batch and a specialised insert_sorted_batch, for example. Anyway, this is all just food for thought really. It would be interesting to hear from other people who have used data structures like this. In my own code I have taken a rather ad-hoc approach, but that is the nature of custom vs. library development: to be useful, a library needs to try to second-guess the requirements of all potential users, yet do so without becoming too complex for anyone to learn. Hopefully there will be some more discussion about some of this, but as far as the review is concerned we should allow Ion to decide what he eventually commits. Regards, Phil.

6 8

[containers] remarks and questions
by Pierre Morcello 12 Aug '11

12 Aug '11

Hello Ion, This is not a review. I took 3 hours to read the docs, checks some tests, try to check some sources, but I am still not used to read so few comments in the code. I played a little with the library then, tried to encapsulate some std::auto_ptr<X> in the new containers and things like that. Based on that very little experience, I would like to share some thoughts and ask a few questions on the proposed boost.containers library. 1/ I would really appreciate that the docs were more complete, at least for the technical part. => ex : "flat_map : more memory friendly and with faster searches" => In what way? is the algorithm complexity lesser than previous systems? or do you mean that contiguous memory is more cache-friendly? => do you provide different kernel implementations? => is there a paper on the subject? => Is there an evaluated algorithm complexity for the stable_vector? => is memory contiguous like a std::vector? can I use memcpy on several elements? These are just examples of questions that I expect to be answered by the docs. EDIT : I read proposition to embed elements of Joaquin M Lopez Munoz's blog. This is exactly that kind of informations I am looking for. => For the tree class, I can't remember any tree interface in the std. Could you point me to some informations ? Sorry If I miss something obvious. 2/ I was surprised (in a good way) to see some Andrei Alexandrescu's code in the library. Will the Loki licence be shipped now with boost? (This is not a problem for me). 3/ A few tests might be added. ex: Test the fact the vector usually are contiguous in memory. I can write this one if you are interested. 4/ The 'move aware' containers are nice to use but as a drawback We are forced to use macro to define the types using the 'move' semantics. What other container libraries can this work be related to? There are some examples of containers requiring the value_type to support only the "defaut constructor + a swap() function". This is a concept I would really appreciate to see in boost.containers. In that case, I would very happily use this library. Otherwise I think I will stick with other containers classes. 5/ "The aim of the library is to offers advanced features" Is the proposed Boost.containers also an effort towards development of new features for containers? If that is the case, then what are the plans for the future ? Is there a roadmap? To sum up : I am surprised that such a container library was not already integrated in boost. This should be a nice addition. But at the moment I don't think I would use it: my main interest would be for the value_type supporting "defaut constructor + a swap() function" to be added to the library. I also would like more detais in the documentation. In my humble opinion, it would also be easier for exterior people to learn from and to contribute to your library if there were more comments in the code. I congratulate you and the other authors for your work and efforts, and wish you the best for the review. Best regards, Pierre Morcello -- View this message in context: http://boost.2283326.n4.nabble.com/boost-containers-remarks-and-questions-t… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 3

[preprocessor] ifdef equivalent inside a macro, is it possible?
by damien benoist 12 Aug '11

12 Aug '11

Hi all, Would there be a way to do some "ifdef" inside a macro? Could be in the form of a macro taking 3 args, - 1st being the macro to test the existance of, - 2nd being the value to expand in case 1st arg is a defined macro - 3rd being the value to expand in case 1st arg is not a defined macro Exemple: #define DUMMY_MACRO1 foo1 // next is commented out and not defined // #define DUMMY_MACRO2 foo2 PP_IFDEF(DUMMY_MACRO1, DUMMY_MACRO1, bar1) // would expand to foo1 PP_IFDEF(DUMMY_MACRO2, DUMMY_MACRO2, bar2) // would expand to bar2 Seems impossible to me, but boost/preprocessor does so many things that seemed impossible to me. Maybe someone will have some more magic... Thanks. Damien.

4 11

[proto] RValue reference support?
by John Maddock 12 Aug '11

12 Aug '11

Does proto have any support for rvalue references in terminals? I'm thinking that if you know that you're assigning an expression involving an rvalue-reference as a terminal, then there are some optimizations that can be performed that aren't otherwise possible. Thanks, John.

5 11

[interprocess] detail/move.hpp macros conflict with boost/move/move.hpp
by Daniel Larimer 11 Aug '11

11 Aug '11

I am attempting to include my own <boost/move/move.hpp> header, but the macros conflict with <boost/interprocess/detail/move.hpp>. It would seem to me that boost interprocess should 'namespace' the macros like it did the types so that when boost/move is included there are no conflicts. When will Boost.Move be included in an official release? Dan

1 0