Blogus Maximus

Rubbing people the wrong way since 1970...

  Home  |   Contact  |   Syndication    |   Login
  1366 Posts | 10 Stories | 2226 Comments | 1336 Trackbacks

News


Google My Blog

Catch me at: The List!


My InstallScript Utility Belt My Amazon Wishlist
My Standard Disclaimer

Tag Cloud


Archives

Post Categories

Image Galleries

Blogs

Code Camps

CTown Geeks

Geeky Webcomics

High Geek

Magenic Blogs

Microsoft Blogs

My Articles

My Sites

PodCasts

UG

XNA

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

Feedback

# re: Accessing your 3D array data in a cache friendly manner 5/2/2006 2:00 PM Passion
Not bad

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

# re: Accessing your 3D array data in a cache friendly manner 9/8/2009 5:45 AM acai berry benefits
Very good article for 3D array.Thank you

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

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

# re: Accessing your 3D array data in a cache friendly manner 8/2/2010 10:55 PM xty
please help me making source code for consanguine calculations..thank you... please..please..please...

# re: Accessing your 3D array data in a cache friendly manner 8/6/2010 7:45 PM Over Door Hanger
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.

Post A Comment
Title:
Name:
Email:
Comment:
Verification: