Sắp xếp lại thời gian của các thành viên dữ liệu?

Question

Tôi đã tự hỏi về một cách có thể để làm cho bố trí bộ nhớ của một lớp có hiệu quả hơn trong mã templated. Theo như tôi biết, Tiêu chuẩn ủy nhiệm các thành viên dữ liệu của một lớp được đưa ra trong bộ nhớ theo thứ tự tuyên bố của họ. Có thể có khả năng đệm được thực hiện bởi trình biên dịch để căn chỉnh các thành viên dữ liệu thêm không cần thiết vào kích thước của lớp. Ý tưởng là sắp xếp lại các khai báo thành viên dữ liệu tại thời gian biên dịch để giảm thiểu sự đệm như vậy. Tôi đã làm một số tìm kiếm, nhưng không thể tìm thấy bất kỳ thông tin (hầu hết thời gian mọi người thảo luận về chỉ thị trình biên dịch đóng gói, mà không phải là khá giống như tôi nhìn thấy nó).

Trước tiên, hãy xem xét như sau (tầm thường, nhưng lặp đi lặp lại và xấu xí) mã (same code on ideone.com) (câu hỏi dưới mã, cảm thấy tự do để bỏ qua phải xuống cho họ): sản lượng

#include <iostream> 
#include <cstdint> 

namespace so 
{ 
template <typename Ta, typename Tb, typename Tc, std::size_t = 
    ((sizeof(Ta) >= sizeof(Tb)) && (sizeof(Tb) >= sizeof(Tc))) ? 10 : 
    ((sizeof(Ta) >= sizeof(Tc)) && (sizeof(Tc) >= sizeof(Tb))) ? 11 : 
    ((sizeof(Tb) >= sizeof(Ta)) && (sizeof(Ta) >= sizeof(Tc))) ? 20 : 
    ((sizeof(Tb) >= sizeof(Tc)) && (sizeof(Tc) >= sizeof(Ta))) ? 21 : 
    ((sizeof(Tc) >= sizeof(Ta)) && (sizeof(Ta) >= sizeof(Tb))) ? 30 : 
    ((sizeof(Tc) >= sizeof(Tb)) && (sizeof(Tb) >= sizeof(Ta))) ? 31 : 0> 
struct foo {}; 

template <typename Ta, typename Tb, typename Tc> 
struct foo<Ta, Tb, Tc, 10> 
{ 
    Ta a; 
    Tb b; 
    Tc c; 
    foo(Ta _a, Tb _b, Tc _c) : a{_a}, b{_b}, c{_c} {} 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct foo<Ta, Tb, Tc, 11> 
{ 
    Ta a; 
    Tc c; 
    Tb b; 
    foo(Ta _a, Tb _b, Tc _c) : a{_a}, c{_c}, b{_b} {} 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct foo<Ta, Tb, Tc, 20> 
{ 
    Tb b; 
    Ta a; 
    Tc c; 
    foo(Ta _a, Tb _b, Tc _c) : b{_b}, a{_a}, c{_c} {} 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct foo<Ta, Tb, Tc, 21> 
{ 
    Tb b; 
    Tc c; 
    Ta a; 
    foo(Ta _a, Tb _b, Tc _c) : b{_b}, c{_c}, a{_a} {} 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct foo<Ta, Tb, Tc, 30> 
{ 
    Tc c; 
    Ta a; 
    Tb b; 
    foo(Ta _a, Tb _b, Tc _c) : c{_c}, a{_a}, b{_b} {} 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct foo<Ta, Tb, Tc, 31> 
{ 
    Tc c; 
    Tb b; 
    Ta a; 
    foo(Ta _a, Tb _b, Tc _c) : c{_c}, b{_b}, a{_a} {} 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct bar: public foo<Ta, Tb, Tc> 
{ 
private: 
    using base = foo<Ta, Tb, Tc>; 
public: 
    bar() = default; 
    using base::base; 
}; 

template <typename Ta, typename Tb, typename Tc> 
struct foobar 
{ 
    Ta a; 
    Tb b; 
    Tc c; 
    foobar() = default; 
    foobar(Ta _a, Tb _b, Tc _c) : a{_a}, b{_b}, c{_c} {} 
}; 
} //namespace so 

int main() 
{ 
so::bar<std::uint16_t, std::uint32_t, std::uint16_t> bar{1, 2, 3}; 
so::foobar<std::uint16_t, std::uint32_t, std::uint16_t> foobar{1, 2, 3}; 

std::cout << sizeof(bar) << "\t" << sizeof(foobar) << std::endl; 

std::cout << bar.a << " : " << bar.b << " : " << bar.c << std::endl; 
std::cout << foobar.a << " : " << foobar.b << " : " << foobar.c << std::endl; 

return (0); 
} 

Chương trình:

8 12 
1 : 2 : 3 
1 : 2 : 3 

Câu hỏi:

1. tôi s có một số, nổi tiếng trình biên dịch độc lập cách giải quyết điều đó (Tăng, có thể)?
2. Nếu không, có một số chỉ thị dành riêng cho trình biên dịch sẽ tự động thực hiện điều đó (không có sự sai lệch dữ liệu như với __atribute__((packed)) của GCC) không?
3. Điều này có thể được thực hiện theo cách tổng quát hơn (có thể sử dụng các mẫu variadic) không?

Cảm ơn bạn trước!

Answer 1

Tôi tin rằng tôi có giải pháp mẫu variadic tương đối đơn giản.

Việc triển khai sẽ yêu cầu một vài người trợ giúp mặc dù, vì vậy tôi sẽ trình bày nó ngược để bạn có thể nắm bắt ý chính của nó trước tiên.

template <typename... Args> 
class OptimizedLayout { 
public: 
    template <size_t I> 
    auto at() -> decltype(std::get<Index<I>::value>(_storage)) { 
     return std::get<Index<I>::value>(_storage); 
    } 

    template <size_t I> 
    auto at() const -> decltype(std::get<Index<I>::value>(_storage)) { 
     return std::get<Index<I>::value>(_storage); 
    } 

private: 
    using Indexed = /**/; // pairs of sorted Args (by decreasing size) 
          // and their original index in the argument list 

    using Storage = /*std::tuple<Indexed.first ...>*/; 

    template <size_t I> 
    using Index = /*index of element of Indexed whose .second is I*/; 

    Storage _storage; 
}; // class OptimizedLayout 

Lợi ích chính ở đây là thay đổi như thế nào để đóng gói các yếu tố sẽ chỉ ảnh hưởng đến cách Indexed được xác định, vì vậy bạn có thể dễ dàng cải thiện các thuật toán. Bây giờ, tôi sẽ chỉ cung cấp một mẫu tương đương với bạn.

---

Tuyên bố từ chối: mã sau đây chưa được kiểm tra, thậm chí không thể biên dịch, hãy để kết quả chính xác.

I. Tạo chỉ mục.

Giải thích có thể được tìm thấy trên the lounge, chúng tôi có thể sử dụng lại nó để tạo một gói cặp (loại, chỉ mục). Để sắp xếp nó, chúng ta sẽ sử dụng một thuật toán MPL, vì vậy nó đơn giản hơn để sản xuất các gói như là một MPL vector.

template <std::size_t... Is> 
struct indices {}; 

template <std::size_t N, std::size_t... Is> 
struct build_indices 
    : build_indices<N-1, N-1, Is...> {}; 

template <std::size_t... Is> 
struct build_indices<0, Is...> { using type = indices<Is...>; }; 

template <typename Tuple, typename Indices> 
struct IndexedImpl; 

template <typename... T, size_t... I> 
struct IndexedImpl< std::tuple<T...>, indices<I...> > { 
    using type = boost::mpl::vector< std::pair<T, I>... >; 
}; 

template <typename Tuple> 
using Indexed = 
    IndexedImpl<Tuple, typename build_indices<std::tuple_size<Tuple>::value>::type>; 

II. Sắp xếp

Để sắp xếp, chúng tôi sẽ sử dụng MPL sort algorithm, hoạt động trên các loại.

struct GreaterSize { 
    template <typename T, typename U> 
    struct apply { 
     using type = boost::mpl::bool_<sizeof(T) > sizeof(U)>; 
    }; 
}; 

template <typename T> 
struct TupleInserter { 
    using state = T; 

    template <typename Seq, typename E> 
    struct apply; 
}; 

template <typename T> 
template <typename... Args, typename E> 
struct TupleInserter<T>::apply<std::tuple<Args...>, E> { 
    using type = std::tuple<Args..., E>; 
}; 

template <typename Tuple> 
using SortedSequence = boost::mpl::sort< 
    typename Indexed<Tuple>::type, 
    GreaterSize, 
    TupleInserter 
>; 

III. Tính toán lớp lưu trữ

Bây giờ, chúng tôi chỉ cần tính toán lớp lưu trữ được thực hiện bằng cách trích phần tử đầu tiên của mỗi cặp. Thật thú vị, khớp mẫu có thể thực sự hỗ trợ ở đây.

template <typename T> 
struct TupleFirstExtractor; 

template <typename... T, size_t... I> 
struct TupleFirstExtractor<std::tuple<std::pair<T, I>...>> { 
    using type = std::tuple<T...>; 
}; 

IV. Tính toán các chỉ số giải

template <typename Tuple, size_t Needle, size_t Acc> 
struct IndexFinderImpl; 

template <typename H, size_t h, typename... Tail, size_t Needle, size_t Acc> 
struct IndexFinderImpl<std::tuple<std::pair<H,h>, Tail...>, Needle, Acc>: 
    IndexFinderImpl<std::tuple<Tail...>, Needle, Acc+1> {}; 

template <typename H, typename... Tail, size_t Needle, size_t Acc> 
struct IndexFinderImpl<std::tuple<std::pair<H, Needle>, Tail...>, Needle, Acc>: 
    std::integral_constant<size_t, Acc> {}; 

V. Đưa nó tất cả cùng nhau

Và bây giờ chúng tôi dây lên tất cả mọi thứ:

template <typename... Args> 
class OptimizedLayout { 
public: 
    template <size_t I> 
    auto at() -> decltype(std::get<Index<I>::value>(_storage)) { 
     return std::get<Index<I>::value>(_storage); 
    } 

    template <size_t I> 
    auto at() const -> decltype(std::get<Index<I>::value>(_storage)) { 
     return std::get<Index<I>::value>(_storage); 
    } 

private: 
    using Indexed = typename SortedSequence<std::tuple<Args...>>::type; 

    using Storage = typename TupleFirstExtractor<Indexed>::type; 

    template <size_t I> 
    using Index = IndexFinderImpl<Indexed, I, 0>; 

    Storage _storage; 
}; // class OptimizedLayout 

Gợi ý: Tôi khuyên sử dụng một không gian tên chuyên ngành để giữ tất cả những người trợ giúp. Mặc dù chúng có thể được xác định trong khuôn mẫu, nhưng việc định nghĩa chúng bên ngoài dễ dàng hơn vì chúng không phụ thuộc vào Args..., tuy nhiên bạn sẽ cần phải tách riêng chúng để tránh xung đột với các phần khác của chương trình.

Answer 2

Hãy xem loạt bài đăng trên blog này của R. Martinho Fernandes: http://flamingdangerzone.com/cxx11/2012/07/06/optimal-tuple-i.html.

Nó phác thảo bao bì tối ưu của bộ dữ liệu. Bạn có thể sử dụng bộ đệm "đóng gói" này làm lưu trữ dữ liệu cho lớp của bạn và cung cấp cho người truy cập ẩn truy cập phần tử kiểu tuple get<0>().