boostorg / boostorg/hana

Sparse Array for Group By

Open
#324 1 comment 1 reaction 0 assignees View on GitHub
Dominant language
C++
Stars
1.9k
Forks
225
PR merge metrics
No merged PRs in 30d

Description

This is just a thought, but we should consider making a sparse array similar to `hana::detail::hash_table` for the purpose of making a fast "group by" algorithm. One problem would be that it would have to use `fold_left` to construct the lookup which I recall was an expensive up front cost.

The result could even be a `hana::map` as it appears that everything except `make_map` is agnostic to the use of `hana::hash`.

I kind of got a start on something. The following is ripped from `hana::detail::hash`:

```cpp
namespace sparse_array
{
template
struct group { };

template
struct lookup_table
: Groups...
{ };

// find indices
template
std::index_sequence find_indices_impl(group const&);

template
std::index_sequence<> find_indices_impl(...);

template
struct find_indices {
using type = decltype(find_indices_impl(Lookup{}));
};

// update_group
template
struct update_group {
using type = Group;
};

template
struct update_group, Key, Index> {
using type = group;
};

// group_insert
template ::type::size() > 0)
>
struct group_insert;

template
struct group_insert, Node, Index, true> {
// There is a group for that Key; append the new index to it.
using type = lookup_table<
typename update_group::type...
>;
};

template
struct group_insert, Node, Index, false> {
// There is no group for that Key; insert a new group.
using type = lookup_table>;
};

template
struct make {
using type = typename decltype(
hana::fold_left(
std::declval(),
hana::type_c>,
hana::template_
)
)::type;
};
}
```

See the following for background information:
http://stackoverflow.com/questions/42541148/how-do-i-speed-up-many-different-hanafilters-on-the-same-input-data

Contributor guide

Open the contributing guide

Research direction

No target file or test is identified. Start by reviewing hana::detail::hash, fold_left, and the linked background discussion to assess the proposed sparse lookup for group-by operations. The issue does not define an API, implementation location, or completion criteria, so those would need agreement before work can begin.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.