I have an assignment:

The three planes X=0, Y=0, and Z=0 divide the 3D space into 8 octant domains. Given an array of 3D points, the following function counts the number of points belonging to each octant. Write a version of that function which doesn’t use either if-statements or the if operator.

The function:

typedef float pnt[3];

void count(pnt const* pnts, const int n, unsigned cnt[8]) {

    for (int i = 0; i < 8;   i)
        cnt[i] = 0;

    for (int i = 0; i < n;   i) {
        if (pnts[i][0] >= 0.0f && pnts[i][1] >= 0.0f && pnts[i][2] >= 0.0f)   cnt[7]; else
        if (pnts[i][0] >= 0.0f && pnts[i][1] >= 0.0f && pnts[i][2] < 0.0f)   cnt[3]; else
        if (pnts[i][0] >= 0.0f && pnts[i][1] < 0.0f && pnts[i][2] >= 0.0f)   cnt[5]; else
        if (pnts[i][0] >= 0.0f && pnts[i][1] < 0.0f && pnts[i][2] < 0.0f)   cnt[1]; else
        if (pnts[i][0] < 0.0f && pnts[i][1] >= 0.0f && pnts[i][2] >= 0.0f)   cnt[6]; else
        if (pnts[i][0] < 0.0f && pnts[i][1] >= 0.0f && pnts[i][2] < 0.0f)   cnt[2]; else
        if (pnts[i][0] < 0.0f && pnts[i][1] < 0.0f && pnts[i][2] >= 0.0f)   cnt[4]; else
          cnt[0];
    }
}

Rest of the assignment:

Also implement the missing code for populating an array of random points and compare the performance of the two versions (with and without if statements) assuming n = 2^24. (hint: each bit in the octant index of a point is associated to one dimension).

I am stuck at populating an array to the function. I have tried different ways and none of them have worked and results in stack overflow. Either I am misunderstanding the assignment or I am doing something wrong with my code:

I am trying to populate my array with random values and sending it to the function like this:

unsigned cnt[8];

pnt arr[(1 << 24)];

for (int i = 0; i < (1 << 24) - 1; i  )
{
    for (int j = 0; j < 3; j  )
    {
        arr[i][j] = (rand() % 100) - 50;
    }
}
    
count(arr, 1 << 24, cnt);

This code gives me stack overflow in debug mode. In release mode I don't get any errors but also it does not even touch my for loop or working with my count function.

I know that pnt arr[(1 << 24)] is alot of space in memory and I also understand that I get stack overflow because that is too much memory allocated for the array but how should I interpret " assuming n = 2^24"?

CodePudding user response：

To populate array drop use of c-arrays. In your scenario they are to big to be stored on stack (as you noticed).

So just use std::vector to hold this values.

using Point = std::array<float, 3>;
using Points = std::vector<Point>;
using DomainCount = std::array<unsigned, 8>;

Points generateRandomData(std::size_t n)
{
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<float> dis{-50, 50};

    Points data;
    data.reserve(n);
    std::generate_n(std::back_inserter(data), n, [dis, &gen]() {
        return Point{dis(gen), dis(gen), dis(gen)};
    };
}

If youi need old API (which is look like very old C style) you can do this:

auto data = generateRandomData(1 << 24);
count(data.data(), data.size(), cnt);

To drop if-s you need use fact that bool expression is implicitly converted to 0 or 1 integer value.

using Point = std::array<float, 3>;
using Points = std::vector<Point>;
using DomainCount = std::array<unsigned, 8>;

DomainCount count(const Points& points) {
    DomainCount r{};

    for (const auto& p : points) {
        auto xIndex = p[0] < 0;
        auto yIndex = static_cast<int>(p[1] < 0) << 1;
        auto zIndex = static_cast<int>(p[2] < 0) << 2;
        
          r[xIndex   yIndex   zIndex];
    }
    return r;
}

https://godbolt.org/z/YGaxnY6Pz

Note technique is called branchless programing and leads to code which is faster then if version (unpredictable branches are hard task for CPU).

CodePudding user response：

Allocating to the heap solved it.

pnt* arr = new pnt [(1 << 24)];

for (int i = 0; i < (1 << 24) - 1; i  )
{
    for (int j = 0; j < 3; j  )
    {
        arr[i][j] = (rand() % 100) - 50;
    }
}

count(arr, 1 << 24, cnt);