How to speed up the work of a stack built on an array of 100M elements?

Question

.NET

Good day to all!
I came across a task here - to make your own stack class, with the methods .pop(), .push(digit), .inc(x, y
) adds the number y to them (accordingly, as a result, we should get a modified stack).
It is necessary that by running this method on a stack of 100000001 inside the loop at 100000001, this case does not hang and works as quickly as possible (the person who checks this work says that it is possible to make the test below pass within a few seconds). Optimization maniacs, come!!!
Test:

[Test]
  public void StackTest()
  {
   var watch = new Stopwatch();
   var stack = new StackClass();
 
   var count = 100000001;
 
   watch.Start();
   for (int i = 0; i < count; i++)
   {
    stack.Push(i);
   }
   Console.WriteLine(watch.Elapsed);
   watch.Restart();
 
   for (int i = 0; i < count; i++)
   {
    stack.Inc(i, 2);
   }
   Console.WriteLine(watch.Elapsed);
   watch.Restart();
 
   for (int i = 0; i < count; i++)
   {
    stack.Pop();
   }
   Console.WriteLine(watch.Elapsed);
  }

I tried several implementations, through List, Collection, Array. The fastest turned out through an ordinary array. Here it is:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Remoting.Messaging;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace NewStack
{
    class Stack
    {
        private int[] arr = new int[100000001];
        private int _count;
        private int _currentIndex;
        public Stack()
        {
            _count = 0;
            _currentIndex = -1;
        }

        public void Push(int digit)
        {
            if (IsFull)
            {
                throw new Exception("Array is full");
            }
            _currentIndex++;
            arr[_currentIndex] = digit;
            _count++;
        }

        public int Pop()
        {
            int tmp = 0;
            if (IsEmpty)
            {
                throw new Exception("No elements in array");
            }
            tmp = arr[_currentIndex];
            arr[_currentIndex] = default(int);
            _count--;
            _currentIndex--;
            return tmp;
        }

        public void Inc(int count, int multiplier)
        {
            if (count > _count)
            {
                throw new Exception("Not enought element in array");
            }
            for (int i = 0; i < count; i++)
            {
                arr[i] += multiplier;
            }
            Console.WriteLine("Ready");
        }

        private bool IsEmpty {
          get{ return _count == 0; }
        }        
        private bool IsFull {
          get { return _currentIndex == arr.Length; }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Type exit and press enter to quit, type push <your digit> to push digit in stack, pop - to see last stack element, inc <count, multiplier> to multiply first <count> elements on <multiplier>");
            Stack stack = new Stack();
            while (true)
            {
                string[] input;
                string command = "";
                input = Console.ReadLine().Split(new char[] { ' ' });
                command = input[0];
                try
                {
                    switch (command)
                    {
                        case "push": { stack.Push(Convert.ToInt32(input[1])); break; }
                        case "pop": { Console.WriteLine(stack.Pop().ToString()); break; }
                        case "inc": { stack.Inc(Convert.ToInt32(input[1]), Convert.ToInt32(input[2])); break; }
                    }
                }
                catch (Exception ex)
                {
                    Console.WriteLine(ex.Message);
                }
                if (command == "exit") break;
            }
        }
    }
}

Answer 1

It's impossible! In the test, the inc method is executed 108 ^times . On average, reading 2 * 10 ⁸ bytes of data in 1 pass. Even if this array is read by a GT 970 video card, it will be able to digest a little more than 1000 inc calls per second on average. You can fit into the second condition if you only rewrite the test and the class and reduce all 555 + 555 + 555 + 555 + ... into one 555 * n.

Answer 2

Isn't the implementation of the stack based on a singly linked list the canonical and most correct one?

Answer 3

I will ask a few questions and it would be very good if you answer them yourself:
- What is the purpose of filling an array when creating a Stack? Do I need to initialize and deinitialize array elements at all?
- Why 100000001 and not 100000000 (look closely at the i<count condition)? And why is a number explicitly used and not a preprocessor directive?
- Are you sure that in StackTest it is necessary to measure each method separately?
- Maybe one call to the Inc method will be enough to measure?
BR, t4g

Answer 4

Who cares - it's possible, the discussion is here ru.stackoverflow.com/questions/605258/%D0%9A%D0%B0...