The cost of using nothing

What is the cost of using nothing? Seems like a silly question.

 

Suppose you see code like this:

 

void * MyClass::DoSomething()

{

int size = sizeof(MyThing) * m_NumItems;

var ptr = malloc(size);

return ptr;
}

 

It’s a method that allocates space for m_NumItems MyThings. This is a real code pattern that exists in a lot of code bases.

 

Suppose, however, that the m_NumItems is 0. What will this code do?

 

If the caller of the code does something like this:

 

void MyClass::CallDoSomething()

{

                var ptr = DoSomething();

                for (int i = 0 ; i < m_NumItems)

{

                ptr[i] = …..;

}

}

 

then the code will not dereference the null block of memory, and thus seem to behave properly.

 

However, try the code sample below.

 

Start Visual Studio. File->New->Project->C# WPF Application.

Dbl-click the MainWindow.Xaml to get to the code behind and replace with the sample below.

 

 

The code calls HeapAlloc (which is what malloc does under the hood) to allocate a block of memory with a size of 0 bytes. It then prints out the address of memory returned in the debug window.

A sample of the output:

 

0b0d07d0

0b0d07e0

0b0d07f0

0b0d0800

0b0d0810

0b0d0820

0b0d0830

Notice that each subsequent call is 16 bytes beyond the prior on my 64 bit Windows 7. This is the overhead of allocating zero bytes.

 

What do you expect happens when you change the sizeToAlloc to 1? The answer will surprise you.

 

Not only is there overhead in allocating 0 bytes, but fragmentation too: as a heap grows with a pattern of allocates and frees, the resulting fragmentation can be crippling.

 

Heaps typically can coalesce adjacent free blocks, but that’s about the extent of their attempt to alleviate the defragmentation.

 

Defragmenting a hard disk consists of moving blocks of data around and updating the pointers (directories) to that data.

 

Defragmenting managed objects occurs via a Garbage Collection: the memory is moved around and pointers (objects that reference other objects) are updated.

 

Defragmenting a native heap is pretty much impossible: once the heap gives out a pointer to the block of memory, that memory cannot be moved.

 

Some memory schemes have tried to allow defragmenting in various ways, such as using a Handle to memory, and using a simple fast function that Dereferences that pointer to get the real address of the memory.

 

FoxPro 2.6, which allowed the same user code to run on Unix, Mac, DOS, and Windows, uses such a handle dereferencing scheme.

 

Older versions of Windows also used handles: see the legacy functions GlobalAlloc, LocaAlloc, which require you to dereference the returned handle via GlobalLock

 

 

 

See also:

 

Managed code using unmanaged memory: HeapCreate, Peek and Poke

<Sample>

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Windows;

using System.Windows.Controls;

using System.Windows.Data;

using System.Windows.Documents;

using System.Windows.Input;

using System.Windows.Media;

using System.Windows.Media.Imaging;

using System.Windows.Navigation;

using System.Windows.Shapes;

using System.Runtime.InteropServices;

namespace WpfApplication1

{

    /// <summary>

    /// Interaction logic for MainWindow.xaml

    /// </summary>

    public partial class MainWindow : Window

    {

        public MainWindow()

        {

            InitializeComponent();

        }

        private IntPtr _hpHandle;

        private void Window_Loaded(object sender, RoutedEventArgs e)

        {

            var wordsize = IntPtr.Size;

            if (wordsize != 4)

            {

                //are we in 32 or 64 bit land? doesn't matter!

            }

            _hpHandle = Heap.HeapCreate(0, 0, 0);

            var nIter = 100;

            IntPtr[] ptrs = new IntPtr[100];

            uint sizeToAlloc = 0;

            for (int i = 0; i < nIter; i++)

            {

                var ptr = Heap.HeapAlloc(_hpHandle, 0, sizeToAlloc);

                System.Diagnostics.Trace.WriteLine(string.Format("{0:x8}", ptr.ToInt32()));

                ptrs[i] = ptr;

            }

            for (int i = 0; i < nIter; i++)

            {

           var res = Heap.HeapFree(_hpHandle, 0, ptrs[i]);

                if (res != true)

                {

                    System.Diagnostics.Trace.WriteLine("Free failed");

                }

            }

            Heap.HeapDestroy(_hpHandle);

       }

    }

    public class Heap

    {

        [DllImport("kernel32.dll", SetLastError = true)]

        public static extern IntPtr HeapCreate(uint flOptions, uint dwInitialsize, uint dwMaximumSize);

        [DllImport("kernel32.dll", SetLastError = true)]

        public static extern IntPtr HeapAlloc(IntPtr hHeap, uint dwFlags, uint dwSize);

        [DllImport("kernel32.dll", SetLastError = true)]

        public static extern bool HeapFree(IntPtr hHeap, uint dwFlags, IntPtr lpMem);

        [DllImport("kernel32.dll", SetLastError = true)]

        public static extern bool HeapDestroy(IntPtr hHeap);

    }

}

</Sample>