5
\$\begingroup\$

Given a 64-bit integer x (which is always larger than 0), we wish to map it to an index so that:

  • when x is between 0..64, we map it to 0,
  • when x is between 65..128, we map it to 1,
  • when x is between 129..192, we map it to 2, etc.

Writing such a function get_index(x) is simple, consider say the following program:

#include <iostream>
#include <cstdint>
#include <cmath>
#include <cassert>

// For benchmarking
#include <vector>
#include <algorithm>

std::uint64_t get_index(std::uint64_t x)
{
    return std::ceil(x / 64.0) - 1;
}

int main()
{
    // To see the expected outcome.
    /*
    for (int i = 1; i <= 129; ++i)
    {
        std::int64_t idx = get_index(i);
        std::cout << "i : " << i << " = " << idx << "\n";
    }
    */

    // A small performance benchmark.
    // Just in case print something so that the compiler doesn't optimize things away.
    std::vector<std::uint64_t> dummy;
    const std::uint64_t MAX = 10000000;
    for (std::uint64_t i = 1; i <= MAX; ++i)
    {
        dummy.push_back(get_index(i));
    }

    std::cout << dummy.size() << " " << *max_element(dummy.begin(), dummy.end()) << "\n";
}

Is there a (much) faster implementation for get_index(x)? Likely one that completely avoids floating-point math, ceilings etc.

For instance, I know that dividing by 64 is the same thing as bit-shifting x to the right by 6, but I'm not much of a bit hack wizard to figure out the rest without resorting to things that seem messy.

\$\endgroup\$
  • \$\begingroup\$ @TobySpeight Sorry, the description should have used 192 as the upper bound, not 256. Fixed now. And indeed, I'm looking for what you suggest, but ceilining instead of floor. \$\endgroup\$ – st28 Dec 13 '17 at 18:27
  • \$\begingroup\$ Color me puzzled. You ask a question, answer it immediately, and then say it's too hard to figure out. What is this routine actually being used for? Could you post actual code instead of this toy driver? \$\endgroup\$ – Snowbody Dec 13 '17 at 18:31
  • 4
    \$\begingroup\$ Shift six bits to the right and call it a day? \$\endgroup\$ – Incomputable Dec 13 '17 at 18:37
  • \$\begingroup\$ @Incomputable Well, almost. Doing that will not map say 64 and 128 correctly. It's perhaps OK to shift by 6, then check if the input number is a multiple of 64, and if so, decrement by 1. But is there something less messier? \$\endgroup\$ – st28 Dec 13 '17 at 18:42
  • 1
    \$\begingroup\$ shift, mask, decrement. Doesn’t look messy for me. \$\endgroup\$ – Incomputable Dec 13 '17 at 18:47
3
\$\begingroup\$
std::uint64_t get_index(std::uint64_t x)
{
    return 0u == x ? 0u : (x-1u)>> 6;
}

Will it faster, I doubt.

By the way, your code for x = 0 will yield -1, which is not same as your description. if you do not need x = 0 input, then you can remove the if statement as

std::uint64_t get_index(std::uint64_t x)
{
    return (x-1u)>> 6;  // for this, x must be not 0u.
}
\$\endgroup\$
3
\$\begingroup\$

I'd split the includes into what's needed for your function, and what's there only for the test. That makes it simpler to separate it from the tests, for use in production code:

#include <cstdint>
#include <cmath>

std::uint64_t get_index(std::uint64_t x)
{
    return std::ceil(x / 64.0) - 1;
}


// For benchmarking
#include <iostream>
#include <vector>
#include <algorithm>

int main()

I removed <cassert>, which wasn't being used.


Naming - can you be more specific than get_index()? Perhaps you've generalised for Code Review, but don't give things such general names in real code, unless you can qualify them with a namespace or a class.


Next, let's look at the benchmark. I had to fix the missing prefix of std::max_element. Unfortunately, this code is mostly testing std::vector::push_back() rather than get_index(), as Valgrind reports:

total heap usage: 27 allocs, 27 frees, 268,509,176 bytes allocated

One possible solution to this is to combine all the results into a single value. You could use addition, but that would overflow, and it requires some thought to predict the correct value. My preference is to XOR together all the results; for an even number of results, we'll end up with 0, because for each get_index() of 2n, there will be a get_index() of 2n+1 which should give the same result:

int main()
{
    // A small performance benchmark.
    auto const start_time = std::chrono::steady_clock::now();

    std::uint64_t total = 0;
    const std::uint64_t MAX = 10000000;
    for (std::uint64_t i = 1; i <= MAX; ++i)
    {
        total ^= get_index(i);
    }

    auto const end_time = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::chrono::seconds::period> time_taken = end_time - start_time;

    std::cout << time_taken.count() << " seconds" << std::endl;

    return total != 0;
}

This runs about 10 times faster, but still exercises the function the same number of times; that means that changes in the result better reflect the performance of our function.


Let's test some more values for correctnes. We should test large values as well as small ones, because we know that floating point loses precision as the magnitude increases:

int expect_eq(std::uint64_t a, std::uint64_t b, const char *as, const char *bs)
{
    if (a == b) return 0;
    std::cerr << as << " (" << a << ") != " << bs << " (" << b << ")\n";
    return 1;
}
#define EXPECT_EQ(a,b) (expect_eq((a),(b),#a,#b))

int main()
{
    // Tests of correctness at boundaries
    return EXPECT_EQ(total, 0)
        +  EXPECT_EQ(get_index(0), 0)
        +  EXPECT_EQ(get_index(1), 0)
        +  EXPECT_EQ(get_index(64), 0)
        +  EXPECT_EQ(get_index(65), 1)
        +  EXPECT_EQ(get_index(128), 1)
        +  EXPECT_EQ(get_index(0xFFFFFFFFFFFFFFC0), 0X3FFFFFFFFFFFFFE)
        +  EXPECT_EQ(get_index(0xFFFFFFFFFFFFFFC1), 0X3FFFFFFFFFFFFFF)
        +  EXPECT_EQ(get_index(0xFFFFFFFFFFFFFFFF), 0X3FFFFFFFFFFFFFF);
}

As well as the rounding errors in the large values, this points out a bug in the implementation - the test that get_index(0) returns 0 fails; it returns UINT64_MAX instead.

We can now provide a fixed implementation:

#include <cstdint>
std::uint64_t get_index(std::uint64_t x)
{
    return x ? (x-1)/64 : 0;
}

This reduces my execution time from 0.636 to 0.237 seconds, and fixes the bugs identified above. Since it's an unsigned type, you could use a bit-shift (>>6 instead of /64), but the division more clearly indicates the intent, and any decent optimising compiler will generate identical code.


Here's my full program:

#include <cstdint>
std::uint64_t get_index(std::uint64_t x)
{
    return x ? (x-1)/64 : 0;
}


#include <chrono>
#include <iostream>

int expect_eq(std::uint64_t a, std::uint64_t b, const char *as, const char *bs)
{
    if (a == b) return 0;
    std::cerr << as << " (" << a << ") != " << bs << " (" << b << ")\n";
    return 1;
}
#define EXPECT_EQ(a,b) (expect_eq((a),(b),#a,#b))

int main()
{
    // A small performance benchmark.
    auto const start_time = std::chrono::steady_clock::now();

    std::uint64_t total = 0;
    const std::uint64_t MAX = 10000000;
    for (std::uint64_t i = 1; i <= MAX; ++i)
    {
        total ^= get_index(i);
    }

    auto const end_time = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::chrono::seconds::period> time_taken = end_time - start_time;

    std::cout << time_taken.count() << " seconds" << std::endl;

    // Tests of correctness at boundaries
    return EXPECT_EQ(total, 0)
        +  EXPECT_EQ(get_index(0), 0)
        +  EXPECT_EQ(get_index(1), 0)
        +  EXPECT_EQ(get_index(64), 0)
        +  EXPECT_EQ(get_index(65), 1)
        +  EXPECT_EQ(get_index(128), 1)
        +  EXPECT_EQ(get_index(0xFFFFFFFFFFFFFFC0), 0X3FFFFFFFFFFFFFE)
        +  EXPECT_EQ(get_index(0xFFFFFFFFFFFFFFC1), 0X3FFFFFFFFFFFFFF)
        +  EXPECT_EQ(get_index(0xFFFFFFFFFFFFFFFF), 0X3FFFFFFFFFFFFFF);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.