CODEWITHSUNDEEP
c++c++11data-structuresbit-manipulation
Mads
Mads

Reputation: 724

Packing integers close together in a vector - can it be done faster?

For the data structure I'm currently making, I need to pack the integers closely together. This means, that if the maximum element in a vector is n, I would use at most lg n bits to represent it. Thus, I treat a vector of integers like a list of bits. My current solution works just fine - but I need to know if I can speed up the unpacking of an integer. That lookup operation is a quite integral part of the search query to my data structure.

// uint is an unsigned 32 bit integer (std::uint32_t)
uint
Data::findInt(const std::vector<uint>& input, int size, int pos) {
    pos = pos*size;
    int end = pos+size;
    int firstc = pos/32;
    int secondc = end/32;
    int ipos = pos % 32;
    int jpos = end % 32;

    if(firstc == secondc) {
        uint number = input.at(firstc);
        number = number >> (32 - end);
        number = number & ((1 << size) - 1);
        return number;
    }
    // else
    uint number = input.at(firstc);
    number = number << (jpos);
    number = number & ((1 << size) -1);
    uint number2 = input.at(secondc);
    number2 = number2 >> (32 - jpos);
    number2 = number2 & ((1 << jpos) - 1);

    return number + number2;
}

std::vector<uint>
Data::packBits(const std::vector<uint>& input, int size) {

    std::vector<char> bits = translatetobits(input, size);
    while(bits.size() % 32 != 0) {
        bits.push_back(0);
    }

    std::vector<uint> packedbits;
    for(int i = 0; i < bits.size(); i += 32) {
        uint res = 0;
        for(int j = 0; j < 31; ++j) {
            res += (bits.at(i+j));
            res = res << 1;
        }
        res += (bits.at(i+31));
        packedbits.push_back(res);
    }

    // Current lookup requires an empty entry - should be fixed
    packedbits.push_back(0);

    return packedbits;
}

I can only fetch one integer at a time and the index of a look-up operation jumps quite arbitrarily around, so I can't batch look-ups together. Does anyone have a good idea for speeding up the look-up?

Upvotes: 0

Views: 306

Answers (1)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275740

at is checked. Check bounds once, not each interaction with the vector.

Consider using raw pointers instead of vectors for the low level operations.

Your packing is extremely inefficient -- it does memory allocation. Why in gods name.

You should be using fixed sized data, not generic uints.

You have duplicated code calculating number. Consider eliminating. The constant 32 in that code is a matter of how the bits where packed -- pack in a different way, save an operation.

You can optimize for branclessness if you want, but that will probably not grant a performance increase (it will grant a worst-case performance increase, but not repeated operations, as branch predictors are pretty solid). One possibility is to always unpack your data into a 64 bit unsigned type, then shift it away: I think there are ways to do it so that the 2nd lookup just injects zeros, or data that gets masked out, if it isn't needed.

Upvotes: 1

Related Questions