Is there a way to improve the speed or efficiency of this lookup? (C/C++)

Question

I have a function I've written to convert from a 64-bit integer to a base 62 string. Originally, I achieved this like so:

char* charset = " 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int charsetLength = strlen(charset);

std::string integerToKey(unsigned long long input)
{
    unsigned long long num = input;
    string key = "";

    while(num)
    {
        key += charset[num % charsetLength];
        num /= charsetLength;
    }

    return key;
}

However, this was too slow.

I improved the speed by providing an option to generate a lookup table. The table is about 62^4 strings in size, and is generated like so:

// Create the integer to key conversion lookup table
int lookupChars;

if(lookupDisabled)
    lookupChars = 1;
else
    largeLookup ? lookupChars = 4 : lookupChars = 2;

lookupSize = pow(charsetLength, lookupChars);
integerToKeyLookup = new char*[lookupSize];

for(unsigned long i = 0; i < lookupSize; i++)
{
    unsigned long num = i;
    int j = 0;

    integerToKeyLookup[i] = new char[lookupChars];

    while(num)
    {
        integerToKeyLookup[i][j] = charset[num % charsetLength];
        num /= charsetLength;

        j++;
    }

    // Null terminate the string
    integerToKeyLookup[i][j] = '\0';
}

The actual conversion then looks like this:

std::string integerToKey(unsigned long long input)
{
    unsigned long long num = input;
    string key = "";

    while(num)
    {
        key += integerToKeyLookup[num % lookupSize];
        num /= lookupSize;
    }

    return key;
}

This improved speed by a large margin, but I still believe it can be improved. Memory usage on a 32-bit system is around 300 MB, and more than 400 MB on a 64-bit system. It seems like I should be able to reduce memory and/or improve speed, but I'm not sure how.

If anyone could help me figure out how this table could be further optimized, I'd greatly appreciate it.

Answer 1

Using some kind of string builder rather than repeated concatenation into 'key' would provide a significant speed boost.

Answer 2

You may want to reserve memory in advance for your string key. This may get you a decent performance gain, as well as a gain in memory utilization. Whenever you call the append operator on std::string, it may double the size of the internal buffer if it has to reallocate. This means each string may be taking up significantly more memory than is necessary to store the characters. You can avoid this by reserving memory for the string in advance.

Answer 3

You don't need to copy input into num, because you pass it by value. You can also compute the length of charset in compiletime, there's no need to compute it in runtime every single time you call the function.

But these are very minor performance issues. I think the the most significant help you can gain is by avoiding the string concatenation in the loop. When you construct the key string pass the string constructor the length of your result string so that there is only one allocation for the string. Then in the loop when you concatenate into the string you will not re-allocate.

You can make things even slightly more efficient if you take the target string as a reference parameter or even as two iterators like the standard algorithms do. But that is arguably a step too far.

By the way, what if the value passed in for input is zero? You won't even enter the loop; shouldn't key then be "0"?

I see the value passed in for input can't be negative, but just so we note: the C remainder operator isn't a modulo operator.

Answer 4

I agree with Rob Walker - you're concentrating on improving performance in the wrong area. The string is the slowest part.

I timed the code (your original is broken, btw) and your original (when fixed) was 44982140 cycles for 100000 lookups and the following code is about 13113670.

const char* charset = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
#define CHARSET_LENGTH 62

// maximum size = 11 chars
void integerToKey(char result[13], unsigned long long input)
{
    char* p = result;
    while(input > 0)
    {
     *p++ = charset[input % CHARSET_LENGTH];
     input /= CHARSET_LENGTH;
    }

    // null termination
    *p = '\0';
    // need to reverse the output
    char* o = result;
    while(o + 1 < p)
     swap(*++o, *--p);
}

Answer 5

This is almost a textbook case of how not to do this. Concatenating strings in a loop is a bad idea, both because appending isn't particularly fast, and because you're constantly allocating memory.

Note: your question states that you're converting to base-62, but the code seems to have 63 symbols. Which are you trying to do?

Given a 64-bit integer, you can calculate that you won't need any more than 11 digits in the result, so using a static 12 character buffer will certainly help improve your speed. On the other hand, it's likely that your C++ library has a long-long equivalent to ultoa, which will be pretty optimal.

---

Edit: Here's something I whipped up. It allows you to specify any desired base as well:

std::string ullToString(unsigned long long v, int base = 64) {
    assert(base < 65);
    assert(base > 1);
    static const char digits[]="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ+/";
    const int max_length=65;
    static char buffer[max_length];

    buffer[max_length-1]=0;
    char *d = buffer + max_length-1;
    do {
     d--;
     int remainder = v % base;
     v /= base;
     *d = digits[remainder];
    } while(v>0);

    return d;
}

This only creates one std::string object, and doesn't move memory around unnecessarily. It currently doesn't zero-pad the output, but it's trivial to change it to do that to however many digits of output you want.

Answer 6

Why not just use a base64 library? Is really important that 63 equals '11' and not a longer string?

size_t base64_encode(char* outbuffer, size_t maxoutbuflen, const char* inbuffer, size_t inbuflen);

std::string integerToKey(unsigned long long input) {
    char buffer[14];
    size_t len = base64_encode(buffer, sizeof buffer, (const char*)&input, sizeof input);
    return std::string(buffer, len);
}

Yes, every string will end with an equal size. If you don't want it to, strip off the equal sign. (Just remember to add it back if you need to decode the number.)

Of course, my real question is why are you turning a fixed width 8byte value and not using it directly as your "key" instead of the variable length string value?

Footnote: I'm well aware of the endian issues with this. He didn't say what the key will be used for and so I assume it isn't being used in network communications between machines of disparate endian-ness.

Answer 7

If you could add two more symbols so that it is converting to base-64, your modulus and division operations would turn into a bit mask and shift. Much faster than a division.

Answer 8

If all you need is a short string key, converting to base-64 numbers would speed up things a lot, since div/mod 64 is very cheap (shift/mask).