Make 2 non-static fields (that are dynamic arrays) use memory near each other

54 views Asked by At

Let B1 and B2 be a dynamic-size storage classes.
(e.g. B1~std::vector<char> B2~std::vector<float>)

In C++11, if I code B1 and B2's move and copy function (rule of five), a class C that contains them as fields will copy/move correctly by default automatically.

class C{
    B1 b1; B2 b2;
};

It works very good.

Problem

Today, I got the profile result + did some test about performance issue.
Main objective: I have to make b1 and b2 of the same instance of C allocate memory near each other :-

b1[0]  b1[1] ... b1[b1.size-1] (minimum gap) b2[0]  b2[1] ... b2[b2.size-1] 

If I can, I will get performance boost by 10-20% for the whole program.

My poor solution

I can use a custom allocator like this (pseudo-code):-

class C{
    B1 b1; 
    B2 b2;
    Allocator* allo_; // can be heap allocator 
    public: void reserve(int size){
        //old : b1.reserve(size); b2.reserve(size);  .... so easy
        //new :-
        B1 b1Next; B2 b2Next;
        int nb1=b1Next.howMuchIWant(size); 
        int nb2=b2Next.howMuchIWant(size);
        //^ request amount of bytes needed if capacity="size"
        void* vPtr=allo_->allocate(nb1+nb2);
        b1Next.setMemory(vPtr);
        b2Next.setMemory(vPtr + nb1);  //add "vPtr" by "nb1" bytes
        b1Next=b1;   //copy assignment (not move memory)
        b2Next=b2;   //copy assignment (not move memory)
        b1=std::move(b1Next);   //move memory
        b2=std::move(b2Next);   //move memory 
        //clean up previous "vPtr" (not shown)
    }
};

It works, but the code become far harder to debug/maintain. Not to mention C's move and copy.

In the old version, all copy/move mess appear only in B1 and B2.
Now, the mess appears in every class that use data-structure like B1 and B2 directly.

Question

What are C++ technique/design-pattern/idiom that can help?
To answer, no runable code is required. Pseudo code or just a concept is enough.

I am so regret for not providing MCVE.
Custom allocator and array management are things that really hard for the minimizing.

1

There are 1 answers

7
nh_ On

One possibility to improve data locality is going from a struct of vectors to a vector of structs. Instead of

struct S
{
    std::vector<char> c;
    std::vector<int> i;
};
S data;

use a

struct S
{
    char c;
    int i;
};
std::vector<S> data;

That way, data is always stored together and you don't need to tinker around with custom allocators. Whether this is applicable in your situation primarily depends on two conditions:

  • Is it necessary to have all char (or int) contiguous? E.g. because an API is called regularly that requires a vector of respective type.
  • Is the number of stored char and int equal (at least nearly equal)?