May 2009 - Boost - lists.boost.org

Re: [boost] gcc-4.4.0 and boost::optional is giving (spurious?) strict-aliasing warnings
by Giovanni Piero Deretta 15 Jul '09

15 Jul '09

On Thu, May 7, 2009 at 3:37 AM, Kim Barrett <kab.conundrums(a)verizon.net> wrote: > At 7:17 PM -0300 5/5/09, Brad Spencer wrote: >> > > In boost/aligned_storage.hpp, the class template > boost::aligned_storage defines its address member function thusly: > > void* address() { return this; } > const void* address() const { return this; } > I'm not 100% sure, but this could be very wrong as, IIRC, there is no guarantee that for non PODS the address of the first element (i.e. aligned_storage.data_) is the same as 'this'. but why doesn't aligned storage implements address() as: void * address { return this.data_.data_.buf; } BTW, I see that boost optional actually uses its own implementation of aligned storage, whose address member function returns a pointer to a char buffer, so it shouldn't be a problem. > There is code in boost/optional/optional.hpp (and probably the other > libs you mention) which looks like: > > internal_type* get_object() { > return static_cast<internal_type*>(m_storage.address()); > } > > What this leads, after some expansion, to something roughly equivalent > to > > static_cast<internal_type*>( > static_cast<void*>( > <a pointer to an instance of aligned_storage> )) > > which I believe is not strict aliasing safe. It is effectively a cast > from aligned_storage* to internal_type*, with a trip through void* > along the way. That trip through void* does not make the conversion > satisfy the strict aliasing rules. > IIRC aliasing rules talk about dynamic types of objects: roughly, you can access a memory location only with a type which is the same as the *dynamic type* of that location or as a char array. Boost optional does an explicit placement new of the stored type on the buffer which changes the dynamic type of the buffer so it should be safe from a standard point of view. Before reusing the buffer It invokes the destructor of the type, which ends the object lifetime. That said, gcc has been known to miscompile placement new from time to time (but it should be more or less fixed on recent versions: it pretty much acts as a compiler optimization barrier). In the end, IMHO the warning is spurious and could be safely ignored (modulo compiler bugs). > [Note that it is not the cast itself that violates the strict aliasing > rules, it is the later dereference of the pointer resulting from the > cast.] > > [Note that I'm pretty sure that switching from static_cast to > reinterpret_cast doesn't help.] > > One of the escape hatches provided by the strict aliasing rules > involves ensuring that there is a union type in scope at the point of > the conversion which contains both of the involved types. [The > "visible union" rule of 6.5.2.3#5.] I do not think this rule actually help you: you can't still read from a field different from the last written to (except for some exceptions like structures with common initial sequences.) Most compilers give additional guarantees, though. > Another escape hatch offered by the strict aliasing rules involves > memcpy and memmove. [6.5#6] I think that the following implementation of > aligned_storage::address will satisfy the strict aliasing rules: > > void* address() { > void* data = data_.data_.buf; > return memmove(data, data, sizeof(*data)); > } > > And I think gcc will optimize away the memmove, at least at sufficient > optimization levels. But note that I have not tested this at all. > > [Hm, using a size of 0 or 1 or some similar small value might be > sufficient to quiet the compiler; I'm not certain whether it is > sufficient to satisfy the letter of the C standard.] I do not see how this helps, first of all sizeof(*data) is illegal (sizeof(void) doesn't make any sense, gcc defines it as 1 as an extension), then how copying one byte will fix aliasing problems? > > The idea is that memmove (and memcpy, but that requres non-overlapping > source and destination, which we don't have here) is defined by the > aliasing rules to strip away the type of the destination, in a way > that a simple cast does not. I do not think it really strips away the type of the destination: in fact it is often unsed to bit cast from integers to float and back: if a memcpy(&some_float, &some_integer, sizeof(int32_t)) really did change the type of some_float, it would break a lot of code (you could no longer threat some_float as a float). What is guarateed is that some_float will contain the same bit pattern of some_integer, while still maintaining the float type. It assumes that the bit pattern of the source is a valid pattern for the destination type, otherwise it is UB. > > [And yes, I agree that this is rather grotesque.] > Aliasing rules really are a mess. -- gpd

3 3

Mark throw_exception as noreturn?
by Andrey Semashev 05 Jul '09

05 Jul '09

Hi, I was wondering why the throw_exception function is not marked as noreturn? This makes it troublesome to use it as a drop-in replacement for throw statements as it starts to flag compiler warnings about missing return statements in non-void functions. I suggest to mark the function as noreturn at least for compilers that support it. GCC has __attribute__((noreturn)), MSVC has __declspec(noreturn).

4 6

[Graph] iterator range splitting
by Tim Keitt 28 Jun '09

28 Jun '09

I've run into some problems with the Graph library as there is a lot of code that splits iterator ranges. An example of this is: (from depth_first_search.hpp) template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { // // should the below not be: // graph_traits<VertexListGraph>::iterator vi, vend; // tie(vi, vend) = vertices(g); // if ( vi == vend ) ... ??? // or perhaps to be more terse // if ( empty_range(vertices(g)) ) // where empty_range(g) compares first and second // if (vertices(g).first == vertices(g).second) return; depth_first_search(g, vis, color, *vertices(g).first); } This is causing problems in my code where I have defined custom graph classes. In my case out_edges(g) != out_edges(g) because memory is allocated within the out_edges call and successive calls will return different ranges (vertex ranges are not a problem in my case as I use a simple counting iterator). Must out_edges(g) == out_edges(g) for a graph class to meet the Graph library requirements? If not, then a good bit of the code needs to be altered and possibly some of the iterator macros deprecated. Below I've located every instance where the first or second member of an iterator pair is thrown away. These cases are only problematic if the retained iterator is later compared to an iterator from another range. The fix is simple. One only needs to retain both members of the iterator pair. I am willing to provide a patch if it is agreed that the current code is wrong. THK egrep '(vertices|edges)\(.*\)\.(first|second)' * adjacency_list_io.hpp: for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){ adjacency_list_io.hpp: for (ei = edges(graph).first; ei != edges(graph).second; ++ei){ adjacency_list_io.hpp: for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){ adjacency_matrix.hpp: return *vertices(g).first; adjacency_matrix.hpp: return *vertices(g).first; adj_list_serialize.hpp: for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi) { adj_list_serialize.hpp: for (ei = edges(graph).first; ei != edges(graph).second; ++ei){ bc_clustering.hpp: if (edges(g).first == edges(g).second) return; bc_clustering.hpp: edge_descriptor e = *max_element(edges(g).first, edges(g).second, cmp); bc_clustering.hpp: } while (!is_done && edges(g).first != edges(g).second); cuthill_mckee_ordering.hpp: if (vertices(G).first == vertices(G).second) cuthill_mckee_ordering.hpp: if (vertices(G).first == vertices(G).second) depth_first_search.hpp: if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g); depth_first_search.hpp: if (vertices(g).first == vertices(g).second) depth_first_search.hpp: depth_first_search(g, vis, color, *vertices(g).first); depth_first_search.hpp: if (vertices(g).first == vertices(g).second) depth_first_search.hpp: *vertices(g).first), edge_connectivity.hpp: std::set_difference(vertices(g).first, vertices(g).second, edge_connectivity.hpp: std::set_difference(vertices(g).first, vertices(g).second, fruchterman_reingold.hpp: Dim minX = position[*vertices(g).first].x, maxX = minX; fruchterman_reingold.hpp: Dim minY = position[*vertices(g).first].y, maxY = minY; graph_test.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; graph_test.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; howard_cycle_ratio.hpp: if (boost::out_edges(vd1, m_g).first == boost::out_edges(vd1, m_g).second) throw bad_graph(m_vim[vd1]); howard_cycle_ratio.hpp: mcr_edge_t ed = *boost::out_edges(vd1, m_g).first; howard_cycle_ratio.hpp: good_vertex = boost::target(*boost::out_edges(good_vertex, m_pi_g).first, m_pi_g); howard_cycle_ratio.hpp: pi_edge_t tmp_ed = *(boost::out_edges(vd, m_pi_g).first); howard_cycle_ratio.hpp: remove_edge(*(out_edges(m_g2pi_g_vm[vd], m_pi_g).first), m_pi_g); is_kuratowski_subgraph.hpp: bipartition_start = next(next(next(vertices(K_3_3).first))); is_kuratowski_subgraph.hpp: si = vertices(contracted_graph).first; isomorphism.hpp: for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first; isomorphism.hpp: e1 != edges(g1).second; ++e1) { isomorphism.hpp: for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first; isomorphism.hpp: e2 != edges(g2).second && !found_edge; ++e2) { iteration_macros.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; iteration_macros.hpp: BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \ johnson_all_pairs_shortest.hpp: typename Traits2::vertex_descriptor s = *vertices(g2).first; kamada_kawai_spring_layout.hpp: for (vertex_iterator ui = vertices(g).first, end = vertices(g).second; kamada_kawai_spring_layout.hpp: vertex_iterator ui, end = vertices(g).second; kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: vertex_descriptor p = *vertices(g).first; kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { king_ordering.hpp: if (vertices(G).first == vertices(G).second) king_ordering.hpp: if (vertices(G).first == vertices(G).second) metric_tsp_approx.hpp: Vertex v(*vertices(g).first); metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, w, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis); metric_tsp_approx.hpp: Tree t(mst, *vertices(mst).first, minimum_degree_ordering.hpp: adj_iter nu = adjacent_vertices(u_node, G).first; planar_canonical_ordering.hpp: vertex_t first_vertex = *vertices(g).first; prim_minimum_spanning_tree.hpp: choose_param(get_param(params, root_vertex_t()), *vertices(g).first), prim_minimum_spanning_tree.hpp: (g, *vertices(g).first, predecessor_map(p_map). property_iter_range.hpp: return std::make_pair(iter(vertices(graph).first, get(tag, graph)), property_iter_range.hpp: iter(vertices(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(vertices(graph).first, get(tag, graph)), property_iter_range.hpp: iter(vertices(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(edges(graph).first, get(tag, graph)), property_iter_range.hpp: iter(edges(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(edges(graph).first, get(tag, graph)), property_iter_range.hpp: iter(edges(graph).second, get(tag, graph))); push_relabel_max_flow.hpp: current(num_vertices(g_), out_edges(*vertices(g_).first, g_).second), push_relabel_max_flow.hpp: current[u] = out_edges(u, g).first; push_relabel_max_flow.hpp: current[v] = out_edges(v, g).first; push_relabel_max_flow.hpp: for (ai = current[u], ai_end = out_edges(u, g).second; push_relabel_max_flow.hpp: current[u] = out_edges(u, g).first; push_relabel_max_flow.hpp: for (; current[u] != out_edges(u, g).second; ++current[u]) { push_relabel_max_flow.hpp: if (current[u] == out_edges(u, g).second) { push_relabel_max_flow.hpp: ai = out_edges(u, g).first; push_relabel_max_flow.hpp: while (excess_flow[u] > 0 && ai != out_edges(u, g).second) { push_relabel_max_flow.hpp: ai = out_edges(u, g).first; random.hpp: i = vertices(g).first; random.hpp: return *vertices(g).first; random.hpp: i = edges(g).first; random.hpp: return *edges(g).first; sloan_ordering.hpp: s = *(vertices(G).first); undirected_dfs.hpp: if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g); undirected_dfs.hpp: undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first); undirected_dfs.hpp: *vertices(g).first), -- Timothy H. Keitt http://www.keittlab.org/

6 16

How to speed up the djikstra graph
by Lennart Berg 23 Jun '09

23 Jun '09

Hi Everybody I have had the pleasure of using the boost graph library for my project now, but I have ran into some problems, that I hope you can guide me on. First of all, let me tell a little about the project. I am a third party developer for paradox interactive, making an expansion for one of their games. Now i have implemented the djikstra alghorithm to simulate the transport capacity of countries, and it works pretty well. However I still think that the speeds to be improved somewhat (takes about 1-2 secs to compute), to make it more playable. First of all the map consists of ~2500 provinces / vertexes each with 4-8 edges / neighbours. I Find all the provinces I can access and then add all neighbours from it as edges. Each edge is allocated a cost according to infrastructure, terrain and distance from orgin to destination. Each "round" of the game is an hour, so a day is effectively 24 rounds. Right now I make a new graph once every day, one separate graph for each country, and compute it for every country once a day. However as the game has up to 300+ countries that becomes a pretty harsh computational burden. Now pretty much every variable in this setup can change hourly. ( location of units, conquest / loss of provinces, destruction of infrastructure, expansion / repair of infrastructure) So the question is how I can improve this approach. Optimally the graph should be persistant and allow me to dynamically add / remove provinces and change the cost of the edges every hour (as I understand it the boost library allows that right now with vertex_clear / add etc.), and giving new values without recomputing every single edge in the graph 300 times every hour. Is that possible? And if how would that be done? Thanks in advance Lennart Berg

8 18

Proposed addition to the iterator library for iterating over all tuples.
by Alex Mendes da Costa 19 Jun '09

19 Jun '09

Hi folks: I quite often have to write code to do the following: Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence. For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20). I think this problem could be solved elegantly with a iterator similar to zip_iterator. I have some questions: (1) Is there already a way to do this in boost? (2) If not, would this be a worthwhile addition to the iterator library? (3) If so, could I contribute code for this, or must the existing library owners write it? (4) If so, how would I go about getting my code added? Most of the docs seem to be about submitting entire libraries, rather than extensions to existing libraries. Thanks, Alex

4 18

[date_time] [#1861] Change for the default duration format
by Andrey Semashev 18 Jun '09

18 Jun '09

Hi, There's a Boost.DateTime ticket: https://svn.boost.org/trac/boost/ticket/1861 The initial problem was that the default handling of the %H format specifier (passing it to strftime) played badly with time durations that could be longer than 24 hours. The resolution was to provide additional %O format specifier that does not have 24 hour restriction. However the original poster proposes to change the default format of time durations from %H:%M:%S%F to %O:%M:%S%F so that formatted durations are always allowed to be longer than 24 hours. I mostly agree with this change, however it is clearly a breaking change that can affect error checking in some cases. What do the community and the maintainer (Jeff?) in particular think about this?

4 15

[mpl] is there a or_seq like logical metafunction?
by vicente.botet 17 Jun '09

17 Jun '09

Hello, I needs calculate the mlp::or_ of a sequence of nullary logical metafunction. This seams quite simple. I have do the following: <code> template <typename Seq> struct or_seq; template <typename Seq, long N> struct or_seq_aux : mpl::or_< typename mpl::front<Seq>::type, or_seq<typename mpl::pop_front<Seq>::type> > {}; template <typename Seq> struct or_seq_aux<Seq, 1> : mpl::front<Seq>::type {}; template <typename Seq> struct or_seq : or_seq_aux<Seq, mpl::size<Seq>::value> {}; </code> Is there a boost or_seq like logical metafunction? Is there a better way to do it? I would be extremely interested in any suggestions. Best regards --------------------------- Vicente Juan Botet Escriba

5 34

[repost][threads] final decision on making parts of Boost.Threads header-only
by joaquin＠tid.es 16 Jun '09

16 Jun '09

I'm reposting this in the hope of catching the attention of the lib's author, who is at the end of the day the person reponsible of making the decision: Hi, A few weeks ago we had a discussion about the convenience of making part of Boost.Threads, namely mutexes and locks, header-only. Some (including Anthony Williams) supported the idea, others disliked it: http://lists.boost.org/Archives/boost/2009/04/150524.php What the final decision on this issue is? If positive (i.e. favoring the change), can it be expected to be done for Boost 1.40? As a remainder, I've created an associated trac ticket: https://svn.boost.org/trac/boost/ticket/2964 Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 4

[mpl] mpl::string, ok to merge to release?
by Eric Niebler 13 Jun '09

13 Jun '09

The mpl::string tests look OK to me on trunk, so I was planning on merging this to release for 1.40. Objections? Aleksey, I've had some problems generating the refmanual html from the rst source. It seems to go OK, but then some of the internal links are broken, and I can't figure what I'm doing wrong. Could you generate new html from the rst on trunk and commit it back to trunk? Please let me know the revision number after you do, and I'll merge it all to release in one go. Thanks. -- Eric Niebler BoostPro Computing http://www.boostpro.com

2 3

[mpl]iter_fold_if Forward Backward rationale?
by Larry Evans 10 Jun '09

10 Jun '09

Why is there both a ForwardOp and BackwardOp template argument to iter_fold_if? https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L… I would have thought that only 1 was needed. Since iter_fold_if is not documented here: http://www.boost.org/doc/libs/1_38_0/libs/mpl/doc/refmanual/refmanual_toc.h… I assume it's not meant to be used by the user, but is only an implementation detail; however, it, or a variation, might be useful to implement the and_seq mentioned here: http://article.gmane.org/gmane.comp.lib.boost.devel/186204 As shown in that post, the template, while_if_then was used, and it does not require anything like both a ForwardOp and BackwardOp, it just requires the If and Then unary metafunctions. One problem I encountered with while_if_then was moving to the end of the sequence, at which time the Then metafunction couldn't be called; hence, I had to make it lazy to avoid dereferencing the end iterator. Is that somehow related to the need for BackwardOp in iter_fold_if. IOW, because iter_fold_if might reach the end iterator, it has to backup? I'm really asking because in the variadic template version of mpl, I wondering if iter_fold_if could be replaced with something like while_if_then (which may be renamed fold_if to be more consistent with other names with similar function). Any insight about the rationale for the iter_fold_if would probably save me considerable time in deciding whether it can be replaced with the proposed fold_if. -regards, Larry

3 28