• Yedidya Feldblum's avatar
    Optimal make_integer_sequence · 890625b2
    Yedidya Feldblum authored
    Summary:
    [Folly] Optimal `make_integer_sequence`.
    
    When the builtin `__make_integer_seq` is available, use that. It is the most optimal implementation.
    
    Otherwise, use a tweaked divide-and-conquer implementation. Designed to reuse more template instantiations than the straightforward divide-and-conquer approach in libstdc++ >= 6. And definitely not linearly recursive as in libstdc++ < 6.
    
    Illustrating with an example. Let `M` be whatever template type implements `make_integer_sequence`. For `M<17>`, libstdc++ < 6 does linear recursion (least optimal), instantiating `M<16>`, `M<15>`, ..., `M<1>`. libstdc++ >= 6 does straightforward divide-and-conquer recursion, instantiating `M<8>` and `M<9>`, recursing into `M<4>` and `M<5>`, recursing into `M<2>` and `M<3>`, recursing into `M<1>`. Our implementation does a variant of divide-and-conquer recursion to maximize reuse, instantiating `M<8>` and `M<1>`, recursing into `M<4>`, recursing into `M<2>`.
    
    Implementation derived from `fatal/type/sequence.h`.
    
    Reviewed By: ericniebler
    
    Differential Revision: D5496975
    
    fbshipit-source-id: 449b4e0a1c7b4a5b602752c1d3dd8914bf9a8e71
    890625b2
UtilityTest.cpp 3.27 KB