Crappy speed with BinaryReader

[Brutus5000]

I try to read the whole statics0.mul and put all ItemIDs into a generic list using a BinaryReader. But the reading speed is unbelievable slow (~3 minutes on a Athlon XP 1600+ and a UDMA/100 HDD).

Here's my code (pStatic is the filestream of statics0.mul)

            BinaryReader reader = new BinaryReader(pStatic);
            long length = pStatic.Length / 7;
            for (int i = 0; i < length; i++)
            {
                short id = reader.ReadInt16();
                if (!m_ItemIDs.Contains(id))
                    m_ItemIDs.Add(id);

                pStatic.Seek(5, SeekOrigin.Current);
            }

The most time-intensive action is the Seek-function. Even if I don't read any bytes and just "walk" through the files by using pStatic.Seek(...) it takes so much time.
What is wrong there?

The Ultima SDK loads the whole data in a few seconds to memory
(But iterating through all static blocks of a TileMatrix takes the same time...)

I would also be pleased for other suggestions how to get all ItemIDs used in one of the static files using Ultima SDK (it's not a RunUO script).

[Aenima]

perhaps use pointers and just increment these as you go instead of using the Seek function?

[Ray]

What's the size of this collection? (ArrayList?).
In a best case scenario, it's exactly the size of the data that has to be read.

If you're using a m_ItemIDs = new ArrayList() statement, .NET just allocates a minimum standard size that has to be reallocated each time you reach the upper bound. Each reallocate copies all the data to a new arraylist and the time grows exponentially(!).

You can allocate enough memory with

m_ItemIDs = new ArrayList( 0x4000 );

as 0x4000 is the maximum ItemID that can be found in statics.mul (afaik, not sure about UOML)


Theres also a faster way to remove the linear complexity growth of the '.Contains()' call:
Use a standard array as a key/value pair to check for itemids:

bool[] array = new bool[4000]; // default value = false
for (int i = 0; i < length; i++)
{
      array[ reader.ReadUInt16() ] = true; // itemid found! -> It's a UInt16 in the file...
      pStatic.Seek(5, SeekOrigin.Current);
}

Now you simply have to check if array[ ItemID] is true to look if this was used.

This should be the fastest way possible. Well.. i was disregarding if Seek() has any performance lacks, but i think it doesn't.

Pleace notice that you'll get an 'index out of range exception' if there are itemid values higher than 0x4000, you should check on this before declaring the program as stable . Please remember that the first values of statics.mul is a file header, not Item-data

[Jeff]

Originally Posted by Brutus5000

The Ultima SDK loads the whole data in a few seconds to memory
(But iterating through all static blocks of a TileMatrix takes the same time...)

It doesnt load the whole thing, it only loads the index, and the index contains wether a id is valid or not.

[dddie]

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;

namespace RunUO
{
	public class LoadMul
	{
		public static List<short> m_ItemIDs;

		const string sStatic = "statics0.mul";
		public static void Main()
		{
			if( !File.Exists( sStatic ) )
			{
				Console.WriteLine( "File not exist!" );
				Console.ReadKey();
				return;
			}

			System.Threading.Thread.CurrentThread.Priority = System.Threading.ThreadPriority.AboveNormal;

			Console.WriteLine( "\t\t\tTime (ms)" );
			Console.Write( "Original function\t" );
			Test( LoadMul_0 );

			Console.Write( "Remove Seek\t\t" );
			Test( LoadMul_1 );

			Console.Write( "Remove Contains\t\t" );
			Test( LoadMul_2 );

			Console.Write( "Use BufferedStream\t" );
			Test( LoadMul_3 );

			Console.Write( "Remove BinaryReader\t" );
			Test( LoadMul_4 );

			Console.Write( "Move buffer allocation\t" );
			Test( LoadMul_5 );

			Console.ReadKey();
		}

		public delegate void Callback();

		public static void Test( Callback callback )
		{
			System.Threading.Thread.Sleep( 25 );
			m_ItemIDs = new List<short>();
			Stopwatch time = new Stopwatch();
			time.Start();
			callback();
			time.Stop();
			m_ItemIDs = null;
			Console.WriteLine( "{0}", time.ElapsedMilliseconds );
		}

		public static void LoadMul_0()
		{
			using( Stream pStatic = new FileStream( sStatic, FileMode.Open ) )
			{
				BinaryReader reader = new BinaryReader( pStatic );
				long length = pStatic.Length / 7;
				for( int i = 0; i < length; i++ )
				{
					short id = reader.ReadInt16();
					if( !m_ItemIDs.Contains( id ) )
						m_ItemIDs.Add( id );

					pStatic.Seek( 5, SeekOrigin.Current );
				}
			}
		}

		public static void LoadMul_1()
		{
			using( Stream pStatic = new FileStream( sStatic, FileMode.Open ) )
			{
				BinaryReader reader = new BinaryReader( pStatic );
				long length = pStatic.Length / 7;
				for( int i = 0; i < length; i++ )
				{
					short id = reader.ReadInt16();
					if( !m_ItemIDs.Contains( id ) )
						m_ItemIDs.Add( id );

					reader.ReadBytes( 5 );
				}
			}
		}

		public static void LoadMul_2()
		{
			using( Stream pStatic = new FileStream( sStatic, FileMode.Open ) )
			{
				BinaryReader reader = new BinaryReader( pStatic );
				long length = pStatic.Length / 7;
				bool[] buff = new bool[0x4000];
				for( int i = 0; i < length; i++ )
				{
					short id = reader.ReadInt16();
					buff[id] = true;

					reader.ReadBytes( 5 );
				}
				for( short i = 0; i < buff.Length; i++ )
					if( buff[i] )
						m_ItemIDs.Add( i );
			}
		}

		public static void LoadMul_3()
		{
			using( Stream pStatic = new BufferedStream( new FileStream( sStatic, FileMode.Open ), 64 * 1024 ) )
			{
				BinaryReader reader = new BinaryReader( pStatic );
				long length = pStatic.Length / 7;
				bool[] buff = new bool[0x4000];
				for( int i = 0; i < length; i++ )
				{
					short id = reader.ReadInt16();
					buff[id] = true;

					reader.ReadBytes( 5 );
				}
				for( short id = 0; id < buff.Length; id++ )
					if( buff[id] )
						m_ItemIDs.Add( id );
			}
		}

		public static void LoadMul_4()
		{
			using( Stream pStatic = new BufferedStream( new FileStream( sStatic, FileMode.Open ), 64 * 1024 ) )
			{
				long length = pStatic.Length / 7;
				bool[] buff = new bool[0x4000];
				for( int i = 0; i < length; i++ )
				{
					byte[] buffer = new byte[7];
					pStatic.Read( buffer, 0, 7 );
					int id = (buffer[1] << 8) + buffer[0];
					buff[id] = true;
				}
				for( int id = 0; id < buff.Length; id++ )
					if( buff[id] )
						m_ItemIDs.Add( (short)id );
			}
		}

		public static void LoadMul_5()
		{
			using( Stream pStatic = new BufferedStream( new FileStream( sStatic, FileMode.Open ), 64 * 1024 ) )
			{
				long length = pStatic.Length / 7;
				bool[] buff = new bool[0x4000];
				byte[] buffer = new byte[7];
				for( int i = 0; i < length; i++ )
				{
					pStatic.Read( buffer, 0, 7 );
					int id = (buffer[1] << 8) + buffer[0];
					buff[id] = true;
				}
				for( int id = 0; id < buff.Length; id++ )
					if( buff[id] )
						m_ItemIDs.Add( (short)id );
			}
		}
	}
}

Intel Pentium 4 - Nortwood 3 GHz, RAM 3 GB PC3200
HD 300 GB MaxLine III 7200 rpm, SATA, 16 MB cache

Hyperthreading: Enabled

                        Time (ms)
Original function       26866
Remove Seek             11357
Remove Contains         529
Use BufferedStream      475
Remove BinaryReader     281
Move buffer allocation  205

Hyperthreading: Disabled

                        Time (ms)
Original function       26289
Remove Seek             11240
Remove Contains         523
Use BufferedStream      484
Remove BinaryReader     293
Move buffer allocation  189

[Jeff]

This demonstration doesnt prove anything, the issue with what the original person was experiencing is they werent using things the wrong way, you dont use binary reader at all to see if a item exists or to load the entire library at once...you just use the file index.