C++ variadic template "tuple" (of pointers to variables) for a marking GC

Question

A question similar to the for_each in std::tuple given here, but not exactly.

Intuitively, I would like a "tuple" of pointers formed from a sequence of variables, and I want to "iterate" on that "tuple"...

It is in context of coding a naive mark and sweep precise garbage collector in C++14 (on Linux/Debian/Sid, either with GCC 4.9 or soon released 5.0 or with Clang/LLVM 3.5 or just released 3.6).

I don't want to use Boost.

I have two unrelated classes : PtrItem and Value. The PtrItem class is a "pointer-like" class containing only one field Item* itemptr;. the Value class contains a discriminated union (see here). Both classes PtrItem and Value have a method

void scan_items(std::function<void(PtrItem)> f) const;

Suppose I have a block starting with

{
  PtrItem pit1, pit2;
  Value valx, valy;

I want to write just after that in the same block

 GCROOT(pit1,pit2,valx,valy);   /// at line 456

with

 class ProtoGcRoot {
   const char* gcrfile;
   int gcrline;
   ProtoGcRoot* gcrprev;
 protected:
   template <typename T1, typename... Args> class GcData
   {
        T1* ptr;
        GcData<Args...> rest;
   public:    
        GcData(T1& v, Args... args) : ptr(&v), rest(args...) {};
     ~GcData() { ptr = nullptr; };
     void scan_gc_data(std::function<void(PtrItem)> f) {
       if (ptr) ptr->scan_items(f);
       rest.scan_gc_data(f);
     }
   };
   template <> class GcData
   { GcData() {};
     ~GcData() {};
     void scan_gc_data(std::function<void(PtrItem)>) {};
   };
   ProtoGcRoot(const char*fil, int lin);
   ProtoGcRoot() = delete;
   ProtoGcRoot(const ProtoGcRoot&) = delete;
   ProtoGcRoot(ProtoGcRoot&&) = delete;
   ProtoGcRoot& operator = (const ProtoGcRoot&) = delete;
   virtual ~ProtoGcRoot();
 public:
   virtual void scan_gc_items (std::function<void(PtrItem)>)= 0;
 };             // end class ProtoGcRoot

 template<typename... Args>
 class GcRoot : ProtoGcRoot {
   ProtoGcRoot::GcData<Args...> gcdata;
 public:
   GcRoot(const char*fil, int lin, Args... rest)
     : ProtoGcRoot(fil,lin),  gcdata(rest...) {};
   ~GcRoot() {};
   virtual void scan_gc_items (std::function<void(PtrItem)> f) {
       gcdata.scan_gc_data(f);
     }
 };
 #define GCROOT_AT(Fil,Lin,...) GcRoot gc_root_##Lin{Fil,Lin,__VA_ARGS__}
 #define GCROOT(...) GCROOT_AT(__FILE__,__LINE__,__VA_ARGS__)

The intent is to have a gc_root_456 variable with an equivalent of

  void scan_gc_items (std::function<void(PtrItem)>f) {
     pit1.scan_items(f);
     pit2.scan_items(f);
     val1.scan_items(f);
     val2.scan_items(f);
  }

But my code does not compile:

 ./yacax.h:729:3: error: extraneous 'template<>' in declaration of class 'GcData'
   template <> class GcData
   ^
 ./yacax.h:729:21: error: redefinition of 'GcData' as different kind of symbol
   template <> class GcData
                     ^
 ./yacax.h:717:50: note: previous definition is here
   template <typename T1, typename... Args> class GcData
                                                  ^

The GcData class is internal in ProtoGcRoot because I don't feel it should be exposed.

`template <> class GcData` is wrong. You are either declaring a class template, and then you put at least one parameter within the `<>` or you are specializing an existing template, and then you need to specify your template parameters after the type name (e.g. `template<> class GcData` if the declaration was `template< typename T > class GCData`) — Giulio Franco, Mar 02 '15 at 13:42
It looks like you're trying to define a specialization for `GcData<>`, but you can't do that, because the first declaration I see is `template class GcData`, meaning you always need to provide at least one parameter. Maybe you want to declare it as `template class GcData` and then specialize for `template class GcData` and `template class GcData`. — Giulio Franco, Mar 02 '15 at 13:45
@Guilo Franco: looks like your combined two comments are nearly making an answer! — Basile Starynkevitch, Mar 02 '15 at 13:46
I've been trying to understand your code, the only conclusion I can come to is that you expect to call `scan_gc_items` on an instance of `ProtoGcRoot` that is out of scope? Is this correct? If not, then surely the implementation can be simpler? — Nim, Mar 02 '15 at 13:58
@Nim: Yes. The point is to be able to scan all the local (GC-declared) pointers on the call stack, as every precise GC do! — Basile Starynkevitch, Mar 02 '15 at 13:59
My point was that if you don't need to reset the pointer on destruction of `GcData` (which would imply you expect it to be accessed *outside of it's local scope* [which would be UB I'd guess]), then your code can be simplified to avoid all the template hackery.. — Nim, Mar 02 '15 at 14:06
@Nim: I don't see the relation. But indeed, the clearing of `GcData` in its destructor is in principle useless (but helpful for debugging). — Basile Starynkevitch, Mar 02 '15 at 14:12

Nim · Accepted Answer · 2015-03-02T15:48:07.543

I think the code below distills down to the same effect? The only difference from your code is that the pointer to the GC-declared item cannot be reset..

#include <functional>
#include <iostream>
#include <set>


// Properly concatenate to form labels - useful when looking at -E output
#ifdef CONCAT_IMPL
#undef CONCAT_IMPL
#endif
#define CONCAT_IMPL( x, y ) x##y
#ifdef MACRO_CONCAT
#undef MACRO_CONCAT
#endif
#define MACRO_CONCAT( x, y ) CONCAT_IMPL( x, y )


// This is a model of your code, I would pass the function object here by reference
struct PtrItem
{
  void scan_items(std::function<void(PtrItem)>& f) const
  {
    std::cout << "scanning "  << this << std::endl;
    f(PtrItem{});
  }
};

struct Value
{
  void scan_items(std::function<void(PtrItem)>& f) const
  {
    std::cout << "scanning "  << this << std::endl;
    f(PtrItem{});
  }
};

class Root;

// Dumb global garbage collector
// because I can't rely on the destructor of the Root class anymore
// for demo
struct Gc
{
  static Gc& instance()
  {
    static Gc _i;
    return _i;
  }

  static void add(Root* inst)
  { instance().add_(inst); }
  static void remove(Root* inst)
  { instance().remove_(inst); }
  static void cleanup()
  { instance().cleanup_(); }

private:
  Gc() = default;

  void add_(Root* inst)
  { _s.insert(inst); }

  void remove_(Root* inst)
  { _s.erase(inst); }

  void cleanup_();

  std::set<Root*> _s;
};

// Base root
struct Root
{
    const char* file;
    int line;

    Root(const char* f, int i): file(f), line(i)
    {
      Gc::add(this); // register this scope
    }

    virtual ~Root()
    {
      Gc::remove(this); // de-register this scope
    }

    // Action
    virtual void scan(std::function<void(PtrItem)> f)
    { }
};

void
Gc::cleanup_()
{
  // Now cleanup - go through all registered scopes...
  auto f = [](PtrItem) { std::cout << "scanned" << std::endl; };
  for (auto r : _s)
   r->scan(f);
}

/**
 * To avoid the std::function<> construction, simply hold a reference directly to the lambda
 * @tparam Handler
 */
template <typename Handler>
struct ScopeRoot : public Root
{
  /** This is the lambda */
  Handler& handler;

  ScopeRoot(const char* f, int i, Handler& h): Root(f, i), handler(h)
  { }

  void scan(std::function<void(PtrItem)> f) override
  { handler(f); }
};

/**
 * This little wrapper allows us to piggy back on the operator, to
 * capture all the macro arguments!
 */
struct FWrapper
{
  /** Hold reference here to avoid copy */
  std::function<void(PtrItem)>& scanner;

  /**
   * Use the operator, to capture each registered variable
   * @param  GC-registered variable
   * @return this to allow chaining
   */
  template <typename T>
  FWrapper& operator,(T& v)
  {
    v.scan_items(scanner);
    return *this;
  }
};

/**
 * Now the macro is expanded to declare the lambda separately to allow us
 * to get it's type for the ScopeRoot instance!
 */
#define GCROOT_AT(Fil, Lin, ...)                                                          \
  auto MACRO_CONCAT(scope_gc_func, Lin) = [&](auto& f) { FWrapper{f}, __VA_ARGS__; }; ScopeRoot<decltype(MACRO_CONCAT(scope_gc_func, Lin))> MACRO_CONCAT(scope_gc_root, Lin){ Fil, Lin, MACRO_CONCAT(scope_gc_func, Lin) };

#define GCROOT(...) GCROOT_AT(__FILE__, __LINE__, __VA_ARGS__)

int main()
{
  PtrItem p1, p2;
  Value v1, v2;

  GCROOT(p1, p2, v1, v2)   
  // Trigger a scan
  Gc::cleanup();
}

Basically you save the state that you need in the lambda, rather than the recursive template structure you have.

However, the generated assembly code (even with `-O3`) is a bit disappointing (lots of `function` related stuff).... — Basile Starynkevitch, Mar 02 '15 at 14:46
@BasileStarynkevitch, did you take the above code as-is? If so, yes there are lot's of copies of the `function<>` objects being made, which can be avoided with strategic moves and references, which should clean things up a little bit. There are two things that differ from your solution, the lambda which captures the state (akin to your tuple,) and the double dispatch, but at the same time you avoid the virtual function overhead, so I would have thought that performance is on the same scale? — Nim, Mar 02 '15 at 15:04
Okay, I optimized it a little bit, so now it will avoid the storage of the lambda in the `std::function<>` at the expense of a virtual function call for `scan()`, now if there is a statistical difference between this and your template code, I'd be keen to know.. :) — Nim, Mar 02 '15 at 15:49

score 0 · Answer 2 · edited May 23 '17 at 11:56

Nim's answer is really clever (but in its initial version was not well optimized, even with -O3 using g++-4.9; I guess the improved version works much better). But I finally wrote something like:

class GarbColl;

class PtrItem {
   Item* itemptr;
public:
   inline void mark_gc(GarbColl*) const;
   //// etc...
}; //end class PtrItem

class Value {
   ///... etc...
public:
   void scan_items(std::function<void(PtrItem)> f) const;
   inline void mark_gc(GarbColl*gc) const
   {
     scan_items([=](PtrItem pit)
               {pit.mark_gc(gc);});
   };
}; /// end class Value

class ProtoGcRoot { 
  // ...etc....
protected:
  ProtoGcRoot(const char*fil, int lin);
  virtual ~ProtoGcRoot();
public:
  virtual void scan_gc_items (GarbColl*)= 0;
}; /// end class ProtoGcRoot

template <typename... Args> struct GcData;

template <> struct GcData<> {
  GcData() {};
  void mark_gc(GarbColl*) {};
};
template <class Arg1Class, typename... RestArgs>
struct GcData<Arg1Class,RestArgs...>
{
 Arg1Class* argdata;
 GcData<RestArgs...> restdata;
 GcData(Arg1Class& arg, RestArgs... rest)
   : argdata(&arg), restdata(rest...) {};
 void mark_gc(GarbColl*gc)
 {
   if (argdata) argdata->mark_gc(gc);
   restdata.mark_gc(gc);
 };
};

template<typename... Args>
class GcRoots : public ProtoGcRoot
{
  GcData<Args...> gcdata;
public:
  GcRoots(const char*fil, int lin, Args... rest...)
    : ProtoGcRoot(fil,lin), gcdata(rest...) {};
  ~GcRoots() {};
  virtual void scan_gc_items (GarbColl* gc)
  {
    this->gcdata.mark_gc(gc);
  }
};
#define GC_ROOTS_HERE_AT_BIS(Fil,Lin,...)  \
     gc_roots_##Lin(Fil,Lin,__VA_ARGS__)
#define GC_ROOTS_HERE_AT(Fil,Lin,...) \
     GC_ROOTS_HERE_AT_BIS(Fil,Lin,__VA_ARGS__)
#define GC_ROOTS_HERE(...) \
     GC_ROOTS_HERE_AT(__FILE__,__LINE__,__VA_ARGS__)
#define GC_ROOTS2_BIS(Fil,Lin,R1,R2) \
   GcRoots<decltype(R1),decltype(R2)> gc_roots2_##Lin(Fil,Lin,R1,R2)
#define GC_ROOTS2_AT(Fil,Lin,R1,R2) GC_ROOTS2_BIS(Fil,Lin,R1,R2)
#define GC_ROOTS2(R1,R2) GC_ROOTS2_AT(__FILE__,__LINE__,R1,R2)

Then I can code either

 void foo(PtrItem pit, Value v) { 
    GcRoots<PtrItem,Value> GC_ROOTS_HERE(pit,v);
 }

or

 void foo(PtrItem pit, Value v) {
    GC_ROOTS2(pit,v);
 }

It is a bit sad that I could not define a variadic and polytypic macro GC_ROOTS but I could accept to have several macros GC_ROOTS1 ... GC_ROOTS15

Meta-programming facilities in C++ are really a pain in the ass. I much prefer Common Lisp macros, or even MELT ones.

Have you looked at `boost::mpl`? I know you said you don't want to look at boost, but for any type manipulation, I've yet to come across anything you can't do with it.. — Nim, Mar 03 '15 at 11:36

C++ variadic template "tuple" (of pointers to variables) for a marking GC

2 Answers2