GSoC 2017

@STEllAR-GROUP/hpx

Project:

Re-implementing hpx::util::unwrapped and unifying the API of hpx::wait and hpx::when

by Denis Blank

Supervised by: Hartmut Kaiser

GSoC project link

Project GitHub HPX commit history link

Overview

Abstract

In HPX we express dependencies between future results through the when_*, wait_* and dataflow functions, which are mostly used in combination with the unwrapped function that allows to work with plain values directly, rather than futures of values. My project added the ability to those functions to also accept arbitrary containers, tuple-like objects and move only types as well as the capability to deal with futures nested inside such types. For my GSoC project, I re-implemented and extended the existing solution of unwrapped into an independent implementation, which provide those functionalities for synchronous and asynchronous usage. This features will make it much easier to express dependencies between futures in HPX in the future while access its result in a convenient way.

Overview

The following report describes the progress that I’ve made during my GSoC 2017 project: “Re-implementing hpx::util::unwrapped and unifying the API of hpx::wait and hpx::when”.

The main task of this project was to provide two utility APIs for traversing and mapping objects in arbitrary variadic packs. In order to solve this task, I implemented a synchronous and an asynchronous version of the traversal API. Support for mapping across types is supported synchronously.

Both utility APIs are used to remove code duplication as well as making the APIs which unwrap or wait for futures more uniform. Additionally, the APIs introduce support for move only types as well as better support for objects which are deeply nested inside homogeneous containers (std::vector, std::list) and tuple like containers (std::tuple, hpx::util::tuple, std::array).

Below you can see, for which APIs the traversal and mapping APIs replace the internal implementation:

Design

Through this contribution, many issues in the HPX issue tracker were approached or closed, for instance: #1126 #1132, #1400, #1404 and #2456.

A detailed description of my original project description is available here.

May

Community Bonding

During the community bonding phase, I approached some light defects in order to get used to the codebase as well as getting to know the HPX community.

  • Documentation improvements:
    • e890af420c Add documentation to invoke_fused and invoke
    • 9085f6b499 Add documentation to hpx::util::unwrapped and hpx::util::unwrapped2. * Also add some internal comments for improved guidance
  • CMake improvements:
    • 7952bcb596 Generate cmake_variables.qbk and cmake_toolchains.qbk outside of the source tree * Prevents built system caused working tree pollution
    • 0bb983f1d8 Fix cmake soft errors due to failing creation of links on windows * Prevents errors when generating the documentation on windows since cmake doesn’t provide the create_symlink there. * We use cmd under windows to create links instead
  • Doxygen improvements:
    • b993029f51 Extract all documentation entities in order to autolink functions correctly * Closes #2615
    • 8f71f2a4e6 Hide the detail namespace in doxygen per default
June

Phase I - June

At the beginning of the first phase, I focused on fixing the requirements of my project.

Due to this I discovered the need of a spread or explode helper function which could invoke a callable object with the content of a given tuple directly, while passing non tuple like types through. A detailed description of my research can be found here.

In the remaining time of the first phase, I implemented the synchronous mapping and traversal API map_pack and traverse_pack, which was submitted as part of pull request #2704.

A minimalistic example of a typical use case of this API might be the following, where we map all values to floats:

1
2
3
4
5
hpx::util::tuple<float, std::vector<float>,
                 hpx::util::tuple<float, float>> res =
map_pack([](int i) {
    return float(i);
}, 1, std::vector<int>{2, 3, 4}, hpx::util::make_tuple(5, 6));

The API fully supports all requirements mentioned above like arbitrarily nested containers and move only types. Thus it’s a real improvement over the previous internal code of the unwrapped function.

Since the API isn’t fixed on mapping hpx::lcos::future objects we can test it, with more generic unit tests. Also, we are able to test the mapping API and the future unwrap functionality independently from each other.

Additionally, the capability to test for compiler features directly with header only parts of HPX was added to CMake. This is used to provide a generic feature test, that uses the traverse_pack API, which tests whether the currently used compiler is capable of full expression SFINAE support.

  • #2704 Implement the synchronous mapping and traversal API:
    • 2de39aa622 Add support of std::array to hpx::util::tuple_size and tuple_element
    • aed3ff37d6 Add an is_tuple_like trait for sequenceable type detection
    • e2fe00b6e2 Remove slashes before CMAKE_FILES_DIRECTORY variables * As stated by https://cmake.org/Wiki/CMake_Useful_Variables CMAKE_FILES_DIRECTORY contains a leading slash already, and should be used as following with the current binary directory: ${CMAKE_CURRENT_BINARY_DIR}${CMAKE_FILES_DIRECTORY}. Otherwise this will lead to paths with double slashes.
    • bcf25f41bd Fix custom include and link directories in config tests
    • 880cfb77f6 Append -D to COMPILE_DEFINITIONS passed to add_hpx_config_test
    • 7586970e85 Make it possible to run feature tests on header only parts of HPX * add_hpx_in_framework_config_test makes HPX and its dependencies available to the corresponding feature test.
    • 4788bdb6db Add a synchronous mapping API * Can be used to traverse or map elements contained in any nested container or tuple-like type. * Meant for replacing the internal API of hpx::util::unwrapped and some functions which are used to wait on futures.
    • 7108fff97d Add a feature test for full expression sfinae support * Tests whether the compiler provides full expression SFINAE supports so all parts of HPX can be compiled. * Currently MSVC is the only compiler that doesn’t implement it.
July

Phase II - July

Based on the mapping API which was implemented in phase one, unwrapped was reimplemented. Pull request #2741 contributed the rewritten implementation of unwrapped as well as the whole conversion of the HPX codebase.

Due to the requirement, that the new unwrapped should pass none future arguments through, it was considered to split the deferred and the immediate unwrapped into two separated interfaces, since the implementation selection of unwrapped would be broken otherwise:

  • unwrap: Unwraps a variadic pack of futures directly
  • unwrapping: Creates a callable object that unwraps the futures

Also, multiple versions of unwrap and unwrapping are provided to unwrap until a particular future depth of a given pack:

  • unwrap_n and unwrapping_n: Unwraps futures recursively until depth n.
  • unwrap_all and unwrapping_all: Unwraps all futures recursively which occur inside the pack.

A simple usage case of unwrap looks like the one below, where we map futures to their real values:

1
2
3
4
5
6
7
// Single arguments
int i1 = hpx:util::unwrap(hpx::lcos::make_ready_future(0));

// Multiple arguments
hpx::tuple<int, int> i2 =
  hpx:util::unwrap(hpx::lcos::make_ready_future(1),
                   hpx::lcos::make_ready_future(2));

Currently, the old unwrapped function forwards its input to unwrap and unwrapping, so we are able to test the behavior of the new implementation. The next step was to replace all occurrences of unwrapped through unwrap and unwrapping accordingly while officially deprecating the unwrapped API.

Overall this step took me longer than expected, mainly because the exact behavior of unwrapped was unknown and thus it had to be derived from many unit tests and examples.

Due to the previously named reasons and because a future is currently considered, the mapping API was improved, to also support 1:n mappings in order to fit to future requirements.

  • #2741 Deprecate unwrapped and implement unwrap and unwrapping:
    • 6bd34c5f51 Move the unwrapped tests from lcos to util
    • 5c208ae687 Correctly return the exit code when the unwrapped unit test failed
    • dcfb50363a Fix tuple_cat when using l-value references * Add basic unit tests to ensure the correctness of tuple_cat.
    • db4f99e61b Fix tuple_cat when using r-value references (and move only types) * Add a unit tests for this.
    • a0b96c0c4d Fix the mapping of containers holding move only types
    • 2ef735bff6 Fix the mapping of arrray like heterogeneous containers
    • 444b431f89 Fix the mapping of l-value references (hpx::lcos::shared_future) * Add some unit tests to ensure the behaviour
    • 7c23554788 Fix the mapping of containers when mapping to references
    • 341025a131 Allow map_pack to apply 1:n mappings
    • ac831b6375 Propagate empty mappings back to the caller * Required for returning empty mappings from vector<future>
    • 0c6265e1d8 Implement the rewritten version of unwrapped (called unwrap and unwrapping) * unwrapped will be deprecated, until it’s removed unwrapped will use unwrap as underlying implementation. * The re-implementation and deprecation was required due to unresolvable issues in the old implementation, which mainly arised from the requirement to route non future values through.
    • 0a50f9c486 Remove the old implementation of unwrapped * Add a proxy which emulates its behaviour using the new unwrap API * The proxy will be flagged as deprecated once the usage of unwrapped was replaced inside all unit tests and examples.
    • 93c55adab0 Remove unsupported tests of unwrap * Disable deprecation warnings inside the legacy unwrapped tests
    • 1ef7985cb4 Map future to zero arguments when unwrapping
    • c093f475ac Implement unit tests for unwrap and unwrapping * Partially re-uses the previous tests of tests/unit/util/unwrapped.cpp
    • 35bd75b730 Remove using namespace in the pack_traversal unit test * Correct the naming of some functions
    • c708feafe5 Rename the internal mapper invoke to invoke_mapper * Prevents wrong function selection caused through ADL * Also namespace a call to make_tuple
    • 1ba82eea86 Add constexpr and noexcept to the pack_traversal API
    • b6545ba263 Use unwrap and unwrapping in the core library
    • e4465fc968 Use unwrap and unwrapping in the examples
    • 347be2f5f5 Use unwrap and unwrapping in the tests
    • 6a32d0cee5 Replace the usage of boost::atomic in the unwrap test * Ref #2782
    • 5982cf22a1 Deprecate hpx::util::unwrapped * Use hpx::util::unwrap and hpx::util::unwrapping instead, that clearify which underlying implementation should be used (the immediate or the deferred one). The automatic implementation selection was broken since unwrapped allowed to pass non future arguments through. * Closes #1400 * Closes #1404 * Closes #2456 * Ref #1126 * Ref #1132
August

Phase III - August

For the third phase of my GSoC project, I implemented the asynchronous traversal API, which makes it possible to traverse futures inside a variadic pack while being able to suspend the current execution context.

We need to provide a special visitor object for this API:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct my_async_visitor
{
    /// The synchronous overload is called for each object,
    /// it may return false to suspend the current control.
    /// In that case the overload below is called.
    template <typename T>
    bool operator()(async_traverse_visit_tag, T&& element)
    {
        return true;
    }

    /// The asynchronous overload this is called when the
    /// synchronous overload returned false.
    /// In addition to the current visited element the overload is
    /// called with a contnuation callable object which resumes the
    /// traversal when it's called later.
    /// The continuation next may be stored and called later or
    /// dropped completely to abort the traversal early.
    template <typename T, typename N>
    void operator()(async_traverse_detach_tag, T&& element, N&& next)
    {
    }

    /// The overload is called when the traversal was finished.
    /// As argument the whole pack is passed over which we
    /// traversed asynchrnously.
    template <typename T>
    void operator()(async_traverse_complete_tag, T&& pack)
    {
    }
};

Then we are able to traverse an arbitrary pack of futureswhile being able to suspend the current execution context at any time to resume it later.

1
2
3
4
hpx::future<void> f1;
hpx::future<int> f2;

util::traverse_pack_async(my_async_visitor{}, f1, 2, f2);

This implementation is equal to a stackless coroutine, however we may re-implement this API with the synchronous one as soon as co_await is introduced and available in C++20.

Finally, I replaced the internal API of wait_all and dataflow with the synchronous and asynchronous traversal API, so both interfaces are able to deal with the same set or arguments (unification). The capabilities of both functions were extended to the one of unwrapped to deal with:

  • nested types
  • move only types
  • arbitrary homogeneous and tuple-like containers
  • passing non future types through

As positive side effect duplicated code in wait_all and dataflow was removed.

  • Fixes for the unwrapped transition:
    • 320f515335 Fix a parsing error with Visual Studio 2015 which occurred in unwrap * Ref #2741
    • c442ec06e9 Fix a potential unconditial moves in hpx::util::tuple_cat * Thanks to K-ballo for pointing this out * We use hpx::util::get now for retrieving a specific element at index i instead of the internal tuple_element API. * Ref #2741
    • 4ea728d97a Fix a unit test failure on GCC in tuple_cat * Add a test which targets the same issue on other toolchains
    • f9ec761db1 Remove constexpr from a void function
  • Improve the continous integration testing:
    • af4fdf501a Add Visual Studio 2015 to the tested toolchains in Appveyor * Closes #2844
  • #2829 Implement an API for asynchronous pack traversal:
Conclusion

Conclusion

For me personally, Google Summer of Code was a great experience because I learned a lot about Open-Source, collaboration, and development (C++ and high-performance computing in particular).

Also I really liked, that I had the chance to contribute to a major Open-Source project, while receiving professional advice.

The HPX community and maintainers (STEllAR-GROUP) were really helpful due to the whole program and provided me great support.

Special thanks go to my mentor Hartmut Kaiser who always was supportive.

I would definitely recommend others to apply for a Google Summer of Code stipend at @STEllAR-GROUP/hpx.

By Denis Blank

— The content of this site is licensed under Creative Commons BY-NC

Design by Tim O’Brien t413.com — SinglePaged theme — this site is open source