TextureFromPoints5 - Low Memory [Repost]

//This was taken down?

//This version demonstrates using a bit of trickery to write directly to file
//- particularily useful in low memory situations.
//However it's hard to paralelise andimprove beyond the base speed.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

namespace TextureFromPoints5
{
    class Program
    {
        static void Main(string[] args)
        {
            //Introduction
            if (false)
            {
                //Let us explore the BMP Format  [http://en.wikipedia.org/wiki/BMP_file_format]
                var bmp = new Bitmap(1024, 1024, PixelFormat.Format32bppArgb);
                var ms = new MemoryStream();
                bmp.Save(ms, ImageFormat.Bmp);

                ms.Position = 0;
                var br = new BinaryReader(ms);

                //Bit Map Header:
                {
                    //Identification - e.g. 'BM'
                    Console.WriteLine(new String(br.ReadChars(2)));
                    //Size of BMP in bytes:
                    Console.WriteLine(br.ReadInt32());  //54 bytes more than raw data - intesting
                    //reserved
                    Console.WriteLine(br.ReadInt16());
                    Console.WriteLine(br.ReadInt16());
                    //Offset
                    Console.WriteLine(br.ReadInt32());  //54 - we might have a winner!
                }

                //What we are going to do:
                //Create a dummy image, and steal the header info for our own use.
                //This is easier than manually writing out own, and as long as we keep things relatively simple will work.
                //Just ensure we have no padding, or ICC color profile - and we can use any other format options we desire!
            }

            while (true) RunExperiment();
        }

        #region Settings
        const int numSensors = 70000;
        const int textureSize = 4096;
        const int intervals = 100;
        const int maxThreads = -1;
        const string directory = @"C:\TextureFromPoints5\";
        #endregion

        static Random rnd = new Random();
        static void RunExperiment()
        {
            var swTotal = Stopwatch.StartNew();
            var sw = Stopwatch.StartNew();
            Console.WriteLine("\n Set-Up \n");

            #region Setups
            var pOptions = new ParallelOptions();
            if (maxThreads > 0) pOptions.MaxDegreeOfParallelism = maxThreads;

            var magic = Math.Sqrt(textureSize * textureSize / numSensors) / 2;  //Magic Formula
            var hash = (int)Math.Pow(2, (int)(Math.Log(magic - 1, 2)) + 1);  //Rounds up to nearest power of 2.
            if (hash < 1) hash = 1;
            Console.WriteLine("Rough Hash Generated: {0}  [Magic Density : {1}]", hash, magic);

            //We now use existing files as preallocation.
            foreach (FileInfo file in Directory.CreateDirectory(directory).GetFiles())
                if (Int32.Parse(file.Name.Split('.')[0]) >= intervals) file.Delete();

            #endregion

            Console.WriteLine("\n Generating Data \n");
            sw.Restart();
            var sensors = GenerateRandomSensors();
            Console.WriteLine("Completed in {0}ms\n", sw.ElapsedMilliseconds);

            Console.WriteLine("\n Generating Spacial Collection \n");
            sw.Restart();
            var spacialHash = new SimpleSpacialCollection(textureSize, hash);
            foreach (var sensor in sensors) spacialHash.AddSensor(sensor);
            Console.WriteLine("Completed in {0}ms\n", sw.ElapsedMilliseconds);

            Console.WriteLine("\n Get Header Data \n");
            sw.Restart();
            byte[] header = GenerateHeaderData();
            Console.WriteLine("Completed in {0}ms\n", sw.ElapsedMilliseconds);


            Console.WriteLine("\n Initialising Images \n");
            sw.Restart();
            var images = new BinaryWriter[intervals];


            Parallel.For(0, images.Length, i =>
            {
                //Just Plain Slow:
                //var stream = MemoryMappedFile.CreateFromFile(directory + i + ".bmp", FileMode.Create, i.ToString(), (textureSize * textureSize + header.Length) * 4).CreateViewStream();

                //The forced buffer significantly helps with HDD writes according to simple testing.
                //We will reuse existing files as preallocation if the exist.
                var stream = new FileStream(directory + i + ".bmp", FileMode.OpenOrCreate, FileAccess.Write, FileShare.None, 1024 * 1024, false);
                stream.SetLength(textureSize * textureSize * 4 + header.Length);
                stream.Position = 0;

                var br = new BinaryWriter(stream);
                br.Write(header);
                images[i] = br;
            });
            Console.WriteLine("Completed in {0}ms\n", sw.ElapsedMilliseconds);

            Console.WriteLine("\n Writing Image Data \n");
            sw.Restart();

            /*
             * for (int x = 0; x < textureSize; x++)
                for (int y = 0; y < textureSize; y++)
                {
                    var sensor = spacialHash.GetNearest(x, y);
                    for (int i = 0; i < intervals; i++)
                        images[i].Write((int)(int.MaxValue * sensor.data[i]));
                }*/

            //Threading only appears to make sence when data is already preallocated -=otherwise it actually takes longer.
            var splitCount = Environment.ProcessorCount * 2;
            Parallel.For(0, splitCount, threadID =>
             {
                 Thread.Sleep(threadID * 10);

                 int offsetSize = textureSize / splitCount;

                 var min = offsetSize * threadID;
                 var max = (threadID == (splitCount - 1)) ? textureSize : min + offsetSize;

                 int rowsToBuffer = 128;
                 var buffer = new float[textureSize * rowsToBuffer][];
                 for (int x = min; x < max; x += rowsToBuffer)
                 {
                     for (int r = 0; r < rowsToBuffer; r++)
                         for (int y = 0; y < textureSize; y++)
                             buffer[r * textureSize + y] = spacialHash.GetNearest(x + r, y).data;
                     for (int i = 0; i < intervals; i++)
                     {
                         var image = images[i];
                         lock (image)
                         {
                             image.BaseStream.Position = header.Length + x * textureSize * 4;
                             for (int y = 0; y < buffer.Length; y++)
                                 image.Write((int)(int.MaxValue * buffer[y][i]));
                         }
                     }
                 };
             });

            Console.WriteLine("Completed in {0}ms\n", sw.ElapsedMilliseconds);

            Console.WriteLine("\n Clean Up \n");
            sw.Restart();
            for (int i = 0; i < images.Length; i++)
            {
                images[i].Flush();
                images[i].Dispose();
            }
            Console.WriteLine("Completed in {0}ms\n", sw.ElapsedMilliseconds);

            Console.WriteLine("\n Finished  in  {0}ms \n", swTotal.ElapsedMilliseconds);
            Console.ReadLine();
            /* */

            /*
            int splitCount = Environment.ProcessorCount;

            var spacialHash = new SimpleSpacialCollection(textureSize, hash);
            foreach (var sensor in sensors) spacialHash.AddSensor(sensor);

            var results = new ConcurrentDictionary<int, int[,]>();
            new Thread(() =>
                 {
                     while (results != null)
                     {
                         foreach (var key in results.Keys)
                         {
                             int[,] data;
                             if (results.TryRemove(key, out data))
                                 for (int i = 0; i < intervals; i++)
                                 {
                                     var image = images[i];
                                     image.BaseStream.Position = header.Length + key * textureSize * 4;
                                     for (int y = 0; y < textureSize; y++)
                                         image.Write((int)(int.MaxValue * data[y, i]));
                                 }
                         }
                     }
                     Console.WriteLine("FileWriter:  All Done!");
                 }).Start();

            var sw2 = Stopwatch.StartNew();
            Parallel.For(0, textureSize, x =>
                {

                    var buffer = new int[textureSize, intervals];
                    for (int y = 0; y < textureSize; y++)
                    {
                        var temp = spacialHash.GetNearest(x, y).data;
                        for (int i = 0; i < intervals; i++)
                            buffer[y, i] = (int)(int.MaxValue * temp[i]);
                    }
                    results[x] = buffer;
                });
            Console.WriteLine("Calculation Time = {0}ms", sw2.ElapsedMilliseconds);

            while (results.Count > 0) Thread.Yield();
            results = null;

            /*Parallel.For(0, splitCount, threadID =>
            //for (int threadID = 0; threadID < splitCount; threadID++)
            {
                Thread.Sleep(threadID * 10);

                int offsetSize = textureSize / splitCount;

                var min = offsetSize * threadID;
                var max = (threadID == (splitCount - 1)) ? textureSize : min + offsetSize;

                int rowsToBuffer = 64;
                var buffer = new float[textureSize * rowsToBuffer][];
                for (int x = min; x < max; x += rowsToBuffer)
                {
                    for (int r = 0; r < rowsToBuffer; r++)
                        for (int y = 0; y < textureSize; y++)
                            buffer[r * textureSize + y] = spacialHash.GetNearest(x + rowsToBuffer, y).data;

                    for (int i = 0; i < intervals; i++)
                    {
                        var image = images[i];
                        lock (image)
                        {
                            image.BaseStream.Position = header.Length + x * textureSize * 4;
                            for (int y = 0; y < buffer.Length; y++)
                                image.Write((int)(int.MaxValue * buffer[y][i]));
                        }
                    }
                };
            });
            /* */

            /*int splitCount = Environment.ProcessorCount * 4;


            var spacialHash = new SimpleSpacialCollection(textureSize, hash);

            foreach (var sensor in sensors) spacialHash.AddSensor(sensor);

            //Threading this is a little more complicated, but doable.
            //Throughtput increased from 74.5MB/s [90s] to 150MB/s [42s]
            //[4096x4096, 100 images - 6.77GB]
            Parallel.For(0, splitCount, threadID =>
            {
                int offsetSize = intervals / splitCount;

                var min = offsetSize * threadID;
                var max = (threadID == splitCount - 1) ? intervals : min + offsetSize;

                for (int x = 0; x < textureSize; x++)
                    for (int y = 0; y < textureSize; y++)
                    {
                        var sensor = spacialHash.GetNearest(x, y);

                        for (int i = min; i < max; i++)
                            images[i].Write((int)(int.MaxValue * sensor.data[i]));
                    }
            }); /* */
        }

        private static byte[] GenerateHeaderData()
        {
            byte[] header;
            using (var ms = new MemoryStream())
            {
                new Bitmap(textureSize, textureSize, PixelFormat.Format32bppArgb).Save(ms, ImageFormat.Bmp);
                using (var br = new BinaryReader(ms))
                {
                    br.BaseStream.Position = 10;
                    header = new byte[br.ReadInt32()];
                    ms.Position = 0;
                    ms.Read(header, 0, header.Length);
                }
            }
            return header;
        }
        private static Sensor[] GenerateRandomSensors()
        {
            var sensors = new Sensor[numSensors];
            for (int i = 0; i < numSensors; i++)
            {
                var sensor = new Sensor();
                sensor.position = new Vector2(textureSize);
                sensor.data = Enumerable.Range(0, intervals).Select(_ => (float)rnd.NextDouble()).ToArray();
                sensors[i] = sensor;
            }
            return sensors;
        }

        public struct Sensor
        {
            public Vector2 position;
            public float[] data;
        }

        public struct Vector2
        {
            public float x;
            public float y;

            public Vector2(float x, float y)
            {
                this.x = x;
                this.y = y;
            }

            public Vector2(float randomDistance)
            {
                this.x = (float)rnd.NextDouble() * randomDistance;
                this.y = (float)rnd.NextDouble() * randomDistance;
            }

            public static Vector2 operator -(Vector2 a, Vector2 b)
            {
                return new Vector2(a.x - b.x, a.y - b.y);
            }

            public float sqrMagnitude()
            {
                return x * x + y * y;
            }

            public float sqrDistanceToPoint(Vector2 point)
            {
                var x = this.x - point.x;
                var y = this.y - point.y;
                return x * x + y * y;
            }
        }

        public class SimpleSpacialCollection
        {
            List<Sensor>[,] buckets;
            public readonly int bounds;
            public readonly int hash;

            public int count { get; private set; }

            public SimpleSpacialCollection(int bounds, int hash)
            {
                this.bounds = bounds;
                this.hash = hash;
                buckets = new List<Sensor>[bounds / hash + 1, bounds / hash + 1];
                count = 0;
            }

            public void AddSensor(Sensor sensor)
            {
                GetBucket(sensor.position).Add(sensor);
                count++;
            }

            List<Sensor> GetBucket(Vector2 v2)
            {
                return GetBucket((int)v2.x, (int)v2.y);
            }

            List<Sensor> GetBucket(int x, int y)
            {
                var bucket = buckets[x / hash, y / hash];
                if (bucket == null)
                {
                    bucket = new List<Sensor>();
                    buckets[x / hash, y / hash] = bucket;
                }
                return bucket;
            }

            public Sensor GetNearest(int pointX, int pointY, int number = 1)
            {
                if (count < number) throw new Exception("Not enough elements!");

                var candidates = new List<Sensor>();

                int maxX, minX, maxY, minY;

                maxX = minX = pointX / hash;
                maxY = minY = pointY / hash;

                do
                {
                    maxX++; maxY++; minX--; minY--;

                    if (minX < 0) minX = 0;
                    if (minY < 0) minY = 0;
                    if (maxX > buckets.GetLength(0)) maxX = buckets.GetLength(0);
                    if (maxY > buckets.GetLength(1)) maxY = buckets.GetLength(1);

                    for (int x = minX; x < maxX; x++)
                        for (int y = minY; y < maxY; y++)
                        {
                            var bucket = buckets[x, y];
                            if (bucket != null) candidates.AddRange(bucket);
                        }
                } while (candidates.Count < number);

                var point = new Vector2(pointX, pointY);

                Sensor nearest = candidates[0];
                float nearestDistance = nearest.position.sqrDistanceToPoint(point);

                for (int i = 1; i < candidates.Count; i++)
                {
                    var candidate = candidates[i];
                    if (candidate.position.sqrDistanceToPoint(point) < nearestDistance)
                    {
                        nearest = candidate;
                        nearestDistance = candidate.position.sqrDistanceToPoint(point);
                    }
                }
                return nearest;
            }
        }
    }
}