Why is array initialization slowing down multithreading?

Question

I'm trying to add threading support to a method that hashes coordinates in multiple dimensions. The long term goal here is to include the FNV1A hash, but the slowdown appears as soon as simply initializing the coordinate array in the Hash method.

I iterate a million times, and for 1 thread I get stopwatch times of ~300ms. For 8 threads that time bumps to ~6000ms.

Is this a false sharing issue? If so, my concern is that the hash will deteriorate with padding and offsets injected into the array. Any help on getting this to perform using local arrays would be greatly appreciated. Thanks much!

public class Foo : MonoBehaviour {
    #region Fields
    private readonly int iterations = 1000000;
    private readonly int threadNum = 1;
    private int iterationsCompleted = 0;
    #endregion

    void Start () {
        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();
        Multithread();
        stopWatch.Stop();
        UnityEngine.Debug.Log(stopWatch.Elapsed.TotalMilliseconds);
    }

    private void Multithread() {
        for (int i = 0; i < threadNum; i++) {
            Hash hash = new Hash();
            new Thread(() => {
                while (Interlocked.Increment(ref iterationsCompleted) < iterations) {
                    hash.Get(0, 0, 0);
                }
                UnityEngine.Debug.Log("Finished thread");
            }).Start();
        }
        while (iterationsCompleted < iterations);
    }
}

public class Hash {
    #region Fields
    // FNV parameters can be found at http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
    private const uint _FNVPrime = 16777619;
    private const uint _FNVOffset = 2166136261;
    private const uint _FNVMask8 = (1<<8)-1;
    #endregion

    #region Class Methods
    private static uint FNV1A(uint[] data) {
        uint hash = _FNVOffset;
        int dataSize = data.Length * sizeof(UInt32);
        byte[] byteArray = new byte[dataSize];
        Buffer.BlockCopy(data, 0, byteArray, 0, dataSize);
        for (int i = 0; i < dataSize; i++) {
            hash = hash ^ byteArray[i];
            hash = hash * _FNVPrime;
        }
        return hash;
    }

    public uint Get(int x, int y, uint seed) {
        uint[] data = new uint[3] { (uint)x, (uint)y, seed };
        //return FNV1A(data);
        return 0;
    }
    #endregion
}

I'm not sure about this because I didn't use threads in unity yet, but I think MonoBehaviour derived classes will have a problem with multithreading (at least functions that are inherited from it). — Gunnar B.
– Gunnar B., Commented May 30, 2016 at 17:38
It must be the overhead of allocating a new array. You have two options: use FNV1A with a fixed amount of ints instead of an array, or preallocate a single array, one per thread. — Tamas Hegedus
– Tamas Hegedus, Commented May 30, 2016 at 17:53
@TamasHegedus it may be helpful to note that for a million iterations and 1 thread I was getting stopwatch times close to ~300ms. Bumping to 8 pushed the time to ~6000ms. That doesn't seem like array overhead. I will add that info to the post also. — Richard Horne
– Richard Horne, Commented May 30, 2016 at 18:36
@RichardHorne I think I found the problem. Update your complete code so that I can test it. — Programmer
– Programmer, Commented May 30, 2016 at 18:39
What are the values of threadNum,iterationsCompleted and iterations? — Programmer
– Programmer, Commented May 30, 2016 at 18:45

Programmer · Accepted Answer · 2016-06-01 06:43:37Z

Memory allocation seems to be the issue here. I made both arrays static then allocated memory outside of the functions once.I locked both array each time they are accessed to make sure that another Thread is not accessing them. Not sure how safe my code even after using the lock keyword.

None related problem:

while (iterationsCompleted < iterations); is called on the main Thread. This is not good and can will freeze Unity temporary each time Multithread() is called and still running. I added another Thread on top of that that will start whenMultithread() is called. So other Threads are now being called from this new Thread instead of the main Thread.

Test Results On My Computer

Original Code:

1 thread = 454.3515
8 threads = 655.008

Modified Code:

1 thread = 296.794
8 threads = 107.8898

Performance for 8 threads improved more than 6x. All tests were done with return FNV1A(data); included in the code and return 0; removed/commented from the code.

Now, your job is to make sure that the data/hash you are getting is what you expect.

public class Foo : MonoBehaviour
{
    #region Fields
    private readonly int iterations = 1000000;
    private readonly int threadNum = 1;
    private int iterationsCompleted = 0;
    #endregion

    void Start()
    {
        Multithread();
    }

    private void Multithread()
    {
        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();

        //Start new Thread so that while (iterationsCompleted < iterations) ; will not run in the main loop
        new Thread(() =>
          {

              for (int i = 0; i < threadNum; i++)
              {
                  Hash hash = new Hash();
                  new Thread(() =>
                  {
                      while (Interlocked.Increment(ref iterationsCompleted) < iterations)
                      {
                          hash.Get(0, 0, 0);
                      }
                      UnityEngine.Debug.Log("Finished thread");
                  }).Start();
              }
              while (iterationsCompleted < iterations) ;
              stopWatch.Stop();
              UnityEngine.Debug.Log(stopWatch.Elapsed.TotalMilliseconds);

          }).Start();
    }
}

public class Hash
{
    #region Fields
    // FNV parameters can be found at http://www.isthe.com/chongo/tech/comp/fnv/#FNV-param
    private const uint _FNVPrime = 16777619;
    private const uint _FNVOffset = 2166136261;
    private const uint _FNVMask8 = (1 << 8) - 1;
    private const int FIXEDSIZE = 3;
    private readonly System.Object locker = new System.Object();
    #endregion

    #region Class Methods
    private static uint FNV1A(uint[] data)
    {
        uint hash = _FNVOffset;

        Buffer.BlockCopy(data, 0, byteArray, 0, byteArray.Length);

        for (int i = 0; i < byteArray.Length; i++)
        {
            hash = hash ^ byteArray[i];
            hash = hash * _FNVPrime;
        }
        return hash;
    }

    static byte[] byteArray = new byte[FIXEDSIZE * sizeof(UInt32)];
    static uint[] data = new uint[3] { (uint)0, (uint)0, 0 };

    public uint Get(int x, int y, uint seed)
    {
        lock (locker)
        {
            data[0] = (uint)x;
            data[1] = (uint)y;
            data[2] = (uint)seed;
            return FNV1A(data);
        }
    }
    #endregion
}

Collectives™ on Stack Overflow

Why is array initialization slowing down multithreading?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related