🔒 Locked

[.net] Question about stackalloc

Started by kryat Aug 24, 2006 at 12:16 AM 1 reply 1.3k views

Original Post

Aug 24, 2006 at 12:16 AM

I'm trying to optimize a program I'm working on. I have a function that has to do a few look ups in rather large arrays, and this function gets called a lot. So if i can shave off a few cycles here, it'll help all the way down the line. Basically heres the basic idea


    public class Worker
    {
        private static int[] Data1 = new int[1 << 16];
        private static int[] Data2 = new int[1 << 16];

        static Worker()
        {
            //Fill Data1 and Data2
        }

        public static void Process(out int data1, out int data2)
        {
            //Calculate and return data from Data1 and Data2
        }
    
    }

I would like to see if using stackalloc would speed things up, though I'm having a bit of trouble with it. And am not entirely sure the scope of an array created by stackalloc. I would like to try is something more like:


    unsafe public class Worker
    {
        static private int* pData1;
        static private int* pData2;

        static Worker()
        {
            int* tpData1 = stackalloc int[1 << 16];
            pData1 = tpData1;

            int tpData2 = stackalloc int[1 << 16];
            pData2 = tpData2;
        }

        public static void Process(out int data1, out int data2)
        {
            //Calculate and return data
            data1 = *(pData1 + i);
            data2 = *(pData2 + i);
        }
    
    }

So I can run it through a profiler and see which one is faster. But I have the feeling that those arrays might fall out of scope as soon as the static constructor is finished, and I would be pointing to pretty much random data. And I'm having trouble finding decent examples of people using stackalloc, most are just one or two lines of code showing the syntax. Is there something I'm missing, or am I just holding on too tight to old C/C++ ways to try to get that last little bit of performance out of this class.

BigBadBob

Aug 24, 2006 at 12:41 AM

stackalloc allows you to do dynamic allocation on the stack, that is all, scoping rules still apply as they would for normal stack variables, i.e. its lifetime is limited to the block in which it is defined. When your constructor exits, the stackalloc data should be free'd.

There is a very important principle that I advise you adhere to, make it right, then make it fast. You can spend a lot of time looking for tiny ways to make your code better as you write it, yet it might be code that isn't even time critical in the end. Concentrate more on algorithmic improvements when writing the code, and worry about micro-optimisation later.

If your look ups into the arrays are like you show there, just pointer addition + dereference, then they will be constant time anyway so I wouldn't worry too much. Unless you need to search the arrays for some values, in that case you can use System::Array::BinarySearch (providing you sort the array first of course).

kryat

Author

kryat

Aug 25, 2006 at 11:40 AM

Thanks. I pretty much figured it wasn't going to improve anything. But I wanted to see if it would try, just coudn't get it to work. I wanted to see if looking up values on the stack was faster than looking up values on the heap, and see how much overhead was involved with System.Array. Like I said, this function gets called a lot so any optimisation here would make a substantial difference.

Just for the record, its a varation of a huffman vlc decoder, algorithmically I can't think of any way to do it faster. I basically build two tables that are the length of the longest code for the table I'm decoding (the longest codes I deal with are 16 bits long so 1<<16). Then store all possible read values in one array and the length of the code in the other array.

So a 1 bit long vlc code would take up 1<<(16-1) entries in the array and a 16 bit long code would natrually take up 1<<(16-16) entry in the array.

Then I can read the next 16 bits from the data stream then look up that value in the values table, look up its length in the length table, then throw away however many bits the code is long, and rinse and repeat.

I thought about using a read buffer rather than rereading the max code length every time (keeping the left over data from the last read to see if I can decode a code out of the remaining bits) but running it through the profiler, the bulk of the cycles are spent actually looking up the values in the array. I still might try it, but it seems like an overly complicated optization with little performance return.

I thought about breaking it into smaller arrays to converve memory, but that would be slower because longer codes would require multiple reads and array dereferences. Unless there is a performance difference between looking up values in large arrays vs. smaller ones.

Thanks for your feedback though.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.