Bison value moving / efficiency
Asked Answered
R

1

6

I'm working on constructing my parse data structure from bison's semantic values. One particular structure is of type std::vector<double>. I'm curious how the bison internals handle moving semantic values. I tried analyzing the c++.m4 file, and found:

template <typename Base>
  inline
  void
  ]b4_parser_class_name[::basic_symbol<Base>::move (basic_symbol& s)
  {
    super_type::move(s);
    ]b4_variant_if([b4_symbol_variant([this->type_get ()], [value], [move],
                                      [s.value])],
                   [value = s.value;])[]b4_locations_if([
    location = s.location;])[
  }

Unfortunately, I cannot decipher this nearly enough to make out the efficiency of moving a data structure like std::vector, partly owing to my ignorance of the m4 syntax.

Given this in my grammar:

%define api.token.constructor
%define api.value.type variant
%type < std::vector<double> > numlist
...
numlist:
    num             { $$ = std::vector<double>(); $$.push_back($1); }
|   numlist "," num { $$ = $1; $$.push_back($3); }
;

I am uncertain of the performance implications. Note that this will be compiled with a C++98 compiler and not a C++11 compiler; hence there will be no move semantics.

I'm guessing that the $$ = std::vector<double>() statement could be removed; I assume it would be default-constructed already, but I haven't tested and I'm not sure how bison's internal variant type works. What I'm particularly interested in is the $$ = $1; $$.push_back($3); Will the vector be copied for every item that is to be added?

I can't determine if this is a case for switching the type to std::vector<double> *; admittedly, much of the reasoning behind using bison's variant type was to use plain C++ types instead of a union of pointers.


I've also had similar curiosities on a parser that does in fact make use of C++11/14 and in particular std::unique_ptr. If one line of a left-recursive rule assigned, say $$ = std::make_unique<...>(...), would the following be able to do $$ = $1; $$->...?

Rybinsk answered 20/3, 2016 at 18:18 Comment(0)
A
3

I am not a Bison / Yacc expert but you can have a look at the generated code:

      {
  case 2:
#line 20 "test.yy" // lalr1.cc:846
    { yylhs.value.as<  std::vector<double>  > () = std::vector<double>();
      yylhs.value.as<  std::vector<double>  > ().push_back(yystack_[0].value.as< double > ()); }
#line 1306 "test.tab.cc" // lalr1.cc:846
    break;

  case 3:
#line 21 "test.yy" // lalr1.cc:846
    { yylhs.value.as<  std::vector<double>  > () = yystack_[2].value.as<  std::vector<double>  > (); 
      yylhs.value.as<  std::vector<double>  > ().push_back(yystack_[0].value.as< double > ()); }
#line 1312 "test.tab.cc" // lalr1.cc:846
    break;

Which lays inside the parser::parse method and where yylhs is a local variable of type stack_symbol_type and yystack_ is an attribute of the parser class of type stack_type (which contains stack_symbol_type).

It looks like the answer is yes, the whole vector will be copied when you do $$ = $1, and I don't see how a compiler could optimize this. The declaration of as is as follows:

template <typename T>
T& as();

With a const variant, so the affectation is done on the type T, which in your case is std::vector<double>, and thus a copy is made. Even if you use move semantics, a copy would be made because the RHS is not an xvalue.

Amphisbaena answered 20/3, 2016 at 18:53 Comment(4)
Thanks! I really wanted to avoid making the pointer-to-vector construct but it looks like that's the best thing to do.Rybinsk
@Rybinsk did you consider swapping $1 and $$ instead of assigning?Juarez
@Michael I hadn't. Are you referring to std::swap()?Rybinsk
@Rybinsk I intended to refer to the member function swap Holt cited, but global swap should be overloaded by the standard library to call the member function for vectors, so either way should work.Juarez

© 2022 - 2024 — McMap. All rights reserved.