Thursday, November 12, 2009

Disk based data structures

codeplex-logo Last year I created a project where I used memory mapped files as storage for a large Array. I’ve now polished the project a bit and included generic List and Dictionary implementations as well. The project can be found at Disk Based Data Structures - CodePlex.

I’ve also created a serializer project which benchmarks and picks the fastest serializer method for your type. This serializer is used to persist the data to disk. The classes are also implemented thread safe.

Background for the project

A disk based version of an array would require a lot of caching logic to make it perform fast enough compared to a pure memory implementation and a couple of years ago I stumbled across Memory Mapped Files which has long existed in the operating systems and is typically used in OS’ for the swap space.

The first time I worked with Memory Mapped files I used a library from MetalWrench, but this time around I got hold of Winterdom's much nicer implementation of the Win32 API. I've included the patch from Steve Simpson, but removed the dynamic paging since it slows things down and it's not necessary on 64bit systems. (If you want to use arrays which hold over 2gb of data on 32bit systems I recommend reverting to Steve's original version and set a view size of 200-500mb.) Future releases will use .Net 4.0’s System.IO.MemoryMappedFiles namespace.

The beauty of 64bit is that you have virtually unlimited address space, so each thread can get it's own view of the mapped file without running out of address space. 32bit Windows can only address 4gb.

As for performance my theory is that Microsoft has implemented a fairly good caching algorithm for it's swap file, so it should prove good enough for me. A few tests show a much better disk IO with the Memory Mapped API than using .Net's file IO library. I haven't testet the performance if you add the SEC_LARGE_PAGES flag, but it might help some.

Hope this library is useful for someone out there :)