Fast numeric lookup?

I am not sure this is even possible, but the issue I have is that I have a method I call over and over and over which tries to map a value to an index.

For numbers between 0 and SIZES[0] return 0, for everything between SIZES[0] and SIZES[1] return 1, and so on.

Right now I just loop though, but the problem is that for the higher values it slows down a bit. Sizes is length of 10 or so, but it gets called constantly. A tree of some kind seems a bit much, and I don't see if that would really be faster. I guess linear search would be slightly faster, but with n of ten might it not be slower?

A switch would be nice, but there's no way to easily round the size to the right values.

EDIT: NM. Of course I think of a simple solution the moment I post.

What is the range of values stored in SIZES?

If they are not too large then you could populate a vector with the result value for each index.

Quote:

---

Originally Posted by originalfamousjohnsmith

For numbers between 0 and SIZES[0] return 0, for everything between SIZES[0] and SIZES[1] return 1, and so on.

---

You can search the SIZES array using a binary search, finding the the index corresponding to an interval in O(ln N) time. That's much faster than a linear search which takes O(N).

You're looking for the index in the SIZES array for which this is true,

value >= SIZES[index] && value < SIZES[index+1]

Quote:

---

Originally Posted by nuzzle

You can search the SIZES array using a binary search, finding the the index corresponding to an interval in O(ln N) time. That's much faster than a linear search which takes O(N).

---

for such small N (the OP says ~10) it's definitely not so obvious...

If the lookup table option is viable, then it's O(1)

Quote:

---

Originally Posted by superbonzo

for such small N (the OP says ~10) it's definitely not so obvious...

---

I missed there were that few items.

A binary search on 10 elements is about 3.5 accesses and a sequential search should require 5 on average. But on the other hand a binary search has more overhead so they should perform fairly equal in this case. But it would be no improvement, I admit that.

I have to say that this whole topic looks silly. One must be very lucky if his app’s performance could benefit from eliminating a couple of compare operators.
Considering this a pure academic discussion – since you are not looking for a match (we need to find a range), you need exactly 3 or 4 accesses with binary search, while a minimum number of accesses for sequential search is 1 (and a maximum – 10). However, if you start from the middle, you’d get a min of 2 and max of 6.
Do we know the valid range for the input value? Is the SIZES array static? Are the ranges of equal size? Are the input values random? Or do they have normal distribution?

Well, what I did was to make a lookup array. I got a few percentage points improvement, but less than I hoped. I must have something not inlining, or else that it's not a const array due to needing to initialize it. The lookup array, anyway. The one with sizes is not.

For linear search or a vector the number of searchs would be the same or less but might take longer per item and I am pretty bare to the metal in this code.

Basically I want to make many fast allocations and deallocations for my memory manager and was hoping to shave off some infinitesimal speed to make more impressive benchmark.

Right now I can allocate and deallocate about 100 000 000 per CPU in 1.3 seconds, and I can't imagine that would be a bottleneck in any real world app.

The weird thing is it takes twice as long for larger blocks, though. I thought this lookup was the reason why but there must be something else I am not seeing. As far as I can tell it should not matter what size the block is.

Maybe it's the block header info being in separate memory area from the data causing the performance drop? I suppose there's not much to do about that without introducing a lot of overhead.

Quote:

---

Originally Posted by originalfamousjohnsmith

The weird thing is it takes twice as long for larger blocks...

---

Would you mind showing the code that "takes twice as long"? And may be the benchmark you use that demonstrates this difference?

Code:

---

        void SAllocationTests::testAllocationPerformance()
        {

                long innerLoopMax = 10000;
                long outerLoopMax = 10000;

                void** allocations = new void*[innerLoopMax];

                size_t storageSize = 0;

                SLock lock;

                while(true)
                {
                        storageSize+=16;

                        long allocationCount = 0;
                        SString allocationTime;
                        SUtil::startTimer();

                        for(long j=0; j<outerLoopMax; j++)
                        {
                                for(long i=0; i<innerLoopMax; i++)
                                {
                                        allocations[i]=SAllocation::allocateArrayStorage(storageSize);
                                }
                                for(long i=0; i<innerLoopMax; i++)
                                {
                                        SAllocation::deallocateArrayStorage(allocations[i], storageSize);
                                }       
                                allocationCount+=innerLoopMax;
                        }

                        SUtil::endTimer(allocationTime);

                        dout+allocationCount+" allocations of size "+storageSize+" took "+allocationTime;
                        dout++;

                        //SThreadUtil::sleep(1000);
                       
                }
        }

---

Code:

---

static inline void* allocateArrayStorage(size_t size)
{
        long index = SThreadUtil::getThreadId();


                if(arrayAllocators[index]==0)
                {
                        arrayAllocators[index] = new SSimpleAllocator;
                }
                return arrayAllocators[index]->allocate(size);
                }
static inline void deallocateArrayStorage(void* address, size_t allocationSize)
{
        long index = SThreadUtil::getThreadId();
        arrayAllocators[index]->deallocate(address, allocationSize);
}

---

The bottom code is the lookup part to select the right sized allocator. The ocde in all those allocators is the same, the block size is just different. They are expandable interleaved free lists that each return blocks of a specific size and takes just a few instructions. Algorithmicly size should do nothing, which is why I wonder if it's some cache issue. I was thinking before linear search made the slowdown but that should not be the case now.

Show us a full program, not just a function or two. Others then can actually run the program instead of trying to guess.

To that, no one is going to know what makes your code slow until we see the actual test beds, both the "slow" code and the "fast" code. Programmers, unless it is obvious, cannot tell what parts of a program can be slow or not. Not only that, the compiler's optimizer plays a role in all of this, making the source code perform much differently than perceived.

That's why profilers are used -- we can't predict what is slow by just eyeballing code, you need specialized tools that work with a running application. It would also help if you told us what compiler, compiler version, and compiler options you used to build this test.

Regards,

Paul McKenzie

Well, I don't want to post all the code. This is part of something I will sell some day, and I might make parts of it open source but if so I'd not just vomit out the half done code on a public forum but debug it and make a formal site so that it won't get turned in by college students around the country, that also could lead to legal issues.

That's the only relavent code anyway. The lookup part seems not to be the issue and any other issue is probably not something that could be figured out casually. I just posted that code out of courtesy and just in case someone spotted something obvious.

Quote:

---

Originally Posted by originalfamousjohnsmith

Well, I don't want to post all the code.

---

That is understood. I wasn't asking for your memory manager code anyway, only for (possibly, simulated) part that shows the slow-down you mentionned.
If you'd like to confirm that your look-up plays no role, you could eliminate it completely from your test: just hard-code a small size during one test, and a large one - during another.
My guess is (as yours) that it (the removal of look-up code) will make no difference. But *IF* it does - we could try to optimize that part.
Also, since you do not access returned memory in your test, I don't think that cache hits/misses would matter. Or are you talking about your cached look-up tables?

Quote:

---

Originally Posted by originalfamousjohnsmith

Well, I don't want to post all the code. This is part of something I will sell some day, and I might make parts of it open source

---

You can find out exactly what's slow by using a profiler. That's what they're there for, so that you don't waste time guessing what is slow, and thus writing code that will make no difference in speed.

You also still haven't mentioned which compiler you're using and version.

Regards,

Paul McKenzie