Week 2 - Hashed LevelCapabilities and Learning more Compile-time template metaprogramming

Adam2392
Published: 06/08/2023

This week, I’ve finished the PR adding level properties as a public member to the level classes. 

 

However, now I am encountering difficulties in adding the ability for hash levels to be coiterated on. Currently, the `Coiterate` class implements a coiteration_helper class, which in turn currently relies on initializing iteration helpers from each level.

 

```

std::tuple<typename Levels::LevelCapabilities::iteration_helper...> m_iterHelpers;

…

, m_iterHelpers(std::apply([&](auto&... args)

                                          { return std::tuple(args.iter_helper(i, pkm1)...); },

                                          coiterate.m_levelsTuple))

```

 

For example, in the above code, we see that `m_iterHelpers` initalizes the `iter_helper` inside each level in `m_levelsTuple`. In addition, `m_iterHelpers` is a tuple of iteration_helpers, but hash levels do not contain this level capability. I need to implement a modification in the design, so that `m_iterHelpers` is only defined on the subset of levels that are ordered.

 

However, it turns out that this is not an issue that requires tackling. Instead, I realized upon inspection and meeting with my mentor Hameer that all levels should have an `iteration_helper` defined through the `LevelCapabilities` namespace inside their class. The `hashed` level contains an `iteration_helper`, but not through the `LevelCapabilities` class, so the next step I realized was to refactor the existing implementation of the `hashed::iterator`, so that it was contained within the `LevelCapabilities` namespace. This is a bit complicated because the hashed level implements a custom iterator and there is some advanced template metaprogramming going on, which I have to figure out. Currently I’m running into two sets of errors that are confusing to me:

 

```

/Users/adam2392/Documents/xsparse/include/xsparse/util/base_traits.hpp:34:9: error: static_assert failed due to requirement 'std::is_convertible_v<xsparse::util::container_traits<std::vector, std::set, std::unordered_map>, unsigned long>' "`PK` must be convertible to uintptr_t."

        static_assert(std::is_convertible_v<PK, uintptr_t>,

        ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

```

 

And

 

```

/Users/adam2392/Documents/xsparse/test/source/hashed_test.cpp:31:34: error: no member named 'iter_helper' in 'xsparse::levels::hashed<std::tuple<>, unsigned long, unsigned long, xsparse::util::container_traits<std::vector, std::set, std::unordered_map>, xsparse::level_properties<false, false, false, false, false>>'

    for (auto const [i2, p2] : h.iter_helper(ZERO))

                               ~ ^

```

 

Future Work - Although this simple PR on improving the co-iteration algorithm has turned into quite a rabbit hole, the main bulk of the GSoC is dedicated to implementing and testing a “merge lattice” data structure, which will leverage the complete co-iteration algorithm.

 

We briefly discussed merge lattices. Merge Lattices co-iterate over subset of levels that are necessary based on properties of the function. For example:

 

E.g. A_ij + B_ik 

 

When iterating over i, both A and B are iterated. When iterating over j, only A is iterated. When iterating over k only B is iterated.

 

Review:

  • Taco paper: on only dense/hashed

  • Taco code: but note they implement this in runtime, rather than at compile time

    • And we need to re-write things in compile-time