Fast integer handling

Question

Each data structure has its own time complexities. The biggest one that jumps out at you is the hash table. The average times for Insertion, Deletion and Searching are all O(1). But it's really just constant time, since there can be multiple reps through each of these to find the right spot. The real question is, can we do each of those operations in exactly one operation, if space wasn't an issue?

Recently I was working on the radix sort, and figuring out how to speed it up as much as possible. The one thing I settled on was doing a 2-byte counting sort, thus you would only have to loop once through. Then I got to thinking about the trie I used before, with integers where I traversed through by modding the number by 10 each time through.

This seemed to be faster than any other data structure that I've tried, but wanted to make it faster. What I tried today was treating the trie as a guaranteed 2-level tree: each node with \$2^{16}\$ (65536) children. That way I can reference each number like this: root->link[twoByte1]->link[twoByte2]. Where twoByte1 is the first 16 bits, and twoByte2 is the second 16-bit chunk. Problem is, this is a lot of memory. Instead, I decided to make an array of structures, with \$2^{16}\$ bool (uint8_t) values instead, and ran across the same issue. To fix this, I made the following structure.

struct trie {
    unsigned int link[2048];
};

I decided to use 2048 unsigned integers (or signed, wasn't sure if there would be a difference) instead. That way I can treat each bit as the true/false value during look up. In order to reference each position, I would take the first 16 bytes, and reference the element he same way as before, but the 2nd I would divide by 32 to find out which element of the integer array to use, and mod the number again by 32 to find out which bit to look at. The following is the code I used to reference it:

uint8_t getData (int data, uint16_t& dir, uint16_t& pos, uint8_t& x) {
    dir = (data >> 0)  & 0xffff;
    pos = (data >> 16) & 0xffff;
    x   =  pos / 32;
    return pos % 32;
}

The insert function was simply finding the spot and turning the bit on. To do this, I would get the data from the function above, then OR the specific bit with 1. Similarly with deletion, only I would invert the bit string, then AND it, to turn it off. Then to search for that element, I would just return the specific bit. Help with how to clear the bit was found in How do you set, clear, and toggle a single bit? on SO.

Here is the code for those three functions:

void insert(trie *root, int data) {
    uint16_t dir, pos;
    uint8_t x, y = getData(data, dir, pos, x);
    root[dir].link[x] |= 1 << y;
}
bool find(trie *root, int data) {
    uint16_t dir, pos;
    uint8_t x, y = getData(data, dir, pos, x);
    return root[dir].link[x] & (1 << y);
}
void remove(trie *root, int data) {
    uint16_t dir, pos;
    uint8_t x, y = getData(data, dir, pos, x);
    root[dir].link[x] &= ~(1 << y);
}

From here it was as simple as initializing the array of structs. The great thing is that with the number of elements coming in, the data structure will never grow any farther out. Also, in the case of threading, since I'm only turning the bits on during insertion, I don't think I would need to synchronize any of the threads. Therefore it could be speed up with threading. What are your thoughts on this? I made a test case on Ideone. I ran a test on a Linux machine running on an i7, and was able to process 250 million integers every 2.5 seconds.

Answer 1

First there is no C++ here.
You are simply doing C (use class and member functions that way you will not be passing pointers around).

So what you have implemented is a chunked set. Each chunk trie uses 2048 integers to hold existence information and somewhere outside the scope of code review you are creating arrays of theses to define your set.

Looking at the code:

uint16_t dir, pos;
uint8_t x, y = getData(data, dir, pos, x);

This is awful. The first think I am thinking is that x is undefined because you think that functions can return multiple values. BUT I read on and find that x is passed in and is assigned inside the function. This is just horrible in terms of style and readability.

Rues of thumb:

1. Declare one variable per line (and make their names meaningful).
2. Don't mix input/output parameters and return values all in the same function.
   When you use output parameters the result is usually a success value.

What is trie.

bool find(trie *root, int data)

It looks like you have to pass an array of them through for this to work. From inside this function I can not tell how legal it is to access multiple elements. I am assuming the memory management is done somewhere else but who know.

You are making the assumption that an unsigned int is 32 bits.

return pos % 32; // assigned to y

// All your code then calculates bit offsets like this
(1 << y)

The standard only requires 16. https://stackoverflow.com/a/271132/14065

Overall I think this is marginal for C code as you can not do much more.
But for C++ code this absolutely terrible. There is no encapsulation, there is no protection from using the code wrong. There is no initialization to make sure it is all set to zero.

Answer 2

int data; data >> 16 is actually Undefined Behavior. My suggestion, in addition to most of what's already been said, is to stick to unsigned ints as much as possible in C.

Edit: uppercased Undefined Behaviour again (after someone unhelpfully lowercased it) because it’s a technical term from the standard.

It’s Undefined Behaviour if data is negative, that is.