how do I speed up many different hana::filters on the same input data?

Question

Sorry for my minimal example being quite big. This is a working hana algorithm that essentially filters the transitions of 8 different states out of a big tuple of all the transitions.

Although it works it is a bit slow especially since I actually need filter each of like 200 states rather than 8. How can I make it faster?

template<int I, int J, typename T>  //dummy representation of a transition
struct transition {
    static constexpr int source = I;
    static constexpr int dest = J;
};

template<int I>  //just to save typing in my test
auto m() {
    return hana::type_c<transition<I,99,void>>;
}

//big test data
auto types = hana::make_tuple(m<1>(), m<2>(), m<3>(), m<4>(), m<5>(), m<6>(), m<7>(), m<8>(), m<9>(), m<10>(), m<11>(), m<12>(), m<13>(), m<14>(), m<15>(), m<16>(), m<17>(), m<18>(), m<19>(), m<20>(), m<21>(), m<22>(), m<23>(), m<24>(), m<25>(), m<26>(), m<27>(), m<28>(), m<29>(), m<30>(), m<31>(), m<32>(), m<33>(), m<34>(), m<35>(), m<36>(), m<37>(), m<38>(), m<39>(), m<40>(), m<41>(), m<42>(), m<43>(), m<44>(), m<45>(), m<46>(), m<47>(), m<48>(), m<49>(), m<50>(), m<51>(), m<52>(), m<53>(), m<54>(), m<55>(), m<56>(), m<57>(), m<58>(), m<59>(), m<60>(), m<61>(), m<62>(), m<63>(), m<64>(), m<65>(), m<66>(), m<67>(), m<68>(), m<69>(), m<70>(), m<71>(), m<72>(), m<73>(), m<74>(), m<75>(), m<76>(), m<77>(), m<78>(), m<79>(), m<80>(), m<81>(), m<82>(), m<83>(), m<84>(), m<85>(), m<86>(), m<87>(), m<88>(), m<89>(), m<90>(), m<91>(), m<92>(), m<93>(), m<94>(), m<95>(), m<96>(), m<97>(), m<98>(), m<99>(), m<100>(), m<101>(), m<102>(), m<103>(), m<104>(), m<105>(), m<106>(), m<107>(), m<108>(), m<109>(), m<110>(), m<111>(), m<112>(), m<113>(), m<114>(), m<115>(), m<116>(), m<117>(), m<118>(), m<119>(), m<120>(), m<121>(), m<122>(), m<123>(), m<124>(), m<125>(), m<126>(), m<127>(), m<128>(), m<129>(), m<130>(), m<131>(), m<132>(), m<133>(), m<134>(), m<135>(), m<136>(), m<137>(), m<138>(), m<139>(), m<140>(), m<141>(), m<142>(), m<143>(), m<144>(), m<145>(), m<146>(), m<147>(), m<148>(), m<149>(), m<150>(), m<151>(), m<152>(), m<153>(), m<154>(), m<155>(), m<156>(), m<157>(), m<158>(), m<159>(), m<160>(), m<161>(), m<162>(), m<163>(), m<164>(), m<165>(), m<166>(), m<167>(), m<168>(), m<169>(), m<170>(), m<171>(), m<172>(), m<173>(), m<174>(), m<175>(), m<176>(), m<177>(), m<178>(), m<179>(), m<180>(), m<181>(), m<182>(), m<183>(), m<184>(), m<185>(), m<186>(), m<187>(), m<188>(), m<189>(), m<190>(), m<191>(), m<192>(), m<193>(), m<194>(), m<195>(), m<196>(), m<197>(), m<198>(), m<199>(), m<200>(), m<201>(), m<202>(), m<203>(), m<204>(), m<205>(), m<206>(), m<207>(), m<208>(), m<209>(), m<210>(), m<211>(), m<212>(), m<213>(), m<214>(), m<215>(), m<216>(), m<217>(), m<218>(), m<219>(), m<220>(), m<221>(), m<222>(), m<223>(), m<224>(), m<225>(), m<226>(), m<227>(), m<228>(), m<229>(), m<230>(), m<231>(), m<232>(), m<233>(), m<234>(), m<235>(), m<236>(), m<237>(), m<238>(), m<239>(), m<240>(), m<241>(), m<242>(), m<243>(), m<244>(), m<245>(), m<246>(), m<247>(), m<248>(), m<249>(), m<250>(), m<251>(), m<252>(), m<253>(), m<254>(), m<255>(), m<256>(), m<257>(), m<258>(), m<259>(), m<260>(), m<261>(), m<262>(), m<263>(), m<264>(), m<265>(), m<266>(), m<267>(), m<268>(), m<269>(), m<270>(), m<271>(), m<272>(), m<273>(), m<274>(), m<275>(), m<276>(), m<277>(), m<278>(), m<279>(), m<280>(), m<281>(), m<282>(), m<283>(), m<284>(), m<285>(), m<286>(), m<287>(), m<288>(), m<289>(), m<290>(), m<291>(), m<292>(), m<293>(), m<294>(), m<295>(), m<296>(), m<297>(), m<298>(), m<299>(), m<300>(), m<301>(), m<302>(), m<303>(), m<304>(), m<305>(), m<306>(), m<307>(), m<308>(), m<309>(), m<310>(), m<311>(), m<312>(), m<313>(), m<314>(), m<315>(), m<316>(), m<317>(), m<318>(), m<319>(), m<320>(), m<321>(), m<322>(), m<323>(), m<324>(), m<325>(), m<326>(), m<327>(), m<328>(), m<329>(), m<330>(), m<331>(), m<332>(), m<333>(), m<334>(), m<335>(), m<336>(), m<337>(), m<338>(), m<339>(), m<340>(), m<341>(), m<342>(), m<343>(), m<344>(), m<345>(), m<346>(), m<347>(), m<348>(), m<349>(), m<350>(), m<351>(), m<352>(), m<353>(), m<354>(), m<355>(), m<356>(), m<357>(), m<358>(), m<359>(), m<360>(), m<361>(), m<362>(), m<363>(), m<364>(), m<365>(), m<366>(), m<367>(), m<368>(), m<369>(), m<370>(), m<371>(), m<372>(), m<373>(), m<374>(), m<375>(), m<376>(), m<377>(), m<378>(), m<379>(), m<380>(), m<381>(), m<382>(), m<383>(), m<384>(), m<385>(), m<386>(), m<387>(), m<388>(), m<389>(), m<390>(), m<391>(), m<392>(), m<393>(), m<394>(), m<395>(), m<396>(), m<397>(), m<398>(), m<399>(), m<400>(), m<401>(), m<402>(), m<403>(), m<404>(), m<405>(), m<406>(), m<407>(), m<408>(), m<409>(), m<410>(), m<411>(), m<412>(), m<413>(), m<414>(), m<415>(), m<416>(), m<417>(), m<418>(), m<419>(), m<420>(), m<421>(), m<422>(), m<423>(), m<424>(), m<425>(), m<426>(), m<427>(), m<428>(), m<429>(), m<430>(), m<431>(), m<432>(), m<433>(), m<434>(), m<435>(), m<436>(), m<437>(), m<438>(), m<439>(), m<440>(), m<441>(), m<442>(), m<443>(), m<444>(), m<445>(), m<446>(), m<447>(), m<448>(), m<449>(), m<450>(), m<451>(), m<452>(), m<453>(), m<454>(), m<455>(), m<456>(), m<457>(), m<458>(), m<459>(), m<460>(), m<461>(), m<462>(), m<463>(), m<464>(), m<465>(), m<466>(), m<467>(), m<468>(), m<469>(), m<470>(), m<471>(), m<472>(), m<473>(), m<474>(), m<475>(), m<476>(), m<477>(), m<478>(), m<479>(), m<480>(), m<481>(), m<482>(), m<483>(), m<484>(), m<485>(), m<486>(), m<487>(), m<488>(), m<489>(), m<490>(), m<491>(), m<492>(), m<493>(), m<494>(), m<495>(), m<496>(), m<497>(), m<498>(), m<499>(), m<500>(), m<501>(), m<502>(), m<503>(), m<504>(), m<505>(), m<506>(), m<507>(), m<508>(), m<509>(), m<510>(), m<511>(), m<512>(), m<513>(), m<514>(), m<515>(), m<516>(), m<517>(), m<518>(), m<519>(), m<520>(), m<521>(), m<522>(), m<523>(), m<524>(), m<525>(), m<526>(), m<527>(), m<528>(), m<529>(), m<530>(), m<531>(), m<532>(), m<533>(), m<534>(), m<535>(), m<536>(), m<537>(), m<538>(), m<539>(), m<540>(), m<541>(), m<542>(), m<543>(), m<544>(), m<545>(), m<546>(), m<547>(), m<548>(), m<549>(), m<550>(), m<551>(), m<552>(), m<553>(), m<554>(), m<555>(), m<556>(), m<557>(), m<558>(), m<559>(), m<560>(), m<561>(), m<562>(), m<563>(), m<564>(), m<565>(), m<566>(), m<567>(), m<568>(), m<569>(), m<570>(), m<571>(), m<572>(), m<573>(), m<574>(), m<575>(), m<576>(), m<577>(), m<578>(), m<579>(), m<580>(), m<581>(), m<582>(), m<583>(), m<584>(), m<585>(), m<586>(), m<587>(), m<588>(), m<589>(), m<590>(), m<591>(), m<592>(), m<593>(), m<594>(), m<595>(), m<596>(), m<597>(), m<598>(), m<599>(), m<600>(), m<601>(), m<602>(), m<603>(), m<604>(), m<605>(), m<606>(), m<607>(), m<608>(), m<609>(), m<610>(), m<611>(), m<612>(), m<613>(), m<614>(), m<615>(), m<616>(), m<617>(), m<618>(), m<619>(), m<620>(), m<621>(), m<622>(), m<623>(), m<624>(), m<625>(), m<626>(), m<627>(), m<628>(), m<629>(), m<630>(), m<631>(), m<632>(), m<633>(), m<634>(), m<635>(), m<636>(), m<637>(), m<638>(), m<639>(), m<640>(), m<641>(), m<642>(), m<643>(), m<644>(), m<645>(), m<646>(), m<647>(), m<648>(), m<649>(), m<650>(), m<651>(), m<652>(), m<653>(), m<654>(), m<655>(), m<656>(), m<657>(), m<658>(), m<659>(), m<660>(), m<661>(), m<662>(), m<663>(), m<664>(), m<665>(), m<666>(), m<667>(), m<668>(), m<669>(), m<670>(), m<671>(), m<672>(), m<673>(), m<674>(), m<675>(), m<676>(), m<677>(), m<678>(), m<679>(), m<680>(), m<681>(), m<682>(), m<683>(), m<684>(), m<685>(), m<686>(), m<687>(), m<688>(), m<689>(), m<690>(), m<691>(), m<692>(), m<693>(), m<694>(), m<695>(), m<696>(), m<697>(), m<698>(), m<699>(), m<700>(), m<701>(), m<702>(), m<703>(), m<704>(), m<705>(), m<706>(), m<707>(), m<708>(), m<709>(), m<710>(), m<711>(), m<712>(), m<713>(), m<714>(), m<715>(), m<716>(), m<717>(), m<718>(), m<719>(), m<720>(), m<721>(), m<722>(), m<723>(), m<724>(), m<725>(), m<726>(), m<727>(), m<728>(), m<729>(), m<730>(), m<731>(), m<732>(), m<733>(), m<734>(), m<735>(), m<736>(), m<737>(), m<738>(), m<739>(), m<740>(), m<741>(), m<742>(), m<743>(), m<744>(), m<745>(), m<746>(), m<747>(), m<748>(), m<749>(), m<750>(), m<751>(), m<752>(), m<753>(), m<754>(), m<755>(), m<756>(), m<757>(), m<758>(), m<759>(), m<760>(), m<761>(), m<762>(), m<763>(), m<764>(), m<765>(), m<766>(), m<767>(), m<768>(), m<769>(), m<770>(), m<771>(), m<772>(), m<773>(), m<774>(), m<775>(), m<776>(), m<777>(), m<778>(), m<779>(), m<780>(), m<781>(), m<782>(), m<783>(), m<784>(), m<785>(), m<786>(), m<787>(), m<788>(), m<789>(), m<790>(), m<791>(), m<792>(), m<793>(), m<794>(), m<795>(), m<796>(), m<797>(), m<798>(), m<799>(), m<800>(), m<801>(), m<802>(), m<803>(), m<804>(), m<805>(), m<806>(), m<807>(), m<808>(), m<809>(), m<810>(), m<811>(), m<812>(), m<813>(), m<814>(), m<815>(), m<816>(), m<817>(), m<818>(), m<819>(), m<820>(), m<821>(), m<822>(), m<823>(), m<824>(), m<825>(), m<826>(), m<827>(), m<828>(), m<829>(), m<830>(), m<831>(), m<832>(), m<833>(), m<834>(), m<835>(), m<836>(), m<837>(), m<838>(), m<839>(), m<840>(), m<841>(), m<842>(), m<843>(), m<844>(), m<845>(), m<846>(), m<847>(), m<848>(), m<849>(), m<850>(), m<851>(), m<852>(), m<853>(), m<854>(), m<855>(), m<856>(), m<857>(), m<858>(), m<859>(), m<860>(), m<861>(), m<862>(), m<863>(), m<864>(), m<865>(), m<866>(), m<867>(), m<868>(), m<869>(), m<870>(), m<871>(), m<872>(), m<873>(), m<874>(), m<875>(), m<876>(), m<877>(), m<878>(), m<879>(), m<880>(), m<881>(), m<882>(), m<883>(), m<884>(), m<885>(), m<886>(), m<887>(), m<888>(), m<889>(), m<890>(), m<891>(), m<892>(), m<893>(), m<894>(), m<895>(), m<896>(), m<897>(), m<898>(), m<899>(), m<900>(), m<901>(), m<902>(), m<903>(), m<904>(), m<905>(), m<906>(), m<907>(), m<908>(), m<909>(), m<910>(), m<911>(), m<912>(), m<913>(), m<914>(), m<915>(), m<916>(), m<917>(), m<918>(), m<919>(), m<920>(), m<921>(), m<922>(), m<923>(), m<924>(), m<925>(), m<926>(), m<927>(), m<928>(), m<929>(), m<930>(), m<931>(), m<932>(), m<933>(), m<934>(), m<935>(), m<936>(), m<937>(), m<938>(), m<939>(), m<940>(), m<941>(), m<942>(), m<943>(), m<944>(), m<945>(), m<946>(), m<947>(), m<948>(), m<949>(), m<950>(), m<951>(), m<952>(), m<953>(), m<954>(), m<955>(), m<956>(), m<957>(), m<958>(), m<959>(), m<960>(), m<961>(), m<962>(), m<963>(), m<964>(), m<965>(), m<966>(), m<967>(), m<968>(), m<969>(), m<970>(), m<971>(), m<972>(), m<973>(), m<974>(), m<975>(), m<976>(), m<977>(), m<978>(), m<979>(), m<980>(), m<981>(), m<982>(), m<983>(), m<984>(), m<985>(), m<986>(), m<987>(), m<988>(), m<989>(), m<990>(), m<991>(), m<992>(), m<993>(), m<994>(), m<995>(), m<996>(), m<997>(), m<998>(), m<999>());

//goal is to make a tuple of tuples, one for each states transitions
auto result = hana::make_tuple(
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 1)>;
}),
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 2)>;
}),  
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 3)>;
}),  
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 4)>;
}),  
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 5)>;
}), 
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 6)>;
}), 
hana::filter(types, [](auto a) {
    return hana::integral_c<bool, (decltype(a)::type::source == 7)>;
}));

Answer 1

If all of your values will have no run-time state (ie hana::type) then one large piece of low hanging fruit would be to use an empty representation of a tuple.

template <typename ...Xs>
struct ding_bat_tuple { };

hana::tuple has to support run-time values and it has several gnarly constructors that make instantiating it an expensive operation.

The cool thing is that you can specialize a few Hana functions for your empty tuple to make it a hana::Sequence getting its corresponding functions for free (like hana::filter)

Here is an example: https://github.com/ricejasonf/nbdl/blob/master/include/mpdef/list.hpp

Also, if the size of types is small, you could use hana::sort then hana::group which might be faster for that use case.

Update

I made a benchmark of the "group by" algorithm using metabench with both tuple representations. The empty tuple is faster, but honestly I was expecting the difference to be more staggering. Note that 20 is really 200 elements in the tuple.

Here is the gist of the benchmark source code:

https://gist.github.com/ricejasonf/c9cfea01876b58d5778abcd934b14484