- Boost - lists.boost.org

[graph][iterators] csr graph and reverse iterator problem
by Takatoshi Kondo 11 Sep '11

11 Sep '11

Hi, All I'm using Boost.Graph and Boost.Iterators. When I use the compressed_sparse_row_graph with reverse_iterator, I ran into a problem. When I dereference the reverse_iterator of compressed_sparse_row_graph's iterator, invalid memory access occurs. On g++ version 4.6.0 with -Os option, The output is below. 0 1 1 0 0 1 134526756 3218710936 1 0 And I also checked where the invalid memory access occurred using valgrind. ==2341== Invalid read of size 4 ==2341== at 0x8048DE7: test_csr_graph() (rev_iter.cpp:45) ==2341== by 0x8048FB3: main (rev_iter.cpp:59) ==2341== Address 0xbe825f88 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==2341== 1 ==2341== Invalid read of size 4 ==2341== at 0x8048E31: test_csr_graph() (rev_iter.cpp:46) ==2341== by 0x8048FB3: main (rev_iter.cpp:59) ==2341== Address 0xbe825f88 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==2341== This result indicates the code below is suspicious. std::cout << *rib++ << std::endl; // NG Why? Line 45 std::cout << *rib++ << std::endl; // NG Why? Line 46 But... boost::tie(ib, ie) = boost::vertices(g); std::cout << *--ie << std::endl; // OK std::cout << *--ie << std::endl; // OK It is OK. Here is the source code that reproduces the problem. ------------ begin ------------- #include <boost/iterator/reverse_iterator.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/compressed_sparse_row_graph.hpp> #include <iostream> #include <cassert> void test_graph() { typedef boost::adjacency_list<> graph_type; graph_type g(2); boost::graph_traits<graph_type>::vertex_iterator ib, ie; { boost::tie(ib, ie) = boost::vertices(g); std::cout << *ib++ << std::endl; // OK std::cout << *ib++ << std::endl; // OK assert(ib == ie); } { boost::tie(ib, ie) = boost::vertices(g); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rib(ie); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rie(ib); std::cout << *rib++ << std::endl; // OK std::cout << *rib++ << std::endl; // OK assert(rib == rie); } } void test_csr_graph() { typedef boost::compressed_sparse_row_graph<> graph_type; std::pair<int, int> e(0, 1); std::pair<int, int> es[] = { e }; graph_type g(boost::edges_are_unsorted, &es[0], &es[1], 2); boost::graph_traits<graph_type>::vertex_iterator ib, ie; { boost::tie(ib, ie) = boost::vertices(g); std::cout << *ib++ << std::endl; // OK std::cout << *ib++ << std::endl; // OK assert(ib == ie); } { boost::tie(ib, ie) = boost::vertices(g); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rib(ie); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rie(ib); std::cout << *rib++ << std::endl; // NG Why? Line 45 std::cout << *rib++ << std::endl; // NG Why? Line 46 assert(rib == rie); } { boost::tie(ib, ie) = boost::vertices(g); std::cout << *--ie << std::endl; // OK std::cout << *--ie << std::endl; // OK assert(ib == ie); } } int main() { test_graph(); test_csr_graph(); } ------------ end ------------- Why does the invalid memory access occur? Am I misusing the libraries? Thanks, Takatoshi

5 10

[type_erasure] ODR violation promotion
by Vicente J. Botet Escriba 10 Sep '11

10 Sep '11

Hi Steven, I'm interested in your TypeErasure library. Where can I find the on going version? The example for concept map seams not complete, as the specialization for less_than_comparable<std::type_info> is not used in any type erasure type. Could you complete it? Before the Boost.Conversion review someone signaled that the Boost.Conversion review was promoting ODR violations as two libraries could specialize a conversion for types S and T and make them incompatible for an end user as the ODR is violated. I think that your library suffer from the same issue, when two libraries need to specialize a concept provided by the library for a 3rd part concrete class using the proposed concept map mechanism. Do you agree? If not, how do the library avoids this kind of issue? Best, Vicente

3 10

[fusion] Algorithm/auxillary documentation
by Daniel James 10 Sep '11

10 Sep '11

Hi, The generated documentation for the algorithm/auxillary section hasn't been checked in. It should be at: http://svn.boost.org/svn/boost/trunk/libs/fusion/doc/html/fusion/algorithm/… http://svn.boost.org/svn/boost/trunk/libs/fusion/doc/html/fusion/algorithm/… Daniel

4 10

[Review] Boost.Endian i/o
by Vicente J. Botet Escriba 10 Sep '11

10 Sep '11

Hi, previous releases of Boost.Endian included a binary stream. Is there something else that can be used to get the same behavior? Best, Vicente

2 1

[Endian] Unaligned fields in packed structs
by Phil Endecott 10 Sep '11

10 Sep '11

Dear All, One of my all-time worst bugs was due to calling htonl() on an unaligned field in a packed struct. It worked in debug mode but not in production code, and there were no compiler warnings about the broken alignment requirement. So I thought I'd try this: inline void inplace_byteswap(uint32_t& val) { val = (val>>24) | ((val>>8) & 0x0000ff00) | ((val<<8) & 0x00ff0000) | (val<<24); } struct S { uint16_t a; uint32_t b; } __attribute__ ((packed)); int main() { S s; s.b = 0x12345678; byteswap(s.b); } This fails to compile: "error: cannot bind packed field ‘s.S::b’ to ‘uint32_t& {aka unsigned int&}’". So it's good that it doesn't just fail unpredictably at runtime like my old nightmare, but it's not ideal. If instead I write: inline uint32_t byteswap(uint32_t val) { return (val>>24) | ((val>>8) & 0x0000ff00) | ((val<<8) & 0x00ff0000) | (val<<24); } ... s.b = byteswap(s.b); ... then of course it does work; the unaligned accesses don't "escape" from where the compiler knows about them and can apply fixups. Anyway, before I tried this I was already wondering about the choice of function signatures: void endian::reorder(T&); // in-place byteswap void endian::reorder(T src, T& dest); // out-of-place byteswap What is the rationale (or precedent) for these and not T endian::reorder(T); ? If sin(theta) returns its result, why shouldn't reorder(val) do so too? Regards, Phil.

3 4

[boost/foreach] What is wrong with BOOST_FOREACH(const std::string &name, m_modules)?
by Demetrio Car 10 Sep '11

10 Sep '11

I am trying to compile this example http://www.boost.org/doc/libs/1_42_0/doc/html/boost_propertytree/tutorial.h… and I am getting the error "/usr/local/boost_1_47_0/boost/property_tree/detail/ptree_implementation.hpp:795:54: error: request for member ‘put_value’ in ‘tr’, which is of non-class type ‘bool’" in this line: BOOST_FOREACH(const std::string &name, m_modules){ pt.put("debug.modules.module", name, true); } My full error message is: make all Building file: ../src/Boost_property_tree.cpp Invoking: GCC C++ Compiler g++ -I/home/mori/Demetrio/WSs/Test/VanManagerParser/json_spirit -I/usr/local/boost_1_47_0/ -I/usr/local/boost_1_47_0/boost/spirit -I/usr/local/curl-7.21.7/ -O0 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF"src/Boost_property_tree.d" -MT"src/Boost_property_tree.d" -o "src/Boost_property_tree.o" "../src/Boost_property_tree.cpp" ../src/Boost_property_tree.cpp: In member function ‘void debug_settings::save(const std::string&)’: ../src/Boost_property_tree.cpp:80:5: error: invalid initialization of reference of type ‘std::string&’ from expression of type ‘const std::basic_string<char>’ In file included from /usr/local/boost_1_47_0/boost/property_tree/ptree.hpp:516:0, from ../src/Boost_property_tree.cpp:4: /usr/local/boost_1_47_0/boost/property_tree/detail/ptree_implementation.hpp: In member function ‘void boost::property_tree::basic_ptree<Key, Data, KeyCompare>::put_value(const Type&, Translator) [with Type = std::basic_string<char>, Translator = bool, Key = std::basic_string<char>, Data = std::basic_string<char>, KeyCompare = std::less<std::basic_string<char> >]’: /usr/local/boost_1_47_0/boost/property_tree/detail/ptree_implementation.hpp:817:13: instantiated from ‘boost::property_tree::basic_ptree<K, D, C>& boost::property_tree::basic_ptree<Key, Data, KeyCompare>::put(boost::property_tree::basic_ptree<Key, Data, KeyCompare>::path_type&, const Type&, Translator) [with Type = std::basic_string<char>, Translator = bool, Key = std::basic_string<char>, Data = std::basic_string<char>, KeyCompare = std::less<std::basic_string<char> >, boost::property_tree::basic_ptree<Key, Data, KeyCompare>::path_type = boost::property_tree::string_path<std::basic_string<char>, boost::property_tree::id_translator<std::basic_string<char> > >]’ ../src/Boost_property_tree.cpp:81:50: instantiated from here /usr/local/boost_1_47_0/boost/property_tree/detail/ptree_implementation.hpp:795:54: error: request for member ‘put_value’ in ‘tr’, which is of non-class type ‘bool’ make: *** [src/Boost_property_tree.o] Error 1 **** Build Finished ****

4 5

[Endian] Review / Comments
by Tim Blechmann 10 Sep '11

10 Sep '11

hi, documentation the documentation in general is pretty short, but sufficient: the concepts of the library are easy, so there is no need to go into more details. however i would prefer if the documentation uses quickbook/boostbook. most of the recent boost libraries have a very similar layout of the documentation, but the boost.endian docs do not follow these conventions. also the docs for `conversion functions' and for `integer types' are separate. personally i'd prefer if they could go into the same document, maybe having a structure like: introduction, integer types, conversion functions, examples, reference (preferably doxygen-generated). section `experience': this section gives no insights for people who use or read the code. it mainly tells: "we are not the first and the domain of the library is important.". imo this section can be removed (maybe the part that it is not related to any c library can go to the `design considerations' section "motivating use cases": this is more a marketing blurb/testimonial. maybe this could be changed to a section about possible use cases, listing `communicating between different devices' and `reading/writing of binary file formats'. provided files i suppose, the msvc project file will go away when the library is merged into trunk. besides, i'd suggest to move "boost/endian/support/timer.hpp" to "lib/endian/support", because it only seems to be used by the benchmarks. testsuite scoped_enum_emulation_test.cpp ... not related to boost.endian, please remove endian_operations_test.cpp and endian_in_union_test.cpp ... maybe rename from _test.cpp to _compile_test.cpp? they don't seem to do any run-time tests. they also should not include <cassert> since no assertion statement is needed, this might speed up the compilation time of the testsuite by something like 50ms ;) conversion functions personally, i find the interface for the conversion functions rather odd, as they don't actually return a value, but take a reference to the return value. so they cannot really be used in a functional style. if the reorder functions would have a signature like: int16_t reorder(int16_t x); it would be possible to use it as unary operator e.g. in with std::transform and the like. this would also avoid the need for both in-place and out-of- place functions. iac, i don't see a reason for the in-place functions. for the reason, see below. performance considerations the current implementation seems to perform horribly on x86_64 hardware. i ran phil's nice benchmark program inside the `perf' profiler on my core i7 920 ("g++-4.6 -O3 -std=gnu++0x -march=native"), where the algorithm takes MUCH more time than htonl, gcc's builtins or a mask/shift implementation. the main reason seems to be a huge amount of byte-wise load/stores, which lead to a huge number of stalls. a mask/shift implementation will be computed completely in registers, making use of instruction-level parallelism on out- of-order cpus and requiring less memory transfers. as a side effect, boost.endian will compose much better, when using the reorder functions on values, which are already in registers, or which need to be placed in registers later in the algorithm. modification for bitmasks: return (src<<24) | ((src<<8) & 0x00ff0000) | ((src>>8) & 0x0000ff00) | (src>>24); modification for boost.endian types (assuming little-endian hardware): uint32_t n; boost::detail::store_big_endian<uint32_t, sizeof(uint32_t)>(&n, src); return n; USE_GCC_BUILTIN: Performance counter stats for './a.out': 986.666145 task-clock # 1.000 CPUs utilized 0 context-switches # 0.000 M/sec 7 CPU-migrations # 0.000 M/sec 307 page-faults # 0.000 M/sec 2,637,245,698 cycles # 2.673 GHz 633,384,188 stalled-cycles-frontend # 24.02% frontend cycles idle 281,512,771 stalled-cycles-backend # 10.67% backend cycles idle 6,007,671,727 instructions # 2.28 insns per cycle # 0.11 stalled cycles per insn 1,001,451,092 branches # 1014.985 M/sec 31,112 branch-misses # 0.00% of all branches 0.987133571 seconds time elapsed USE_HTONL Performance counter stats for './a.out': 938.226124 task-clock # 1.000 CPUs utilized 0 context-switches # 0.000 M/sec 3 CPU-migrations # 0.000 M/sec 307 page-faults # 0.000 M/sec 2,507,753,527 cycles # 2.673 GHz 504,694,743 stalled-cycles-frontend # 20.13% frontend cycles idle 53,006,181 stalled-cycles-backend # 2.11% backend cycles idle 6,006,376,475 instructions # 2.40 insns per cycle # 0.08 stalled cycles per insn 1,001,180,324 branches # 1067.099 M/sec 23,212 branch-misses # 0.00% of all branches 0.938684989 seconds time elapsed USE_BEMAN Performance counter stats for './a.out': 7494.906291 task-clock # 1.000 CPUs utilized 0 context-switches # 0.000 M/sec 12 CPU-migrations # 0.000 M/sec 307 page-faults # 0.000 M/sec 20,033,609,533 cycles # 2.673 GHz 15,018,356,865 stalled-cycles-frontend # 74.97% frontend cycles idle 11,372,397,445 stalled-cycles-backend # 56.77% backend cycles idle 15,030,059,048 instructions # 0.75 insns per cycle # 1.00 stalled cycles per insn 1,005,600,935 branches # 134.171 M/sec 88,848 branch-misses # 0.01% of all branches 7.497572144 seconds time elapsed USE_BITMASK Performance counter stats for './a.out': 986.085196 task-clock # 0.999 CPUs utilized 0 context-switches # 0.000 M/sec 0 CPU-migrations # 0.000 M/sec 307 page-faults # 0.000 M/sec 2,635,658,193 cycles # 2.673 GHz 631,672,783 stalled-cycles-frontend # 23.97% frontend cycles idle 269,536,819 stalled-cycles-backend # 10.23% backend cycles idle 6,008,101,435 instructions # 2.28 insns per cycle # 0.11 stalled cycles per insn 1,001,523,773 branches # 1015.656 M/sec 31,020 branch-misses # 0.00% of all branches 0.986601856 seconds time elapsed USE_TYPES Performance counter stats for './a.out': 7121.796026 task-clock # 1.000 CPUs utilized 0 context-switches # 0.000 M/sec 12 CPU-migrations # 0.000 M/sec 307 page-faults # 0.000 M/sec 19,035,784,897 cycles # 2.673 GHz 15,019,771,466 stalled-cycles-frontend # 78.90% frontend cycles idle 1,182,185,735 stalled-cycles-backend # 6.21% backend cycles idle 14,032,012,033 instructions # 0.74 insns per cycle # 1.07 stalled cycles per insn 1,005,916,931 branches # 141.245 M/sec 84,751 branch-misses # 0.01% of all branches 7.124340206 seconds time elapsed What is your evaluation of the potential usefulness of the library? very important, very useful How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? roughly 3 hours, reading code, documentation, running some benchmarks. besides, i'm using an older version of the library for about 2 years without having any problems. Are you knowledgeable about the problem domain? yes Do you think the library should be accepted as a Boost library? the library should be accepted, if (a) the interface of the conversion functions is changed (b) the performance can be improved (c) the documentation integrates better with the rest of the boost documentation. cheers, tim

5 8

[Review] Boost.Endian - template requirements and scope
by Vicente J. Botet Escriba 10 Sep '11

10 Sep '11

Hi, I have not found the requiremenst of the endian class template parapeter T and conversion functions. What are they? Could them be added to the documentation? I have not found a tutorial on how to use the endian conversions. Could you give an example that shows how easy is to use them with UDT? Collections of UDT? Could the user overload the conversion functions for UDT? While the predefined endian types are useful I guess that the user could instantiate the endian class with a UDT, isn't it? Could you post a working example and add it to the documentation? The scope of Boost.Endian is integer types. Aren't floating point types and endianness related? If the scope of the library is limited to integers, maybe Integer.Endian could be a better name? Best, Vicente

3 5

[proto] proto::as_child potentially unsafe?
by John Maddock 09 Sep '11

09 Sep '11

Following the guide here: http://www.boost.org/doc/libs/1_47_0/doc/html/proto/users_guide.html#boost_… I fell into a nasty trap: as_child stores it's argument as a reference, and as far as I can tell there is no way to force it to store by value, unless you apply deep_copy to the whole expression tree (not just the one child created with as_child). I found this when trying to protoize a function that looked like: template <class Exp> some-return-type foo(const Exp&, int i); In which the value "i" was returned as a reference to a value on the stack which then went out of scope :-( Even if the function has a signature such as: template <class Exp> some-return-type foo(const Exp&, const int& i); There is still a potential trap, because you don't know where "i" came from and when it will go out of scope - OK so the result of the expression will *usually* be calculated before that happens - but you never know. IMO I think this trap needs better documenting, because the section in question (and text preceding it) read to me "as if" arguments to as_child were stored by value. I'm sure I'm reading that wrong.... but you know ;-) John.

2 1

[Endian] Proposed endian integer types
by Phil Endecott 09 Sep '11

09 Sep '11

Dear All, I have had a quick look at the proposed endian::big|littleN_t types. A couple of comments: - I was expecting to find that these types would use the conversion functions that I've already looked at at the lowest level, so that optimisations made to those functions would be useful here too. But instead, these classes seem to use their own byte-shuffling code. This seems like an odd design. - I'm not convinced that these types cause the conversion to happen at the optimum time. For example: struct file_header { big32_t n_things; .... }; int main() { file_header h; h.n_things = 0; while (....) { ++h.n_things; .... } write(h); .... } Here the conversion is happening twice every time that n_things is incremented. It would be better to instead do the conversion once, just before the file_header is written. The same thing applies in reverse when reading from a file. (Surely this is the most common use-case?) I have been wondering if there is a better design that can avoid this. If we had some sort of struct introspection, we could store the fields in native byte order and then template <typename T> T external_representation(const T& t) { T res(t); for each field of T { res.field.reorder(); } } ++h.n_things; // cheap write(external_representation(h)); // conversion happens once here. Of course we don't have introspection of structs so we can't do that. Maybe someone else has another idea. Regards, Phil.

3 2