November 2014 - Boost-users

Thread prioritization
by Alexander Carôt 20 Nov '14

20 Nov '14

Hello all, is it correct that boost does not offer thread prioritization ? I am dealing with an application with a number of threads, which all depend on the realtime-scheduled sound card callback thread. These threads must have the same realtime scheduling priority. Is there a way to achieve this ? Thanks in advance, best Alex >

3 3

[BGL] [push_relabel_max_flow] multigraphs ?
by Pablo Madoery 20 Nov '14

20 Nov '14

I was wondering if the push_relabel_max_flow algorithm can be used in multigraphs. I mean, can I have two vertices joined by two edges: one in a direction an the other in the opposite direction with equal capacities ( 1000 for example ). It is clear in the documentation that the reverse edge must exist for each edge in the graph, so there must be 4 edges in the case I am describing. but the question is: does the algorithm works properly for this case ?

1 0

[BGL] [push_relabel_max_flow]
by Pablo Madoery 19 Nov '14

19 Nov '14

Hello, I am having trouble using the push_relabel_max_flow algorithm when i put std::numeric_limits<double>::max() as capacity attribute in some edges. is there a maximum value that I can use as capacities. which ?. This is the example I am using : #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/push_relabel_max_flow.hpp> #include <boost/graph/graphviz.hpp> using namespace std; using namespace boost; struct vertexInfo { }; struct edgeInfo { double capacity; double residualCapacity; double flow; adjacency_list_traits<vecS, vecS, bidirectionalS>::edge_descriptor rev; edgeInfo() { residualCapacity = 1000; } }; typedef adjacency_list<vecS, vecS, bidirectionalS, vertexInfo, edgeInfo> Graph; typedef Graph::edge_descriptor edge_d; const char* names[] = { "SV", "L1", "L2", "L3", "L4", "ET"}; template<typename Vertex> void create_edge(Graph& g, Vertex v0, Vertex v1, double capacity) { //the algorithm requires that for each edge u-v in the graph, the edge v-u also exists Graph::edge_descriptor ep0 = (add_edge(v0, v1, g)).first; Graph::edge_descriptor ep1 = (add_edge(v1, v0, g)).first; g[ep0].capacity = capacity; g[ep0].rev = ep1; g[ep1].capacity = 0; // the capacity of v-u needs to be 0 g[ep1].rev = ep0; } int main() { Graph graph; Graph::vertex_descriptor SV = add_vertex(graph); Graph::vertex_descriptor L1 = add_vertex(graph); Graph::vertex_descriptor L2 = add_vertex(graph); Graph::vertex_descriptor L3 = add_vertex(graph); Graph::vertex_descriptor L4 = add_vertex(graph); Graph::vertex_descriptor ET = add_vertex(graph); create_edge(graph, SV, L1, std::numeric_limits<double>::max()); create_edge(graph, SV, L2, std::numeric_limits<double>::max()); create_edge(graph, SV, L3, std::numeric_limits<double>::max()); create_edge(graph, SV, L4, std::numeric_limits<double>::max()); create_edge(graph, L3, ET, 1000); create_edge(graph, L4, L3, 1000); create_edge(graph, L2, L3, 1000); create_edge(graph, L1, L2, 1000); // arcos de vuelta create_edge(graph, L3, L4, 1000); create_edge(graph, L3, L2, 1000); create_edge(graph, L2, L1, 1000); std::cout << "Max flow: " << push_relabel_max_flow(graph, SV, ET, get(&edgeInfo::capacity, graph), get(&edgeInfo::residualCapacity, graph), get(&edgeInfo::rev, graph), get(boost::vertex_index, graph)) << std::endl; graph_traits<Graph>::vertex_iterator vi, vi_end; graph_traits<Graph>::out_edge_iterator ei, ei_end; cout.precision(20); for (tie(vi, vi_end) = vertices(graph); vi!= vi_end; ++vi) { for (tie(ei, ei_end) = out_edges(*vi, graph); ei != ei_end; ++ei) { graph[*ei].flow = graph[*ei].capacity - graph[*ei].residualCapacity; if (graph[*ei].capacity > 0) { std::cout << names[*vi] << " " << names[target(*ei, graph)] << " " << (graph[*ei].capacity - graph[*ei].residualCapacity) << "/" << graph[*ei].capacity << std::endl; } } } cout<<"end"<<endl; return 0; } ----------------------------------------------------------------------------------------------------------------------------- And this is the exception: /home/madoery/boost_1_55_0/boost/graph/push_relabel_max_flow.hpp:706: typename boost::property_traits<CapacityEdgeMap>::value_type boost::push_relabel_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, VertexIndexMap) [with Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, vertexInfo, edgeInfo>, CapacityEdgeMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, long unsigned int, edgeInfo, double edgeInfo::*>, ResidualCapacityEdgeMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, long unsigned int, edgeInfo, double edgeInfo::*>, ReverseEdgeMap = boost::adj_list_edge_property_map<boost::bidirectional_tag, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int>&, long unsigned int, edgeInfo, boost::detail::edge_desc_impl<boost::bidirectional_tag, long unsigned int> edgeInfo::*>, VertexIndexMap = boost::vec_adj_list_vertex_id_map<vertexInfo, long unsigned int>, typename boost::property_traits<CapacityEdgeMap>::value_type = double, typename boost::graph_traits<Graph>::vertex_descriptor = long unsigned int]: Assertion `algo.is_flow()' failed. Thank You

2 2

More than strange performance test results of Boost.MultiIndex
by Ernest Zaslavsky 19 Nov '14

19 Nov '14

I was rewriting our production code since there were performance concerns and switched from our monstrous std::map to boost multi_index_containers which looked exactly what we need. Then when running performance tests I've noticed that once I use composite_key which includes string the performance drops in orders of magnitude, to be precise, 5 orders. Which, I would say, not reasonable at all. So I created a minimal repro case to post here and ran it on Coliru. Surprise! This behavior does not reproduce on GCC, moreover, the composite key with string for some reason was searched twice faster than int only composite. To me it sounds like a bug or in Boost.MultiIndex MS specific implementation (if such exists) or in MSVC. Tech details: VS2012, Win7x64. The code was compiled and linked targeting x64 architecture. Test output on my local machine: Populating data. Index size: 999999 Running FlyweightMICTest::deepTest Checking getTestData perf. 999999 sum of all IDs. 1M calls took 0 seconds or 125ns per call. ------------------------------------------------------------- Populating data. Index size: 999999 Running FlyweightMICTestWithString::deepTest Checking getTestData perf. 99 sum of all IDs. 99 calls took 1 seconds or 10132326ns per call. =============================================================== Coliru output (live example can be found here http://coliru.stacked-crooked.com/a/ef76d297279f15a8) Populating data. Index size: 999999 Running deepTest Checking getTestData perf. 999999 sum of all IDs. 1M calls took 0 seconds or 395ns per call. ------------------------------------------------------------- Populating data. Index size: 999999 Running deepTest Checking getTestData perf. 999999 sum of all IDs. 999999 calls took 0 seconds or 181ns per call. =============================================================== [Read More]<http://feeds.feedburner.com/~r/sizmek-blog/~6/1> [http://www.sizmek.com/Sizmek.png]<http://www.sizmek.com/>

4 7

Re: [Boost-users] Boost-users Digest, Vol 3971, Issue 2
by vibhor aggarwal 18 Nov '14

18 Nov '14

Thanks for the message Joaquin! I am running the boost invariant checks for multi-index and something which took a minute is now taking a full day to run. Any how, I haven't had any of the assertions fail in 5 iterations which completed so far and I have moved to version 1.57.0 Will get back if I see any issues with this again. On Thursday, 13 November 2014 10:30 PM, "boost-users-request(a)lists.boost.org" <boost-users-request(a)lists.boost.org> wrote: Send Boost-users mailing list submissions to boost-users(a)lists.boost.org To subscribe or unsubscribe via the World Wide Web, visit http://lists.boost.org/mailman/listinfo.cgi/boost-users or, via email, send a message with subject or body 'help' to boost-users-request(a)lists.boost.org You can reach the person managing the list at boost-users-owner(a)lists.boost.org When replying, please edit your Subject line so it is more specific than "Re: Contents of Boost-users digest..." Today's Topics: 1. Re: [Mutli-Index, InterProcess] Multi-index stability issue with interprocess? (Joaquin M Lopez Munoz) 2. [Graph] A* with heterogeneous heuristics (Sensei) 3. 1.57.0 link errors (missing ctor/dtor for boost::archive::detail::shared_ptr_helper) (David Abdurachmanov) 4. [BGL] Shortest-Path subject to length constraint (Yun Liu) ---------------------------------------------------------------------- Message: 1 Date: Thu, 13 Nov 2014 10:41:08 +0000 (UTC) From: Joaquin M Lopez Munoz <joaquin(a)tid.es> To: boost-users(a)lists.boost.org Subject: Re: [Boost-users] [Mutli-Index, InterProcess] Multi-index stability issue with interprocess? Message-ID: <loom.20141113T111909-42(a)post.gmane.org> Content-Type: text/plain; charset=utf-8 vibhor aggarwal <vibhor.aggarwal <at> yahoo.com> writes: > > I am creating a multi-index [...] and storing that in a managed > memory mapped file (boos::interprocess) [...] > All the data is first inserted into the multi-index once and then it > is read from the muti-index with a query [...] > > boost::tie(l, u) = m_p_mi_ts->get<0>(). > equal_range(boost::make_tuple(i, j)); > > We are testing this whole process over and over again (each iteration > is a new run of the process), and once in every 50 or so iterations > we get a segment fault inside boost on firing the query. Here is the > boost part of the stack from the core dump: With so little information, I can only guess: the crash is hapenning at a very superficial level into equal_range, namely when dereferencing the container's header node (the top of the rb-tree ordered indices are based on). This suggests that the container layout is seriously screwed; possible reasons: * Memory overwrites from some adjacent structure * File corruption (?) * m_p_mi has been changed somewhere * Some sort of overrun within the memory-mapped file It'd be best if you could provide a testing case for this or some more context. If this is not an option, you can activate Boost.MultiIndex invariant-checking mode: http://www.boost.org/libs/multi_index/doc/tutorial /debug.html#invariant_check which will assert as soon as some internal corruption is detected (caveat: this mode will reduce performance drastically). Joaqu?n M L?pez Mu?oz Telef?nica ------------------------------ Message: 2 Date: Thu, 13 Nov 2014 12:41:32 +0100 From: Sensei <senseiwa(a)gmail.com> To: boost-users(a)lists.boost.org Subject: [Boost-users] [Graph] A* with heterogeneous heuristics Message-ID: <546498EC.6070204(a)gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Dear all, I haven't given up in trying to implement an A* algorithm with BGL. My problem is theoretically simple, as in some previous posts. Given a graph of letters, and a word, find the path in the graph that minimizes the distance between the letters of the word and the nodes in the graph. It's best to show an example: /* * B H * / \ / * A---D---F---G---I * \ /\ * C E * * input: A E I O U * result: A D F G I */ With that graph, my heuristic should take into account not just the letter in the graph per se, but the *corresponding* one in the input word. So, starting with "AEIOU" the search will: - expand A (A in **A**EIOU) - find B, C, D - expand D (closest to E in A**E**IOU) - find D, F - expand F (closest to I in AE**I**OU) - find G - expand G (only one, closest to O in AEI**O**U) - find H, I - expand U (closest to U in AEIO**U**) This settings could also be more complicated, adding weights to edges, but for now I am happy with this problem. What I've done now? Implementing my own A* algorithm, by hand. Of course this might work, but I'd prefer using BGL's facilities. I must say that I am quite confused about BGL's data structures, as for instance in the A* cities example (1), we need to create a weight map, so what if I don't need weights? Moreover, predecessors and distances are instantiated with a std::vector, but what happens if I need to operate on a very large graph, for instance 200M nodes? Moreover, what will happen when I will distribute the graph over a cluster with Boost Parallel Graph? ... Ok maybe this is too ahead of the time! :) Basically, I'd need to replicate my A* ugly by-hand implementation with custom visitors and custom heuristics. Below you may find my failed attempt. I need some help with this, because I find the documentation a little bit hard to understand, especially when some newbie like me approaches Boost :) Failures in my code: I can't get to define a non-weighted graph, and the call to the A* search is cryptic: I don't have weights. Should I define fake ones for instance all equal to 1? I really hope you guys can help me in this, my code works, but using BGL would be best! Thanks! (1) http://www.boost.org/doc/libs/1_57_0/libs/graph/example/astar-cities.cpp #include <iostream> #include <unordered_map> #include <vector> #include <string> #include <utility> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/breadth_first_search.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/astar_search.hpp> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS > graph; typedef boost::graph_traits<graph>::edge_iterator edge_iterator; // Custom A* heuristic template <class Graph, class CostType> class bestmatch_heuristic : public boost::astar_heuristic<Graph, CostType> { public: typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; bestmatch_heuristic() { }; CostType operator()(Vertex u) { std::cout << ">>>> h(" << u << ") = " << 1 << std::endl; return 1; } private: }; // Used to end the A* search algorithm struct end_astar { }; // Custom A* visitor template <class Vertex> class bestmatch_visitor : public boost::default_astar_visitor { public: bestmatch_visitor(Vertex goal) : destination_(goal) { }; template<class Graph> void discover_vertex(Vertex u, const Graph &g) { std::cout << "discover " << u << std::endl; } template <class Graph> void examine_vertex(Vertex u, Graph& g) { std::cout << "examine " << u << std::endl; if (u == destination_) throw end_astar(); } private: Vertex destination_; }; int main() { /* * B H * / \ / * A---D---F---G---I * \ /\ * C E * * input: A E I O U * result: A D F G I */ std::unordered_map<char, std::size_t> letters; auto getletter = [](std::size_t i) -> char { return 'A' + i; }; for (int i = 'A'; i <= 'I'; i++) letters[i] = i - 'A'; graph g; boost::add_edge(letters['A'], letters['B'], g); boost::add_edge(letters['A'], letters['C'], g); boost::add_edge(letters['A'], letters['D'], g); boost::add_edge(letters['B'], letters['D'], g); boost::add_edge(letters['C'], letters['D'], g); boost::add_edge(letters['D'], letters['E'], g); boost::add_edge(letters['D'], letters['F'], g); boost::add_edge(letters['F'], letters['G'], g); boost::add_edge(letters['G'], letters['H'], g); boost::add_edge(letters['G'], letters['I'], g); edge_iterator ei, ee; for (boost::tie(ei, ee) = boost::edges(g); ei != ee; ei++) { std::cout << getletter(boost::source(*ei, g)) << " -> " << getletter(boost::target(*ei, g)) << std::endl; } // Heuristics bestmatch_heuristic<graph, int> h; // Predecessors std::vector<graph::vertex_descriptor> p(boost::num_vertices(g)); try { #if 0 boost::astar_search_tree(// Graph g, // Start node letters['A'], // Heuristics bestmatch_heuristic<graph, int>(), // Predecessor map boost::predecessor_map(boost::make_iterator_property_map(p.begin(), boost::get(boost::vertex_index, g)))); #endif } catch (end_astar e) { } } ------------------------------ Message: 3 Date: Thu, 13 Nov 2014 10:07:07 +0100 From: David Abdurachmanov <david.abdurachmanov(a)gmail.com> To: boost-users(a)lists.boost.org Cc: amey(a)rrsd.com Subject: [Boost-users] 1.57.0 link errors (missing ctor/dtor for boost::archive::detail::shared_ptr_helper) Message-ID: <C512A56C-8078-438E-BDBC-376A9EF590F9(a)gmail.com> Content-Type: text/plain; charset="us-ascii" Hi, I am moving to Boost 1.57.0 and having issues with some code related to serialization. https://github.com/cms-sw/cmssw/blob/CMSSW_7_3_X/CondFormats/Serialization/… https://github.com/cms-sw/cmssw/blob/CMSSW_7_3_X/CondFormats/Serialization/… In both cases the problem is here: #if BOOST_VERSION >= 103500 #include <boost/archive/shared_ptr_helper.hpp> #endif [snip] #if BOOST_VERSION >= 103500 // mix-in helper class for serializing shared_ptr , public boost::archive::detail::shared_ptr_helper #endif A similar (or the same) problem is reported here: http://boost.2283326.n4.nabble.com/Serialization-link-error-in-1-56-td46668… It seems that ctor/dtor are not exported anymore: /testSerializationDQMObjects.o: In function `eos::portable_oarchive::portable_oarchive(std::ostream& , unsigned int)': testSerializationDQMObjects.cpp:(.text._ZN3eos17portable_oarchiveC2ERSoj[_ZN3eos17portable_oarchiveC5ERSoj]+0x54): undefined reference to `boost::archive::detail::shared_ptr_helper: :shared_ptr_helper()' testSerializationDQMObjects.cpp:(.text._ZN3eos17portable_oarchiveC2ERSoj[_ZN3eos17portable_oarchiveC5ERSoj]+0x1c1): undefined reference to `boost::archive::detail::shared_ptr_helper ::~shared_ptr_helper()' boost::serialization::shared_ptr_helper does not seem to be a drop-in replacement at first look. There is also 'shared_ptr_helper_base', but is only available in the implementation file. Is such mix-in class still available in a new Boost version? Thanks, david

1 0

Iostreams: how can I control my (ostream) filter?
by Akim Demaille 16 Nov '14

16 Nov '14

Hi! I'm trying to use Boost.Iostream to create a filter that will escape some characters (typically backslash must be backslashed). This is to conform with the syntax of an output format that requires some portions to be escaped this way. But other place must be left untouched. My problem is I don't find a means to "talk" to my filter. My first attempt used two streams: the "real" ostream and the filtered one that wraps it. Of course it failed: both streams are not synchronized, and buffers are flushed at different moments resulting in scrambled output. I don't want to flush too often (I got to keep my throughput high), so that's ruled out. My second attempt was to introduce an xalloc-based custom iomanip to enable/disable the processing in my filter. But my problem is that in my filter, I don't know how to reach the final ostream and fetch it pword, so I failed to have it work. From the syntax point of view (from the caller viewpoint) that was my favorite approach. In my third attempt, I have to boolean variable living in the caller frame, taken as a bool& by my filter's actor, and checked in its "write" function to decide whether to escape or not. This looks worrying (bool& members don't look nice), and anyway does not work nicely, again, with buffers: the asynchrony between setting/unsetting the boolean and using it breaks everything. So, what are the good options? I think I really needed something like an iomanipulator which ensures that "sequentiality" is preserved, but how should I do that? Thanks in advance! PS/ One not-good-option would be to have my filter try to "parse" what it is outputting to decide what's the current state, and whether it should escape or not. First, things become uselessly complex, and second, anyway that's not right; for instance when I'm in a string, double-quotes should be escaped, or mark the end of the string. The filter cannot know which kind of double-quote it just saw, but I know, so _I_ should change the state at that time, not it.

2 4

Why does `boost::asio::deadline_timer` allocate a `timer_queue` instance for each `deadline_timer` object?
by Wang Danqi 16 Nov '14

16 Nov '14

Hi I am looking into the implementation of `boost::asio::deadline_timer`, based on boost 1.52. As described in [the article on highscore](http://en.highscore.de/cpp/boost/asio.html#asio_extensions), it is implemented in three parts: * `deadline_timer`, the i/o object * `deadline_timer_service`, the service * `detail::deadline_timer_service`, the service implementation There will be a single instance of `deadline_timer_service` serving many `deadline_timer` objects. An instance of `detail::deadline_timer_service` is created for each `deadline_timer` object. Moreover, the timers are scheduled by a scheduler, which is usually a reactor (i.e. `epoll_reactor` on Linux in most cases). There is a `timer_queue_` member of type `timer_queue` in `detail::deadline_timer_service` which is a heap that stores scheduled timers. This means that there will be one instance of `timer_queue` for each `deadline_timer` object. Multiple `timer_queue` objects can be added to the scheduler by `add_timer_queue()`, and they are managed by a class `timer_queue_set`. My question is, why `asio` create multiple queues to handle timers? What is the drawback if we have a single timer queue instance in the scheduler that all timers can share? Please note that I am asking about the `boost::asio::deadline_timer`, not the example in the highscore link. I have posted this question on stackoverflow previously [here](http://stackoverflow.com/q/26922754/930095) -- Best wishes, Wang Danqi

2 2

Re: [Boost-users] lockfree::spsc_queue & move semantics
by quang.trinh＠gmail.com 15 Nov '14

15 Nov '14

------Original Message------ From: Bjorn Reese Sender: Boost-users To: boost-users(a)lists.boost.org ReplyTo: boost-users(a)lists.boost.org Subject: Re: [Boost-users] lockfree::spsc_queue & move semantics Sent: Nov 10, 2014 2:39 PM On 11/09/2014 09:49 PM, Thomas Danckaert wrote: > I'd like to use a spsc_queue of unique_ptr's to bigger objects, to > transfer ownership between threads. That way, I can create/allocate an This limitation inherited from atomic, and I am afraid that it is a bit more complicated than adding a move constructor. Fortunately, there is a C++ proposal to address the problem: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4058.pdf _______________________________________________ Boost-users mailing list Boost-users(a)lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users Sent from my BlackBerry device on the Rogers Wireless Network

1 0

How to track boost::asio pending handlers
by Thierry Morigault 14 Nov '14

14 Nov '14

Hi, I am debugging a huge application with numbers of handlers posted in a boost::asio::io_service, running on Windows 7, Visual Studio 2012 and with boost 1.55. My problem is that the io_service doesn't stop because of pending handlers ... And i can't know what are precisely these handlers : there is only a function in boost::io_service which give the number of pending handlers. Is there a way to display the name of the different pending handlers in the io_service ? It can be so helpful ! I know the macro BOOST_ASIO_ENABLE_HANDLER_TRACKING but this only prints the boost::asio internal functions names (async_accept, async write etc.), and not my proper posted handlers.

1 0

[BGL] Shortest-Path subject to length constraint
by Yun Liu 13 Nov '14

13 Nov '14

Hi all, apologies in advance if this question is trivial; I couldn't find anything like it asked previously in the mailing list. My question is, if I have a directed graph (with non-negative edge weights, to keep things simple for now), I would like to find the shortest-cost path from a source node to target node, but with the constraint on the maximum number of edges allowed. For example, if I have the graph with vertices {A,B,C,D} and edges: A->B (cost 1), B->C (cost 1), C->D (cost 1), A->D (cost 1000), but I have the constraint that my path should only be a maximum of 2 edges, the correct solution would still be A->D with cost 1000. Looking through the previous BGL examples, say with bellman-ford or Dijkstra, it did not seem immediately obvious how to enforce this stipulation. Thanks again for any ideas! -Yun

1 0