Fast numeric lookup?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 14 of 14

Thread: Fast numeric lookup?

  1. #1

    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.
    Last edited by originalfamousjohnsmith; November 6th, 2009 at 05:40 AM.

  2. #2
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,694

    Re: Fast numeric lookup?

    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.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  3. #3
    Join Date
    May 2009
    Posts
    2,413

    Re: Fast numeric lookup?

    Quote Originally Posted by originalfamousjohnsmith View Post
    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]
    Last edited by nuzzle; November 6th, 2009 at 05:58 AM.

  4. #4
    Join Date
    Oct 2008
    Posts
    1,077

    Re: Fast numeric lookup?

    Quote Originally Posted by nuzzle View Post
    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...

  5. #5
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,694

    Re: Fast numeric lookup?

    If the lookup table option is viable, then it's O(1)
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: Fast numeric lookup?

    Quote Originally Posted by superbonzo View Post
    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.

  7. #7
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,523

    Re: Fast numeric lookup?

    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?
    Vlad - MS MVP [2007 - 2012] - www.FeinSoftware.com
    Convenience and productivity tools for Microsoft Visual Studio:
    FeinViewer - an integrated GDI objects viewer for Visual C++ Debugger, and more...

  8. #8

    Re: Fast numeric lookup?

    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.

  9. #9
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,523

    Re: Fast numeric lookup?

    Quote Originally Posted by originalfamousjohnsmith View Post
    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?
    Vlad - MS MVP [2007 - 2012] - www.FeinSoftware.com
    Convenience and productivity tools for Microsoft Visual Studio:
    FeinViewer - an integrated GDI objects viewer for Visual C++ Debugger, and more...

  10. #10

    Re: Fast numeric lookup?

    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.

  11. #11
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Fast numeric lookup?

    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
    Last edited by Paul McKenzie; November 8th, 2009 at 07:32 AM.

  12. #12

    Re: Fast numeric lookup?

    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.

  13. #13
    Join Date
    Aug 2000
    Location
    New York, NY, USA
    Posts
    5,523

    Re: Fast numeric lookup?

    Quote Originally Posted by originalfamousjohnsmith View Post
    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?
    Vlad - MS MVP [2007 - 2012] - www.FeinSoftware.com
    Convenience and productivity tools for Microsoft Visual Studio:
    FeinViewer - an integrated GDI objects viewer for Visual C++ Debugger, and more...

  14. #14
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Fast numeric lookup?

    Quote Originally Posted by originalfamousjohnsmith View Post
    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center