5
\$\begingroup\$

I've created a MiniStack to assist in removing recursion from routines using a manual stack.

Obviously if the stack is an object it lives on the heap and its creation and destruction takes a significant amount of time. Therefore any heap based option is out for loops that create and destroy the TStack.

Is there anything that can be altered to:

  1. make it faster?
  2. improve the checking during debug time?

unit Ministacks;

interface

const
  DefaultSize = 31;

type
  /// <summary>
  /// The ministack stores 31 elements on the system's stack.
  /// It is coded for raw speed.
  /// The stack is safe for holding managed types
  /// It does not do range checking, other than through Assertions at debug time
  /// </summary>
  TMiniStack<T> = record
{$IFDEF DEBUG}
  strict private
    function capacity: Integer;
{$ENDIF}
  private
    SP: Integer;
{$IFDEF CPUX64}
    Filler: integer; // Keep array aligned
{$ENDIF}
{$IFDEF DEBUG}
    HeapFlag: TGUID;
    HeapSize: Integer;
{$ENDIF}
    Items: array[0..DefaultSize - 1] of T;
    function GetItem(index: Integer): T; inline;
  public
    procedure Free;
    /// <summary>
    /// Initializes the stack.
    /// Must be called before the stack can be used.
    /// </summary>
    procedure Init; inline;
    function Pop: T; inline;
    procedure Push(const Item: T); inline;
    /// <summary>
    /// Returns the top item on the stack, does not alter the stack pointer.
    /// </summary>
    /// <returns></returns>
    function Peek: T; inline;
    function IsEmpty: Boolean; inline;
    /// <summary>
    /// Allows the stack to be accessed as a read-only array.
    /// </summary>
    property Item[index: Integer]: T read GetItem;
    property Count: integer read SP;
  end;

  MiniStack<T> = class
  public type
    PStack = ^Stack;
    Stack = TMiniStack<T>;
  public
    /// <summary>
    /// Creates new ministack on the heap.
    /// </summary>
    /// <param name="Size">The maximum number of elements the stack can hold</param>
    /// <returns>Pointer to the newly created stack.</returns>
    /// <remarks>
    /// Do not create and destroy a Ministack in a loop, use the stack based Ministack instead.
    /// You can increase the constant DefaultSize (must be a true constant) if you need a bigger
    /// stack.
    /// </remarks>
    class function Create(Size: integer = DefaultSize): PStack;
  end;

{$IFDEF DEBUG}
const
  MagicHeapFlag: TGUID = '{EF227045-27A9-4EF3-99E3-9D279D58F9A0}';
  FreedAlreadyFlag: TGUID = '{A76BBA2F-09C5-44B7-81BF-3C8869FB8D80}';
{$ENDIF}

implementation

uses
  System.SysUtils;

{ TMiniStack<T> }

procedure TMiniStack<T>.Init;
var
  i: Integer;
begin
  SP:= 0;
end;

class function MiniStack<T>.Create(Size: integer = DefaultSize): PStack;
begin
  Result:= AllocMem(SizeOf(TMiniStack<T>) - (DefaultSize * SizeOf(T)) + (Size * SizeOf(T)));
{$IFDEF DEBUG}
  Result.HeapFlag:= MagicHeapFlag;
  Result.HeapSize:= Size;
{$ENDIF}
end;

{$IFDEF DEBUG}
function TMiniStack<T>.capacity: Integer;
begin
  if HeapFlag = MagicHeapFlag then begin
    Result:= HeapSize;
  end
  else Result:= DefaultSize;
end;
{$ENDIF}

procedure TMiniStack<T>.Free;
begin
{$IFDEF DEBUG}
  Assert((HeapFlag = MagicHeapFlag) or (HeapFlag = FreedAlreadyFlag),
    'Do not call free on stack based MiniStacks');
  Assert((HeapFlag <> FreedAlreadyFlag), 'This stack has already been freed');
{$ENDIF}
  Finalize(Items, count);
  FreeMem(@Self);
end;

function TMiniStack<T>.GetItem(index: Integer): T;
begin
  Assert((index >= 0) and (index < Count),
    Format('Trying to get item #%d, but there are only %d items on the stack',[index, count]));
  Result:= Items[index];
end;

function TMiniStack<T>.IsEmpty: Boolean;
begin
  Result:= (SP = 0);
end;

function TMiniStack<T>.Pop: T;
begin
  Assert(SP > 0, 'Stack underflow');
  Dec(SP);
  Result:= Items[SP];
end;

function TMiniStack<T>.Peek: T;
begin
  Assert(SP > 0, 'You cannot peek at an empty stack');
  Result:= Items[SP-1];
end;

procedure TMiniStack<T>.Push(const Item: T);
begin
  Items[SP]:= Item;
  Inc(SP);
{$IFDEF DEBUG}
  Assert(SP <= Capacity, 'Stack overflow');
{$ENDIF}
end;

end.

Please do not suggest anything that will make it slower. There is absolutely no checking during runtime; this is by design.

\$\endgroup\$
  • 1
    \$\begingroup\$ I do not know delphi enough, but it looks like you have the main point of a fast stack: it pre-allocates a set size, so that means it won't grow and shrink all the time (at least not each time you push and pop--I see below that your size is static though...) That's the first optimization. The second one is to place the stack outside of your loop. When your inner process ends, the stack should be empty (you can have a debug to verify the feat) so it is ready to be used on the next iteration of your loop. That is the second optimization you can generally do with such stacks. \$\endgroup\$ – Alexis Wilke Aug 30 '14 at 19:59
6
\$\begingroup\$
  1. Stack with fixed size has very troublesome usability. That is why modern Operating Systems don't limit stack size by default, only to provide some reasonable 'max' that is used to detect real stack overflow caused by an infinite recursion. And they also don't allocate whole possible stack at once.

    For example, on Windows a thread created withing a process will get its stack allocated with 1 or a few pages and one guard page at the end.

    The guard page is flagged as invalid from the perspective of hardware processor.

    When any instruction processed by the processor touches the guard page, the processor generates exception state which is then handled by the Operating System which in turn finds out it is an stack overflow state and allocates another page (or a few more) and adds them to the thread's stack space (modifies definition of the virtual memory layout of the SS segment selector).

    So the effect is that the stack can grow automatically as needed. The grows happens only when the guard page was hit. This guard page hit test is done at 0 cost in the hardware.

    Similar approach would be useful also in this class. Either reallocate the Items array to make it bigger (see source code of TList which does the same) or allocate several pointers to several Items (buckets) where only 1 of them is the current one containing the TOS pointer.

    Without auto growing stack and without any runtime checking you'll soon face mysterious access violations at best and random application behavior at worst. Both being hard to guess and find bugs.

    (Also profiling your code would probably show that even if you leave the run-time safety checks in there the cost payed would be very small compared to the other things the functions do)

  2. Debug time checking would get little bit faster if instead of HeapFlag being 16bit long array of bytes with states identified by special magic constants, there would be an enum flagged to be sized as native processor data type (32bit cardinal on 32bit system, 64bit cardinal on 64bit system) as manipulating such types costs almost always only 1-clock

  3. Also analyzing the assembly language code generated by the compiler from your class is a good guide for identifying if your code is optimal. In the generated assembly code the most frequently used operations (Push, Pop) should be also very short and efficient.


Some related things you may want to read

\$\endgroup\$
  • \$\begingroup\$ Please add related links. \$\endgroup\$ – bhathiya-perera Aug 31 '14 at 6:45
  • 1
    \$\begingroup\$ @JaDogg done, [1][2][4] are different implementations in C#, Object Pascal, C++. The other links provide some tips on how is stack used from the perspective of the assembly language and Windows-like Operating System and how to verify implementation's efficiency by reading the generated assembly language code \$\endgroup\$ – xmojmr Sep 1 '14 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.