Geeks With Blogs

News

Google My Blog

Catch me at: The List!


My InstallScript Utility Belt My Amazon Wishlist
My Standard Disclaimer


Archives
Blogus Maximus Rubbing people the wrong way since 1970...
There are basically two ways of sequentially accessing every cell of a cube of data. At first glance, drilling and slicing appear to be the same thing depending on how you are "facing" the cube, but actually can make a difference in terms of processing speed.

Let's say we have a cube 99 x 99 x 99 (X, Y & Z). I think it's safe to assume most people view the X coordinate as Horizontal, the Y coordinate as Vertical and the Z coordinate as Depth. I use a cube similar to this in HA! (with different dimensions) when storing my dungeon maps.

Slicing the data implies searching left to right, top to bottom, front to back... 1 layer at a time, or in my case, 1 dungeon level at a time. Drilling the data implies searching front to back, top to bottom, left to right... effectively punching a straight line through the cube from near to far.

Now before you start emailing me to tell me I'm an idiot and that they are the same thing, just from different facings... hear me out. First of all, you're right, but there's a catch. When slicing the cube, you are actually working against the preferred access method of your data cube.

VB.NET defines arrays in row order, meaning that the members of the right-most index are stored adjacently in memory. Your CPU cache will work WAY more efficiently than if it has to read data from non adjacent memory locations. When we use the right-most (Z) index, we are drilling through the cube and accessing memory in a CPU cache friendly manner. This result in much faster reads.

        ' arrTest is a 3D array: (99, 99, 99)

        ' Drilling
        dStart = Timer
        For intx = 0 To 99
            For inty = 0 To 99
                For intz = 0 To 99
                    arrTest(intx, inty, intz) = "a"
                Next
            Next
        Next
        dEnd = Timer


        ' Scraping
        dStart = Timer
        For intz = 0 To 99
            For inty = 0 To 99
                For intx = 0 To 99
                    arrTest(intx, inty, intz) = "a"
                Next
            Next
        Next
        dEnd = Timer

On my machine, the results were pretty clear. Drilling took 0.015 seconds and scraping took 0.109 seconds to access the exact same data. That's a difference of roughly tenfold. The span between a hundredth of a second and a tenth of a second may not seem like much, but if it's a commonly accessed routine, times a few thousand simultaneous users (in a web app for example), it adds up quick.

Accessing your data in this fashion requires visualizing your data from a slightly different perspective, but if you can wrap your head around it, your CPU cache will thank you. Posted on Saturday, March 26, 2005 6:10 PM | Back to top



Comments on this post: Accessing your 3D array data in a cache friendly manner

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
Not bad
Left by Passion on May 02, 2006 2:00 PM

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
How do you save to a file a 3D array using VB.Net?
Left by Jose Sanchez on Mar 20, 2009 7:27 PM

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
Very good article for 3D array.Thank you
Left by acai berry benefits on Sep 08, 2009 5:45 AM

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
That's really nice and I am happy to find it. Thanks for sharing it here.
Left by Birthday SMS on Feb 13, 2010 7:10 PM

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
thanks for the article. Caching in a user-friendly manner can be difficult if you have lots of content.
Left by get a big penis naturally on Jul 15, 2010 10:04 PM

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
please help me making source code for consanguine calculations..thank you... please..please..please...
Left by xty on Aug 02, 2010 10:55 PM

# re: Accessing your 3D array data in a cache friendly manner
Requesting Gravatar...
Always hated 3 way arrays. Specifically remember having to code one in C++ and it just seemed like a waste of time since they have libraries for that now.
Left by Over Door Hanger on Aug 06, 2010 7:45 PM

Your comment:
 (will show your gravatar)


Copyright © Chris G. Williams | Powered by: GeeksWithBlogs.net | Join free